Версия для печати
Алгоритмы нечеткого сравнения строк. Практическое применение.
http://www.delphikingdom.com/asp/viewitem.asp?catalogID=1147Left Left
дата публикации 01-08-2005 09:07Алгоритмы нечеткого сравнения строк. Практическое применение. Совсем недавно мне пришлось заниматься конвертацией БД(из парадокса в интербейз) и в контексте этой работы очень плотно пользоваться нечетким сравнением строк. Я написал алгоритм который мне очень помог. Уже после в сокровищнице нашел очерк Кузана Дмитрия (дата публикации 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. Пример 3. Выводы: в некоторых случаях при выборе маленького количества символов совпадения мой алгоритм отрабатывает неправильно(как в примере 2, хотя в примере 3 он тут же исправился), но выигрыш во времени очевиден.