DAWG, in depth: minimal word graphs, incremental construction from sorted input, perfect hashing and packed dictionaries

Right languages and the register

Define the right language of a node as the set of strings that lead from it to an accepting state. In a trie, two nodes with the same right language are redundant: anything you can do from one, you can do from the other. Merging all such nodes gives the minimal deterministic automaton for the set, and by the Myhill-Nerode theorem it is unique up to renaming of states. That uniqueness is what makes the two construction methods below checkable against each other.

Equality of right languages can be decided locally, bottom-up: two states are equivalent exactly when they agree on whether they are final and have the same outgoing labels leading to the same (already canonical) children. That gives a signature for each state, the tuple (final, sorted list of (label, child id)), and a hash table from signature to canonical state, usually called the register. If you know tries, you already know half of the structure; the register is the other half.

Method 1: build a trie, then minimise

The simple method builds the full trie, then walks it in post-order. Each node's children are canonicalised first, so the node's signature uses canonical child ids; the node is then looked up in the register and either replaced by the existing equivalent or registered as new. This is correct and easy, and it is how you should write the test oracle. Its weakness is memory: the peak is the size of the trie, which for a large dictionary can be ten or more times the final DAWG, as the numbers in the example section show.

Method 2: incremental construction from sorted input

Daciuk, Mihov, Watson and Watson (2000) showed how to avoid ever building the full trie. Feed the words in sorted order. When a new word arrives, compute its common prefix with the previous word. Every state on the previous word's path below that prefix can never gain another edge, because all later words are larger and branch off at or above the prefix. So those states are final in both senses: they can be minimised immediately, deepest first, and replaced by registered equivalents. Then the new word's suffix is appended as a fresh chain. Peak memory is the final DAWG plus one word's worth of unfinished states.

class State:
    __slots__ = ("final", "edges", "count")
    def __init__(self):
        self.final = False
        self.edges = {}            # label -> State
        self.count = 0             # words accepted from here (filled in later)
    def key(self):                 # signature: equal keys = equal right languages
        return (self.final,
                tuple((ch, id(t)) for ch, t in sorted(self.edges.items())))

class DawgBuilder:
    """Daciuk et al. (2000): minimal DAWG from words given in sorted order."""
    def __init__(self):
        self.root = State()
        self.register = {}         # signature -> canonical State
        self.prev = ""
        self.path = [self.root]    # states along the previous word

    def insert(self, word):
        if self.prev and word <= self.prev:
            raise ValueError("words must arrive in strictly increasing order")
        cp = 0                     # length of common prefix with previous word
        while cp < min(len(word), len(self.prev)) and word[cp] == self.prev[cp]:
            cp += 1
        self._minimize(cp)         # previous word's tail can never change again
        node = self.path[cp]
        for ch in word[cp:]:
            nxt = State()
            node.edges[ch] = nxt
            self.path.append(nxt)
            node = nxt
        node.final = True
        self.prev = word

    def _minimize(self, down_to):
        while len(self.path) - 1 > down_to:
            child = self.path.pop()
            parent = self.path[-1]
            ch = self.prev[len(self.path) - 1]
            k = child.key()
            if k in self.register:
                parent.edges[ch] = self.register[k]   # reuse equivalent state
            else:
                self.register[k] = child

    def finish(self):
        self._minimize(0)
        return self.root

Each word is processed in time proportional to its length times the cost of a signature hash, which is bounded by the alphabet size, so the whole build is linear in the total input length for a fixed alphabet. The same paper also gives a slower variant for unsorted input, which has to clone states that are shared but about to change; if you can sort, sort.

One subtle point: a state's signature includes its children's identities, so a state can only be registered after its children are canonical. Popping the path deepest first guarantees that. Another: a registered state must never be mutated afterwards, because its signature is a hash key. The sorted-order invariant is what guarantees that, which is why the builder rejects out-of-order input rather than quietly corrupting the register.

Worked example

Take six words: cat, cats, fact, facts, facet, facets. Sorted, they arrive as cat, cats, facet, facets, fact, facts. The trie has 13 nodes including the root. The DAWG has 8 states and 9 edges.

Walk through what gets merged. The states reached after cats, facets and facts are all final with no edges, so they collapse to one state (7). The states after cat, facet and fact are all final with a single s edge to that leaf, so they collapse too (6). The interesting merge is state 5: the node after ca and the node after face both have exactly one continuation, t, leading to state 6, so their right languages are both {t, ts}, and they become one state even though the prefixes that reach them have nothing in common. The node after fac has two edges (e and t) and stays distinct.

On a slightly more realistic set, every combination of five prefixes (re, un, pre, de and none), five stems (load, play, build, work, code) and six endings (none, s, ed, ing, er, ers), giving 150 words, the trie has 314 nodes while the DAWG has 26 states and 40 edges. Morphologically regular vocabularies compress extremely well, because every stem shares the same ending subgraph.

Perfect hashing with word counts

A plain DAWG can say whether a word is present but cannot attach data to it, because merged states are shared by many words. The fix is to store at each state the number of words accepted below it. Then a word's rank in sorted order is the sum, along its path, of the counts of all smaller sibling edges, plus one for every proper prefix that is itself a word. That rank is a minimal perfect hash: a bijection between the words and 0 to n - 1, so payloads live in a plain array indexed by rank. The inverse walk recovers the word from its rank.

def count_words(root):
    """Fill state.count = number of words accepted from that state (memoised)."""
    seen = set()
    def go(s):
        if id(s) not in seen:
            seen.add(id(s))
            s.count = int(s.final) + sum(go(t) for t in s.edges.values())
        return s.count
    return go(root)

def word_to_index(root, word):
    idx, s = 0, root
    for ch in word:
        if s.final:
            idx += 1                         # a shorter word sorts first
        for label, t in sorted(s.edges.items()):
            if label == ch:
                break
            idx += t.count                   # skip all words under smaller labels
        else:
            return None
        s = s.edges[ch]
    return idx if s.final else None

def index_to_word(root, idx):
    s, out = root, []
    while True:
        if s.final:
            if idx == 0:
                return "".join(out)
            idx -= 1
        for label, t in sorted(s.edges.items()):
            if idx < t.count:
                out.append(label)
                s = t
                break
            idx -= t.count
        else:
            return None                      # idx out of range

In the example, the ranks are cat 0, cats 1, facet 2, facets 3, fact 4, facts 5, and index 3 decodes back to facets. Counts are exact integers, so on large vocabularies use 32-bit or 64-bit fields. The listings were checked by building 400 random dictionaries both incrementally and by trie minimisation, asserting equal state counts, identical accepted languages and a perfect round trip of every rank.

Packing, byte labels and transducers

Python objects are fine for learning; production DAWGs are flat arrays. The usual layout stores each state's outgoing edges contiguously, each edge as a label, a flag for whether it is the last edge of its state, a flag for whether its target is final, and the target's offset. Children are often laid out right after the parent so the most common target needs no explicit pointer. With 4-byte edges, a dictionary of a few hundred thousand words typically fits in a few megabytes and can be memory-mapped straight from disk with zero parse time.

Labels can be bytes of UTF-8 rather than code points, which keeps the alphabet at 256 and makes sorted order byte order; just make sure the sort used during construction is the same byte order used during lookups, or the incremental builder will reject input or, with a buggy check, produce a non-minimal graph.

Attaching outputs to edges rather than states turns the DAWG into a finite-state transducer. Lucene's term dictionary uses this idea: outputs along a path combine into the term's value, and the construction is the same sorted-input minimisation with outputs pushed as close to the root as possible. For substring rather than whole-word queries, reach for suffix structures instead, such as suffix arrays.

Where DAWGs are used

• Spell checking and autocorrect: a depth-first walk with a bounded edit budget explores only paths that are valid prefixes, which prunes most of the search.
• Word games: Scrabble move generators have used DAWGs since Appel and Jacobson (1988), and the related GADDAG since 1994, because prefix validity checks dominate the search.
• Autocomplete: prefix walk, then enumerate below; add per-state maximum weights to stream the top completions first.
• Vocabularies and dictionaries: memory-mapped, read-only term lookups with a perfect hash to an id, useful for tokenizer vocabularies and inverted indexes.

Failure modes and trade-offs

Compared with alternatives: a hash set answers membership in O(1) but stores every word in full and cannot do prefix queries; a trie supports prefixes but repeats every suffix; a DAWG supports prefixes and shares suffixes but is read-only. For many dictionaries that last restriction is fine, because the word list changes in releases rather than per request. A deeper look at trie variants is in the trie deep dive.

What to do next

1. Type in the incremental builder and the trie-minimisation oracle; assert they agree on state counts for random word sets.
2. Reproduce the six-word example and confirm the ca and face merge by printing state ids.
3. Add counts, then round-trip every word through word_to_index and index_to_word.
4. Load a real word list (sorted as bytes), compare trie node count with DAWG state count, and measure the ratio.
5. Pack the result into a flat edge array and memory-map it; benchmark lookups against a hash set.
6. Read the suffix automaton article to see how the same minimisation idea applies to all substrings of one string.