Deterministischer azyklischer endlicher Automat
Ein deterministischer azyklischer endlicher Automat (DAEA; englisch deterministic acyclic finite state automaton (DAFSA)[1] 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,[1] 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.[1]
Vergleich mit Tries (Präfixbäumen) Bearbeiten
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 vi für 0 ≤ i ≤ 5 und den folgenden Kanten darstellen: eine Kante von v0 nach v1 mit der Bezeichnung "t", zwei Kanten von v1 nach v2 mit den Bezeichnungen "a" und "o", eine Kante von v2 nach v3 mit der Bezeichnung "p", eine Kante von v3 nach v4 mit der Bezeichnung "s" und Kanten von v3 und v4 nach v5 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.[2]
Anwendungen Bearbeiten
- 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.[3]
Literatur Bearbeiten
- A. Blumer, J. Blumer, D. Haussler, A. Ehrenfeucht, M. T. Chen, J. Seiferas: The smallest automaton recognizing the subwords of a text. In: Theoretical Computer Science. 40. Jahrgang, 1985, S. 31–55, doi:10.1016/0304-3975(85)90157-4 (englisch).
- Andrew Appel, Guy Jacobsen: The World's Fastest Scrabble Program. In: Communications of the ACM. 31. Jahrgang, Nr. 5, 1988, S. 572–578, doi:10.1145/42411.42420 (englisch, cmu.edu [PDF]). Einer der frühesten Erwähnungen dieser Datenstruktur.
- Cees J. A. Jansen, Dick E. Boekee: On the significance of the directed acyclic word graph in cryptology. In: Lecture Notes in Computer Science. Band 453. Springer-Verlag, 1990, ISBN 3-540-53000-2, S. 318–326, doi:10.1007/BFb0030372 (englisch).
- Chiara Epifanio, Filippo Mignosi, Jeffrey Shallit, Ilaria Venturini: Developments in language theory. Proceedings, 8th international conference (DLT 2004), Auckland, New Zealand. In: Lecture Notes in Computer Science. Band 3340. Springer-Verlag, Auckland, Neuseeland 2004, ISBN 3-540-24014-4, Sturmian graphs and a conjecture of Moser, S. 175–187.
- Tiago Tresoldi: DAFSA: a Python library for Deterministic Acyclic Finite State Automata. In: Journal of Open Source Software. 5. Jahrgang, Nr. 46, 2020, S. 1986, doi:10.21105/joss.01986 (englisch).
Siehe auch Bearbeiten
Weblinks Bearbeiten
- dafsa 1.0 . Eine Programmbibliothek geschrieben in der Programmiersprache Python für die Nutzung von deterministischen azyklischen endlichen Automaten
Einzelnachweise Bearbeiten
- ↑ a b c Jan Daciuk, Stoyan Mihov, Bruce Watson and Richard Watson (2000). Incremental construction of minimal acyclic finite state automata. Computational Linguistics 26(1):3-16.
- ↑ T. Kowaltowski, CL Lucchesi: Applications of finite automata representing large vocabularies. In: Software-Practice and Experience. 1993. Jahrgang, 1993, S. 15–30 (englisch).
- ↑ DAWG = Directed Acyclic Word Graphs. In: tesseract-ocr.repairfaq.org. 28. Februar 2007, abgerufen am 22. Februar 2023.