Subtree Deduplication and the DAWG

A trie is a tree because it never shares a subtree between two parents. That is not a requirement of the data; it is an artifact of how the trie is built. Two nodes whose subtrees are structurally identical — same labels on the same edges, same terminal marks, recursively — describe the same set of key suffixes, and once the path that leads to them is forgotten, nothing distinguishes one from the other. Merging them into a single node yields a directed acyclic graph that accepts exactly the same key set with strictly fewer nodes. The construction is the same minimization that turns an acyclic deterministic automaton into its minimal form, and the minimal graph it produces is often called a DAWG, a directed acyclic word graph — a name the string-indexing literature also uses for a different, per-word structure.

When two nodes are equivalent

The equivalence is defined recursively. Two nodes are equivalent if both carry the same terminal mark and, for every label, either both lack a child on that label or their children on that label are equivalent. A leaf that is not terminal is equivalent to every other such leaf, so all dead ends collapse to one node. A leaf that is terminal is equivalent to every other terminal leaf.

The merging proceeds bottom-up, because the test for a node depends on the equivalence classes of its children. Process the deepest nodes first, assign each an identifier derived from its (terminal mark, sorted list of (label, child class)) pair, and merge nodes with equal identifiers. After one pass over the trie in decreasing depth order, every equivalence class has a single representative, and the result is minimal: no further merging is possible.

The identifier is exactly the input to a hash-consing table: hash the canonical description of the node, look it up, and reuse the existing node if the description is already present. The hash table’s key is the tuple of child classes, so the table’s size is the number of distinct nodes in the output, which is the quantity being minimized.

use std::collections::HashMap;

type NodeId = usize;

struct Builder {
    // canonical form -> node id
    table: HashMap<(bool, Vec<(u8, NodeId)>), NodeId>,
    nodes: Vec<(bool, Vec<(u8, NodeId)>)>,
}

impl Builder {
    fn intern(&mut self, terminal: bool, mut kids: Vec<(u8, NodeId)>) -> NodeId {
        kids.sort_unstable_by_key(|&(label, _)| label); // canonical order
        let key = (terminal, kids);
        if let Some(&id) = self.table.get(&key) {
            return id;                                   // reuse the class
        }
        let id = self.nodes.len();
        self.nodes.push(key.clone());
        self.table.insert(key, id);
        id
    }
}

Two details decide whether the output is minimal. The children must be put in a canonical order before hashing, or two nodes with the same subtree in different insertion order produce different keys and fail to merge. And the pass must be bottom-up, so that children have already been interned when their parent is processed; a top-down pass would hash child pointers that later change.

What deduplication buys, and on what inputs

The saving depends entirely on how much suffix structure the key set repeats, and the difference between the prefix-sharing and suffix-sharing regimes is large.

For a set of unrelated keys — random identifiers, for instance — suffixes are as diverse as prefixes, and there is almost nothing to merge. The DAWG is the trie, and the hashing pass costs time proportional to the node count while returning the same node count.

For a natural-language word list, suffixes repeat heavily: plural -s, past -ed, the -ing and -tion families, and the shared endings of related words. An unmerged trie over English inflected forms needs a node for every distinct prefix of every word; the minimal DAG merges every shared ending, so the reduction grows with how much morphology the word list encodes. The compression is not asymptotic in the way path compression is, since it does not remove a factor of key length for a single key, but it removes a multiplicative factor that no amount of edge compression touches, because it exploits repetition across different prefixes rather than along one.

The combination is what matters in practice. A Patricia-compressed trie removes unary chains, and a DAWG merge removes equivalent subtrees; applied together, the result is a minimal acyclic automaton whose edges may also be compressed. The two optimizations are independent — one looks at the shape of a path, the other at the identity of a subtree — and neither subsumes the other. The path-compression side is covered in path compression and the Patricia trie.

The catch: a DAG is not a tree

Every operation that assumed a node has one parent breaks.

Deletion by pruning is the clearest case. In a trie, removing a key clears a terminal mark and then frees ancestors that have become childless, and the upward walk is safe because each ancestor has exactly one parent. In a DAWG, the terminal node being cleared may be shared by hundreds of keys reached through different prefixes. Clearing the mark is still correct — it removes the key — but the node is not freeable just because the key was removed, and it is not freeable when it becomes childless either, since other paths may still pass through it. Reference counting per node, or a mark-and-sweep over reachable nodes, is required to reclaim anything.

Insertion is worse. Adding a key that shares a suffix with existing keys may require splitting a shared node: the new key needs a distinct continuation where the existing node has the old one, so the node must be cloned and one path redirected. This is the same split as in a Patricia trie, generalized to a DAG. Incremental construction of a minimal automaton handles it by keeping the unmerged trie for the portion of the key set not yet processed and merging only nodes that can no longer change — a suffix of the sorted key order. The technique is what makes minimal-automaton construction possible in a single streaming pass over lexicographically sorted keys, with memory proportional to the longest key rather than to the key set.

The ordering requirement is worth stating: keys must arrive in lexicographic order, because a node may be merged only once all keys that could extend it have been seen. Processing keys in arbitrary order forces either a full rebuild per insertion or a clone-on-write discipline that undermines the compression.

Why the structure is a minimal DFA

The equivalence being computed is the Myhill–Nerode equivalence of the finite language the trie accepts: two states are equivalent when they accept the same set of suffixes. Minimal deterministic automata are unique up to state renaming, and the bottom-up merge produces that unique automaton for the finite language. So the DAWG is not an approximation or a heuristic — it is the smallest deterministic automaton for the key set, and no other acyclic deterministic structure accepting the same keys can have fewer states.

That theoretical fact has a practical consequence: the node count is a property of the language, not of the insertion order or the implementation, and it gives a lower bound that explains why some key sets compress and others do not. A set of keys with no shared suffixes needs roughly the number of trie nodes it needs in tree form, one per distinct prefix, and no deterministic acyclic structure can do better while preserving those keys.

Determinism is the constraint doing the work. A nondeterministic automaton for the same language can be smaller, but it requires tracking a set of states during a match, which converts a lookup into a subset simulation and destroys the one-node-per-byte property that made the trie useful. The DAWG keeps the property and gives up mutability instead.

Where the compression is not worth it

The merge pass costs a hash of every node’s canonical description, and the table holds one entry per output node. For a key set with little suffix sharing, that is a large hash table built for no benefit, and the memory during construction can exceed the final structure. Construction is a batch operation, and the peak is a real constraint.

Lookup speed does not improve and can degrade slightly. The number of nodes on a path is unchanged — the path length is the key length, and merging does not shorten paths — so a lookup performs the same number of dependent loads. What improves is the working set: fewer nodes means a smaller footprint, so more of the structure stays in cache. That matters when the trie does not fit in cache; when either form fits, the merge changes nothing on the read path.

The structure also loses the one-to-one correspondence between nodes and prefixes, which several algorithms rely on. Counting keys with a given prefix, or enumerating them, requires knowing which paths reach a node, and a shared node is reached by many. Prefix queries in a DAWG are answered by walking from the root, which is fine, but any query phrased over the set of prefixes — rather than over paths from the root — needs the trie, or an auxiliary index. The ordered traversal machinery of lexicographic enumeration over a trie still works from the root, but a swept traversal that marks nodes as visited visits each shared node once and must therefore reconstruct the paths that lead to it separately.

The honest summary: deduplication is a space optimization for static key sets with heavy suffix repetition, bought with a construction pass, an immutable-or-append-only update model, and the loss of prefix-to-node correspondence. For a read-only dictionary or a morphological lexicon it is close to free. For a mutable index it is the wrong structure, and the adaptive layouts of adaptive radix tree node layouts are the right one.