Double Array Tries

Seit Jahren schaue ich mir immer wieder mal den Artikel “An Efficient Implementation of Trie Structures” von Aoe, Morimot und Sato an. Es ist eines meiner Steckenpferde, obwohl ich selber keine eigene Implementierung in Java beendet oder jemals Tries in meinen Projekten verwendet habe.

Ein Trie ist ein Suchbaum, dessen Zweige Zeichen repräsentieren und jeder Weg von der Wurzel zu einem Blatt eine im Trie gespeicherte Zeichenkette darstellt. Der Name Trie  wurde von  Edward Fredkin vorgeschlagen, verkürzt aus Information Retrieval .

Der erste hier dargestellte Trie enthält die Wörter BABY, BACHELOR, BADGE und JAR.  Es ist schon eine optimierte Version, da die eindeutigen Suffixe der Wörter (Y, HELOR, GE und AR) nicht über Zweige repräsentiert sind.

Nachteilig bei dieser Repräsentation ist es, dass an jedem Knoten, die ausgehenden Zweige einzeln auf das aktuelle Zeichen geprüft werden müssen, bevor der Algorithmus zum korrekten Folgeknoten wechseln kann.

Angenehmer wäre es hier, wenn man über eine Tabelle und dem Indexwert für den Buchstaben zum Folgeknoten springen könnte.

Der zweite Trie verwendet in jedem Knoten eine solche Tabelle, in der für jeden Buchstaben ein Verweis auf den Folgeknoten steht. Wie man schon in diesem kleinen Beispiel sieht, enthalten die Tabellen viele leere Felder.

Aber auch in diesem Beispiel ist schon eine Optimierung enthalten, die Länge der Tabellen ist auf den Index des letzten genutzten Buchstaben reduziert. Diese Optimierung dient aber insbesondere dem Autoren dazu,  einfachere Abbildungen zu zeichnen. Aber schon das Hinzufügen des Wortes BUS würde viele weitere Leerfelder produzieren.

Der dritte abgebildete Trie, verwendet eine einzige Tabelle in der die Tabellen des zweiten Trie ineinander geschoben werden. Durch das Füllen von Lücken in den Tabellen reduziert sich der Speicherbedarfs dieses Tries. Das Befüllen eines solchen Tries ist aufwendiger, da es bei neuen Einträge zu Kollisionen kommen kann, weil ein Tabellenplatz schon von einem anderen Knoten verwendet wird. Dann müssen die Einträge eines Knoten verschoben werden.

Damit in diesem Trie eindeutig ist, zu welchem Knoten der jeweilige Eintrag gehört, besteht jeder Tabellenplatz  aus zwei Werten base und check. Der base Wert gibt für den entsprechenden Knoten an, an welcher Position in der Tabelle die eigenen Einträge beginnen. Enthält ein Eintrag in base den Wert 22, dann kann man in der Tabelle ab der Position 22 die Einträge zu einem Knoten finden. Die Tabellenposition 26 kann also einen Eintrag für den Buchstaben C enthalten. Ob an dieser Position aber tatsächlich der Buchstabe C codiert ist, kann erst über den Wert in check verifiziert werden. Steht hier die Tabellenposition 20 des base Wertes 22, dann gehört die Tabellenposition 26 zum Knoten und der Buchstabe C ist darin enthalten. Steht dort ein anderer Wert, dann gehört diese Tabellenposition zu einem anderen, bzw. zu keinem Knoten.

Der Name Double-Array Trie ergibt sich also aus der Erfordernis für jeden Tabelleneintrag zwei Werte zu speichern.  Wie man Werte in einen Double-Array Trie einfügt und wie man sie wieder herausbekommen kann, wird in einem weiteren Beitrag beschrieben.