Большой архив статей, книг, документации по программированию, вебдизайну, компьютерной графике, сетям, операционным системам и многому другому
 
<Добавить в Избранное>    <Сделать стартовой>    <Реклама на сайте>    <Контакты>
  Главная Документация Программы Обои   Экспорт RSS E-Books
 
 

   Программирование -> 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 вставлял его функцию. Здесь описан его алгоритм .

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

Ссылки по теме
Алгоритмы Сортировки. Часть 1
Введение в Delphi 8
Работа с реестром в Delphi
Delphi и ресурсы компьютера
Советы начинающим программировать на Delphi
Структуры и базы данных, методы сортировки
 

Компьютерная документация от А до Я - Главная

 

 
Интересное в сети
 
10 новых программ
CodeLobster PHP Edition 3.7.2
WinToFlash 0.7.0008
Free Video to Flash Converter 4.7.24
Total Commander v7.55
aTunes 2.0.1
Process Explorer v12.04
Backup42 v3.0
Predator 2.0.1
FastStone Image Viewer 4.1
Process Lasso 3.70.4
FastStone Image Viewer 4.0
Xion Audio Player 1.0.125
Notepad GNU v.2.2.8.7.7
K-Lite Codec Pack 5.3.0 Full


Наши сервисы
Рассылка новостей. Подпишитесь на рассылку сейчас и вы всегда будете в курсе последних событий в мире информационных технологий.
Новостные информеры. Поставьте наши информеры к себе и у вас на сайте появится дополнительный постоянно обновляемый раздел.
Добавление статей. Если вы являетесь автором статьи или обзора на тему ИТ присылайте материал нам, мы с удовольствием опубликуем его у себя на сайте.
Реклама на сайте. Размещая рекламу у нас, вы получите новых посетителей, которые могут стать вашими клиентами.
 
Это интересно
 

Copyright © CompDoc.Ru
При цитировании и перепечатке ссылка на www.compdoc.ru обязательна. Карта сайта.
 
Rambler's Top100