Как использовать Trie для проверки орфографии

У меня есть три, которые я создал из словаря слов. Я хочу использовать это для проверки орфографии (и предлагать ближайшие совпадения в словаре, возможно, для заданного количества изменений x). Я думаю, что использовал бы levenshtein расстояние между целевым словом и словами в моем словаре, но есть ли разумный способ пересечь trie, фактически не управляя логикой расстояния редактирования над каждым словом отдельно? Как мне выполнить обход и сопоставление расстояния редактирования?

Например, если у меня есть слова MAN, MANE, я должен иметь возможность повторно использовать вычисление расстояния редактирования на MAN в MANE. В противном случае Trie не будет выполнять никаких целей

Ответ 1

Попробуйте вычислить для каждого дерева node массив A, где A [x] - самое маленькое расстояние редактирования, которое должно находиться в этой позиции в trie после сопоставления первых x букв целевого слова.

Затем вы можете прекратить рассмотрение любых узлов, если каждый элемент массива больше целевого.

Например, с trie, содержащим MAN и MANE, и входной BANE:

Node 0 representing '', A=[0,1,2,3,4]
Node 1 representing 'M', A=[1,1,2,3,4]
Node 2 representing 'MA', A=[2,1,1,2,3]
Node 3 representing 'MAN' A=[3,2,2,1,2]
Node 4 representing 'MANE' A=[4,3,2,2,1]

Наименьшее значение для A [end] равно 1, достигнув слова "MANE", поэтому это наилучшее совпадение.

Ответ 2

Думаю, вам стоит попробовать bk-trees; это структура данных, которая хорошо подходит для проверки орфографии, поскольку это позволит вам эффективно вычислить расстояние редактирования со словами вашего словаря.

Эта ссылка дает хорошее представление о BK-деревьях, применяемых для проверки орфографии