Die Trie-Datenstruktur: Ein vernachlässigtes Juwel

Seit den ersten Tagen unseres Programmiererlebens beschäftigen wir uns alle mit Datenstrukturen: Arrays, verkettete Listen, Bäume, Sets, Stacks und Queues sind unsere alltäglichen Begleiter, und der erfahrene Programmierer weiß, wann und warum er sie zu verwenden hat. In diesem Artikel werden wir sehen, wie eine oft vernachlässigte Datenstruktur, die trie , in Anwendungsdomänen mit spezifischen Funktionen wie Wortspielen wirklich glänzt.

Wortspiele als Versuchsbeispiel

Betrachten wir für den Anfang ein einfaches Worträtsel: Finden Sie alle gültigen Wörter in einem 4x4-Buchstabenbrett, indem Sie benachbarte Buchstaben horizontal, vertikal oder diagonal verbinden. In der folgenden Tafel sehen wir zum Beispiel die Buchstaben „W“, „A“, „I“ und „T“, die sich zu dem Wort „WAIT“ verbinden.

Die naive Lösung, um alle gültigen Wörter zu finden, wäre, das Brett von der oberen linken Ecke aus zu erkunden und dann mit der Tiefe zuerst zu längeren Sequenzen zu gehen, wieder beginnend mit dem zweiten Buchstaben in der ersten Reihe, und so weiter. In einem 4x4-Brett, das vertikale, horizontale und diagonale Bewegungen zulässt, gibt es 12029640 Sequenzen mit einer Länge von einem bis sechzehn Zeichen.

Unser Ziel ist es nun, die beste Datenstruktur zu finden, um diesen Valid-Word-Checker zu implementieren, dh unser Vokabular. Ein paar Punkte, die Sie beachten sollten:

• Wir brauchen nur eine einzige Kopie jedes Wortes, dh unser Vokabular ist aus logischer Sicht ein Satz.
• Wir müssen die folgenden Fragen für jedes gegebene Wort beantworten:
  • Enthält die aktuelle Zeichenfolge ein gültiges Wort?
  • Gibt es längere Wörter, die mit dieser Sequenz beginnen? Wenn nicht, können wir unsere Tiefenerkundung aufgeben, da ein tieferes Vordringen keine gültigen Worte ergibt.

Um den zweiten Punkt zu veranschaulichen, betrachten Sie die folgende Tafel: Es hat keinen Sinn, nachfolgende Züge zu untersuchen, da es im Wörterbuch keine Wörter gibt, die mit „ASF“ beginnen.

Wir würden uns freuen, wenn unsere Datenstruktur diese Fragen so schnell wie möglich beantwortet. ~O(1) Zugriffszeit (zum Prüfen einer Sequenz) wäre ideal!

Wir können die Vocabulary-Schnittstelle wie folgt definieren (siehe hier für das GitHub-Repo):

 public interface Vocabulary { boolean add(String word); boolean isPrefix(String prefix); boolean contains(String word); }

Versuchen Sie Datenstruktur vs. Alternativen

Die Implementierung der Methode contains() erfordert eine unterstützende Datenstruktur, mit der Sie Elemente effizient finden können, während die Methode isPrefix() erfordert, dass wir das „nächst größere Element“ finden, dh wir müssen das Vokabular irgendwie sortiert halten.

Wir können Hash-basierte Sätze leicht aus unserer Kandidatenliste ausschließen: Während eine solche Struktur uns eine ständige Überprüfung auf contains() geben würde, würde sie bei isPrefix() ziemlich schlecht abschneiden und im schlimmsten Fall erfordern, dass wir das Ganze scannen einstellen.

Aus genau dem gegenteiligen Grund können wir auch sortierte verkettete Listen ausschließen, da sie erfordern, dass die Liste mindestens bis zum ersten Element gescannt wird, das größer oder gleich dem gesuchten Wort oder Präfix ist.

Zwei gültige Optionen verwenden eine sortierte Array-unterstützte Liste oder einen Binärbaum.
In der sortierten Array-unterstützten Liste können wir die binäre Suche verwenden, um die aktuelle Sequenz, falls vorhanden, oder das nächstgrößere Element zu einem Preis von O(log2(n)) zu finden, wobei n die Anzahl der Wörter im Wörterbuch ist.

Wir können ein Array-gestütztes Vokabular implementieren, das immer eine solche Reihenfolge beibehält, indem wir standardmäßig java.util.ArrayList und java.util.Collections.binarySeach verwenden:

 public class ListVocabulary implements Vocabulary { private List<String> words = new ArrayList<String>(); /** * Constructor that adds all the words and then sorts the underlying list */ public ListVocabulary(Collection<String> words) { this.words.addAll(words); Collections.sort(this.words); } public boolean add(String word) { int pos = Collections.binarySearch(words, word); // pos > 0 means the word is already in the list. Insert only // if it's not there yet if (pos < 0) { words.add(-(pos+1), word); return true; } return false; } public boolean isPrefix(String prefix) { int pos = Collections.binarySearch(words, prefix) ; if (pos >= 0) { // The prefix is a word. Check the following word, because we are looking // for words that are longer than the prefix if (pos +1 < words.size()) { String nextWord = words.get(pos+1); return nextWord.startsWith(prefix); } return false; } pos = -(pos+1); // The prefix is not a word. Check where it would be inserted and get the next word. // If it starts with prefix, return true. if (pos == words.size()) { return false; } String nextWord = words.get(pos); return nextWord.startsWith(prefix); } public boolean contains(String word) { int pos = Collections.binarySearch(words, word); return pos >= 0; } }

Wenn wir uns für die Verwendung eines Binärbaums entschieden haben, könnte die Implementierung noch kürzer und eleganter sein (hier ist wieder ein Link zum Code):

 public class TreeVocabulary extends TreeSet<String> implements Vocabulary { public TreeVocabulary(Collection<String> c) { super(c); } public boolean isPrefix(String prefix) { String nextWord = ceiling(prefix); if (nextWord == null) { return false; } if (nextWord.equals(prefix)) { Set<String> tail = tailSet(nextWord, false); if (tail.isEmpty()) { return false; } nextWord = tail.iterator().next(); } return nextWord.startsWith(prefix); } /** * There is a mismatch between the parameter types of vocabulary and TreeSet, so * force call to the upper-class method */ public boolean contains(String word) { return super.contains(word); } }

In beiden Fällen können wir für jede Zugriffsmethode ( contains() und isPrefix() ) eine Leistung von O(log n) erwarten. Hinsichtlich des Platzbedarfs erfordern sowohl die Array-unterstützte Implementierung als auch die Baum-unterstützte Implementierung O(n+M) , wobei n die Anzahl der Wörter im Wörterbuch und M die Bytegröße des Wörterbuchs ist, dh die Summe der Länge von die Zeichenfolgen im Wörterbuch.

Trie-Anwendungen: Wann und warum Tries verwenden

Logarithmische Leistung und linearer Speicher sind nicht schlecht. Aber es gibt noch ein paar weitere Merkmale unserer Anwendungsdomäne, die uns zu einer besseren Leistung führen können:

• Wir können davon ausgehen, dass alle Wörter klein geschrieben sind.
• Wir akzeptieren nur az-Buchstaben – keine Satzzeichen, keine Bindestriche, keine Akzente usw.
• Das Wörterbuch enthält viele gebeugte Formen: Plurale, konjugierte Verben, zusammengesetzte Wörter (zB Haus –> Haushälterin). Daher haben viele Wörter denselben Wortstamm .
• Wörter haben eine begrenzte Länge. Wenn wir zum Beispiel an einem 4x4-Board arbeiten, können alle Wörter, die länger als 16 Zeichen sind, verworfen werden.

Hier kommt der Trie (ausgesprochen „try“) ins Spiel. Aber was genau ist ein Trie? Versuche sind vernachlässigte Datenstrukturen, die in Büchern, aber selten in Standardbibliotheken zu finden sind.

Betrachten wir zur Motivation zunächst das Aushängeschild der Informatik: den Binärbaum. Wenn wir nun die Leistung eines Binärbaums analysieren und sagen, dass die Operation x O(log(n)) ist, sprechen wir ständig von logarithmischer Basis 2. Aber was wäre, wenn wir anstelle eines Binärbaums einen ternären Baum verwenden würden, wo Jeder Knoten hat drei Kinder (oder einen Fan-out von drei). Dann würden wir von Logbasis 3 sprechen. (Das ist eine Leistungsverbesserung, wenn auch nur um einen konstanten Faktor.) Im Wesentlichen würden unsere Bäume breiter, aber kürzer, und wir könnten weniger Suchen durchführen, da wir nicht ganz absteigen müssen so tief.

Gehen wir noch einen Schritt weiter: Was wäre, wenn wir einen Baum mit einer Auffächerung hätten, die gleich der Anzahl möglicher Werte unseres Datentyps ist?

Das ist die Motivation hinter dem Trie. Und wie Sie vielleicht erraten haben, ist ein Trie tatsächlich ein Baum, sozusagen ein Trie-Baum!

Aber im Gegensatz zu den meisten Binärbäumen, die Sie zum Sortieren von Zeichenfolgen verwenden würden, die ganze Wörter in ihren Knoten speichern würden, enthält jeder Knoten eines Tries ein einzelnes Zeichen (und nicht einmal das, wie wir gleich sehen werden) und hat eine maximale Auffächerung gleich der Länge des Alphabets. In unserem Fall beträgt die Länge des Alphabets 26; daher haben die Knoten des Tries eine maximale Auffächerung von 26. Und während ein ausgeglichener Binärbaum eine Log2(n) -Tiefe hat, ist die maximale Tiefe des Tries gleich der maximalen Länge eines Wortes! (Wieder breiter, aber kürzer.)

Innerhalb eines Tries teilen sich Wörter mit demselben Stamm (Präfix) den Speicherbereich, der dem Stamm entspricht.

Um den Unterschied zu veranschaulichen, betrachten wir ein kleines Wörterbuch aus fünf Wörtern. Nehmen Sie an, dass die griechischen Buchstaben Zeiger anzeigen, und beachten Sie, dass rote Zeichen im Trie Knoten anzeigen, die gültige Wörter enthalten.

Java Trie-Implementierung

Wie wir wissen, werden im Baum die Zeiger auf die untergeordneten Elemente normalerweise mit einer linken und einer rechten Variablen implementiert, da die maximale Auffächerung auf zwei festgelegt ist.

Bei einem Versuch, ein Alphabet mit 26 Buchstaben zu indizieren, hat jeder Knoten 26 mögliche Kinder und daher 26 mögliche Zeiger. Jeder Knoten weist somit ein Array von 26 (Zeigern auf) Teilbäumen auf, wobei jeder Wert entweder null (wenn es kein solches Kind gibt) oder ein anderer Knoten sein könnte.

Wie schlagen wir dann ein Wort in einem Versuch nach? Hier ist die Methode, die bei einem gegebenen String s den Knoten identifiziert, der dem letzten Buchstaben des Wortes entspricht, falls er im Baum vorhanden ist:

 public LowercaseTrieVocabulary getNode(String s) { LowercaseTrieVocabulary node = this; for (int i = 0; i < s.length(); i++) { int index = LOWERCASE.getIndex(s.charAt(i)); LowercaseTrieVocabulary child = node.children[index]; if (child == null) { // There is no such word return null; } node = child; } return node; }

Die LOWERCASE.getIndex(s.charAt(i)) gibt einfach die Position des i- ten Zeichens im Alphabet zurück. Auf dem zurückgegebenen node gibt ein boolescher Eigenschaftsknoten an, dass der Knoten dem letzten Buchstaben eines Wortes entspricht, dh einem im vorherigen Beispiel rot markierten Buchstaben. Da jeder Knoten einen Zähler für die Anzahl der Kinder führt, gibt es, wenn dieser Zähler positiv ist, längere Wörter im Wörterbuch, die die aktuelle Zeichenfolge als Präfix haben. Hinweis: Der Knoten muss nicht wirklich einen Verweis auf das Zeichen führen, dem er entspricht, da er in seiner Position im Trie implizit enthalten ist.

Leistung analysieren

Was die Trie-Struktur in diesen Situationen wirklich gut macht, ist, dass die Kosten für das Nachschlagen eines Wortes oder Präfixes festgelegt sind und nur von der Anzahl der Zeichen im Wort und nicht von der Größe des Vokabulars abhängen.

Da wir in unserem spezifischen Bereich Zeichenfolgen mit höchstens 16 Zeichen haben, sind genau 16 Schritte notwendig, um ein Wort zu finden, das im Vokabular enthalten ist, während jede negative Antwort, dh das Wort oder Präfix ist nicht im Trie, erhalten werden kann in höchstens 16 Schritten! In Anbetracht dessen, dass wir zuvor die Länge des Strings bei der Berechnung der Laufzeitkomplexität sowohl für die Array-unterstützte sortierte Liste als auch für den Baum ignoriert haben, der in den String-Vergleichen verborgen ist, können wir ihn hier auch ignorieren und sicher sagen, dass die Suche abgeschlossen ist in O(1) Zeit.

In Anbetracht des Platzbedarfs (und der Tatsache, dass wir mit M die Bytegröße des Wörterbuchs angegeben haben) könnte der Trie im schlimmsten Fall M Knoten haben, wenn keine zwei Zeichenfolgen ein Präfix gemeinsam haben. Da wir jedoch festgestellt haben, dass das Wörterbuch einen hohen Grad an Redundanz aufweist, muss viel komprimiert werden. Das im Beispielcode verwendete englische Wörterbuch ist 935.017 Byte groß und erfordert 250.264 Knoten mit einem Komprimierungsverhältnis von etwa 73 %.

Trotzdem benötigt selbst ein komprimierter Trie normalerweise mehr Speicher als ein Baum oder ein Array. Dies liegt daran, dass für jeden Knoten mindestens 26 x sizeof(pointer) Bytes erforderlich sind, plus etwas Overhead für das Objekt und zusätzliche Attribute. Auf einem 64-Bit-Rechner benötigt jeder Knoten mehr als 200 Bytes, wohingegen ein Zeichenfolgenzeichen ein einzelnes Byte erfordert oder zwei, wenn wir UTF-Zeichenfolgen betrachten.

Versuche und Leistungstests

Also, was ist mit der Leistung? Die Vokabularimplementierungen wurden in zwei verschiedenen Situationen getestet: Überprüfung auf 20.000.000 zufällige Zeichenfolgen und Auffinden aller Wörter in 15.000 Brettern, die zufällig aus derselben Wortliste generiert wurden.

Vier Datenstrukturen wurden analysiert: eine Array-gestützte sortierte Liste, ein Binärbaum, der oben beschriebene Trie und ein Trie, der Arrays von Bytes verwendet, die dem Alphabet-Index der Zeichen selbst entsprechen (eine geringfügige und einfach zu implementierende Leistungsoptimierung). Hier sind die Ergebnisse in ms:

Die durchschnittliche Anzahl an Zügen zur Lösung des Spielbretts beträgt 2.188. Für jeden Zug werden ein Wort-Lookup und ein Präfix-Lookup durchgeführt, dh zum Überprüfen aller Boards wurden mehr als 32 Millionen Wort-Lookups und 32 Millionen Präfix-Lookups durchgeführt. Hinweis: Diese könnten in einem einzigen Schritt durchgeführt werden, ich habe sie zur besseren Übersichtlichkeit in der Darstellung getrennt gehalten. Sie in einem einzigen Schritt zu komprimieren, würde die Zeit zum Lösen der Bretter fast halbieren und den Trie wahrscheinlich noch mehr begünstigen.

Wie oben zu sehen ist, funktioniert die Wortsuche mit dem Trie besser, selbst wenn Zeichenfolgen verwendet werden, und ist sogar noch schneller, wenn Alphabet-Indizes verwendet werden, wobei letztere mehr als doppelt so schnell wie ein Standard-Binärbaum sind. Der Unterschied beim Lösen der Bretter ist noch deutlicher, wobei die schnelle Trie-Alphabet-Index-Lösung mehr als viermal so schnell ist wie die Liste und der Baum.

Einpacken

Der Trie ist eine sehr spezialisierte Datenstruktur, die viel mehr Speicher benötigt als Bäume und Listen. Wenn jedoch bestimmte Domänenmerkmale zutreffen, wie ein begrenztes Alphabet und eine hohe Redundanz im ersten Teil der Zeichenfolgen, kann dies sehr effektiv bei der Leistungsoptimierung sein.

Verweise

Eine ausführliche Erläuterung von Tries und Alphabeten findet sich in Kapitel 5 von Robert Sedgewicks Buch „Algorithms, 4th edition“. Die begleitende Website in Princeton enthält den Code für eine Implementierung von Alphabet und TrieST, die umfangreicher ist als mein Beispiel.

Eine Beschreibung des Tries und Implementierungen für verschiedene Sprachen finden Sie auch auf Wikipedia und Sie können sich auch diese Trie-Ressource der Boston University ansehen.