A minimal directed acyclic word graph (DAWG) recognizes a word set with the fewest possible states. Unlike a trie, it deduplicates suffixes as well as prefixes, producing a directed acyclic graph; it is also called a deterministic acyclic finite state automaton. section 5.4
The incremental construction depends on a useful invariant:
- Add words one at a time in alphabetical, character-by-character ordinal order. section 5.4
- After each addition, minimize every part except the nodes belonging to the newest word. section 5.4
- When the final word is added, minimize its remaining nodes to obtain the minimal graph. section 5.4
Why delayed minimization matters
With car, care, cares, and cars, equivalent states can temporarily remain in the newest word. After fir is added, a state for its suffix can be replaced by an existing equivalent state. The algorithm moves backward from the previous word’s end, fixing redundant states before continuing. section 5.4
