5 What’s up with you, Directed Acyclic Word Graph?

This chapter introduces the problem of storing and searching large word lists efficiently, especially for operations such as checking whether a word exists and finding all words with a given prefix. It compares simple approaches first: hash sets are excellent for exact lookup but poor for prefix search, while sorted lists support both operations reasonably well through binary search but still require extra work to enumerate matches and can consume significant memory when stored as ordinary strings.

The chapter then develops tries, or prefix trees, as a better fit for prefix-based searching. A trie stores shared prefixes only once, allowing word lookup and prefix navigation in time proportional to the length of the input string rather than the size of the word list. However, tries can still waste substantial memory because many nodes, especially leaf nodes and common suffix patterns, are duplicated. This motivates viewing tries as finite state automata, where nodes are states, edges are character transitions, and accepted strings are the stored words.

The final major idea is the Directed Acyclic Word Graph, which improves on a trie by deduplicating suffixes as well as prefixes. The chapter explains an incremental algorithm for building a minimal DAWG from a sorted word list: each new word is added while the previously added word’s unique suffix is optimized by replacing equivalent nodes with canonical ones. This preserves efficient search operations while greatly reducing node count in realistic word lists. The chapter concludes that DAWGs offer an elegant and practical balance of fast lookup, prefix search, and compact storage, especially when combined with low-level byte-array representations for memory-constrained systems.

The trie for a nine-word list, laid out here left to right, and in alphabetical order from top to bottom. Node numbers are not data in the tree; they are just so we can refer to them in the discussion which follows. Double-circle nodes represent ends of words.

The trie for the word list “car”

The trie for the word list “car”, “care”.

A trie with nine words: car, care, cares, cars, fir, fire, firer, firers, firs

Deduplicating all the leaves of the trie produces an equivalent word graph.

We’ve added car, care, cares and cars. The graph is optimized for everything except “cars”. Node 6 is identical to node 5, but node 6 is in “cars” so we have not fixed it yet.

After adding “fir” the graph is optimized for every word except “fir”. State 9 could be replaced with state 5, so this graph is not optimized for the final word.

Do you notice something odd about this graph after adding “fire”?

After adding “firer” and “firers”, the nodes for “firers” are still not optimized.

We look for optimizations moving backwards from the end of the previous word added, and first discover that node 12 is redundant; node 11 should have an edge to node 5 instead.

We’ve now fully optimized the “ers” portion of “firers” and we’re ready to add “firs”.

“firs” is added, and everything is optimized except for node 13, which is redundant to node 4.

This is the smallest possible DAWG that represents those nine words.

• Storing n words of average length m in a list such that we can generate all the words matching a particular prefix is a common problem. The number of words can be very large.
• Hash sets are great at determining if a given word is contained in a set, but not at all good at generating completions given a prefix.
• We can get O(m log n) search performance by using binary search on a sorted list, which is probably acceptable -- but this solution uses a surprisingly large amount of memory if we use off-the-shelf parts.
• We can get O(m) search performance by using a trie to deduplicate prefixes, but the number of redundant nodes is potentially enormous.
• By noticing that tries are a special case of finite state automata, we could use any one of many algorithms that minimize FSAs without changing the language they recognize. But starting with the huge, space-inefficient trie in memory and running an expensive, difficult minimization algorithm is not great; what we really want is to build an optimized DAWG one word at a time.
• Efficiently detecting when two nodes are redundant and can be safely merged is a key sub-problem in graph minimization; if we are careful about not mutating a node after it is in the canonical set of optimized nodes, we can do so very efficiently.
• We can make DAWGs very small in memory if we need to; this is exactly what game developers did back in the day.

FAQ