Es gibt mehrere Möglichkeiten, Tries darzustellen, die unterschiedlichen Kompromissen zwischen Speicherverbrauch und Geschwindigkeit der Operationen entsprechen. Die Grundform ist die einer verknüpften Menge von Knoten, wobei jeder Knoten ein Array von Kindzeigern enthält, einen für jedes Symbol im Alphabet (für das englische Alphabet würde man also 26 Kindzeiger speichern und für das Alphabet der Bytes 256 Zeiger). Dies ist einfach, aber speicherintensiv: Bei Verwendung des Byte-Alphabets (Größe 256) und Vier-Byte-Zeigern benötigt jeder Knoten ein Kilobyte Speicherplatz, und wenn sich die Präfixe der Zeichenketten nur wenig überschneiden, entspricht die Anzahl der benötigten Knoten ungefähr der Gesamtlänge der gespeicherten Zeichenketten.Anders ausgedrückt: Die Knoten am unteren Ende des Baums haben in der Regel nur wenige Kinder, und es gibt viele von ihnen, so dass die Struktur Platz für die Speicherung von Null-Zeigern verschwendet.
Das Speicherproblem kann durch eine Implementierungstechnik namens Alphabet-Reduktion gemildert werden, bei der die ursprünglichen Zeichenketten als längere Zeichenketten über ein kleineres Alphabet neu interpretiert werden. Beispielsweise kann eine Zeichenkette von n Bytes alternativ als eine Zeichenkette von 2n Vier-Bit-Einheiten betrachtet und in einem Trie mit sechzehn Zeigern pro Knoten gespeichert werden. Im schlimmsten Fall müssen doppelt so viele Knoten nachgeschlagen werden, aber der Speicherbedarf sinkt um den Faktor acht.:347-352
Eine alternative Implementierung stellt einen Knoten als Tripel (Symbol, Kind, nächstes) dar und verknüpft die Kinder eines Knotens als einfach verknüpfte Liste: Kind zeigt auf das erste Kind des Knotens, nächstes auf das nächste Kind des Elternknotens. Die Menge der Kinder kann auch als binärer Suchbaum dargestellt werden; ein Beispiel für diese Idee ist der von Bentley und Sedgewick entwickelte ternäre Suchbaum.353
Eine weitere Alternative, um die Verwendung eines Arrays von 256 Zeigern (ASCII) zu vermeiden, ist die Speicherung des Alphabet-Arrays als Bitmap von 256 Bits, die das ASCII-Alphabet repräsentieren, was die Größe der Knoten drastisch reduziert.
Bitweise VersucheBearbeiten
Bitweise Versuche entsprechen im Wesentlichen einem normalen zeichenbasierten Versuch, mit der Ausnahme, dass einzelne Bits verwendet werden, um eine Art Binärbaum zu durchlaufen. Im Allgemeinen verwenden Implementierungen einen speziellen CPU-Befehl, um sehr schnell das erste gesetzte Bit in einem Schlüssel fester Länge zu finden (z.B. GCCs __builtin_clz() intrinsic). Dieser Wert wird dann verwendet, um eine Tabelle mit 32 oder 64 Einträgen zu indizieren, die auf das erste Element im bitweisen Trie mit dieser Anzahl von führenden Nullbits verweist. Die Suche wird dann fortgesetzt, indem jedes nachfolgende Bit im Schlüssel getestet und child oder child entsprechend ausgewählt wird, bis das Element gefunden ist.
Auch wenn dieser Prozess langsam klingt, ist er sehr cache-lokal und aufgrund des Fehlens von Registerabhängigkeiten hochgradig parallelisierbar und hat daher tatsächlich eine ausgezeichnete Leistung auf modernen CPUs mit Out-of-Order-Ausführung. Ein rot-schwarzer Baum beispielsweise schneidet auf dem Papier viel besser ab, ist aber sehr cache-unfreundlich und verursacht auf modernen CPUs mehrere Pipeline- und TLB-Stalls, so dass dieser Algorithmus eher an die Speicherlatenz als an die CPU-Geschwindigkeit gebunden ist. Im Vergleich dazu greift ein bitweiser Trie nur selten auf den Speicher zu, und wenn, dann nur zum Lesen, wodurch der SMP-Cache-Kohärenz-Overhead vermieden wird. Daher wird er zunehmend zum bevorzugten Algorithmus für Code, der viele schnelle Einfügungen und Löschungen vornimmt, wie z. B. Speicherallokatoren (z. B. neuere Versionen des berühmten Allokators von Doug Lea (dlmalloc) und seiner Nachkommen). Der ungünstigste Fall von Schritten für die Suche ist derselbe wie die Bits, die für die Indizierung von Bins im Baum verwendet werden.
Alternativ kann sich der Begriff „bitweiser Trie“ allgemeiner auf eine binäre Baumstruktur beziehen, die ganzzahlige Werte enthält und diese nach ihrem binären Präfix sortiert. Ein Beispiel ist der x-fast trie.
Komprimieren von VersuchenBearbeiten
Das Komprimieren des trie und Zusammenführen der gemeinsamen Zweige kann manchmal große Leistungsgewinne bringen. Dies funktioniert am besten unter den folgenden Bedingungen:
- Der Trie ist (größtenteils) statisch, so dass keine Schlüsseleinfügungen oder -löschungen erforderlich sind (z. B. nach der Massenerstellung des Trie).
- Nur Lookups sind erforderlich.
- Die Trie-Knoten sind nicht durch knotenspezifische Daten verschlüsselt, oder die Daten der Knoten sind gemeinsam.
- Die Gesamtmenge der gespeicherten Schlüssel ist in ihrem Repräsentationsraum sehr spärlich (so dass sich die Kompression lohnt).
Sie kann z.B. verwendet werden, um spärliche Bitmengen zu repräsentieren, d.h. Teilmengen einer viel größeren, fest aufzählbaren Menge. In einem solchen Fall wird der Trie durch die Position des Bitelements innerhalb der vollständigen Menge verschlüsselt. Der Schlüssel wird aus der Bitfolge gebildet, die zur Codierung der ganzzahligen Position jedes Elements erforderlich ist. Solche Versuche haben eine sehr degenerierte Form mit vielen fehlenden Zweigen. Nach der Erkennung der Wiederholung gemeinsamer Muster oder dem Füllen der ungenutzten Lücken können die eindeutigen Blattknoten (Bit-Strings) leicht gespeichert und komprimiert werden, wodurch die Gesamtgröße des Trie reduziert wird.
Eine solche Komprimierung wird auch bei der Implementierung der verschiedenen schnellen Nachschlagetabellen zum Abrufen von Unicode-Zeicheneigenschaften verwendet. Dazu gehören Tabellen zur Groß- und Kleinschreibung (z.B. für den griechischen Buchstaben pi, von Π zu π) oder Nachschlagetabellen, die die Kombination von Basis- und Kombinationszeichen normalisieren (wie der a-Umlaut im Deutschen, ä, oder das dalet-patah-dagesh-ole im biblischen Hebräisch, דַּ֫). Für solche Anwendungen ist die Darstellung ähnlich wie die Umwandlung einer sehr großen, eindimensionalen, spärlichen Tabelle (z. B. Unicode-Codepunkte) in eine mehrdimensionale Matrix ihrer Kombinationen und die anschließende Verwendung der Koordinaten in der Hypermatrix als String-Schlüssel eines unkomprimierten Trie, um das resultierende Zeichen darzustellen. Die Komprimierung besteht dann darin, die gemeinsamen Spalten innerhalb der Hypermatrix zu erkennen und zusammenzuführen, um die letzte Dimension des Schlüssels zu komprimieren. Um beispielsweise zu vermeiden, dass für jedes Element, das eine Matrixspalte bildet, der vollständige, mehrere Bytes umfassende Unicode-Codepunkt gespeichert wird, können die Gruppierungen ähnlicher Codepunkte ausgenutzt werden. Jede Dimension der Hypermatrix speichert die Startposition der nächsten Dimension, so dass nur der Offset (in der Regel ein einzelnes Byte) gespeichert werden muss. Der sich ergebende Vektor ist selbst komprimierbar, wenn er ebenfalls spärlich ist, so dass jede Dimension (die einer Ebene im Trie zugeordnet ist) separat komprimiert werden kann.
Einige Implementierungen unterstützen eine solche Datenkompression innerhalb dynamischer Sparse-Tries und erlauben Einfügungen und Löschungen in komprimierten Tries. Dies ist jedoch in der Regel mit erheblichen Kosten verbunden, wenn komprimierte Segmente geteilt oder zusammengeführt werden müssen. Es muss ein Kompromiss zwischen Datenkompression und Aktualisierungsgeschwindigkeit gefunden werden. Eine typische Strategie besteht darin, den Bereich der globalen Suchvorgänge für den Vergleich der gemeinsamen Zweige im spärlichen Trie einzuschränken.
Das Ergebnis einer solchen Komprimierung kann ähnlich aussehen wie der Versuch, den Trie in einen gerichteten azyklischen Graphen (DAG) umzuwandeln, denn die umgekehrte Umwandlung von einem DAG in einen Trie ist offensichtlich und immer möglich. Die Form des DAG wird jedoch durch die Form des für die Indizierung der Knoten gewählten Schlüssels bestimmt, was wiederum die mögliche Komprimierung einschränkt.
Eine andere Komprimierungsstrategie besteht darin, die Datenstruktur in ein einziges Byte-Array zu „entwirren“, wodurch die Notwendigkeit von Knotenzeigern entfällt und der Speicherbedarf erheblich reduziert wird. Dies wiederum ermöglicht ein Memory Mapping und die Verwendung von virtuellem Speicher, um die Daten effizient von der Festplatte zu laden.
Ein weiterer Ansatz ist das „Packen“ des Trie. Liang beschreibt eine platzsparende Implementierung eines spärlichen gepackten Trie für die automatische Silbentrennung, bei der die Nachkommen jedes Knotens im Speicher verschachtelt werden können.
Externer SpeicherTrieEdit
Einige Trie-Varianten eignen sich für die Verwaltung von Zeichenketten im externen Speicher, einschließlich Suffixbäumen. Eine Kombination aus Trie und B-Tree, genannt B-Trie, wurde ebenfalls für diese Aufgabe vorgeschlagen; im Vergleich zu Suffixbäumen sind sie in den unterstützten Operationen eingeschränkt, aber auch kompakter, während sie Aktualisierungsoperationen schneller durchführen.