Deterministic acyclic finite state automaton

The strings "tap", "taps", "top", and "tops" stored in atrie(left) and a DAFSA (right),EOWstands for End-of-word.

Incomputer science,adeterministic acyclic finite state automaton(DAFSA),^[1] also called adirected acyclic word graph(DAWG;though that name also refers to arelated data structurethat functions as a suffix index^[2]) is adata structurethat represents a set ofstrings,and allows for a query operation that tests whether a given string belongs to the set in time proportional to its length. Algorithms exist to construct and maintain suchautomata,^[1]while keeping themminimal.

A DAFSA is a special case of afinite state recognizerthat takes the form of adirected acyclic graphwith a single source vertex (a vertex with no incoming edges), in which each edge of the graph is labeled by a letter or symbol, and in which each vertex has at most one outgoing edge for each possible letter or symbol. The strings represented by the DAFSA are formed by the symbols on paths in the graph from the source vertex to any sink vertex (a vertex with no outgoing edges). In fact, adeterministic finite state automatonis acyclicif and only ifit recognizes afinite set of strings.^[1]

Comparison to tries[edit]

By allowing the same vertices to be reached by multiple paths, a DAFSA may use significantly fewer vertices than the strongly relatedtriedata structure. Consider, for example, the four English words "tap", "taps", "top", and "tops". A trie for those four words would have 12 vertices, one for each of the strings formed as a prefix of one of these words, or for one of the words followed by the end-of-string marker. However, a DAFSA can represent these same four words using only six verticesv_ifor 0 ≤i≤ 5, and the following edges: an edge fromv₀tov₁labeled "t", two edges fromv₁tov₂labeled "a" and "o", an edge fromv₂tov₃labeled "p", an edgev₃tov₄labeled "s", and edges fromv₃andv₄tov₅labeled with the end-of-string marker. There is a tradeoff between memory and functionality, because a standard DAFSA can tell you if a word exists within it, but it cannot point you to auxiliary information about that word, whereas a trie can.

The primary difference between DAFSA and trie is the elimination of suffix and infix redundancy in storing strings. The trie eliminates prefix redundancy since all common prefixes are shared between strings, such as betweendoctorsanddoctoratethedoctorprefix is shared. In a DAFSA common suffixes are also shared, for words that have the same set of possible suffixes as each other. For dictionary sets of common English words, this translates into major memory usage reduction.

Because the terminal nodes of a DAFSA can be reached by multiple paths, a DAFSA cannot directly store auxiliary information relating to each path, e.g. a word's frequency in the English language. However, if for each node we store the number of unique paths through that point in the structure, we can use it to retrieve the index of a word, or a word given its index.^[3]The auxiliary information can then be stored in an array.

References[edit]

^^a ^b ^cJan Daciuk, Stoyan Mihov, Bruce Watson and Richard Watson (2000). Incremental construction of minimal acyclic finite state automata. Computational Linguistics26(1):3-16.
^This article incorporatespublic domain materialfromPaul E. Black."directed acyclic word graph".Dictionary of Algorithms and Data Structures.NIST.
^Kowaltowski, T.; CL Lucchesi (1993). "Applications of finite automata representing large vocabularies".Software-Practice and Experience.1993:15–30.CiteSeerX10.1.1.56.5272.

Blumer, A.; Blumer, J.; Haussler, D.; Ehrenfeucht, A.; Chen, M.T.; Seiferas, J. (1985), "The smallest automaton recognizing the subwords of a text",Theoretical Computer Science,40:31–55,doi:10.1016/0304-3975(85)90157-4
Appel, Andrew; Jacobsen, Guy (1988),"The World's Fastest Scrabble Program"(PDF),Communications of the ACM,31(5): 572–578,doi:10.1145/42411.42420.One of the early mentions of the data structure.
Jansen, Cees J. A.; Boekee, Dick E. (1990), "On the significance of the directed acyclic word graph in cryptology",Advances in Cryptology – AUSCRYPT '90,Lecture Notes in Computer Science,vol. 453,Springer-Verlag,pp. 318–326,doi:10.1007/BFb0030372,ISBN 3-540-53000-2.
Epifanio, Chiara; Mignosi, Filippo; Shallit, Jeffrey; Venturini, Ilaria (2004), "Sturmian graphs and a conjecture of Moser", in Calude, Cristian S.; Calude, Elena; Dineen, Michael J. (eds.),Developments in language theory. Proceedings, 8th international conference (DLT 2004), Auckland, New Zealand, December 2004,Lecture Notes in Computer Science, vol. 3340,Springer-Verlag,pp. 175–187,ISBN 3-540-24014-4,Zbl 1117.68454
Tresoldi, Tiago (2020), "DAFSA: a Python library for Deterministic Acyclic Finite State Automata",Journal of Open Source Software,5(46): 1986,doi:10.21105/joss.01986,hdl:21.11116/0000-0005-AD0D-BAnopen source Pythonimplementation.

External links[edit]

"Directed Acyclic Word Graph or DAWG"– JohnPaul Adamovsky teaches how to construct a DAFSA using an array of integers (Archived22 July 2022 at theWayback Machine)
"Caroline Word Graph or CWG"– JohnPaul Adamovsky teaches how to construct a DAFSA hash function using a novel encoding with multiple integer arrays (Archived27 July 2022 at theWayback Machine)

[daciuk-1] Jan Daciuk, Stoyan Mihov, Bruce Watson and Richard Watson (2000). Incremental construction of minimal acyclic finite state automata. Computational Linguistics26(1):3-16.

[2] This article incorporatespublic domain materialfromPaul E. Black."directed acyclic word graph".Dictionary of Algorithms and Data Structures.NIST.

[kowaltowski1993-3] Kowaltowski, T.; CL Lucchesi (1993). "Applications of finite automata representing large vocabularies".Software-Practice and Experience.1993:15–30.CiteSeerX10.1.1.56.5272.

[1]

[2]

[3]

v t e Data structures
Types	Collection Container
Abstract	Associative array Multimap Retrieval Data Structure List Stack Queue Double-ended queue Priority queue Double-ended priority queue Set Multiset Disjoint-set
Arrays	Bit array Circular buffer Dynamic array Hash table Hashed array tree Sparse matrix
Linked	Association list Linked list Skip list Unrolled linked list XOR linked list
Trees	B-tree Binary search tree AA tree AVL tree Red–black tree Self-balancing tree Splay tree Heap Binary heap Binomial heap Fibonacci heap R-tree R* tree R+ tree Hilbert R-tree Trie Hash tree
Graphs	Binary decision diagram Directed acyclic graph Directed acyclic word graph
List of data structures

v t e Strings
String metric	Approximate string matching Bitap algorithm Damerau–Levenshtein distance Edit distance Gestalt pattern matching Hamming distance Jaro–Winkler distance Lee distance Levenshtein automaton Levenshtein distance Wagner–Fischer algorithm
String-searching algorithm	Apostolico–Giancarlo algorithm Boyer–Moore string-search algorithm Boyer–Moore–Horspool algorithm Knuth–Morris–Pratt algorithm Rabin–Karp algorithm Raita algorithm Trigram search Two-way string-matching algorithm Zhu–Takaoka string matching algorithm
Multiple string searching	Aho–Corasick Commentz-Walter algorithm
Regular expression	Comparison of regular-expression engines Regular grammar Thompson's construction Nondeterministic finite automaton
Sequence alignment	BLAST Hirschberg's algorithm Needleman–Wunsch algorithm Smith–Waterman algorithm
Data structure	DAFSA Suffix array Suffix automaton Suffix tree Generalized suffix tree Rope Ternary search tree Trie
Other	Parsing Pattern matching Compressed pattern matching Longest common subsequence Longest common substring Sequential pattern mining Sorting String rewriting systems String operations