Программирование -> Delphi / Pascal -> Алгоритмы нечеткого сравнения строк.

Алгоритмы нечеткого сравнения строк. Практическое применение

Совсем недавно мне пришлось заниматься конвертацией БД (из парадокса в интербейз) и в контексте этой работы очень плотно пользоваться нечетким сравнением строк. Я написал алгоритм который мне очень помог. Уже после в сокровищнице нашел очерк Кузана Дмитрия (дата публикации 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 вставлял его функцию. Здесь описан его алгоритм .

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