|
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, он посвящен исключительно нечеткому поиску и, на мой взгляд, весьма интересен.
|
