Поиск по сайту.



Математика. Пути и Графы. Комбинаторика и перебор

Сортировка

Защита и сокрытие информации. Атаки и взлом

Сжатие информации и кодирование. СRC

Графика и обработка изображений. Фракталы

Поиск в строках, массивах,
последовательностях


Разбор выражений.
Компиляторы и интерпретаторы


Cтруктуры данных.
Хранение информации


AI, ГА, Нейронные сети

Вейвлеты

Игры, и все с ними связанное

Разное


Софт: просмотр PS и PDF файлов

   Написать веб-мастеру
   Почитать историю сайта

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

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

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| = m и, конечно, 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), его эффективность не лучше, чем у адаптации прямого, с квадратичным временем, подхода динамического программирования.

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

  • AGREPEnglish pdf - известную утилиту сравнения строк, которая превосходит почти все известные алгоритмы. В статье есть описание алгоритма, а также отдельно даны исходники на Си.

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

  • Tries for approximate string mathingEnglish 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).