Какая была бы лучшая структура данных для хранения всех слов словаря? Лучшее, что я мог подумать, это использовать HashMap, который будет отображаться на HashTable. В основном, в зависимости от первого символа, мы получим связанный HashTable, а затем, используя это, мы можем добавить слова, начинающиеся с этого символа. Затем мы выберем хорошую хэш-функцию, основанную на строке.
Есть ли лучший подход?
В зависимости от того, что вы хотите сделать, существует много хороших структур данных.
Если вы просто хотите сохранить слова и спросить "это слово здесь или нет?", стандартная хеш-таблица без каких-либо других причудливых механизмов - разумный подход. Если это слово указано заранее, подумайте об использовании идеальной хеш-таблицы, чтобы получить отличную производительность и использование пространства.
Если вы хотите проверить, существует ли данный префикс при поддержке быстрого поиска, trie является хорошим вариантом, хотя это может быть немного неэффективным. Он также поддерживает быстрые вставки или удаления. Он также допускает итерацию в алфавитном порядке, которую хеширование не предлагает. Это, по сути, структура, которую вы описали в своем ответе, но в зависимости от варианта использования другие представления попыток могут быть лучше.
Если в дополнение к вышесказанному вы знаете, что список слов исправлен, рассмотрите возможность использования DAWG (направленный ациклический текстовый график), который по существу является DFA с минимальным состоянием для языка. Он существенно компактнее, чем trie, но поддерживает многие из тех же операций.
Если вы хотите поведение типа trie, но не хотите платить огромное количество штрафов, то дерево оснований. Это очень разные структуры, но они могут быть намного лучше, чем три в разных обстоятельствах.
Если пространство вызывает беспокойство, но вы хотите получить trie, посмотрите на сжатое trie представление, которое имеет более медленный поиск, но примерно теоретически оптимальное пространство Применение. Ссылка обсуждает, как она используется в JavaScript как простой способ передачи огромного количества данных. Альтернативным компактным представлением является double-array trie, хотя, по общему признанию, я очень мало знаю об этом.
Если вы хотите использовать словарь для операций, таких как проверка орфографии, где вам нужно найти слова, похожие на другие слова, BK-tree является отличной структурой данных, которую следует учитывать.
Надеюсь, это поможет!