Какой алгоритм лучше всего подходит для ближайшего слова?

Question

Какой алгоритм лучше всего подходит для ближайшего слова.

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

Answer 1

Один из вариантов - BK-деревья - см. Мой пост в блоге о них здесь . Другой, более быстрый, но более сложный вариант - автоматы Левенштейна, о которых я также писал, здесь .

Answer 2

Существуют такие инструменты, как HunSpell (широко проверяющая правописание с открытым исходным кодом, включая OpenOffice), которые подошли к проблеме с разных точек зрения.Одним из широко используемых критериев для определения того, насколько близки слова, является расстояние Левенштейна , которое также используется в HunSpell.

Answer 3

Вы можете использовать BLAST

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

В BLAST уже встроено понятие редактирования расстояний.

В качестве альтернативы вы можете использовать суффиксные деревья (у Дана Гусфельда есть отличная книга по основным алгоритмам сопоставления строк) и встроить идею редактирования расстояний.в.