Rambler's Top100
"Knowledge itself is power"
F.Bacon
Поиск | Карта сайта | Помощь | О проекте | ТТХ  
 Сокровищница
  
 

Фильтр по датам

 
 К н и г и
 
Книжная полка
 
 
Библиотека
 
  
  
 


Поиск
 
Поиск по КС
Поиск в статьях
Яndex© + Google©
Поиск книг

 
  
Тематический каталог
Все манускрипты

 
  
Карта VCL
ОШИБКИ
Сообщения системы

 
Форумы
 
Круглый стол
Новые вопросы

 
  
Базарная площадь
Городская площадь

 
   
С Л С

 
Летопись
 
Королевские Хроники
Рыцарский Зал
Глас народа!

 
  
ТТХ
Конкурсы
Королевская клюква

 
Разделы
 
Hello, World!
Лицей

Квинтана

 
  
Сокровищница
Подземелье Магов
Подводные камни
Свитки

 
  
Школа ОБЕРОНА

 
  
Арсенальная башня
Фолианты
Полигон

 
  
Книга Песка
Дальние земли

 
  
АРХИВЫ

 
 

Сейчас на сайте присутствуют:
 
 
 11:01 NGPOL
 
 
Во Флориде и в Королевстве сейчас  11:07[Войти] | [Зарегистрироваться]

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

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




Смотрите также материалы по темам:
[INTERBASE] [Поиск и сортировка] [Обработка текста] [Нечеткое сравнение]

 Обсуждение материала [ 18-05-2009 01:51 ] 5 сообщений
  
Время на сайте: GMT минус 5 часов

Если вы заметили орфографическую ошибку на этой странице, просто выделите ошибку мышью и нажмите Ctrl+Enter.
Функция может не работать в некоторых версиях броузеров.

Web hosting for this web site provided by DotNetPark (ASP.NET, SharePoint, MS SQL hosting)  
Software for IIS, Hyper-V, MS SQL. Tools for Windows server administrators. Server migration utilities  

 
© При использовании любых материалов «Королевства Delphi» необходимо указывать источник информации. Перепечатка авторских статей возможна только при согласии всех авторов и администрации сайта.
Все используемые на сайте торговые марки являются собственностью их производителей.

Яндекс цитирования