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

Question

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

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

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

Answer 1

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

Основы:

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

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

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

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

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

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

• Каждый знает HashTables, верно? Ваша система уже будет иметь хорошо оптимизированную реализацию, быстрее, чем попытки для большинства целей.
• Ваши ключи не должны иметь специальной конструкции.
• Более эффективно чем очевидная связанная структура TRIE (см комментариев ниже)

Answer 2

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

Answer 3

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

Answer 4

Использование дерево:

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

Answer 5

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

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

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

Answer 6

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

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

Answer 7

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

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

Answer 8

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

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

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

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

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

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