Как выбрать между хеш-таблицей и Trie (префиксное дерево)?

Итак, если мне нужно выбрать между хеш-таблицей или деревом префикса, какие дискриминационные факторы приведут меня к выбору одного из них. С моей собственной наивной точки зрения кажется, что использование trie имеет некоторые дополнительные накладные расходы, поскольку оно не хранится в виде массива, а с точки зрения времени выполнения (при условии, что самый длинный ключ является самым длинным английским словом), это может быть по существу O (1) (относительно верхней границы). Может быть, самое длинное английское слово - 50 символов?

Хэш-таблицы мгновенно просматриваются, как только вы получаете индекс. Хеширование клавиши, чтобы получить индекс, похоже, что он может легко принять около 50 шагов.

Может ли кто-нибудь предоставить мне более опытный взгляд на это? Спасибо!

Ответ 1

Преимущества попыток:

Основы:

Предсказуемое время поиска O (k), где k - размер ключа
Поиск может занимать менее k раз, если он не там
Поддерживает упорядоченный обход
Нет необходимости в хэш-функции
Исключение прост.

Новые операции:

Вы можете быстро искать префиксы ключей, перечислять все записи с заданным префиксом и т.д.

Преимущества связанной структуры:

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

Преимущества хэш-таблиц:

Всем известно, hashtables, не так ли? Ваша система уже будет иметь хорошо оптимизированную реализацию, быстрее, чем попытки для большинства целей.
У ваших ключей не должно быть специальной структуры.
Больше пространства, чем очевидная связанная структура trie (см. комментарии ниже)

Ответ 2

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

Ответ 3

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

Создание огромных хэш-таблиц для эффективного поиска не является изящным решением в большинстве промышленных сценариев, где важны даже малые задержки/масштабируемость (например, высокая частота торговли). Вы должны заботиться о том, чтобы структуры данных были оптимизированы для пространства, которое оно занимает в памяти, также для уменьшения промаха в кэше.

Очень хороший пример, где trie лучше соответствует требованиям, - это промежуточное программное обеспечение для обмена сообщениями. У вас есть миллион подписчиков и издателей сообщений для разных категорий (в условиях JMS - темы или обмены), в таких случаях, если вы хотите отфильтровать сообщения на основе тем (которые фактически являются строками), вы определенно не хотите создавать хэш-таблицу за миллион подписей с миллионами тем. Лучший подход - хранить темы в trie, поэтому, когда фильтрация выполняется на основе соответствия тем, ее сложность не зависит от количества тем/подписчиков/издателей (зависит только от длины строки). Мне это нравится, потому что вы можете проявлять творческий подход к этой структуре данных для оптимизации требований к пространству и, следовательно, более низкого промаха в кеше.

Ответ 4

Используйте дерево:

Если вам нужна функция автозаполнения
Найти все слова, начинающиеся с 'a' или 'ax' и так далее.
Деревом суффикса является специальная форма дерева. Суффикс-деревья имеют целый список преимуществ, которые хэш не может покрыть.

Ответ 5

Есть кое-что, что я не видел, чтобы кто-то прямо упоминал, что я считаю важным иметь в виду. Как в хэш-таблицах, так и в попытках различных типов обычно используются операции O(k), где k - длина строки в битах (или эквивалентно в символах).

Это предполагает, что у вас есть хорошая хеш-функция. Если вы не хотите, чтобы "ферма" и "сельскохозяйственные животные" хэшировали одно и то же значение, то хэш-функция должна будет использовать все биты ключа, поэтому хеширование "сельскохозяйственных животных" должно занимать примерно вдвое больше времени, чем "ферма" (если вы не используете какой-то сценарий с переменным хэшем, но есть и несколько похожих сценариев сохранения операций с попытками). И с ванильным деревом ясно, почему вставка "сельскохозяйственных животных" займет в два раза больше времени, чем просто "ферма". В долгосрочной перспективе это верно и для сжатых попыток.

Ответ 6

Реализация HashTable является пространственной эффективностью по сравнению с базовой реализацией Trie. Но при использовании струн в большинстве практических применений необходимо упорядочить. Но HashTable полностью нарушает лессографический порядок. Теперь, если ваше приложение выполняет операции, основанные на лексическом порядке (например, частичный поиск, все строки с заданным префиксом, все слова в отсортированном порядке), вы должны использовать Tries. Для просмотра только HashTable следует использовать (как возможно, он дает минимальное время поиска).

P.S.: Кроме того, отличный выбор будет Ternary Search Trees (TSTs). Его время поиска больше, чем HashTable, но эффективно во всех других операциях. Кроме того, его более эффективное пространство, чем попытки.

Ответ 7

Вставка и поиск по trie линейны с длиной текущей строки O (s).

Хэш предоставит вам O (1) для вставки ans для поиска, но сначала вы должны вычислить хэш на основе входной строки, которая снова является O (s).

Conclussion, асимптотическая временная сложность является линейной в обоих случаях.

У trie есть некоторые дополнительные накладные расходы с точки зрения данных, но вы можете выбрать сжатое trie, которое снова поставит вас на более высокий уровень привязки к хеш-таблице.

Чтобы сломать галстук, задайте себе этот вопрос: нужно ли мне искать только полные слова? Или мне нужно вернуть все слова, соответствующие префиксу? (Как в системе интеллектуального ввода текста). В первом случае перейдите к хешу. Это более простой и чистый код. Легче тестировать и поддерживать. Для более эффективного использования, где префиксы или суффиксы имеют значение, перейдите к trie.

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

Ответ 8

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