Версия для печати


Алгоритмы нечеткого сравнения строк. Практическое применение.
http://www.delphikingdom.com/asp/viewitem.asp?catalogID=1147

Left 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 он тут же исправился), но выигрыш во времени очевиден.