Алгоритмы нечеткого сравнения строк. Практическое применение
Совсем недавно мне пришлось заниматься конвертацией БД (из парадокса в интербейз) и в контексте этой работы очень плотно пользоваться нечетким сравнением строк. Я написал алгоритм который мне очень помог. Уже после в сокровищнице нашел очерк Кузана Дмитрия (дата публикации 02-12-2002 14:06). Как выяснилось алгоритмы очень похожие, но реализация отличалась и в связи с этим я выявил несколько недостатков собрата моего алгоритма. Привожу краткий анализ, который производился на реальной базе.
Допустим необходимо какой либо строке (из одной базы ) подобрать наиболее подходящую строку из другой. Алгоритм примерно такой:
function GetMaxMatch(Source: String; var Name_: String): integer;
var SyncCount, NCount, NCount_: integer;
TempStr: String;
begin
TempStr:= Source;
table1.First;
SyncCount:= 0;
NCount_:= Length(TempStr);
while not(table1.Eof) do
begin
if (CompareStrings(TempStr, table1.FieldByName('NAME').AsString,
MatchCount, NCount) > SyncCount)or
((CompareStrings(TempStr, table1.FieldByName('NAME').AsString,
MatchCount, NCount) = SyncCount)and(NCount < NCount_)) then
begin
SyncCount:= CompareStrings(TempStr,
table1.FieldByName('NAME').AsString, MatchCount, NCount);
NCount_:= NCount;
Result:= table1.FieldByName('Primary Key').AsInteger;
Name_:= table1.FieldByName('NAME').AsString;
end;
table1.Next;
end;
end;
Вернет идентификатор записи(РК) и саму запись(Name_). CompareStrings - как раз нечеткое сравнение (алгоритм ниже). Здесь NCount - кол-во не совпавших символов(в случае если две строки имеют одинаковое число символов совпадения, отсев идет по символам несовпадения).
Для теста алгогритма Кузана Д. я применял эту же функцию, а вместо CompareStrings вставлял его функцию. Здесь описан его алгоритм .
A это мой:
function CompareStrings(S1, S2: string; MatchCount: integer;
out NCount: integer):integer;
var i, j, Count_, Count: integer;
S1_, S2_: String;
function Flag:Boolean;
begin
Result:= false;
if (i + Count_ <= Length(S1_))and(j + Count_ <= Length(S2_)) then
if (UpCharRus(S1_[i+Count_]) = UpCharRus(S2_[j+Count_]))
{and(S1[j+Count_] <> ' ')} then
Result:= true;
end;
begin
Count:= 0;
NCount:= 0;
S1_:=S1;
ReplaceAllStr(S1_, ' ', '');
S2_:=S2;
ReplaceAllStr(S2_, ' ', '');
if (S1_ = '')or(S2_ = '') then
begin
Result:= 0;
NCount:= 255;
Exit;
end;
i:= 1;
repeat
j:= 1;
repeat
if (UpCharRus(S1_[i]) = UpCharRus(S2_[j])){and(S1[i] <> ' ')} then
begin
Count_:= 1;
while flag do
Inc(Count_);
i:= i + Count_ - 1;
j:= j + Count_ - 1;
if Count_ >= MatchCount then
Count:= Count + Count_;
end;
inc(j)
until j >= Length(S2_);
inc(i)
until i >= Length(S1_);
if Length(S1_) < Length(S2_) then
Count_:= Length(S1_)
else
Count_:= Length(S2_);
Result:= Count;
NCount:= Count_ - Count;
end;
|
|
Ниже анализ с учетом времени работы(без выводов - они очевидны)
Пример 1.
Пример 2.
Выводы: в некоторых случаях при выборе маленького количества символов совпадения мой алгоритм отрабатывает неправильно (как в примере 2, хотя в примере 3 он тут же исправился), но выигрыш во времени очевиден.
Автор: Left Left
Источник: www.delphikingdom.com
|
