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

134

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

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

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

Джастин Бозонье
источник
1
Стоит отметить, что дерево redix более эффективно, чем простое дерево, потому что вам не нужна новая ветвь для каждого байта строки. Кроме того, деревья redix обеспечивают поддержку «нечетких» поисков лучше, чем хеш-таблицы, потому что вы смотрите на отдельные биты при работе по пути. Например, 00110010может быть входной байт, но вы хотите включить совпадение, 00111010которое удалено только на один бит.
Xeoncross

Ответы:

116

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

Основы:

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

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

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

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

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

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

  • Все знают хеш-таблицы, верно? Ваша система уже будет иметь хорошую, хорошо оптимизированную реализацию, более быструю, чем попытки для большинства целей.
  • Ваши ключи не должны иметь какой-либо специальной структуры.
  • Более компактный, чем очевидная связанная структура дерева ( см. Комментарии ниже )
Darius Bacon
источник
27
может не совсем согласиться с «Более эффективным с точки зрения пространства, чем очевидная связанная структура трия» - в общей реализации хэш-таблицы она занимает гораздо больше места для хранения ключей, в то время как при попытках каждый узел представляет слово. В этом смысле попытки более экономичны.
Галактика
1
как насчет доступа к данным из одной структуры против другой? Я думаю, кеш и местоположение
Хория Тома
8
@galactica, это противоречит моему опыту: например, в этом ответе всех структур, которые я измерил для космоса, три ударили по худшему. Это имеет смысл, поскольку указатель намного больше байта. Да, совместное использование префиксов помогает, но для достижения паритета необходимо преодолеть много накладных расходов. Более эффективное представление пространства может сильно помочь, но тогда мы больше не говорим об очевидной связанной структуре.
Дариус Бэкон
1
@DariusBacon обработка телефонных номеров выглядит разумным сценарием для попыток. Пример сценария: соответствие номера телефона оператору связи, вкл. номера переносятся с одного носителя на другой. Для обычных словарей это может зависеть от языка (мандарин против английского), вам потребуются n-граммы и / или другие статистические данные. Для рифмы книга суффиксов также кажется хорошим вариантом.
MBX
Разнообразие данных для поиска имеет большое значение. Если большой процент значений ваших данных уникален, ваша сложность пространства увеличится по сравнению с хешем из-за использования дополнительных нулевых указателей.
Изучение статистики на примере
45

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

Адам Розенфилд
источник
8
если хеш-таблица и trie имеют одинаковую сложность в запросе, O (k) для строки длиной k, почему мы должны идти на хеш? не могли бы вы объяснить?
Саззад Хиссейн Хан
29

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

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

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

user179156
источник
11

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

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

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

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

user3391564
источник
3

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

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

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

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

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

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

Visiedo
источник
«Хеш даст вам O (1) для поиска и вставки, но сначала вы должны вычислить хеш на основе входной строки, которая снова равна O (s)». Спасибо за объяснение этого!
Абадави
Вычисление хеш-функции не является O (s). Это на самом деле O (1). Вам не нужны все биты строки, чтобы вычислить ее, некоторые из них (их постоянное число) достаточно.
Никола Амадио
2

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

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

Джей Джодивал
источник
-2

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

Адам Лисс
источник
6
Большинство хеш-таблиц не гарантируют известное время выполнения - наихудший случай - O (n), если каждый элемент сталкивается и связывается
Адам Розенфилд
2
Для любого набора данных вы можете вычислить идеальную хеш-функцию, которая гарантирует O (1) поиск этих данных. Конечно, вычисление идеального хэша не является бесплатным.
Джордж В. Рейли
5
Кроме того, цепочка не единственный способ справиться с коллизиями; Есть много интересных и умных способов справиться с этим - хеширование кукушки ( en.wikipedia.org/wiki/Cuckoo_hashing ) для одного - и лучший выбор зависит от потребностей клиентского кода.
Хэнк Гей
не знал о хешировании кукушки и его связи с фильтром Блума, сделаю для интересного чтения, спасибо!
Хория Тома
Не забывайте о Robin-hood Hashing, который лучше всего подходит для кеша и дисперсии. sebastiansylvan.com/2013/05/08/… codecapsule.com/2013/11/11/robin-hood-hashing
Джарред Николлс