Быстрая оценка минимального расстояния Левенштейна

Question

У нас есть реализация проверки орфографии, основанная на расстоянии Левенштейна . Поскольку мы не могли рассчитать расстояние для всех возможных подстановок (расстояние Левенштейна между двумя строками, рассчитанное в O(n^2)), мы используем индекс K-грамма для поиска кандидатов на подстановку.

Таким образом, индекс K-граммы - это только один из способов быстрого устранения несущественной замены. Меня интересуют и другие способы. На данный момент мы использовали еще несколько трюков. Учитывая, что нас интересуют только замены расстояния редактирования не более d из исходной строки, мы могли бы использовать следующие правила:

• расстояние редактирования между двумя строками не может быть меньше разницы в длине между ними. Таким образом, замены с разницей в длине, превышающей d , могут быть исключены;
• один символ изменить / удалить при изменении строки минимум k к-грамм. Поэтому строки с разницей в k-граммах k * d не могли иметь расстояние редактирования меньше d : .

Верны ли эти предположения? И какие существуют другие способы устранения подстановок, применимые к проверкам правописания?

Answer 1

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

Также вы можете использовать индекс перестановки.рассмотрите все повороты запроса и просмотрите дерево B, чтобы найти любые словарные термины, которые соответствуют любому вращению.Вы также можете уточнить эту схему вращения, пропустив суффикс из l символов перед выполнением обхода

Answer 2

По моему опыту, приближение k-граммы оставляет желать лучшего (оно исключает множество релевантных результатов).

Вместо этого достаточно поместить ваши термины в автомат / преобразователь, три или даже отсортированный массив.и найти истинные совпадения Левенштейна через пересечение.

это интуитивно понятно, если вы думаете об этом: если вы хотите, чтобы слова были только на расстоянии 1, а входной термин - "foo", нет смысла исследовать"bar", "baz" и т. д. при проверке узлов 'b'.Только boo, bfoo и т. д. имеют шанс, поэтому вы можете ограничить поиск только префиксами, которые могут привести к конечному состоянию.

, поэтому вы просто создаете автомат, который принимает все слова в пределах k расстояний редактирования, равных "foo"и затем пересекайте этот автомат с вашим словарем-автоматом / три / чем угодно.

вы можете очень эффективно вычислить эти эти DFA, избегая медленного определения NFA-DFA и т. д .:

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.16.652