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


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

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

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

8 121

8 ответов:

преимущества нах:

основы:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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