Deterministic acyclic finite state automaton

In computer science, a deterministic acyclic finite state automaton (DAFSA),[1] 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.

[1] Blumer et al[3] first defined terminology Directed Acyclic Word Graph (DAWG) in 1983.

Independent of earlier work, Daciuk et al[1] rediscovered the latter data structure in 2000 but called it DAFSA.

The primary difference between DAFSA and trie is the elimination of suffix and infix redundancy in storing strings.

For dictionary sets of common English words, this translates into major memory usage reduction.

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