Naive Spellchecking, или поиск ближайших слов из словаря по метрике Левенштейна на Scala

Приветствую! В этой статье будет показан алгоритм поиска ближайших к заданному слов из корпуса в терминах метрики Левенштейна. Наивным spellchecking-ом назван потому, что не учитывает ни морфологии, ни контекста, ни вероятности появления скорректированного слова в предложении, однако в качестве первого приближения сойдет вполне. Также алгоритм может быть расширен на поиск ближайших последовательностей из любых других сравнимых объектов, нежели простой алфавит из Char-ов, и, после допиливания напильником, его можно приспособить и для учета вероятностей появления скорректированных слов. Но в данной статье сосредоточимся на базовом алгоритме для слов определенного алфавита, скажем, английского.

Код в статье будет на Scala.

Всех заинтересовавшихся прошу под кат.

Вообще говоря, для поиска в метрическом пространстве существуют специализированные структуры данных, такие как VP-Tree (Vantage Point Tree). Однако эксперименты показывают, что для пространства слов с метрикой Левенштейна VP-дерево работает крайне плохо. Причина банальна — данное метрическое пространство очень плотное. У слова из, скажем, 4х букв, имеется огромное множество соседей на расстоянии 1. На больших расстояниях количество вариантов становится сопоставимо с размером всего множества, что делает поиск в VP-дереве ничуть не более производительным, чем линейный поиск по множеству. К счастью, для строк существует более оптимальное решение, и сейчас мы его разберем.

Для компактного хранения множества слов с общим префиксом используем такую структуру данных, как бор (trie).

В двух словах алгоритм описывается как простой поиск алгоритмом Дейкстры на неявном графе вариантов префиксного совпадения искомого слова и слов в боре (trie). Узлами графа при нечетком поиске будут являться вышеназванные варианты, а весами ребер — собственно расстояние Левенштейна заданного префикса строки и узла бора.

Для начала, опишем узел бора, напишем алгоритм вставки и четкого поиска слова в боре. Нечеткий поиск оставим на закуску.

Как видим, ничего сверхъестественного. Узел бора представляет собой объект со ссылкой на родителя, Map-ой ссылок на потомков, буквенным значением узла, и флагом, является ли узел конечным узлом для какой-нибудь строки.

Теперь опишем четкий поиск в боре:

Ничего сложного. Спускаемся по детям узла до тех пор, пока не встретим совпадение (t.ends) или не увидим, что дальше спускаться некуда.

Наш бор — immutable, так что функция + возвращает нам новый бор.

Построение бора из корпуса слов выглядит как-то так:

Базовое построение готово.

Опишем узел графа:

Pos — позиция, на которой заканчивается префикс искомой строки в рассматриваемом варианте. Node — префикс бора в рассматриваемом варианте. Penalty — расстояние Левенштейна префикса строки и префикса бора.

Каррированный case-class означает, что функции equals/hashCode компилятор будет генерить только для первого argument-list'а. Penalty в сравнении Variant-ов не учитываются.

Перебором узлов графа с неубывающим penalty заведует функция с вот такой сигнатурой:

Для ее реализации напишем небольшой хелпер, генерирующий Stream функцией-генератором:

Теперь реализуем immutable context поиска, который мы будем передавать в функцию выше, и который содержит в себе все, что нужно для перебора узлов неявного графа алгоритмом Дейкстры: очередь с приоритетом и множество посещенных узлов:

Очередь узлов сделана из простой immutable TreeMap-ы. Ноды в очереди сортированы по возрастанию penalty и убыванию prefix pos.

Ну и наконец сам генератор стрима вариантов:

Наибольшего внимания тут заслуживает, разумеется, genvars. Она для данного узла графа генерирует ребра, исходящие из него. Для каждого потомка узла бора данного варианта поиска мы генерируем вариант со вставкой символа

и заменой символа

Если не дошли до конца строки — то генерим еще и вариант с удалением символа

Конечно, функция prefixes для общего использования малопригодна. Напишем обертки, позволяющие нам искать более-менее осмысленно. Для начала, ограничим перебор вариантов некоторым разумным значением penalty для предотвращения застревания алгоритма на каком-нибудь слове, для которого в словаре не существует более-менее адекватной замены

Далее отфильтруем варианты с полным, а не префиксным совпадением, то есть такие, у которых pos равен длине искомой строки, и node указывает на конечный узел с флагом ends == true:

Ну и наконец преобразуем стрим вариантов в стрим слов, для этого в классе Trie напишем код, который возвращает нам найденное слово:

Ничего сложного. Поднимаемся по parent-ам, записывая значения узлов, пока не встретим корень бора.

Надо сказать, что функция matches весьма универсальна. Используя ее, можно производить поиск K ближайших, делая просто

или поиск Delta-ближайших, то есть строк на расстоянии не больше D:

Еще алгоритм можно расширить, вводя разные веса для вставки/удаления/замены символов. В класс Variant можно добавить конкретные счетчики замен/удалений/вставок. Trie можно обобщить, чтобы можно было в конечных узлах хранить значения, и в качестве ключей использовать не только строки, но и индексированные последовательности любых сравнимых типов ключей. Также можно каждый узел бора помечать вероятностью его встретить (для конечного узла это вероятность встретить слово + вероятности встретить все слова-потомки, для промежуточного — только сумма вероятностей потомков) и учитывать этот вес при расчете penalty, но это все находится уже за рамками данной статьи.