Double Array Tries (Teil 2)

“Smart data structures and dumb code works a lot better than the other way around.”

Eric S. Raymond

In einem früheren Beitrag wurde die Datenstruktur Double Array Trie (DAT) vorgestellt. Zur schnellen Suche von Wörtern werden diese in einer linearisierten Baumstruktur gespeichert. Die einzelnen Knoten des Baumes werden dabei überlappend in die Liste eingefügt. Enthält ein Knoten Lücken, dann können diese durch Werte anderer Knoten aufgefüllt werden. In diesem Beitrag werden Einfügen und Auslesen der DAT Struktur erläutert.

Der DAT enthält traditionell eine Liste Base, in der die Basis der einzelnen Baumknoten definiert ist. In einer zweiten Liste Check werden die Positionen markiert, die zum einem Knoten gehören. Dazu wird an dieser Position der Index der Basis eingetragen. Durch den Abstand zwischen den Positionen von Base und Check Werten ergibt sich der codierte Buchstabe. Dabei muss noch der Offset subtrahiert werden, der im Base Eintrag steht. Üblicherweise ist der Wert 1 das Wortende Zeichen, 2 der Buchstabe A, 3 Der Buchstabe B usw.

Lesen aus einem DAT

Der nachfolgende DAT enthält die Wörter bachelor, badge und jar. Die korrespondierenden Werte aus Base und Check sind farbig markiert, Lücken enthalten weiße Nullen.

Um das Wort badge in diesem DAT zu finden, beginnt man mit dem ersten Base Eintrag an Position 1. Zu dessen Wert 1 wird der Code 3 für den Buchstaben b addiert. Der Wert 1 in der Check-Liste an Position 1+3=4 bedeutet, dass es einen Buchstaben b in diesem Knoten gibt. Ein anderer Wert bedeutet, dass dieser Eintrag nicht zum Knoten gehört und wir unser Wort nicht finden konnten.

Dann wird der Base Wert 1 an Position 4 mit dem Code 2 für den Buchstaben a addiert und der Check Wert an Position 1+2=3 geprüft. In diesem Feld steht eine 4, in diesem zweiten Knoten existiert also der Buchstabe a.

Der Wert von Base an Position 3 ist wieder eine 1. Wir addieren sie zum Code 5 für den Buchstaben d und gelangen so zum Check Wert 3 an der Position 1+5=6 . Also besitzt der dritte Knoten den Buchstaben d und wir können weitermachen.

An dieser Stelle ergibt sich eine Besonderheit. Da ab dieser Stelle nur noch ein einzelnes Wort gespeichert ist, wird hier der Suffix des Wortes gespeichert. Da der Suffix ge mit dem Rest des Suchwortes übereinstimmt, haben wir das Wort badge im DAT gefunden. Stimmen die Suffixe nicht überein, weil das Suchwort etwa badguy lautet, dann existiert das gesuchte Wort nicht im DAT.

In Java kann eine entsprechende contains Methode folgendermaßen definiert sein:

public boolean contains(String value) {
  String word = alphabet.checkEot(value);
  int s = 1;
  for (int i = 0; i < word.length(); i++) {
    int code = alphabet.code(word.charAt(i));
    int t = da.getBase(s) + code;
    if (da.getCheck(t) != s) {
      return false;
    }
    if (da.getTail(t) != null) {
      return da.getTail(t).equals(word.substring(i + 1));
    }
    s = t;
  }
  return false;
}

In der ersten Zeile wird, über die Hilfsklasse Alphabet geprüft, das Suchwort mit einem Ende-Marker präpariert ist. Im Original-Manuskript wurde dafür das Zeichen # verwendet. In dieser Implementierung wird das Unicode-Zeichen End-Of-Transmission (EOT) verwendet. Alle Wörter im DAT besitzen dieses EOT-Zeichen an ihrem Ende und können daher kein Präfix eines anderen Wortes im DAT sein.

Dann wird in einer Schleife, für jeden Buchstaben geprüft, ob es entsprechende Felder Base und Check gibt. Wenn die Werte nicht passen oder ein existierender Suffix nicht zum Rest des Suchwortes past, dann wird false zurückgegeben.

Interessant an diesem Algorithmus ist, dass er in O(n) den Trie nach einem Wort durchsucht. Wobei n die Länge des Wortes ist und nur Array Zugriffe benötigt werden. Eine sehr schnelle Art der Suche.

Einfügen in einen DAT

Das Einfügen von Wörtern in den Trie ist etwas mühseliger als die Suche. Da die Knoten der Baumstruktur überlappend in die Liste eingefügt werden, kann es durch neue Wörter zu Kollisionen kommen.

Beim Einfügen eines neuen Wortes sind deshalb 3 Fälle zu beachten.

1. Einfügen ohne Kollision
2. Einfügen mit einer Kollision im Suffix
3. Einfügen mit einer Kollision im Knoten

Einfügen ohne Kollisionen

Beim Einfügen ohne Kollision läuft der Algorithmus solange durch den Trie, bis er auf einen leeren Eintrag stößt. An dieser Stelle angekommen, kann der Check Wert auf den Index des letzten Base Wertes gesetzt und der Rest des Wortes als Suffix gespeichert werden.

Der einfachste Fall ist das Einfügen in den leeren Trie. Da nur ein Eintrag mit Base 1 existiert, kann ein neuer Eintrag an Position 4 für den Buchstaben b erstellt werden und der Suffix achelor gespeichert werden.

Ein weiterer Eintrag in den selben Knoten funktioniert genauso. Die Position für den Buchstaben j für das Wort jar ist noch frei. Also wird im Eintrag 12, der Wert Check auf 1 und der Suffix auf ar gesetzt.

Einfügen mit einer Kollision im Suffix

Fügt man in den obigen DAT als nächstes Wort badge ein, dann muss eine Kollision im Suffix behandelt werden.

Der Algorithmus findet im vierten Eintragen Suffix achelor, Dieser passt nicht zum Rest des aktuellen Wortes adge. Um das Problem zu lösen, wird für den gemeinsamen ersten Buchstaben der Suffixe ein Knoten angelegt. Dann werden für die verbliebenen Suffixe chelor und dge neue Einträge angelegt.

In diesem Beispiel haben die beiden Suffixe nur einen gemeinsamen Buchstaben. Es kann jedoch sein, dass dieser Schritt für eine größere Zahl von Buchstaben durchgeführt werden muss.

Einfügen mit einer Kollision innerhalb eines Knotens

Kompliziert wird es, wenn die Kollision innerhalb eines Knoten passiert. In unserem Beispiel wird das Wort baby eingefügt. Der zweite Buchstabe b (in blau) sollte an die Position 4 gesetzt werden. Hier steht aber schon der erste Buchstabe b (in rot).

Das Problem kann durch das Verschieben von einem der beiden Knoten passieren. Welcher von beiden bewegt wird, liegt an der Anzahl von Elementen in der jeweiligen Struktur. Beide Knoten enthalten zwei Einträge. Da aber der blaue Knoten einen neuen Eintrag hinzugefügt bekommt, gewinnt er und der rote Knoten wird verschoben.

Damit der rote Knoten mit seinen Einträgen verschoben werden kann, muss freier Platz gefunden werden. In der momentanen einfachen Implementierung, wird die Liste von vorne nach hinten nach passenden leeren Einträgen durchsucht. Optimierungspotenzial ist auf jeden Fall vorhanden.

Ist ein Platz gefunden, und spätestens am Ende der Liste ist welcher zu finden, dann werden die Einträge dorthin kopiert. Da sich die Position der Elemente ändert, muss dass Offset im ersten Eintrag von 1 auf 4 erhöht werden.

Da einige der verschobenen Einträge von nachfolgenden Einträgen adressiert werden, müssen deren Check-Werte angepasst werden. Im konkreten Fall, die grüne 4 durch eine 7 ersetzt werden.

Dann ist es schon fast geschafft. Ein kleines Detail hat diesen Beitrag jedoch lange an seiner Realisierung gehindert. Obwohl es scheinbar keinen großen Unterschied macht, welcher Knoten bei der Kollision verschoben wird, muss bei der Verschiebung der roten Knoten aufgepasst werden.

Der neue Eintrag wird dem berechneten Check-Wert in die Liste eingetragen. Beim Verschieben des blauen Knoten ist dieser immer eindeutig, da sich die restliche Trie-Struktur nicht ändert. Wird der rote Knoten verschoben, kann es in seltenen Fällen vorkommen, dass er der Vorgänger des blauen Knoten ist. Daher muss bei der Verschiebung ggf. der berechnete Check-Wert angepasst werden.

Ausblick

Obwohl die aktuelle Implementierung bis auf das Löschen funktional vollständig ist, muss sie noch den spröden Charme ihrer prozeduralen Ursprünge verlieren. Außerdem können noch einige Optimierungen und Erweiterungen eingebaut werden. Aber das wird Inhalt eines weiteren Beitrags werden.