Вопрос по algorithm, string – Лучшая структура данных для реализации словаря?

61

Какова была бы лучшая структура данных для хранения всех слов словаря? Лучшее, что я мог придумать, это использоватьHashMap, который будет сопоставлен сHashTable. В основном, в зависимости от первого символа, мы получим связанныйHashTable и затем, используя это, мы можем добавить слова, начинающиеся с этого символа. Затем мы выберем хорошую хеш-функцию на основе строки.

Есть ли лучший подход?

Ваш Ответ

1   ответ
131

что вы хотите сделать, есть много хороших структур данных.

Если вы просто хотите сохранить слова и спросить «это слово здесь или нет?», То разумным подходом является стандартная хеш-таблица без каких-либо других причудливых механизмов. Если это слово заранее исправлено, рассмотрите возможность использования идеальная хеш-таблица, чтобы получить отличную производительность и использование пространства.

Если вы хотите иметь возможность проверить, существует ли данный префикс при поддержке быстрого поиска, то Trie - хороший вариант, хотя он может быть немного неэффективным. Он также поддерживает быстрые вставки или удаления. Это также позволяет выполнять итерации в алфавитном порядке, чего не предлагает хеширование. По сути, это структура, которую вы описали в своем ответе, но в зависимости от варианта использования другие варианты попыток могут быть лучше.

Если в дополнение к вышесказанному вы точно знаете, что список слов фиксирован, рассмотрите возможность использования DAWG (направленный ациклический граф слов), который по сути является DFA с минимальным состоянием для языка. Он существенно более компактен, чем Trie, но поддерживает многие из тех же операций.

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

Если пространство вызывает беспокойство, но вы хотите три, посмотрите на succinct trie представление, которое имеет более медленный поиск, но примерно теоретически оптимальное использование пространства. Ссылка обсуждает, как он используется в JavaScript как простой способ передачи огромного количества данных. Альтернативное компактное представление - это двойной масс, правда, я об этом очень мало знаю.

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

Надеюсь это поможет

+ 1 комментарий: хотя это может быть немного экономно ... неэффективно, верно? Gert Arnold

Похожие вопросы