“…einen habe ich noch!”
Otto Waalkes
Eine angenehme Seite des Programmieren ist, wenn es läuft, dann läuft es. Unter Software Entwicklern wird dieser Zustand gerne “The Flow” genannt. Es sind die wenigen wirklich produktiven Stunden des Sprints, die das Projekt voranbringen. Besonders schade, wenn sie von Vorgesetzten oder Ehefrauen unterbrochen werden. Kein Bug-Report oder Einkaufszettel kann so wichtig sein, dass dadurch dieser kreative Zustand gestört wird.
In den ersten drei Beiträgen dieser Reihe wurde das Thema Löschen aus einem Double Array Trie immer wieder umgangen. Eine kleine Sünde, die in diesem Beitrag nun endlich ihr Ende findet. Außerdem wird die Einsatzmöglichkeit des Trie erweitert, in dem eine Map Implementierung basierend auf dem Double Array Trie Algorithmus vorgestellt wird.
Das Löschen aus einem Trie
Das Löschen eines Wortes aus einem Double Array Trie scheint mit vielen Mühen behaftet zu sein. Aus diesem Grund blieb diese Funktionalität lange nicht umgesetzt. Ein Blick auf die Abbildung eines DAT zeigt jedoch, wie einfach die Implementierung wirklich ist.
Um aus dem obigen Double Array Trie das Wort jar zu löschen, muss nur das entsprechende letzte Element für diesen Eintrag in der Liste gefunden werden und dann der Verweis auf seine Basis gelöscht werden. Da in diesem Beispiel die Basis 1 ist, sind wir schon fertig mit dem Löschen.
Etwas komplizierter ist das Löschen des Wortes baby, da wir nicht direkt aus dem roten Basis Knoten löschen, sondern zuerst das blaue Element an Position 4 löschen. Beim Löschen aus einem anderen als den Basis-Knoten muss geprüft werden, ob er noch weitere Elemente enthält. In diesem Fall die Elemente an Position 5 und 6. Enthält er weitere Einträge, dann muss er nicht gelöscht werden und der Löschvorgang ist beendet. Enthält er keine weiteren Elemente, dann muss er aus seinem Vorgänger gelöscht werden. Dieser Prozess endet, wenn der Basis-Knoten erreicht wird.
Eine Map implementieren
Die Map Implementierung lebt von einem kleinen Trick bei der Implementierung des Double Array Trie. Die gemeinsamen Präfixe von Wörtern sind in den Knoten des Double Array Trie kodiert, der Rest eines Wortes ist als String gespeichert. In der Original-Implementierung gab es dafür eine eigene, als Tail bezeichnete Speicherstruktur, in dieser Implementierung existiert in den einzelnen Node Objekten ein Attribut tail.
Es vereinfacht zwar die Implementierung, verursacht aber einen unnötig großen Speicherverbrauch, da auch alle inneren Knoten dieses Attribut mit sich tragen. Eine Unterscheidung zwischen InnerNode und TailNode könnte in Zukunft für geringeren Speicherverbrauch sorgen.
Versehen wir nun jedes Node Objekt neben dem tail Attribut einem value Attribut, dann haben wir aus unserem Double Array Trie, das Grundgerüst für eine Double Array Map geschaffen.
Das Auslesen eines Wertes aus der Map ist nichts weiter, als das Finden des letzen Node des Schlüssels. Existiert so ein Node, dann steht in seinem value Attribute der zu diesem Schlüssel gespeicherte Wert. Eingefügt wird ein Wert, in dem der entsprechende Schlüssel eingefügt wird und in den letzten Node neben dem Suffix in tail auch der Wert in value gespeichert wird.
Interessante Methoden einer Map sind keySet, entrySet und values, die verschiedene Sichten auf die Daten in der Double Array Map liefern. Erstaunlich einfach sind keySet und entrySet zu implementieren. Das Ergebnis von keySet ist ein Set der Wörter in der internen Struktur der Map. Im vorherigen Beitrag wurden Tries als Set<String> implementiert. Die naheliegende Implementierung für die keySet Methode ist ein spezieller Trie, der die internen Strukturen der Double Array Map nutzt.
@Override
public Set<String> keySet() {
return Tries.unmodifiable(new KeySet<>(da, alphabet, size));
}
static class KeySet<V> extends AbstractDoubleArrayTrie<EntryNode<V>> {
KeySet(DoubleArray<EntryNode<V>> da, Alphabet alphabet, int size) {
super(da, alphabet, size);
}
}
Die Methode entrySet liefert ein Set zurück, das einen speziellen Iterator über den Trie aus dem keySet verwendet, um seine Einträge zu iterieren.
Für die Implementierung der Collection aus der values Methode existieren zwei Varianten. Die einfache Version läuft über die interne Liste der Map und liefert alle Werte aus Node Elementen, deren tail Attribute gesetzt ist. Die andere Version verwendet arbeitet ähnlich der entrySet Methode, aber liefert nur den Wert aus dem value Attribut.
Beispielhaftes mit der Double Array Map
Zur Demonstration der Möglichkeiten der Double Array Map liest der folgende Code die Wörter von Kafkas – Die Verwandlung ein und zählt ihre Häufigkeit.
final Alphabet alphabet = Alphabet.with().letters().letters("äöüßÄÖÜ-").build(GERMANY);
Map<String, AtomicInteger> map = new DoubleArrayMap<>(alphabet);
try (Scanner s = new Scanner(getClass().getResourceAsStream("/dieverwandlung.txt"))) {
while (s.hasNext()) {
final String word = s.next().replaceAll("[.,;:!?»«]", "");
if (word.matches("^[a-zA-ZaäöüßÄÖÜ-]+$")) {
map.computeIfAbsent(word, k -> new AtomicInteger()).getAndIncrement();
}
}
}
String result = map.entrySet().stream()
.sorted(reverseOrder(comparingInt(a -> a.getValue().get())))
.map(e -> e.getKey() + "=" + e.getValue())
.collect(joining(", "));
System.out.println(result);
Die Ausgabe beginnt mit den folgenden Einträgen.
die=585, und=585, er=405, der=403, zu=347, sich=311, in=297, nicht=259, sie=250, den=243, war=234, Gregor=218, mit=188, das=179, auf=175, es=172, dem=164, the=160, hatte=155, aber=136, ein=136, daß=133, als=122, auch=110, of=108, Schwester=107, an=104, nur=95, von=93, wie=93, --=92, ihn=91, Mutter=91, so=91, Vater=91, schon=89, um=88, im=87, des=81, noch=80, ihm=79, address=1, addresses=1, against=1, ...
Die folgende zwei Zeilen geben alle Wörter die mit da beginnen und ihre Häufigkeit aus.
String result = ((Trie) map.keySet()).stream("da")
.map(k -> k + "=" + map.get(k))
.collect(joining(", "));
System.out.println(result);
Die Ausgabe beginnt mit da=47 und endet mit dazwischen=2.
da=47, dabei=3, dachte=20, dachten=1, dadurch=7, dafür=2, dagegen=8, daher=4, dahin=1, dahintorkelte=1, dalag=1, damage=1, damaged=1, damages=2, damals=2, damit=7, dampfte=1, danach=1, dankbar=1, dankbaren=1, danke=1, danken=2, dankte=1, dann=47, dar=2, daran=20, daranzusetzen=1, darauf=9, daraus=2, darf=2, darin=1, darnach=2, darstellte=1, darum=2, darunter=1, darüber=12, das=179, dasaß=1, dastand=2, daß=133, data=1, date=2, dauern=1, dauerte=1, davon=6, davonzulaufen=1, days=4, dazu=5, dazwischen=2
Fazit
Obwohl die Double Array Map schon einsatzbereit ist, sind noch diverse Methoden einer Map nicht unterstützt und einige Methoden liefern bislang nicht veränderbare Instanzen zurück. Auch muss über den Speicherverbrauch der Trie und Map Implementierungen nachgedacht werden. Zwei ungenutzte Attribute an jedem internen Knoten ist pure Verschwendung.
Wer mehr über die Implementierung des Doube Array Trie und der Double Array Map erfahren möchte, die Sourcen sind wieder auf GitLab zu finden und eine erste Version liegt zum Download auf JFrog Bintray bereit.
Nachtrag
Im Zuge der Ankündigung von JFrog, ihr Repository JCenter zu schließen, ist die Bibliothek als Java 11 Binary nach Maven Central migriert.
<dependency> <groupId>de.schegge</groupId> <artifactId>double-array-trie</artifactId> <version>0.1.2</version> </dependency>