In der Informatik ist ein trie oder Präfix-Baum, eine Datenstruktur des geordneten Baums, die verwendet wird, um eine assoziative Reihe zu versorgen, wo die Schlüssel gewöhnlich Schnuren sind. Verschieden von einem binären Suchbaum versorgt kein Knoten im Baum den mit diesem Knoten vereinigten Schlüssel; statt dessen definiert seine Position im Baum den Schlüssel, mit dem er vereinigt wird. Alle Nachkommen eines Knotens haben ein allgemeines Präfix der Schnur, die mit diesem Knoten vereinigt ist, und die Wurzel wird mit der leeren Schnur vereinigt. Werte werden normalerweise mit jedem Knoten, nur mit Blättern und einigen inneren Knoten nicht vereinigt, die Schlüsseln von Interesse entsprechen.

Der Begriff trie kommt aus der Wiederauffindung. Im Anschluss an die Etymologie spricht der Erfinder, Edward Fredkin, es "Baum" aus. Jedoch wird es "Versuch" von anderen Autoren ausgesprochen.

Im gezeigten Beispiel werden Schlüssel in den Knoten und Werten unter ihnen verzeichnet. Jedes ganze englische Wort hat einen willkürlichen damit vereinigten Wert der ganzen Zahl. Ein trie kann als ein deterministischer begrenzter Automat gesehen werden, obwohl das Symbol an jedem Rand häufig in der Ordnung der Zweige implizit ist.

Es ist für Schlüssel nicht notwendig, in Knoten ausführlich versorgt zu werden. (In der Zahl, wie man zeigt, illustrieren Wörter nur, wie der trie arbeitet.)

Obwohl es am üblichsten ist, brauchen Versuche nicht durch Charakter-Schnuren eingegeben zu werden. Dieselben Algorithmen können leicht angepasst werden, um ähnlichen Funktionen von geordneten Listen jeder Konstruktion, z.B, Versetzungen auf einer Liste von Ziffern oder Gestalten zu dienen. Insbesondere ein bitwise trie wird auf den individuellen Bit eingegeben, die eine kurze, feste Größe von Bit wie eine Zahl der ganzen Zahl oder Zeigestock zum Gedächtnis zusammensetzen.

Vorteile hinsichtlich anderer Suchalgorithmen

File:BitwiseTreesScaling.png|Behavior Fredkin-artiger Versuche als eine Funktion der Größe (in diesem Fall, nedtries, der eine Durchführung im Platz ist, und deshalb eine viel steilere Kurve hat als ein dynamisches Gedächtnis, hat trie Durchführung gestützt)

File:RedBlackTreesScaling.png|Behavior rot-schwarzer Bäume als eine Funktion der Größe (in diesem Fall, der BSD rbtree.h, der Klassiker O zeigt (loggen N) Verhalten)

File:HashTableScaling.png|Behavior Hash-Tabellen als eine Funktion der Größe (in diesem Fall, uthash, der wenn durchschnittlicher Show-Klassiker O (1) Verhalten)

</Galerie>

Verschieden von den meisten anderen Algorithmen haben Versuche die eigenartige Eigenschaft, dass der Codepfad, und folglich die erforderliche Zeit, fast für den Einsatz identisch ist, löschen Sie, und finden Sie Operationen. Infolgedessen für Situationen, wo Code einfügt, löschend und im gleichen Maß findend, können Versuche binäre Suchbäume handlich schlagen, sowie eine bessere Grundlage für die Instruktion der Zentraleinheit und geheime Zweiglager schaffen.

Der folgende ist die Hauptvorteile von Versuchen über binäre Suchbäume (BSTs):

• Das Aufblicken von Schlüsseln ist schneller. Wenn sie einen Schlüssel der Länge nachschlägt, nimmt M Grenzfall O (m) Zeit. Ein BST führt O (Klotz (n)) Vergleiche von Schlüsseln durch, wo n die Zahl der Elemente im Baum ist, weil lookups von der Tiefe des Baums abhängen, der in der Zahl von Schlüsseln logarithmisch ist, wenn der Baum erwogen wird. Folglich im Grenzfall nimmt ein BST O (M Klotz n) Zeit. Außerdem im Grenzfall-Klotz wird sich (n) M nähern. Außerdem ist der einfache Operationsversuch-Gebrauch während lookup, wie das Reihe-Indexieren mit einem Charakter, auf echten Maschinen schnell.
• Versuche sind raumeffizienter, wenn sie eine Vielzahl von kurzen Schlüsseln enthalten, da Knoten zwischen Schlüsseln mit allgemeinen anfänglichen Subfolgen geteilt werden.
• Versuche erleichtern das Zusammenbringen des längsten Präfixes.
• Die Zahl von inneren Knoten von der Wurzel bis Blatt kommt der Länge des Schlüssels gleich. Das Ausgleichen des Baums ist deshalb keiner Sorge.

Der folgende ist die Hauptvorteile von Versuchen über Hash-Tabellen:

• Versuch-Unterstützung hat Wiederholung bestellt, wohingegen die Wiederholung über eine Hash-Tabelle auf eine pseudozufällige durch die Kuddelmuddel-Funktion gegebene Ordnung hinauslaufen wird (und weiter betroffen durch die Ordnung von Kuddelmuddel-Kollisionen, die durch die Durchführung bestimmt wird).
• Versuche erleichtern das Zusammenbringen des längsten Präfixes, aber hashing tut nicht demzufolge des obengenannten. Das Durchführen solch ein "am nächsten passend" findet abhängig von der Durchführung, kann so schnell sein, wie ein genauer findet.
• Versuche neigen dazu, durchschnittlich an der Einfügung schneller zu sein, als Hash-Tabellen, weil Hash-Tabellen ihren Index wieder aufbauen müssen, wenn es voll - eine sehr teure Operation wird. Versuche haben deshalb Grenzfall-Zeitkosten viel besser begrenzt, der für mit der Latenz empfindliche Programme wichtig ist.
• Da keine Kuddelmuddel-Funktion verwendet wird, sind Versuche allgemein schneller als Hash-Tabellen für kleine Schlüssel.

Anwendungen

Als Ersatz anderer Datenstrukturen

Wie erwähnt, hat ein trie mehrere Vorteile gegenüber binären Suchbäumen. Ein trie kann auch verwendet werden, um eine Hash-Tabelle zu ersetzen, gegenüber der er die folgenden Vorteile hat:

• Das Aufblicken von Daten in einem trie ist im Grenzfall, O (m) Zeit im Vergleich zu einer unvollständigen Hash-Tabelle schneller. Eine unvollständige Hash-Tabelle kann Schlüsselkollisionen haben. Eine Schlüsselkollision ist die Kuddelmuddel-Funktion, die von verschiedenen Schlüsseln zu derselben Position in einer Hash-Tabelle kartografisch darstellt. Der Grenzfall lookup Geschwindigkeit bei einer unvollständigen Hash-Tabelle ist O (N) Zeit, aber ist viel mehr normalerweise O (1), mit O (m) Zeit hat das Auswerten des Kuddelmuddels ausgegeben.
• Es gibt keine Kollisionen von verschiedenen Schlüsseln in einem trie.
• Eimer in einem trie, die Hash-Tabelle-Eimern analog sind, die Schlüsselkollisionen versorgen, sind nur notwendig, wenn ein einzelner Schlüssel mit mehr als einem Wert vereinigt wird.
• Es gibt kein Bedürfnis, eine Kuddelmuddel-Funktion zur Verfügung zu stellen oder Kuddelmuddel-Funktionen zu ändern, weil mehr Schlüssel zu einem trie hinzugefügt werden.
• Ein trie kann eine alphabetische Einrichtung der Einträge durch den Schlüssel zur Verfügung stellen.

Versuche haben wirklich einige Nachteile ebenso:

• Versuche können in einigen Fällen langsamer sein als Hash-Tabellen, um Daten besonders nachzuschlagen, wenn auf die Daten auf einer Festplatte oder einem anderen sekundären Speichergerät direkt zugegriffen wird, wo die zufällige Zugriffszeit im Vergleich zum Hauptgedächtnis hoch ist.
• Einige Schlüssel, wie Schwimmpunkt-Zahlen, können zu langen Ketten und Präfixen führen, die nicht besonders bedeutungsvoll sind. Dennoch kann ein bitwise trie normalen IEEE einzelnes und doppeltes Format behandeln, das Punkt-Zahlen schwimmen lässt.

Wörterbuch-Darstellung

Eine allgemeine Anwendung eines trie versorgt ein Wörterbuch, solcher als ein gefundener auf einem Handy. Solche Anwendungen nutzen eine Fähigkeit eines trie aus, schnell zu suchen, Einträge einzufügen, und zu löschen; jedoch, wenn Speicherung von Wörterbuch-Wörtern alles ist, was erforderlich ist (d. h. die Lagerung der zu jedem Wort Hilfs-Information nicht erforderlich ist), würde ein minimaler acyclic deterministischer begrenzter Automat weniger Raum verwenden als ein trie. Das ist, weil ein acyclic deterministischer begrenzter Automat identische Zweige von den trie zusammenpressen kann, die denselben Nachsilben (oder Teile) verschiedener Wörter entsprechen, die versorgen werden.

Um

Versuche wird auch gut angepasst, ungefähre zusammenpassende Algorithmen, einschließlich derjenigen durchzuführen, die verwendet sind, indem sie Rechtschreibung prüfen und hyphenation Software.

Algorithmen

Wir können trie lookup (und Mitgliedschaft) leicht beschreiben. In Anbetracht eines rekursiven trie

Typ, einen fakultativen Wert an jedem Knoten und eine Liste von Kinderversuchen versorgend, die durch den folgenden Charakter, (hier mit einem Inhaltsverzeichnis versehen sind, vertreten als ein Datentyp von Haskell):

Daten Trie =

Trie {Wert:: Vielleicht ein

Kinder:: [(Rotforelle, Trie a)] }\

</Quelle>

Wir können einen Wert im trie wie folgt nachschlagen:

finden Sie:: Schnur-> Trie-> Vielleicht ein

finden Sie [] t = schätzen t

finden Sie (k:ks) t = Fall lookup k (Kinder t) von

Nichts-> Nichts

Gerade t'-> finden ks t'

</Quelle>

In einem befehlenden Stil und dem Annehmen eines passenden Datentyps im Platz können wir denselben Algorithmus in der Pythonschlange (hier spezifisch beschreiben, um Mitgliedschaft zu prüfen). Bemerken Sie, dass das Karte Kinder eines Knotens ist; und wir sagen, dass ein "End"-Knoten derjenige ist, der ein gültiges Wort enthält.

def finden (Knoten, Schlüssel):

für die Rotforelle im Schlüssel:

wenn Rotforelle nicht in node.children:

geben Sie Niemanden zurück

sonst:

Knoten = node.children [Rotforelle]

geben Sie node.value zurück

</Quelle>

Eine einfache Version von Ruby:

Klasse Trie

def initialisieren

@root = Hash.new

Ende

def bauen (str)

Knoten = @root

str.each_char tun |ch|

Knoten [ch] || = Hash.new

Knoten = Knoten [ch]

Ende

Knoten [: Ende] = wahrer

Ende

def finden (str)

Knoten = @root

str.each_char tun |ch|

geben Sie Null wenn Knoten = Knoten [ch] zurück

Ende

Knoten [: Ende] && wahrer

Ende

Ende

</Quelle>

Das Sortieren

Das lexikografische Sortieren von einer Reihe von Schlüsseln kann mit einem einfachen mit Sitz in trie Algorithmus wie folgt vollbracht werden:

• Fügen Sie alle Schlüssel in einen trie ein.
• Produktion alle Schlüssel im trie mittels des Vorordnungstraversals, das auf Produktion hinausläuft, die in der lexikografisch zunehmenden Ordnung ist. Vorordnungstraversal ist eine Art Tiefe das erste Traversal. Um Traversal eine andere Art der Tiefe das erste Traversal ist, das für outputting die Werte passender ist, die in einem binären Suchbaum aber nicht einem trie sind.

Dieser Algorithmus ist eine Form der Basis-Sorte.

Ein trie bildet die grundsätzliche Datenstruktur von Burstsort, zurzeit (2007) das schnellste bekannt, memory/cache-based, Schnur-Sortieren-Algorithmus.

Ein paralleler Algorithmus, um N auf Versuchen gestützte Schlüssel zu sortieren, ist O (1), wenn es N Verarbeiter gibt und die Längen der Schlüssel eine Konstante ober gebunden haben. Es gibt das Potenzial, das die Schlüssel kollidieren könnten, indem sie allgemeine Präfixe gehabt worden ist, oder indem sie zu einander identisch gewesen worden ist, reduzierend oder den Geschwindigkeitsvorteil beseitigend, vielfache Verarbeiter zu haben, die in der Parallele funktionieren.

Volle Textsuche

Eine spezielle Art von trie, genannt einen Nachsilbe-Baum, kann verwendet werden, um alle Nachsilben in einem Text mit einem Inhaltsverzeichnis zu versehen, um schnell volle Textsuchen auszuführen.

Versuche von Bitwise

Versuche von Bitwise sind ziemlich gleich, weil ein normaler Charakter trie gestützt hat, außer dass individuelle Bit verwendet werden, um zu überqueren, was effektiv eine Form des binären Baums wird. Allgemein verwenden Durchführungen eine spezielle Zentraleinheitsinstruktion an sehr schnell finden, dass der erste Satz in einem festen Länge-Schlüssel (z.B GCC __ builtin_clz inner) gebissen hat. Dieser Wert wird dann verwendet, um einen 32 oder 64 Zugang-Tisch mit einem Inhaltsverzeichnis zu versehen, der zum ersten Artikel im bitwise trie mit dieser Zahl von Hauptnullbit hinweist. Die Suche geht dann durch die Prüfung jedes nachfolgenden Bit im Schlüssel und die Auswahl des Kindes [0] oder Kindes [1] passend weiter, bis der Artikel gefunden wird.

Obwohl dieser Prozess langsam klingen könnte, ist es sehr mit dem geheimem Lager lokal und hoch parallelizable wegen des Mangels an Register-Abhängigkeiten und leistet deshalb tatsächlich ausgezeichnet auf dem modernen in Unordnung Ausführungszentraleinheiten. Ein rot-schwarzer Baum leistet zum Beispiel viel besser auf Papier, aber ist hoch mit dem geheimem Lager unfreundlich und verursacht vielfache Rohrleitung und TLB-Marktbuden auf modernen Zentraleinheiten, der diesen Algorithmus gebunden durch die Speicherlatenz aber nicht Zentraleinheitsgeschwindigkeit macht. Im Vergleich ein bitwise trie selten tut Zugriffsgedächtnis, und wenn es es tut, so, um nur zu lesen, so SMP Kohärenz des geheimen Lagers oben vermeidend, und wird folglich zunehmend der Algorithmus der Wahl für den Code, der viele Einfügungen und Auswischen wie Speicherverteiler (z.B neue Versionen des Zuteilers des berühmten Doug Leas (dlmalloc) und seiner Nachkommen) tut.

Eine Bezugsdurchführung von Bitwise-Versuchen in C und C ++ nützlich für die weitere Studie kann an http://www.nedprod.com/programs/portable/nedtries/. gefunden werden

Das Zusammendrücken von Versuchen

Wenn der trie, d. h. alle Einfügungen größtenteils statisch ist oder das Auswischen von Schlüsseln von einem vorgefüllten trie arbeitsunfähig ist und nur lookups erforderlich sind, und wenn die trie Knoten durch den Knoten spezifische Daten nicht eingegeben werden (oder wenn die Daten des Knotens üblich sind), ist es möglich, die trie Darstellung durch das Mischen der allgemeinen Zweige zusammenzupressen.

Diese Anwendung wird normalerweise verwendet, um Nachschlagetabellen zusammenzupressen, wenn der Gesamtsatz von versorgten Schlüsseln innerhalb ihres Darstellungsraums sehr spärlich ist.

Zum Beispiel kann es verwendet werden, um spärlichen bitsets zu vertreten (d. h. Teilmengen des viel festen enumerable größeren Satzes) das Verwenden eines trie, der durch die Bit-Element-Position innerhalb des vollen Satzes mit dem von der Schnur von Bit geschaffenen Schlüssel eingegeben ist, musste die integrierte Position jedes Elements verschlüsseln. Der trie wird dann eine sehr degenerierte Form mit vielen fehlenden Zweigen haben, und Kompression wird möglich durch die Speicherung der Blatt-Knoten (Satz-Segmente mit der festen Länge) und das Kombinieren von ihnen nach dem Ermitteln der Wiederholung von allgemeinen Mustern oder durch das Schließen der unbenutzten Lücken.

Solche Kompression wird auch normalerweise in der Durchführung der verschiedenen schnellen Nachschlagetabellen verwendet musste Charakter-Eigenschaften von Unicode wiederbekommen (zum Beispiel, um Fall-Tische des kartografisch darstellenden zu vertreten, oder Nachschlagetabellen, die die Kombination der Basis enthalten und Charaktere verbinden, mussten Normalisierung von Unicode unterstützen). Für solche Anwendung ist die Darstellung dem Umwandeln eines sehr großen unidimensional spärlichen Tisches in eine mehrdimensionale Matrix und dann des Verwendens der Koordinaten in der Hypermatrix als der Schnur-Schlüssel eines unkomprimierten trie ähnlich. Die Kompression wird dann aus dem Ermitteln und Mischen der allgemeinen Säulen innerhalb der Hypermatrix bestehen, um die letzte Dimension im Schlüssel zusammenzupressen; jede Dimension der Hypermatrix versorgt die Anfang-Position innerhalb eines Lagerungsvektoren der folgenden Dimension für jeden Koordinatenwert, und der resultierende Vektor ist selbst komprimierbar, wenn es auch spärlich ist, so wird jede Dimension (vereinigt zu einem Schicht-Niveau im trie) getrennt zusammengepresst.

Einige Durchführungen unterstützen wirklich solche Datenkompression innerhalb von dynamischen spärlichen Versuchen und erlauben Einfügungen und Auswischen in komprimierten Versuchen, aber allgemein hat das bedeutende Kosten, wenn komprimierte Segmente gespalten oder verschmolzen werden müssen, und etwas Umtausch zwischen der kleinsten Größe des komprimierten trie und der Geschwindigkeit von Aktualisierungen, durch das Begrenzen der Reihe von globalem lookups gemacht werden muss, für die allgemeinen Zweige im spärlichen trie zu vergleichen.

Das Ergebnis solcher Kompression kann ähnlich dem Versuchen aussehen, den trie in einen geleiteten acyclic Graphen (DAG) umzugestalten, weil sich die Rückseite von einem DAG bis einen trie verwandelt, ist offensichtlich und immer möglich, jedoch wird es durch die Form des Schlüssels beschränkt, der gewählt ist, um die Knoten mit einem Inhaltsverzeichnis zu versehen.

Eine andere Kompressionsannäherung soll die Datenstruktur in eine einzelne Byte-Reihe "ausfasern".

Diese Annäherung beseitigt das Bedürfnis nach Knotenzeigestöcken, das die Speichervoraussetzungen wesentlich reduziert und Gedächtnis macht, das möglich kartografisch darstellt, der dem virtuellen Speicherbetriebsleiter erlaubt, die Daten ins Gedächtnis sehr effizient zu laden.

Eine andere Kompressionsannäherung soll den trie "einpacken". Liang beschreibt eine raumeffiziente Durchführung eines spärlichen gepackten trie, der auf hyphenation angewandt ist, in dem die Nachkommen jedes Knotens im Gedächtnis durchgeschossen werden können.

Siehe auch

• Basis-Baum
• Geleiteter acyclic Wortgraph (auch bekannt als DAWG)
• Dreifältige Suche versucht
• Acyclic deterministische begrenzte Automaten
• Kuddelmuddel trie
• Deterministische begrenzte Automaten
• Reihe von Judy
• Suchen Sie Algorithmus
• Ausdehnbarer hashing
• Kuddelmuddel-Reihe hat trie kartografisch dargestellt
• Präfix-Kuddelmuddel-Baum
• Burstsort
• Algorithmus von Luleå
• Huffman, der codiert
• Ctrie

Außenverbindungen

• Das Wörterbuch von NIST von Algorithmen und Datenstrukturen: Trie
• Durchführung von Trie und Visualisierung im Blitz
• Versuche durch Lloyd Allison
• Das Verwenden von Versuchen Topcoder Tutorenkurs
• Eine Durchführung der Doppelten Reihe Trie
• de la Briandais Tree
• Das Besprechen einer trie Durchführung im Lispeln
• ServerKit "Syntaxanalyse-Bäume" führen eine Form von Trie in C durch
• Eine einfache Durchführung von Trie in der Pythonschlange
• Ein Trie, der in Ruby durchgeführt ist
• Eine Bezugsdurchführung von bitwise versucht in C und C ++
• Eine Bezugsdurchführung in Java
• Ein schneller Tutorenkurs auf TRIE in Java und C ++
• Eine C Kompaktdurchführung von Judy Tries
• Daten:: Trie und Tree:: Durchführungen von Trie Perl.