Поиск в строках, массивах, последовательностях:
Нечеткий поиск.

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

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

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

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

Пример:

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

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

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

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

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

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

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

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

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

Tries for approximate string mathing^{English pdf}. Что интересно, его сложность не зависит от размера текста, и при использовании по назначению он бьет даже AGREP.

Архив статей.

• A randomized algorithm for approximate string mathing


Цель алгоритма - вектор размера N, который образуется, если сдвигать образец вдоль текста и сохранять количество совпадений на i-й позиции образца в i-й координате вектора. Сложность nlogm.


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


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

Вверх по странице, к оглавлению и навигации