Deterministic acyclic finite state automaton

In computer science, a deterministic acyclic finite state automaton (DAFSA), also called a directed acyclic word graph (DAWG; though that name also refers to a related data structure that functions as a suffix index) is a data structure that represents a set of strings, 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 such automata, while keeping them minimal.

A DAFSA is a special case of a finite state recognizer that takes the form of a directed acyclic graph with 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, a deterministic finite state automaton is acyclic if and only if it recognizes a finite set of strings.

By allowing the same vertices to be reached by multiple paths, a DAFSA may use significantly fewer vertices than the strongly related trie data structure. Consider, for example, the four English words "tap", "taps", "top", and "tops". A trie for those four words would have 11 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 vertices v_i for 0 ≤ i ≤ 5, and the following edges: an edge from v₀ to v₁ labeled "t", two edges from v₁ to v₂ labeled "a" and "o", an edge from v₂ to v₃ labeled "p", an edge v₃ to v₄ labeled "s", and edges from v₃ and v₄ to v₅ 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.

...
Wikipedia