Какой будет хорошая структура данных для хранения словаря (слов) для оптимизации времени поиска?

Question

Предоставив список допустимых слов и поисковое слово, я хочу выяснить, является ли поисковое слово действительным словом или нет, ПОЗВОЛЯЕТ 2 опечатки.

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

Если допустимых символов опечатки нет, тогда Trie будет хорошим способом.хранить слова, но не уверен, что это лучший способ сохранить словарь, когда опечатки разрешены.Не уверен, какова будет сложность алгоритма обратного отслеживания (для поиска слова в Trie, допускающего 2 опечатки).Есть идеи по этому поводу?

Answer 1

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

1.) Построить набор, содержащий хэши всех допустимых слов (не включая опечатки)).Так что, вероятно, мы говорим здесь о приблизительно 10.000 записях, которые все еще должны позволять довольно быстрые поиски с двоичным поиском.Если хеш слова найден в наборе, он набран правильно.

2.) Если хеш слова не найден в наборе, слово, вероятно, неправильно введено.Поэтому рассчитайте расстояние Дамерау-Левенштейна между словом и всеми известными словами, чтобы выяснить, что мог значить пользователь.Чтобы добиться некоторой производительности, измените алгоритм DL, чтобы прервать вычисление, если расстояние превышает допустимый порог в 2 опечатки.

Answer 2

Возможно, вы захотите оформить направленную ациклическую графику слов или DAWG .У него больше автоматной структуры, чем у дерева графовой структуры.Множество возможностей из одного места могут предоставить вам ваше решение.