Постановка проблемы
Имеется база данных, содержащая список российских и украинских имён-фамилий в английской транскрипции, как она записана в туристических паспортах. Поскольку некоторое время назад правила транскрибирования для оных паспортов в России поменялись (толи с английских на французские, толи наоборот), имеется вполне реальная и даже официальная возможность того, что какое либо ФИО может быть записано иначе. Кроме того, данные порой могут браться из морского паспорта, что делает ситуацию ещё запутанней.
А теперь представьте, что вам нужно быстро найти в этой базе человека по фамилии, ну например, Щеглов… (смайл)
Варианты решения
Существующие алгоритмы не понравились либо ориентацией на чистый английский, либо полной невозможностью «горячего поиска» (фамилию нужно вводить целиком, и только потом сравнивать). И тут я вспомнил об одном достаточно простом алгоритме, который написал лет много тому назад для одного греческого проекта, где подобная проблема стояла даже в более жостком варианте: фамилии (греческие) операторам там приходилось ловить на слух, по телефону. Описание алгоритма мне дал мой тогдашний компаньон, назвав его «воэл». Греческий и русский, конечно, похожи мало, но каши с транскрибированием вполне схожи, и я решил рискнуть переделать упомянутый «воэл» под российские нужды.
Некоторые необходимые пояснения
Много лет назад — когда солнце было ярче, трава зеленее, девушки загадочней, а про слово 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;
В данный момент вышеприведённый класс используется для «отладки» «фонетической таблицы» на скромном списке в десяток тысяч человек. Разумеется, окончательная реализация будет (должна быть) написана в виде встроенной в БД процедуры.