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