Простой пример реализации фонетического поиска

Постановка проблемы

Имеется база данных, содержащая список российских и украинских имён-фамилий в английской транскрипции, как она записана в туристических паспортах. Поскольку некоторое время назад правила транскрибирования для оных паспортов в России поменялись (толи с английских на французские, толи наоборот), имеется вполне реальная и даже официальная возможность того, что какое либо ФИО может быть записано иначе. Кроме того, данные порой могут браться из морского паспорта, что делает ситуацию ещё запутанней.
А теперь представьте, что вам нужно быстро найти в этой базе человека по фамилии, ну например, Щеглов… (смайл)

Варианты решения

Существующие алгоритмы не понравились либо ориентацией на чистый английский, либо полной невозможностью «горячего поиска» (фамилию нужно вводить целиком, и только потом сравнивать). И тут я вспомнил об одном достаточно простом алгоритме, который написал лет много тому назад для одного греческого проекта, где подобная проблема стояла даже в более жостком варианте: фамилии (греческие) операторам там приходилось ловить на слух, по телефону. Описание алгоритма мне дал мой тогдашний компаньон, назвав его «воэл». Греческий и русский, конечно, похожи мало, но каши с транскрибированием вполне схожи, и я решил рискнуть переделать упомянутый «воэл» под российские нужды.

Некоторые необходимые пояснения

Много лет назад — когда солнце было ярче, трава зеленее, девушки загадочней, а про слово RAD писали толстенные книжки, автор этих строк с парой единомышленников зарабатывал в меру своих сил на хлеб с маслом написанием бэкэндов для малых и средних греческих компашек.
С тех пор многое изменилось, в частности род деятельности автора уже много лет не связан с ай-ти вообще и с програмированием в частности. Скучный хьюман ресоурс мэнэджмент, серые будни офисной крысы.
Говорят, однако, что програмисты бывшими не бывают, и когда в связи с переездом офиса ребром встал вопрос о переходе на безбумажное делопроизводство, я рискнул взятся за написание системы, благо нужды достаточно скромные.
Некоторыми интересными на мой взгляд, и/или спорными частями проекта я рискнул поделится в скромной надежде на дельную критику и ценные замечания.
Итак, «Щеглов».

Предлагаемое решение

В общем-то упомянутый «воэл» делал очень простую вещь: переводил всё слово в один регистр, например в нижний, и заменял одни буквы или комбинации букв их «фонетическими соответствиями», т.е., попросту, другими буквами (много реже — комбинациями).
Попробовал построить подобную таблицу «фонетических соответствий» для русского языка, и получилось что-то вроде следующего (замечания приветствуются):

Во первых – всевозможные сдвоенные согласные. Убираем, одной вполне достаточно:

bb=b	kk=k	rr=r
cc=c	ll=l	ss=s
dd=d	mm=m	tt=t
ff=v	nn=n	zz=z
hh=h	pp=p

Далее — разнообразные шипяще-свистящие:

sh=s	zch=s	ck=k
ch=c	sch=s	ks=x
shch=s	csh=s	ts=c
zhch=s	zh=z	tc=c

Потом остальные фирменные фишки русского языка, такие как «ю», «я», «ё», «й», «ф» и тп:

yu=u	je=e	oy=oi
ju=u	ei=ei	oj=oi
u=u	ey=ei	ph=f
ya=a	ej=ei	yy=i
ja=a	yo=e	ii=i
ia=a	io=e	iy=i
ye=e	jo=e	y=i
ie=e	oi=oi	yy=i

Ну и прочее, оставшееся:

kh=h

gh=g

'=

Т.е., будь вышеупомянутый Щеглов записан как «Shcheglov», «Scheglov» или даже «Zchegloff» — с помощью данной таблицы он будет переведён в однозначное «seglov».
Осталось написать код.

Класс TVoel

В примере ниже использована Дельфи.
Таблица соответствий читается из файла в лист типа TStringList, и сортируется для возможности бинарного поиска в нём. Функция Locate выполняет этот поиск. Имплементации соответствующих функций опущены за банальностью.

type

  TVoel = class
  private
    FFileName: String;
    FList: TStrings;
    procedure setFileName(const Value: String);
    procedure readFile;
    function isReady: Boolean;
    function Locate(const Value: String; var Index: Integer): Boolean;
  public
    constructor Create;
    destructor Destroy; override;
    function Convert(const Value: String): String;
    property FileName: String read FFileName write SetFileName;
end;

implementation

function TVoel.Convert(const Value: String): String;
var
  ii, p, len: Integer;
  str: String;
  Ch: String;
  found: Boolean;
begin
  Result := '';
  len := Length(Value);
  ii := 0;
  while ii < len do begin
    Inc(ii);
    Ch := Value[ii];
    found := Locate(Ch, p);
    if found then begin
      str := Value[ii];
      while found and (ii < len) do begin
        Inc(ii);
        str := str + Value[ii];
        found := Locate(str, p);
      end;

      if not found then begin
        setlength(str, length(str)-1);
        Dec(ii);
      end;

      if CompareText(str, FList.Names[p]) = 0 then
        Ch := FList.ValueFromIndex[p];
    end;
    Result := Result + Ch;
  end;
  Result := ANSIUpperCase(Result);
end;

В данный момент вышеприведённый класс используется для «отладки» «фонетической таблицы» на скромном списке в десяток тысяч человек. Разумеется, окончательная реализация будет (должна быть) написана в виде встроенной в БД процедуры.