Нечёткий поиск

Описание

Levenshtein distance - метрика для строк, определяющая степень их близости. Применяется для приближенного поиска вхождения подстроки.

Что на этой страничке подразумевается под поиском на неточное равенство?

Под поиском на неточное равенство, или под поиском по сходству (английский термин – fuzzy search) на этом сайте подразумевается, прежде всего, поиск в массиве текстовой информации по ключевым словам или по-другому терминам. Термины могут не совпадать со словами текстовых документов, а быть только «похожими». Кроме того, в разделе «Статьи» можно найти информацию по поиску в общих метрических пространствах.

А зачем он нужен?
Как мне кажется, поиск по сходству нужен по двум причинам. Во-первых, человек может не всегда знать точное написание слова, например, если слово является научным термином. Так, количество медицинских и/или биологических терминов превышает десять миллионов. Во-вторых, электронные документы содержат ошибки, что иногда не позволяет найти нужную информацию.
Особенно это актуально, если нужно найти редкий термин (то есть выборка документов очень маленькая), при том, что термин указан в документе с ошибкой. Пробовали ли вы когда-нибудь искать с помощью Яндекса по ключевому слову «хэширование»? Если да, то вы наверняка уже заметили, что если искать по ключевому слову «хеширование», то результаты поиска отличаются.
Что же понимается под «похожестью» ключевых слов запросов и слов документа?
Существует бесконечно много способов определения меры «похожести». Наиболее известной является функция (метрика) Левенштайна, которую также называют расстоянием редактирования. Получили распространение также функции, которые рассчитывают меру близости по количеству общих подстрок определенной длины.
Так что же все-таки представляет из себя эта функция Левенштейна?
Если считать все типы ошибок, такие, как удаление, добавление и замены символа равноправными, то расстояние редактирование равно минимальному количеству операций редактирования, которые преобразуют одно слово в другое.

Реализация функции в принципе соответствует описанию с одной оговоркой: матрица из описания заменена статическим буффером, длина которого равна удвоенной максимальной длине строк.
Это сделано для:

экономии памяти и во избежание её перераспределений
повышения быстродействия (у меня функция работает в обработчике onfilterRecord)

таким образом, в реализации половинами буффера представлены только две последние строки матрицы, которые меняются местами каждую итерацию внешнего цикла (по i)… для определения того, какая из половин буффера является «нижней строкой», служит переменная flip т. е. при flip = false первая половина буффера является предпоследней строкой, а вторая - последней; при flip = true наоборот, первая половина - последняя строка, вторая половина - предпоследняя.

Пример

const cuthalf = 100;
   { константа, ограничивающая макс. длину обрабатываемых строк }
 
var buf: array [0..((cuthalf * 2) - 1)] of integer;
   { рабочий буффер, заменяет матрицу, представленную в описании }
 
function min3(a, b, c: integer): integer; { вспомогательная функция }
begin
  Result := a;
  if b < Result then Result := b;
  if c < Result then Result := c;
end;
 
 
function LeveDist(s, t: string): integer;
var i, j, m, n: integer;
    cost: integer;
    flip: boolean;
begin
  s := copy(s, 1, cuthalf - 1);
  t := copy(t, 1, cuthalf - 1);
  m := length(s);
  n := length(t);
  if m = 0 then Result := n
  else if n = 0 then Result := m
  else begin
    flip := false;
    for i := 0 to n do buf[i] := i;
    for i := 1 to m do begin
      if flip then buf[0] := i
      else buf[cuthalf] := i;
      for j := 1 to n do begin
        if s[i] = t[j] then cost := 0
        else cost := 1;
        if flip then
          buf[j] := min3((buf[cuthalf + j] + 1),
                         (buf[j - 1] + 1),
                         (buf[cuthalf + j - 1] + cost))
        else
          buf[cuthalf + j] := min3((buf[j] + 1),
                                   (buf[cuthalf + j - 1] + 1),
                                   (buf[j - 1] + cost));
      end;
      flip := not flip;
    end;
    if flip then Result := buf[cuthalf + n]
    else Result := buf[n];
  end;
end;
 
begin
     writeln (LeveDist ('Pascal', 'Paskal'));
     readln;
end.

Содержание

Нечёткий поиск

Описание

Пример

Ссылки