:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте ::
Путь: Поиск. Строки и последовательности » Нечеткий поиск
  Нечеткий поиск




  Обозначения.



Cтрока x длины |x| = m записывается как x1x2 ... xm, где xi представляет i-й символ x.

Подстрока xixi+1 ... xj строки x, где i<=j<=m, будет обозначаться x(i,j). В случае, когда i>j, обращенная подстрока обозначается так xR(i,j).

Обычно x будет обозначать искомый образец, а y – текстовую строку; |x| = m, |y| = n и, конечно, m<=n.

Пример:

x = trismegistus
|x| = 12
x(7,10) = gist
xR(7,4) = gems

Обобщенная задача сопоставления строк, включающая в себя нахождение подстрок строки текста, близких к заданному образцу строки, называется также задачей нечеткого сопоставления строк. Задачу нечеткого сопоставления строк можно сформулировать следующим образом:

Пусть даны образец x, |x| = m, и текст y, |y| = n, m, n > 0 и m < n. Пусть даны также целое k > 0 и функция расстояния d. Требуется найти все подстроки s текста y такие, что d(x, s) < k.

Здесь и далее, d - метрика.

Расстояние Хемминга [Hamming, 1982] между двумя строками одинаковой длины определяется как число позиций, в которых символы не совпадают. Это эквивалентно минимальной цене преобразования первой строки во вторую в случае, когда разрешена только операция замены с единичным весом. Если допускается сравнение строк разной длины, то, как правило, требуются также вставка и удаление. Если придать им тот же вес, что и замене, минимальная общая цена преобразования будет равна одной из метрик, предложенных Левенштейном [Levenstein, 1965]. Другая метрика равна минимальной цене преобразования в случае, когда разрешены только вставка и удаление. Это эквивалентно назначению цены 1 удалению и вставке, и 2 замене, так как последнюю можно заменить парой вставка-удаление. Первую из этих метрик мы ниже называем расстоянием Левенштейна, а вторую – расстоянием редактирования.

Задача, таким образом, состоит в том, чтобы при заданной функции расстояния найти все подстроки текста, отстоящие от образца не более, чем на k. Если d является расстоянием Хемминга, задача называется сопоставлением строк с k несовпадениями, если же d – расстояние Левенштейна, задача называется сопоставлением строк с k различиями (или, иногда, ошибками).

Наивный подход к задаче сопоставления строк, требующий времени O(mn), легко адаптировать к задаче k несовпадений, разрешив k несовпадений при сравнениях символов подстроки в тексте.

Однако, как и для задачи сопоставления строк, для задач k несовпадений и k различий были изобретены более эффективные подходы.

k несовпадений – Ландау-Вишкин
k-различий – Ландау-Вишкин

Их алгоритм гораздо лучше, если k пропорционально O(m/log n). Для неограниченных алфавитов он алгоритм быстрее, если k пропорционально O(log1/2m). Он, безусловно, превосходен, когда границей k является O(log1/2m). Заметим, однако, что при больших k, то есть когда k равняется O(m), его эффективность не лучше, чем у адаптации прямого, с квадратичным временем, подхода динамического программирования.

Для практических целей особо рекомендую
AGREPzip

Если цель нечеткого поиска - исключить ошибки наборщика, то метод, оптимизированный для поиска очень похожих на образец вхождений описан в статье
Tries for approximate string matchingzip

Также советую посетить сайт ITMAN, он посвящен исключительно нечеткому поиску и, на мой взгляд, весьма интересен.


  Дополнительные материалы:




A randomized algorithm for approximate string mathing z i p
Цель алгоритма - вектор размера N, который образуется, если сдвигать образец вдоль текста и сохранять количество совпадений на i-й позиции образца в i-й координате вектора. Сложность nlogm.

A New Data Structure for Fast Approximate Matching z i p
Триангуляционные деревья - новые структуры данных, позволяющие производить нечеткий поиск /и не только/ с малым числом сравнений. Разобрано применение для дистанции Хэмминга и для проверки графов на изоморфизм.

VP-tree z i p
Структура данных, позволяющая проводить быстрый поиск ближайшего соседа в любых пространствах, причем не обязательно Евклидовой метрики. Построение - O(nlogn), поиск O(logn).