Wie wähle ich zwischen einer Hash-Tabelle und einem Trie (Präfixbaum)?

134

Wenn ich also zwischen einer Hash-Tabelle oder einem Präfixbaum wählen muss, was sind die Unterscheidungsfaktoren, die mich dazu bringen würden, einen über den anderen zu wählen? Aus meiner naiven Sicht scheint es, als hätte die Verwendung eines Tries einen zusätzlichen Aufwand, da er nicht als Array gespeichert ist, sondern in Bezug auf die Laufzeit (vorausgesetzt, der längste Schlüssel ist das längste englische Wort) im Wesentlichen O sein kann (1) (in Bezug auf die Obergrenze). Vielleicht ist das längste englische Wort 50 Zeichen?

Hash-Tabellen werden sofort nachgeschlagen, sobald Sie den Index erhalten haben . Das Drücken der Taste, um den Index zu erhalten, scheint jedoch leicht fast 50 Schritte zu dauern.

Kann mir jemand eine erfahrenere Perspektive dazu geben? Vielen Dank!

Justin Bozonier
quelle
1
Es ist erwähnenswert, dass ein Redix-Baum effizienter ist als ein einfacher Versuch, da Sie nicht für jedes Zeichenfolgenbyte einen neuen Zweig benötigen. Außerdem bieten Redix-Bäume eine bessere Unterstützung für "Fuzzy" -Suchen als Hash-Tabellen, da Sie beim Bearbeiten des Pfads einzelne Bits betrachten. Zum Beispiel 00110010könnte das Eingabebyte sein, aber Sie möchten die Übereinstimmung einschließen, die 00111010nur ein Bit entfernt ist.
Xeoncross

Antworten:

116

Vorteile von Versuchen:

Die Grundlagen:

  • Vorhersagbare O (k) -Suchzeit, wobei k die Größe des Schlüssels ist
  • Die Suche kann weniger als k Mal dauern, wenn sie nicht vorhanden ist
  • Unterstützt die bestellte Durchquerung
  • Keine Notwendigkeit für eine Hash-Funktion
  • Das Löschen ist unkompliziert

Neue Operationen:

  • Sie können schnell nach Präfixen von Schlüsseln suchen, alle Einträge mit einem bestimmten Präfix auflisten usw.

Vorteile der verknüpften Struktur:

  • Wenn es viele gängige Präfixe gibt, wird der benötigte Speicherplatz gemeinsam genutzt.
  • Unveränderliche Versuche können die Struktur teilen. Anstatt einen Versuch an Ort und Stelle zu aktualisieren, können Sie einen neuen Versuch erstellen, der sich nur entlang eines Zweigs unterscheidet und an anderer Stelle auf den alten Versuch verweist. Dies kann nützlich sein für Parallelität, mehrere gleichzeitige Versionen einer Tabelle usw.
  • Ein unveränderlicher Versuch ist komprimierbar. Das heißt, es kann auch die Struktur der Suffixe durch Hash-Consing teilen.

Vorteile von Hashtabellen:

  • Jeder kennt Hashtabellen, oder? Ihr System verfügt bereits über eine schöne, gut optimierte Implementierung, die für die meisten Zwecke schneller als versucht ist.
  • Ihre Schlüssel müssen keine spezielle Struktur haben.
  • Platzsparender als die offensichtlich verknüpfte Struktur ( siehe Kommentare unten )
Darius Bacon
quelle
25
kann nicht ganz mit "Platzsparender als die offensichtlich verknüpfte Trie-Struktur" übereinstimmen - in einer allgemeinen Hash-Tabellen-Implementierung nimmt sie einen viel größeren Platz ein, um Schlüssel zu enthalten, während in Versuchen jeder Knoten ein Wort darstellt. In diesem Sinne sind Versuche platzsparender.
Galactica
1
Wie wäre es mit dem Zugriff auf Daten von einer Struktur zur anderen? Ich denke an Cache und Speicherort
Horia Toma
8
@galactica, das widerspricht meiner Erfahrung: In dieser Antwort aller Strukturen, die ich für den Raum gemessen habe, erging es einem Versuch am schlechtesten. Dies ist sinnvoll, da ein Zeiger viel größer als ein Byte ist. Ja, das Teilen von Präfixen hilft, aber es muss viel Aufwand überwunden werden, um die Parität zu erreichen. Eine platzsparendere Darstellung kann viel helfen, aber dann sprechen wir nicht mehr über die offensichtliche verknüpfte Struktur.
Darius Bacon
1
@DariusBacon, der Telefonnummernpläne bearbeitet, scheint ein vernünftiges Szenario für Versuche zu sein. Beispielszenario: Telefonnummer zu Carrier Matching inkl. Nummern, die von einem Netzbetreiber auf einen anderen portiert wurden. Für übliche Wörterbücher kann es von der Sprache abhängen (Mandarin vs Englisch), Sie benötigen n-Gramm und / oder andere statistische Daten. Für ein Reimbuch scheint auch ein Suffixbaum eine gute Option zu sein.
mbx
Die Vielfalt der zu suchenden Daten ist sehr wichtig. Wenn ein großer Prozentsatz Ihrer Datenwerte eindeutig ist, steigt Ihre Speicherplatzkomplexität aufgrund der Verwendung zusätzlicher Nullzeiger über den Hash.
Beispiel
45

Es hängt alles davon ab, welches Problem Sie lösen möchten. Wenn Sie nur Einfügungen und Suchvorgänge ausführen müssen, verwenden Sie eine Hash-Tabelle. Wenn Sie komplexere Probleme wie Präfix-bezogene Abfragen lösen müssen, ist ein Versuch möglicherweise die bessere Lösung.

Adam Rosenfield
quelle
8
Wenn Hash-Tabelle und Trie bei der Abfrage dieselbe Komplexität haben, O (k) für Zeichenfolge mit k-Länge, warum sollten wir Hash wählen? könnten Sie bitte erklären?
Sazzad Hissain Khan
29

Jeder kennt die Hash-Tabelle und ihre Verwendung, aber es ist nicht gerade eine konstante Nachschlagezeit. Sie hängt davon ab, wie groß die Hash-Tabelle ist und wie komplex die Hash-Funktion ist.

Das Erstellen großer Hash-Tabellen für eine effiziente Suche ist in den meisten industriellen Szenarien, in denen selbst eine geringe Latenz / Skalierbarkeit von Bedeutung ist (z. B. Hochfrequenzhandel), keine elegante Lösung. Sie müssen sich um die Datenstrukturen kümmern, die für den Speicherplatz optimiert werden sollen, den sie auch im Speicher beanspruchen, um den Cache-Fehler zu reduzieren.

Ein sehr gutes Beispiel, bei dem die Anforderungen besser erfüllt werden, ist die Messaging-Middleware. Sie haben eine Million Abonnenten und Herausgeber von Nachrichten in verschiedenen Kategorien (in JMS-Begriffen - Themen oder Austausch). Wenn Sie in solchen Fällen Nachrichten nach Themen herausfiltern möchten (die eigentlich Zeichenfolgen sind), möchten Sie definitiv keine Hash-Tabelle erstellen für die Millionen Abonnements mit Millionen Themen. Ein besserer Ansatz besteht darin, die Themen in trie zu speichern. Wenn die Filterung auf der Grundlage der Themenübereinstimmung erfolgt, ist ihre Komplexität unabhängig von der Anzahl der Themen / Abonnements / Herausgeber (hängt nur von der Länge der Zeichenfolge ab). Ich mag es, weil Sie mit dieser Datenstruktur kreativ sein können, um den Platzbedarf zu optimieren und somit einen geringeren Cache-Miss zu haben.

user179156
quelle
10

Verwenden Sie einen Baum:

  1. Wenn Sie eine automatische Vervollständigung benötigen
  2. Finden Sie alle Wörter, die mit 'a' oder 'axe' beginnen.
  3. Ein Suffixbaum ist eine spezielle Form eines Baumes. Suffixbäume haben eine ganze Liste von Vorteilen, die Hash nicht abdecken kann.
Dr.Sai
quelle
4

Es gibt etwas, das ich nicht ausdrücklich erwähnt habe und das ich für wichtig halte. Sowohl Hash-Tabellen als auch Versuche verschiedener Art haben normalerweise O(k)Operationen, wobei kdie Länge der Zeichenfolge in Bits (oder äquivalent in Zeichen) angegeben ist.

Dies setzt voraus, dass Sie eine gute Hash-Funktion haben. Wenn Sie nicht möchten, dass "Farm" und "Farm Animals" denselben Wert haben, muss die Hash-Funktion alle Bits des Schlüssels verwenden. Daher sollte das Hashing von "Farm Animals" etwa doppelt so lange dauern wie "farm" (es sei denn, Sie befinden sich in einem rollierenden Hash-Szenario, aber es gibt auch ähnliche betriebssparende Szenarien mit Versuchen). Und mit einem Vanille-Versuch ist klar, warum das Einfügen von "Nutztieren" etwa doppelt so lange dauert wie das Einfügen von "Nutztieren". Auf lange Sicht gilt dies auch für komprimierte Versuche.

Benutzer3391564
quelle
3

Das Einfügen und Nachschlagen eines Versuchs erfolgt linear mit der Länge der Eingabezeichenfolge O (s).

Ein Hash gibt Ihnen ein O (1) zum Nachschlagen und Einfügen, aber zuerst müssen Sie den Hash basierend auf der Eingabezeichenfolge berechnen, die wiederum O (s) ist.

Schlussfolgerung: Die asymptotische Zeitkomplexität ist in beiden Fällen linear.

Der Trie hat aus Datenperspektive etwas mehr Overhead, aber Sie können einen komprimierten Trie auswählen, der Sie mehr oder weniger mit der Hash-Tabelle in Verbindung bringt.

Um die Krawatte zu lösen, stellen Sie sich folgende Frage: Muss ich nur nach vollständigen Wörtern suchen? Oder muss ich alle Wörter zurückgeben, die einem Präfix entsprechen? (Wie in einem prädiktiven Texteingabesystem). Für den ersten Fall gehen Sie für einen Hash. Es ist einfacher und sauberer Code. Einfacher zu testen und zu warten. Für einen ausgefeilteren Anwendungsfall, bei dem Präfixe oder Sufixe eine Rolle spielen, versuchen Sie es.

Und wenn Sie es nur zum Spaß tun, würde die Implementierung eines Tries einen Sonntagnachmittag sinnvoll nutzen.

Visiedo
quelle
"Ein Hash gibt Ihnen ein O (1) zum Nachschlagen und Einfügen, aber zuerst müssen Sie den Hash basierend auf der Eingabezeichenfolge berechnen, die wiederum O (s) ist." Danke, dass du das erklärt hast!
Abadawi
2

Die HashTable- Implementierung ist im Vergleich zur grundlegenden Trie- Implementierung platzsparend . Bei Zeichenfolgen ist jedoch in den meisten praktischen Anwendungen eine Bestellung erforderlich. Aber HashTable stört die lexografische Reihenfolge völlig. Wenn Ihre Anwendung jetzt Operationen basierend auf der lexografischen Reihenfolge ausführt (z. B. Teilsuche, alle Zeichenfolgen mit angegebenem Präfix, alle Wörter in sortierter Reihenfolge), sollten Sie Versuche verwenden. Nur für die Suche sollte HashTable verwendet werden (da dies wohl eine minimale Suchzeit bietet).

PS: Anders als diese, Ternary Suchbäume (TSTs) wäre eine ausgezeichnete Wahl. Die Suchzeit ist länger als bei HashTable, bei allen anderen Vorgängen jedoch zeiteffizient. Außerdem ist es platzsparender als Versuche.

Jay Jodiwal
quelle
-2

Einige (normalerweise eingebettete Echtzeitanwendungen) erfordern, dass die Verarbeitungszeit unabhängig von den Daten ist. In diesem Fall kann eine Hash-Tabelle eine bekannte Ausführungszeit garantieren, während ein Versuch basierend auf den Daten variiert.

Adam Liss
quelle
6
Die meisten Hash-Tabellen garantieren keine bekannte Ausführungszeit - der schlimmste Fall ist O (n), wenn jedes Element kollidiert und verkettet wird
Adam Rosenfield
2
Für jeden Datensatz können Sie eine perfekte Hash-Funktion berechnen, die O (1) -Suchen für diese Daten garantiert. Natürlich ist es nicht kostenlos, den perfekten Hash zu berechnen.
George V. Reilly
5
Auch die Verkettung ist nicht die einzige Möglichkeit, mit Kollisionen umzugehen. Es gibt alle möglichen interessanten und cleveren Möglichkeiten, damit umzugehen - Kuckuck-Hashing ( en.wikipedia.org/wiki/Cuckoo_hashing ) - und die beste Wahl hängt von den Anforderungen des Client-Codes ab.
Hank Gay
Ich wusste nichts über Kuckucks-Hashing und seine Beziehung zum Bloom-Filter. Das wird eine interessante Lektüre sein, danke!
Horia Toma
Vergessen Sie nicht Robin-Hood Hashing, das in Bezug auf Cache und Varianz überlegen ist. sebastiansylvan.com/2013/05/08/… codecapsule.com/2013/11/11/robin-hood-hashing
Jarred Nicholls