A directed acyclic word graph (DAWG) stores a set of words by sharing both prefixes and suffixes. A trie shares prefixes; a DAWG also lets different paths point to the same equivalent node. The result is a graph with no cycles. DAWGs are also called deterministic acyclic finite state automata (DAFSAs). They are useful when a large word list must support membership checks and prefix searches without keeping every word as a separate string. section 5.4 section 5.0
Why share suffixes?
Consider car, care, cares, cars, fir, fire, firer, firers, and firs. Their trie already shares the beginning of each car or fir word. But several branches finish at separate, logically identical end-of-word leaves. Redirecting their incoming edges to one leaf preserves the words while removing redundant nodes. Sharing other equivalent suffix nodes extends that idea beyond leaves. section 5.2.4 section 5.4
One incremental construction algorithm takes words in ordinal, character-by-character sorted order:
- Find the new word’s common prefix with the previous word. section 5.4.1
- Work backward through the previous word’s remaining nodes, replacing redundant nodes with already optimized ones. Leave the newest word’s nodes unoptimized for now. section 5.4.1 section 5.4
- Add the new suffix as in a trie. After the last insertion, optimize that final word too. section 5.4.1 section 5.4
The payoff depends on representation as well as node count. For the 172,820-word ENABLE list, the DAWG has 54,167 nodes versus 387,881 for a trie—86% fewer. Yet a C# node containing a dictionary carries object overhead: this implementation uses less memory than a naïve list of strings, but more than a custom list backed by a single byte array. Like the trie, the word-graph search follows at most one edge per input character for a membership check. section 5.5 section 5.2.3
Table 5.1 Comparison of nodes by outgoing edge count
| Outgoing edges |
Trie nodes |
DAWG nodes |
|---|---|---|
| 0 |
111,507 |
1 |
| 1 |
214,096 |
25,921 |
| 2 |
39,181 |
12,840 |
| 3 |
13,525 |
6,755 |
| 4 |
4,490 |
3,618 |
| 5 |
1,994 |
1,944 |
| 6–26 |
3,088 |
3,088 |
| Total nodes |
387,881 |
54,167 |
| Total edges |
387,880 |
122,975 |
Compare outgoing-edge counts as well as totals: the trie has 111,507 separate leaf nodes, while the DAWG has one shared leaf. section 5.5
