Deterministischer azyklischer endlicher Automat
# Deterministischer azyklischer endlicher Automat

Ein deterministischer azyklischer endlicher Automat (DAEA; englisch deterministic acyclic finite state automaton (DAFSA) oder directed acyclic word graph, DAWG) ist in der theoretischen Informatik eine Datenstruktur, die eine Menge von Zeichenketten darstellt und eine Abfrageoperation ermöglicht, die prüft, ob eine gegebene Zeichenkette in einer Zeit, die proportional zu ihrer Länge ist, zu dieser Menge gehört. Es gibt Algorithmen, um solche Automaten zu konstruieren und zu verwalten, wobei diese minimal gehalten werden.

Ein DAEA ist ein Spezialfall eines endlichen Automaten, der die Form eines gerichteten azyklischen Graphen mit einem einzigen Quellknoten (einem Knoten ohne eingehende Kanten) hat, bei dem jede Kante des Graphen mit einem Buchstaben oder Symbol beschriftet ist und bei dem jeder Knoten höchstens eine ausgehende Kante für jeden möglichen Buchstaben oder jedes mögliche Symbol hat. Die durch die DAEA dargestellten Zeichenketten werden durch die Symbole auf den Pfaden im Graphen vom Quellknoten zu einem beliebigen Senkenknoten (ein Knoten ohne ausgehende Kanten) gebildet. Ein deterministischer endlicher Automat ist dann und nur dann azyklisch, wenn er eine endliche Menge von Zeichenketten erkennt.

## Vergleich mit Tries (Präfixbäumen)

Da dieselben Knotenpunkte über mehrere Pfade erreicht werden können, kann ein DAEA deutlich weniger Knotenpunkte verwenden als die stark verwandte Trie-Datenstruktur. Nehmen wir etwa die vier englischen Wörter "tap", "taps", "top" und "tops". Ein Trie für diese vier Wörter hätte 12 Kanten, einen für jede der Zeichenketten, die als Präfix eines dieser Wörter gebildet werden, oder für eines der Wörter, gefolgt von der Markierung des Zeichenkettenendes. Ein DAEA kann jedoch dieselben vier Wörter mit nur sechs Kanten $v_i$ für 0 ≤ i ≤ 5 und den folgenden Kanten darstellen: eine Kante von $v_0$ nach $v_1$ mit der Bezeichnung "t", zwei Kanten von $v_1$ nach $v_2$ mit den Bezeichnungen "a" und "o", eine Kante von $v_2$ nach $v_3$ mit der Bezeichnung "p", eine Kante von $v_3$ nach $v_4$ mit der Bezeichnung "s" und Kanten von $v_3$ und $v_4$ nach $v_5$ mit der Bezeichnung "End-of-word". Es besteht ein Kompromiss zwischen Speicherplatz und Funktionalität, denn ein Standard-DAEA kann zwar sagen, ob ein Wort darin vorkommt, aber er kann nicht auf Zusatzinformationen zu diesem Wort hinweisen, während ein Trie dies kann.

Der Hauptunterschied zwischen DAEA und Trie besteht in der Beseitigung der Suffix- und Infix-Redundanz bei der Speicherung von Zeichenketten. Der Trie eliminiert die Präfix-Redundanz, da alle gemeinsamen Präfixe zwischen den Zeichenketten einmalig gespeichert werden, wie zum Beispiel zwischen Doktor und Doktorat der Präfix Doktor nur einmal gespeichert wird. In einem DAEA werden auch gemeinsame Suffixe gemeinsam genutzt, und zwar für Wörter, die dieselbe Menge möglicher Suffixe haben wie die anderen. Bei Wörterbüchern mit üblichen deutschen oder englischen Wörtern führt dies zu einer erheblichen Verringerung der Speichernutzung.

Da die Endknoten eines DAEA über mehrere Pfade erreicht werden können, kann ein DAEA nicht direkt Hilfsinformationen zu den einzelnen Pfaden speichern, insbesondere die Häufigkeit eines Wortes in der deutschen Sprache. Wenn man jedoch für jeden Knoten die Anzahl der eindeutigen Pfade durch diesen Punkt in der Struktur speichert, kann man damit den Index eines Wortes oder eines Wortes mit seinem Index abrufen. Die Zusatzinformationen können dann in einem Array gespeichert werden.

## Anwendungen

* In Tesseract, einer freien Software zur Texterkennung, werden deterministische azyklische endliche Automaten in Form von Directed Acyclic Word Graphs (DAWG) verwendet, um Wortlisten effizient zu speichern.
