Deterministischer azyklischer endlicher Automat

Definition und Funktionsweise

Ein deterministischer azyklischer endlicher Automat (DAEA; englisch deterministic acyclic finite state automaton, DAFSA, oder directed acyclic word graph, DAWG) ist eine Datenstruktur der theoretischen Informatik. Er stellt eine Menge von Zeichenketten dar und kann prüfen, ob eine gegebene Zeichenkette zu dieser Menge gehört. Die benötigte Zeit ist proportional zur Länge der abgefragten Zeichenkette. Es gibt Algorithmen, mit denen sich solche Automaten konstruieren, verwalten und minimal halten lassen.

Ein DAEA ist ein spezieller endlicher Automat in Form eines gerichteten azyklischen Graphen. „Gerichtet“ bedeutet, dass die Kanten nur in einer festgelegten Richtung durchlaufen werden; „azyklisch“ bedeutet, dass der Graph keine gerichteten Kreise enthält. Er besitzt genau einen Quellknoten, also einen Knoten ohne eingehende Kanten. Jede Kante ist mit einem Buchstaben oder einem anderen Symbol beschriftet. Von jedem Knoten darf für jeden möglichen Buchstaben oder jedes mögliche Symbol höchstens eine ausgehende Kante existieren. Diese Eindeutigkeit macht den Automaten deterministisch.

Die dargestellten Zeichenketten entstehen aus den Symbolen auf den Pfaden vom Quellknoten zu einem Senkenknoten, also einem Knoten ohne ausgehende Kanten. Ein deterministischer endlicher Automat ist genau dann azyklisch, wenn er eine endliche Menge von Zeichenketten erkennt.

Unterschied zum Präfixbaum

Ein Trie oder Präfixbaum speichert gemeinsame Präfixe nur einmal. Ein Präfix ist ein gemeinsamer Wortanfang: Bei „Doktor“ und „Doktorat“ wird beispielsweise der Präfix „Doktor“ nur einmal gespeichert. Ein DAEA beseitigt darüber hinaus Suffix- und Infix-Redundanz. Ein Suffix ist ein gemeinsames Wortende; als Infix bezeichnet man einen gemeinsamen Teil innerhalb von Zeichenketten. In einem DAEA können Wörter gemeinsame Strukturen verwenden, wenn sie dieselbe Menge möglicher Suffixe besitzen.

Da derselbe Knoten über mehrere Pfade erreichbar sein kann, benötigt ein DAEA häufig deutlich weniger Knoten und Kanten als ein Trie. Bei Wörterbüchern mit üblichen deutschen oder englischen Wörtern kann dies die Speichernutzung erheblich verringern.

Dieser Speichergewinn bringt einen Kompromiss mit sich: Ein Standard-DAEA kann feststellen, ob ein Wort enthalten ist, aber nicht direkt auf Zusatzinformationen zu genau diesem Wort verweisen. Ein Trie kann solche Informationen speichern. Insbesondere lässt sich an gemeinsam erreichten Endknoten eines DAEA nicht unmittelbar die Häufigkeit eines einzelnen Wortes in der deutschen Sprache hinterlegen. Speichert man jedoch für jeden Knoten die Anzahl der eindeutigen Pfade durch diesen Punkt, kann man den Index eines Wortes bestimmen oder ein Wort anhand seines Index abrufen. Die eigentlichen Zusatzinformationen können dann in einem Array gespeichert werden.

Beispiel mit vier Wörtern

Die englischen Wörter „tap“, „taps“, „top“ und „tops“ zeigen die mögliche Platzersparnis. Ein Trie benötigt dafür 12 Kanten: je eine für die Zeichenketten, die Präfixe der Wörter sind, sowie für die Wörter mit nachfolgender Markierung des Zeichenkettenendes.

Ein DAEA stellt dieselben vier Wörter mit nur sechs Kanten und den Knoten v₀ bis v₅ dar. Von v₀ führt eine mit „t“ beschriftete Kante zu v₁. Von v₁ führen zwei Kanten mit den Beschriftungen „a“ und „o“ zu v₂. Danach führt „p“ von v₂ zu v₃ und „s“ von v₃ zu v₄. Schließlich führen von v₃ und v₄ Kanten mit der Beschriftung „End-of-word“ (EOW, Ende des Wortes) zu v₅. Durch die gemeinsame Nutzung der weiteren Pfade werden die vier Wörter kompakter als im Trie gespeichert.

Einsatz in der Texterkennung

Die freie Texterkennungssoftware Tesseract verwendet deterministische azyklische endliche Automaten in Form von Directed Acyclic Word Graphs (DAWG). Sie dienen dort dazu, Wortlisten effizient zu speichern.