Was ist der Unterschied zwischen Trie- und Radix-Trie-Datenstrukturen?

95

Sind die Datenstrukturen trie und radix trie dasselbe?

Wenn sie gleich sind, was bedeutet dann Radix Trie (AKA Patricia Trie)?

Aryak Sengupta
quelle
4
Bin ich der einzige, der es etwas nervig findet, dass das Tag radix-treeeher als ist radix-trie? Darüber hinaus sind einige Fragen damit verbunden.
Errantlinguist
@errantlinguist Wikipedia nennt den radix trieArtikel als Radix tree. Darüber hinaus ist der Begriff "Radixbaum" in der Literatur weit verbreitet. Wenn irgendetwas, das versucht, "Präfixbäume" aufzurufen, für mich sinnvoller wäre. Immerhin sind sie alle Baumdatenstrukturen .
Amelio Vazquez-Reina
Außerdem: "Was bedeutet Radix Trie (AKA Patricia Trie)?" Dies setzt voraus, dass Radixbäume und PATRICIA-Bäume ein und dasselbe sind, aber nicht (siehe z. B. diese Antwort ). PATRICIA-Bäume sind Bäume, die Sie durch Ausführen des PATRICIA- Algorithmus erhalten (auch FYI PATRICIA ist ein Akronym, das für "Praktischer Algorithmus zum Abrufen von in alphanumerischer Sprache codierten Informationen" steht). Die resultierenden Bäume können als Radix-Bäume mit verstanden werden. Dies radix = 2bedeutet, dass Sie den Baum durchlaufen, indem Sie jeweils nach log2(radix)=1Bits der Eingabezeichenfolge suchen .
Amelio Vazquez-Reina

Antworten:

118

Ein Radix-Baum ist eine komprimierte Version eines Versuchs. In einem Versuch schreiben Sie an jeder Kante einen einzelnen Buchstaben, während Sie in einem PATRICIA-Baum (oder Radix-Baum) ganze Wörter speichern.

Es sei nun angenommen , um die Worte hello, hatund have. Um sie in einem Trie zu speichern , würde es so aussehen:

    e - l - l - o
  /
h - a - t
      \
       v - e

Und du brauchst neun Knoten. Ich habe die Buchstaben in den Knoten platziert, aber tatsächlich beschriften sie die Kanten.

In einem Radix-Baum haben Sie:

            *
           /
        (ello)
         /
* - h - * -(a) - * - (t) - *
                 \
                 (ve)
                   \
                    *

und Sie brauchen nur fünf Knoten. Im Bild oben sind die Knoten die Sternchen.

Insgesamt benötigt ein Radix-Baum weniger Speicher , ist jedoch schwieriger zu implementieren. Ansonsten ist der Anwendungsfall von beiden ziemlich gleich.

Ivaylo Strandjev
quelle
Danke ... Können Sie mir eine gute Ressource zur Verfügung stellen, um Trie DS zu studieren ... Das wäre eine große Hilfe ...
Aryak Sengupta
Ich glaube, das einzige, was ich bei der ersten Implementierung von Trie verwendet habe, war der Wikipedia-Artikel . Ich sage nicht, dass es perfekt ist, aber es ist gut genug.
Ivaylo Strandjev
1
Kann ich sagen, dass die Suche in TRIE schneller ist als der Radix-Baum? Wenn Sie in TRIE das nächste Zeichen suchen möchten, müssen Sie den i-ten Index im untergeordneten Array des aktuellen Knotens sehen, aber im Radix-Baum müssen Sie nacheinander nach allen untergeordneten Knoten suchen. Siehe die Umsetzung code.google.com/p/radixtree/source/browse/trunk/RadixTree/src/...
Versuch ,
4
Tatsächlich können Sie in einem Radix-Baum nicht mehr als eine einzelne Kante haben, die mit demselben Buchstaben beginnt, sodass Sie dieselbe konstante Indizierung verwenden können.
Ivaylo Strandjev
1
@ Algorithmisch versuchen Radix ist schneller als TRIE, deshalb lohnt es sich, die Komprimierung durchzuführen. Weniger zu ladende Knoten und weniger Speicherplatz sind im Allgemeinen besser. Die Implementierungsqualität kann jedoch variieren.
Glenn Teitelbaum
68

Meine Frage ist, ob Trie- Datenstruktur und Radix Trie dasselbe sind.

Kurz gesagt, nein. Die Kategorie Radix Trie beschreibt eine bestimmte Kategorie von Trie , aber das bedeutet nicht, dass alle Versuche Radix-Versuche sind.

Wenn sie [nicht] gleich sind, was bedeutet dann Radix Trie (auch bekannt als Patricia Trie)?

Ich nehme an, Sie wollten schreiben, sind nicht in Ihrer Frage, daher meine Korrektur.

In ähnlicher Weise bezeichnet PATRICIA einen bestimmten Typ von Radix-Versuchen, aber nicht alle Radix-Versuche sind PATRICIA-Versuche.


Was ist ein Versuch?

"Trie" beschreibt eine Baumdatenstruktur, die zur Verwendung als assoziatives Array geeignet ist, wobei Zweige oder Kanten Teilen eines Schlüssels entsprechen. Die Definition von Teilen ist hier ziemlich vage, da unterschiedliche Implementierungen von Versuchen unterschiedliche Bitlängen verwenden, um Kanten zu entsprechen. Beispielsweise hat ein binärer Versuch zwei Kanten pro Knoten, die einer 0 oder einer 1 entsprechen, während ein 16-Wege-Versuch sechzehn Kanten pro Knoten hat, die vier Bits entsprechen (oder eine hexadezimale Ziffer: 0x0 bis 0xf).

Dieses aus Wikipedia abgerufene Diagramm scheint einen Versuch mit (mindestens) den eingefügten Schlüsseln 'A', 'bis', 'Tee', 'Ted', 'Zehn' und 'Gasthaus' darzustellen:

Grundversuch

Wenn dieser Versuch Elemente für die Schlüssel 't', 'te', 'i' oder 'in' speichern würde, müssten an jedem Knoten zusätzliche Informationen vorhanden sein, um zwischen Nullknoten und Knoten mit tatsächlichen Werten zu unterscheiden.


Was ist ein Radix Trie?

"Radix trie" scheint eine Form von trie zu beschreiben, die gemeinsame Präfixteile verdichtet, wie Ivaylo Strandjev in seiner Antwort beschrieben hat. Betrachten Sie einen 256-Wege-Versuch, der die Tasten "Lächeln", "Lächeln", "Lächeln" und "Lächeln" mit den folgenden statischen Zuweisungen indiziert:

root['s']['m']['i']['l']['e']['\0'] = smile_item;
root['s']['m']['i']['l']['e']['d']['\0'] = smiled_item;
root['s']['m']['i']['l']['e']['s']['\0'] = smiles_item;
root['s']['m']['i']['l']['i']['n']['g']['\0'] = smiling_item;

Jeder Index greift auf einen internen Knoten zu. Das heißt, um abzurufen smile_item, müssen Sie auf sieben Knoten zugreifen. Acht Knotenzugriffe entsprechen smiled_itemund smiles_itemund neun smiling_item. Für diese vier Elemente gibt es insgesamt vierzehn Knoten. Sie alle haben jedoch die ersten vier Bytes (entsprechend den ersten vier Knoten) gemeinsam. Durch die Verdichtung dieser vier Bytes zu einem rootentsprechenden Byte ['s']['m']['i']['l']wurden vier Knotenzugriffe optimiert. Das bedeutet weniger Speicher und weniger Knotenzugriffe, was ein sehr guter Hinweis ist. Die Optimierung kann rekursiv angewendet werden, um den Zugriff auf unnötige Suffixbytes zu reduzieren. Schließlich kommen Sie zu einem Punkt, an dem Sie nur die Unterschiede zwischen dem Suchschlüssel und den indizierten Schlüsseln an den vom Versuch indizierten Stellen vergleichen. Dies ist ein Radix-Versuch.

root = smil_dummy;
root['e'] = smile_item;
root['e']['d'] = smiled_item;
root['e']['s'] = smiles_item;
root['i'] = smiling_item;

Zum Abrufen von Elementen benötigt jeder Knoten eine Position. Mit einem Suchschlüssel von "Lächeln" und einem root.positionvon 4 greifen wir zu root["smiles"[4]], was zufällig ist root['e']. Wir speichern dies in einer Variablen namens current. current.positionist 5, was der Ort der Differenz zwischen "smiled"und ist "smiles", also wird der nächste Zugriff sein root["smiles"[5]]. Dies bringt uns zum smiles_itemEnde unserer Saite. Unsere Suche wurde beendet und der Artikel wurde mit nur drei statt acht Knotenzugriffen abgerufen.


Was ist ein PATRICIA-Versuch?

Ein PATRICIA-Versuch ist eine Variante von Radix-Versuchen, für die immer nur nKnoten verwendet werden sollten, die nElemente enthalten . In unserem primitiv demonstriert radix Trie Pseudocode oben, gibt es fünf Knoten in Summe: root(die eine nullary Knoten ist, es enthält keinen Ist - Wert), root['e'], root['e']['d'], root['e']['s']und root['i']. In einem PATRICIA-Versuch sollten es nur vier sein. Schauen wir uns an, wie sich diese Präfixe unterscheiden können, indem wir sie binär betrachten, da PATRICIA ein binärer Algorithmus ist.

smile:   0111 0011  0110 1101  0110 1001  0110 1100  0110 0101  0000 0000  0000 0000
smiled:  0111 0011  0110 1101  0110 1001  0110 1100  0110 0101  0110 0100  0000 0000
smiles:  0111 0011  0110 1101  0110 1001  0110 1100  0110 0101  0111 0011  0000 0000
smiling: 0111 0011  0110 1101  0110 1001  0110 1100  0110 1001  0110 1110  0110 0111 ...

Nehmen wir an, dass die Knoten in der oben angegebenen Reihenfolge hinzugefügt werden. smile_itemist die Wurzel dieses Baumes. Der Unterschied, der fett gedruckt ist, um das Erkennen etwas zu erleichtern, liegt im letzten Byte von "smile"Bit 36. Bis zu diesem Punkt haben alle unsere Knoten das gleiche Präfix. smiled_nodegehört zu smile_node[0]. Der Unterschied zwischen "smiled"und "smiles"tritt bei Bit 43 auf, wo "smiles"es ein '1'-Bit smiled_node[1]gibt smiles_node.

Anstatt mit NULLals Zweig und / oder zusätzliche interne Informationen zu bezeichnen , wenn eine Suche beendet, die Zweige zurück Link auf den Baum irgendwo, so dass eine Suche beendet , wenn der zu Test Offset verringert statt erhöht. Hier ist ein einfaches Diagramm eines solchen Baums (obwohl PATRICIA, wie Sie sehen werden, eher ein zyklischer Graph als ein Baum ist), das in Sedgewicks unten erwähntem Buch enthalten war:

Einfaches PATRICIA-Diagramm

Ein komplexerer PATRICIA-Algorithmus mit Schlüsseln unterschiedlicher Länge ist möglich, obwohl einige der technischen Eigenschaften von PATRICIA dabei verloren gehen (nämlich, dass jeder Knoten ein gemeinsames Präfix mit dem Knoten davor enthält):

Komplexes PATRICIA-Diagramm

Eine solche Verzweigung bietet eine Reihe von Vorteilen: Jeder Knoten enthält einen Wert. Das schließt die Wurzel ein. Infolgedessen wird die Länge und Komplexität des Codes viel kürzer und in der Realität wahrscheinlich etwas schneller. Mindestens ein Zweig und höchstens kZweige (wobei kdie Anzahl der Bits im Suchschlüssel angegeben ist) werden befolgt, um ein Element zu lokalisieren. Die Knoten sind winzig , da sie jeweils nur zwei Zweige speichern, was sie für die Optimierung der Cache-Lokalität ziemlich geeignet macht. Diese Eigenschaften machen PATRICIA zu meinem bisherigen Lieblingsalgorithmus ...

Ich werde diese Beschreibung hier kurz fassen, um die Schwere meiner bevorstehenden Arthritis zu verringern. Wenn Sie jedoch mehr über PATRICIA erfahren möchten, können Sie Bücher wie "Die Kunst der Computerprogrammierung, Band 3" von Donald Knuth konsultieren oder einer der "Algorithmen in {Ihrer Lieblingssprache}, Teile 1-4" von Sedgewick.

autistisch
quelle
Würden Sie mir bitte helfen, die Bedeutung des Begriffs "Radix" zu verstehen? Ich verstehe, wie wir auf natürliche Weise versuchen können, eine TRIE in eine kompakte TRIE zu verwandeln, indem wir mehrere Symbole / Kanten zu einer Kante verschmelzen lassen. Ich kann jedoch nicht erkennen, warum ein nicht komprimierter TRIE (einfach ein TRIE) nicht als Radix TRIE bezeichnet werden kann.
KGhatak
@ Seb - Würde mich sehr über Ihr Feedback zum Beitrag stackoverflow.com/questions/40087385/… auf Radix Tree freuen . Danke in adv.
KGhatak
@BuckCherry Ich würde gerne dazu in der Lage sein, aber bitte stellen Sie fest, dass ich, da mein Computer gestohlen wurde, nicht in der Lage sein würde, eine angemessene Antwort zu finden.
autistisch
18

TRIE:
Wir können ein Suchschema haben, bei dem wir nicht einen ganzen Suchschlüssel mit allen vorhandenen Schlüsseln vergleichen (z. B. ein Hash-Schema), sondern auch jedes Zeichen des Suchschlüssels vergleichen können. Nach dieser Idee können wir eine Struktur (wie unten gezeigt) erstellen, die drei vorhandene Schlüssel enthält - " Papa ", " Tupfen " und " Kabine ".

         [root]
     ...// | \\...
           |  \
           c   d
           |    \
          [*]    [*]
      ...//|\.  ./|\\...        Fig-I
        a       a
       /       /
     [*]      [*]
 ...//|\..  ../|\\...
    /        /   \
   B        b     d
  /        /       \
 []       []       []

(cab)   (dab)     (dad)

Dies ist im Wesentlichen ein M-ary-Baum mit einem internen Knoten, der als [*] dargestellt wird, und einem Blattknoten, der als [] dargestellt wird. Diese Struktur wird Trie genannt . Die Verzweigungsentscheidung an jedem Knoten kann gleich der Anzahl der eindeutigen Symbole des Alphabets gehalten werden, z. B. R. Für englische Kleinbuchstaben az ist R = 26; für erweiterte ASCII-Alphabete ist R = 256 und für binäre Ziffern / Zeichenfolgen R = 2.

Kompaktes TRIE:
Normalerweise verwendet ein Knoten in einem Trie ein Array mit der Größe = R und verursacht somit Speicherverschwendung, wenn jeder Knoten weniger Kanten hat. Um das Gedächtnisproblem zu umgehen, wurden verschiedene Vorschläge gemacht. Basierend auf diesen Variationen werden Trie auch als " Compact Trie " und " Compressed Trie " bezeichnet. Während eine konsistente Nomenklatur selten ist, wird eine häufigste Version eines kompakten Verses gebildet, indem alle Kanten gruppiert werden, wenn Knoten eine einzelne Kante haben. Unter Verwendung dieses Konzepts kann der obige Versuch (Fig. I) mit den Schlüsseln "Papa", "Tupfen" und "Kabine" die folgende Form annehmen.

         [root]
     ...// | \\...
           |  \
          cab  da
           |    \
          [ ]   [*]                Fig-II
               ./|\\...
                 |  \
                 b   d
                 |    \
                []    []

Beachten Sie, dass jedes von 'c', 'a' und 'b' die einzige Kante für den entsprechenden übergeordneten Knoten ist und daher zu einer einzigen Kante "cab" zusammengefasst ist. In ähnlicher Weise werden 'd' und a 'zu einer einzigen Kante zusammengeführt, die als "da" bezeichnet wird.

Radix Trie:
Der Begriff Radix bedeutet in der Mathematik eine Basis eines Zahlensystems und gibt im Wesentlichen die Anzahl der eindeutigen Symbole an, die zur Darstellung einer beliebigen Zahl in diesem System erforderlich sind. Zum Beispiel ist das Dezimalsystem Radix zehn und das Binärsystem ist Radix zwei. Wenn wir nach dem ähnlichen Konzept eine Datenstruktur oder einen Algorithmus anhand der Anzahl der eindeutigen Symbole des zugrunde liegenden Repräsentationssystems charakterisieren möchten, kennzeichnen wir das Konzept mit dem Begriff „Radix“. Zum Beispiel "Radix-Sortierung" für einen bestimmten Sortieralgorithmus. In der gleichen Logik werden alle Varianten von triederen Eigenschaften (wie Tiefe, Speicherbedarf, Laufzeit von Suchfehlern / Treffern usw.) vom Radix der zugrunde liegenden Alphabete abhängen, können wir als Radix „Tries“ bezeichnen. Zum Beispiel können wir einen nicht verdichteten sowie einen verdichteten Versuch, wenn Alphabete az verwendet werden, einen Radix 26- Versuch nennen . Jeder Versuch, der nur zwei Symbole verwendet (traditionell '0' und '1'), kann als Radix-2- Versuch bezeichnet werden . Irgendwie schränkten jedoch viele Literaturen die Verwendung des Begriffs „Radix Trie“ nur für den verdichteten Trie ein .

Vorspiel zu PATRICIA Tree / Trie:
Es wäre interessant festzustellen, dass sogar Zeichenfolgen als Schlüssel mit Binäralphabeten dargestellt werden können. Wenn wir ASCII - Kodierung annehmen, dann ist ein Schlüssel „dad“ kann durch das Schreiben der binären Darstellung jedes Zeichens in Folge, sagen als „in binärer Form geschrieben werden 01100100 01100001 01100100 “ durch das Schreiben binärer Form von ‚d‘, ‚a‘, und 'd' nacheinander. Mit diesem Konzept kann ein Trie (mit Radix Two) gebildet werden. Im Folgenden wird dieses Konzept anhand einer vereinfachten Annahme dargestellt, dass die Buchstaben 'a', 'b', 'c' und 'von' aus einem kleineren Alphabet anstelle von ASCII stammen.

Anmerkung zu Abb. III: Um die Darstellung zu vereinfachen, nehmen wir, wie erwähnt, ein Alphabet mit nur 4 Buchstaben {a, b, c, d} an. Die entsprechenden binären Darstellungen sind „00“, „01“, „10“ und "11". Damit werden unsere String-Tasten "dad", "tupfen" und "cab" zu "110011", "110001" bzw. "100001". Der Versuch hierfür ist wie unten in Fig. III gezeigt (Bits werden von links nach rechts gelesen, genau wie Strings von links nach rechts gelesen werden).

          [root]
             \1               
              \
              [*]
             0/ \1               
             /   \
           [*]   [*]         
           0/     /               
           /     /0
         [*]    [*]      
        0/      /               
        /      /0
      [*]    [*]
     0/     0/ \1                Fig-III
     /      /   \
    [*]   [*]   [*]
     \1     \1    \1
      \      \     \
      []     []    []
    (cab)   (dab) (dad)

PATRICIA Trie / Tree:
Wenn wir den obigen binären Trie (Abb. III) unter Verwendung einer Einzelkantenverdichtung komprimieren, hätte er viel weniger Knoten als oben gezeigt, und dennoch wären die Knoten immer noch größer als die 3, die Anzahl der darin enthaltenen Schlüssel . Donald R. Morrison fand (1968) einen innovativen Weg, um mithilfe von binären Versuchen N Schlüssel mit nur N Knoten darzustellen, und nannte diese Datenstruktur PATRICIA. Seine Trie-Struktur beseitigte im Wesentlichen einzelne Kanten (Einwegverzweigung); Dabei wurde auch die Vorstellung von zwei Arten von Knoten beseitigt - inneren Knoten (die keinen Schlüssel darstellen) und Blattknoten (die Schlüssel darstellen). Im Gegensatz zu der oben erläuterten Verdichtungslogik verwendet sein Versuch ein anderes Konzept, bei dem jeder Knoten eine Angabe darüber enthält, wie viele Bits eines Schlüssels für eine Verzweigungsentscheidung übersprungen werden sollen. Ein weiteres Merkmal seines PATRICIA-Versuchs ist, dass er die Schlüssel nicht speichert. Dies bedeutet, dass eine solche Datenstruktur nicht zur Beantwortung von Fragen geeignet ist, z. B. zum Auflisten aller Schlüssel, die einem bestimmten Präfix entsprechen , aber zum Auffinden, ob ein Schlüssel vorhanden ist oder nicht nicht in der trie. Nichtsdestotrotz wurde der Begriff Patricia Tree oder Patricia Trie seitdem in vielen verschiedenen, aber ähnlichen Sinnen verwendet, beispielsweise um einen kompakten Trie [NIST] oder einen Radix Trie mit Radix zwei [wie subtil angegeben] anzuzeigen Weg in WIKI] und so weiter.

Trie, die möglicherweise kein Radix-Trie ist:
Ternary Search Trie (auch bekannt als Ternary Search Tree), oft als TST abgekürzt, ist eine Datenstruktur (vorgeschlagen von J. Bentley und R. Sedgewick ), die einem Trie mit Drei-Wege-Verzweigung sehr ähnlich sieht. Für einen solchen Baum hat jeder Knoten ein charakteristisches Alphabet 'x', so dass die Verzweigungsentscheidung davon abhängt, ob ein Zeichen eines Schlüssels kleiner, gleich oder größer als 'x' ist. Aufgrund dieser festen 3-Wege-Verzweigungsfunktion bietet es eine speichereffiziente Alternative für Trie, insbesondere wenn R (Radix) sehr groß ist, z. B. für Unicode-Alphabete. Interessanterweise werden die Eigenschaften des TST im Gegensatz zum (R-Weg-) Versuch nicht von R beeinflusst. Beispielsweise ist der Suchfehler für TST ln (N).im Gegensatz zu log R (N) für R-way Trie. Der Speicherbedarf von TST, im Gegensatz zu R-Wege - Trie ist nicht eine Funktion von R als auch. Wir sollten also vorsichtig sein, einen TST als Radix-Trie zu bezeichnen. Ich persönlich denke nicht, dass wir es als Radix-Trie bezeichnen sollten, da (soweit ich weiß) keine seiner Eigenschaften durch die Radix R der zugrunde liegenden Alphabete beeinflusst wird.

KGhatak
quelle
2
Als jemand, der PATRICIA nach Morrison, Sedgewick und Knuth implementiert hat, kann ich Ihnen sagen, dass der hier beschriebene Algorithmus (den ich auch in meiner Antwort zu beschreiben versucht habe) immer noch sehr gut für die Beantwortung von Fragen geeignet ist, z. B. die Auflistung aller Schlüssel, die einem bestimmten Wert entsprechen Präfix . PS Schön, jemanden am Ball zu sehen: diese andere Frage :) Ich mag diese Erklärung.
autistisch
Re "ist nicht geeignet für die Beantwortung von Fragen wie" Alle Schlüssel auflisten, die einem bestimmten Präfix entsprechen ", ernsthaft?
Pacerier
@ Pacerier Sicher! Classic PATRICIA speichert eine Ganzzahl, die Sie als Index für ein Array verwenden können. In das Array setzen Sie den String. In den Versuch geben Sie den 0-basierten Array-Index für die Zeichenfolge ein. Lassen Sie die Such-, Vergleichs- und Bitextraktionsfunktionen mit der Zeichenfolge arbeiten, die der Ganzzahl und nicht der Ganzzahl entspricht, und ob Ihre Einfügefunktion auf den anderen basiert (wie es sein sollte, da es dort viele wiederholte Logik gibt) und Sie ' Ich bin auf dem besten Weg. Sie können auch uintptr_tals Ganzzahl verwenden , da dieser Typ normalerweise erwartet wird (obwohl er nicht erforderlich ist).
autistisch
Sie geben an, "viele Literaturen haben die Verwendung des Begriffs" Radix Trie "nur für den komprimierten Trie eingeschränkt." Eigentlich kann ich keine andere Referenz als Wikipedia finden. Hast du andere gefunden?
WDS
@ wds - Sie haben vielleicht Recht, da ich mich nicht wirklich daran erinnere, auf welche Ressourcen ich beim Schreiben verwiesen habe. Durch schnelles Googeln bekomme ich Links wie mathcs.emory.edu/~cheung/Courses/323/Syllabus/Text/trie02.html oder tutorialsdiary.com/radix-trie-patricia-trie-or-compressed-trie, die im Wesentlichen auf oder verweisen (höchstwahrscheinlich) abgeleitet von / beeinflusst von Wiki. Wenn ich eine andere zuverlässige / wissenschaftliche Ressource finde, werde ich hier posten.
KGhatak