Minimal acyclic dictionaries: merge equivalent word suffix states

Last updated: 5 Oct 20269 min read

tutorial

A minimal acyclic deterministic word dictionary recognizes a fixed finite set of strings while sharing states with identical future accepted suffixes. Build a normal trie first. In postorder, assign each node a signature containing its terminal flag and sorted character-to-canonical-child transitions; intern nodes with equal signatures as one state. Terminal status is part of the signature because a complete word and a nonterminal prefix cannot be merged merely because their child edges match. The resulting directed acyclic graph may have several incoming paths to one state, and each distinct state represents one right-language of suffix continuations. Lookup follows one labeled transition per character and accepts only when the final state is terminal. The builder deduplicates input words and supports the empty string through a terminal root. It is static; adding a word would require rebuilding or a more involved incremental minimization algorithm.

Operational case

The dictionary contains dock47, rack47, dock83, and rack83. Both prefixes share the same two suffix choices, so equivalent suffix states merge even though the visible word prefixes differ. The sample has nine canonical states. Looking up rack47 succeeds, but rack alone fails because it reaches a nonterminal prefix state. A normal trie for these four strings retains separate suffix paths; the shared graph can reduce state count without changing accepted words. State numbers depend on postorder interning and are not durable IDs. Attaching a mutable payload directly to a shared state could mix values from different full words, so this model stores terminal membership only.

Working Python program

class MinimalIncidentDictionary:
    def __init__(self, words):
        trie = {"terminal": False, "edges": {}}
        for word in set(words):
            node = trie
            for character in word:
                node = node["edges"].setdefault(character, {"terminal": False, "edges": {}})
            node["terminal"] = True
        self.states = []
        registry = {}

        def intern(node):
            edges = tuple((character, intern(child))
                          for character, child in sorted(node["edges"].items()))
            signature = node["terminal"], edges
            if signature not in registry:
                registry[signature] = len(self.states)
                self.states.append((node["terminal"], dict(edges)))
            return registry[signature]

        self.root = intern(trie)

    def contains(self, word):
        state = self.root
        for character in word:
            state = self.states[state][1].get(character)
            if state is None:
                return False
        return self.states[state][0]


if __name__ == "__main__":
    dictionary = MinimalIncidentDictionary(["dock47", "rack47", "dock83", "rack83"])
    print(dictionary.contains("rack47"), dictionary.contains("rack"))
    print(len(dictionary.states), dictionary.root)

Output

True False
9 8

Time, space, and tradeoff

Let S be the total input character count and A the maximum outgoing alphabet size. Building the temporary trie uses O(S) nodes and expected O(S) dictionary updates. Sorting each node's outgoing labels and hashing its signature yields approximately O(S log A) work under ordinary Python dictionary assumptions, plus O(S) temporary and retained state storage in the worst case. Recursion depth follows the longest word and may exceed Python's recursion limit. Lookup costs O(L) expected dictionary transitions for a length-L word and O(1) auxiliary space. Sharing is workload-dependent: a dictionary with few repeated future suffix languages may save little. A compressed trie merges unary paths; this automaton merges equivalent future languages, which is a different reduction.

Common Mistakes

Do not omit terminal status from a state's canonical signature.
Do not attach per-word mutable payloads to a state reached by several words.
Do not treat a prefix path as an accepted word without its terminal flag.
Do not mutate the original word set while keeping this frozen automaton.

Connected lessons

Compare this operation boundary with Adaptive radix trees: grow byte-edge nodes as incident codes branch, Bit-sliced indexes: filter and sum fixed-width sensor readings, SimHash bands: find near-duplicate incident fingerprints, then complete the audit project and decision quiz.

data structures

trees-and-heaps