Рекомендуемая структура данных при разработке что-то вроде словаря?

Question

Является ли TRIE наиболее рекомендуемой структурой данных при разработке чего-то вроде словаря для хранения слов?Любые другие альтернативы, которые улучшают или время или производительность памяти?

Я считаю, что хеш может быть полезен, если нет коллизий, но тогда требования к памяти начинают ухудшаться для перекрывающихся слов: перекрытия, перекрытия, перекрытия, перекрытия, перекрытия, все занимают эксклюзивное хранилище, в то время как мы могли бы совместно использовать пространство в три.1003 *

РЕДАКТИРОВАТЬ: Спасибо @Moron и всем вам за очень полезные ответы.Я согласен - генерация хеш-ключа - это O (n), так же как и поиск TRIE.Тем не менее, для хэшей вещи могут быть хуже с добавлением цепочки ко времени, в то время как для TRIE этого не произойдет.Я по-прежнему обеспокоен тем, что для каждого узла в TRIE мне нужно сохранить указатель, который может выдавать вещи, если размер словаря мал.

Answer 1

У дерева есть следующие преимущества по сравнению с хэш-таблицей:

1. Поиск данных в дереве быстрее в худшем случае, O(m) раз, по сравнению с несовершенной хэш-таблицей.Несовершенная хеш-таблица может иметь ключевые коллизии.Ключевое столкновение - это отображение хеш-функции разных ключей в одну и ту же позицию в хеш-таблице.Скорость поиска в наихудшем случае в несовершенной хеш-таблице составляет O(N) время, но гораздо чаще O(1), при O(m) времени, потраченном на оценку хеш-функции.
2. Нет столкновений различных ключей вtrie.
3. Пакеты в блоке, аналогичные сегментам хеш-таблицы, в которых хранятся коллизии ключей, необходимы только в том случае, если один ключ связан с несколькими значениями.
4. Нет необходимостипредоставить хеш-функцию или изменить хеш-функции по мере того, как к дереву добавляется больше ключей.
5. Три могут обеспечивать алфавитное упорядочение записей по ключу.

Попытки имеют следующиенедостатки:

1. В некоторых случаях попытки могут выполняться медленнее, чем хеш-таблицы для поиска данных, особенно если к данным осуществляется прямой доступ к жесткому диску или другому вспомогательному устройству хранения, где время произвольного доступа составляетвысокий по сравнению с основной памятью.
2. Нелегко представить все ключи в виде строк, таких как числа с плавающей запятой - прямаяпрямое кодирование с использованием цепочки битов их кодирования приводит к длинным цепочкам и префиксам, которые не имеют особого смысла.

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

Источник: Википедия: Trie # Как замена других структур данных

Answer 2

Вы можете попробовать рассмотреть Направленный ациклический граф Word , который в основном является trie, но имеет лучшее использование памяти, и, согласно вики, для английского, потребление памяти намного ниже, чем trie. *

Время мудрое, это похоже на три и, вероятно, лучше, чем хэш. Не уверен, где вы получили время O (logn) для хэша. Для разумных хэшей это должно быть O (n), где n - длина искомого слова.

Answer 3

Полагаю, это большой вопрос, а? Может быть, попробуйте посмотреть на фильтр Блума?

http://en.wikipedia.org/wiki/Bloom_filter