Метод Левенштейна

Введение

Базовыми системами контроля орфографических ошибок и полноформатных систем поиска информации, аналогичных Google или Yandex, считаются алгоритмы нечёткого поиска (другое название поиск по сходству). К примеру, подобные алгоритмы применяются для сообщений типа «Вероятно вы имели в виду…» в вышеназванных системах поиска. Система нечёткого поиска выступает как очень полезная опция всех поисковых систем. Но при этом, её полноформатное исполнение будет существенно более сложным, чем выполнить простой поиск по алгоритму точного совпадения.

Проблема нечёткого поиска формулируется следующим образом: имеется заданное слово и требуется выполнить поиск в тексте или словаре, имеющем размер n, все слова, которые совпадают с заданным словом (или начинаются с заданного слова), учитывая k всевозможных отличий. К примеру, выполняется запрос по слову «Машина» и допускается две возможные ошибки. Требуется найти слова типа «Машинка», «Махина», и тому подобные. Характеристикой алгоритмов нечёткого поиска является метрика. Это функция дистанции между двумя словами, которая позволяет оценивать уровень их похожести в этом смысле. В строгой математической формулировке метрика состоит из необходимости соответствия условию неравенства треугольника, где Х — словесное подмножество, Р — обозначение метрики):

Рисунок 1. Неравенство. Автор24 — интернет-биржа студенческих работ

Но, как правило, более часто метрика является более обобщённым термином, которое не требует исполнения условия, приведённого выше. Метрику возможно определить как расстояние. Среди самых известных метрик можно выделить расстояние Хемминга, Левенштейна и Дамерау-Левенштейна. Но у Хемминга расстояние считается метрикой лишь на словесном подмножестве, где все слова имеют одинаковую длину, и это обстоятельство существенно сужает сферу его использования. Поэтому расстояние Хемминга для практического использования фактически бесполезно, не выдерживая соперничества с более лучшими метриками, по мнению большинства людей.

Расстояние Левенштейна

Расстояние Левенштейна, или по-другому, расстояние редактирования, используется чаще всего и практически везде можно встретить алгоритмы его расчётов. Одним из таких алгоритмов является способ Вагнера – Фишера, который описывается с помощью матрицы, где m и n это размеры строк, подлежащих сравнению. Начальная версия алгоритма обладает временной сложностью О(mn) и требует O(mn) памяти. Матрица выглядит таким образом:

Рисунок 2. Матрица. Автор24 — интернет-биржа студенческих работ

Проанализировав работу алгоритма, можно увидеть, что при каждом последующем действии применяются лишь две последние строчки матрицы. Это означает, что размеры требуемой памяти возможно уменьшить к O(min(m, n)).

Рисунок 3. Оптимизация алгоритма. Автор24 — интернет-биржа студенческих работ

Если пойти дальше, то есть ещё возможности для оптимизации алгоритма, когда поставлена задача найти не больше К отличий. В таком варианте необходимо находить в матрице только полосу по диагонали, имеющую ширину 2к+1 (рассечение Укконена). При этом временная сложность будет O(k min(m, n)).

Префиксное расстояние

Иногда есть необходимость определить дистанцию от префикса, который является образцом, до строки. То есть определить длину от заданного префикса до самого близкого префикса строки. В таком случае нужно выбрать самое маленькое расстояние, из всех известных, от образцового префикса до всех строчных префиксов. Понятно, что мы не можем считать префиксное расстояние метрикой, в принятом толковании этого термина, что сужает область его использования. Очень часто при выполнении нечёткого поиска имеет значение не сама величина дистанции, а только лишь её превышение некоторой величины.

Расстояние Дамерау-Левенштейна

Этот вариант добавляет в формулировку расстояния Левенштейна дополнительное условие. А именно, обмен местами (транспозиция) двух, стоящих рядом, букв, то же считается одной из операций, такой же как вставка, удаление и замена. Совсем недавно Ф. Дамерау был полностью уверен, что практически все ошибки при вводе текста являются транспозициями. По этой причине применение такого варианта метрики показывает самые лучшие практические итоги.

Рисунок 4. Расстояние Дамерау-Левенштейна. Автор24 — интернет-биржа студенческих работ

Для вычисления этой дистанции, надо просто чуть изменить алгоритм определения стандартного расстояния Левенштейна. Конкретно, надо сохранять не две, три последние строки матрицы. И ещё одно добавочное правило, если находится транспозиция, то при определении расстояния надо принимать во внимание так же её стоимость.

Помимо приведённых выше, есть ещё различные другие, редко используемые на практике, расстояния. Например, метрика Джаро – Винклера и другие, которые описаны в технической литературе.

Алгоритмы нечеткого поиска без индексации (Онлайн)

Такие алгоритмы служат для поисков по не определённому исходному тексту, и возможно их применение, к примеру, в редакторах текста, просмотровых приложениях или в браузерах, где выполняется поиск на странице. Для них не требуется предварительная переработка текстовой информации и они способны обрабатывать постоянный информационный поток.

Линейный поиск

Под линейным поиском понимается поочерёдное использование определённой метрики (к примеру, Левенштейна) к набору слов исходного текста. Если применяется метрика с наличием ограничения, то линейный поиск даёт оптимальное быстродействие. Правда, в этом случае, при возрастании к, сильно растёт и время обработки. Формула временной оценки, следующая: О(кn).

Алгоритм Bitap

Этот алгоритм, а также разные его варианты, чаще всего применяются для нечётких поисков без использования индексов. Одним из вариантов является утилита unix, которая называется agrep и предназначена для выполнения операций, аналогичных утилите grep, но с возможностью поддержки ошибок в запросе на поиск и предоставлении некоторых удобств при использовании стандартных выражений. Идея данного способа была высказана в 1992-ом году в одной научной статье, опубликованной Ricardo Baeza-Yates и Gaston Gonnet. В этом алгоритме сначала применялась только замена символов, и, практически, определялось расстояние Хемминга. Но позднее Sun Wu и Udi Manber модифицировали этот метод, и он стал применим для определения расстояния Левенштейна. Была добавлена поддержка удалений и вставок, что позволило сделать на его базе исходный вариант утилиты agrep.

Процедура Bitshift

Рисунок 5. Процедура. Автор24 — интернет-биржа студенческих работ

Вставки

Рисунок 6. Вставки. Автор24 — интернет-биржа студенческих работ

Удаления

Рисунок 7. Удаления. Автор24 — интернет-биржа студенческих работ

Замены

Рисунок 8. Замены. Автор24 — интернет-биржа студенческих работ

Результат

Рисунок 9. Результат. Автор24 — интернет-биржа студенческих работ

Здесь к — число ошибок, j — индексация символов, sx — маска символики (в маске единичные биты расположены на местах, которые соответствуют расположению этой символики в запросе)

Совпал или не совпал поиск по запросу, решается по содержимому последнего бита вектора результата R. Высокое быстродействие этого метода получается за счёт применения параллельных битовых вычислительных операций. Одна операция включает в себя работу с 32-мя и больше битами единовременно. Это при том, что стандартный вариант может выполнять поиск слов, размером не больше тридцать два. Возможно применение и типов большей разрядности, но это приведёт к замедлению исполнения алгоритма.