Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Compressed tries: split shared edge labels at the divergence

Last updated: 5 Oct 20269 min read
tutorial
IntermediateBy AITrove Editorial

A compressed trie stores a sequence of symbols on each edge instead of forcing one node per symbol. When two keys share only part of an existing edge, insertion splits that edge at their longest common prefix. A terminal marker still distinguishes a complete stored key from a route toward longer keys. The compressed form can cut node count when keys have long nonbranching runs, but it retains edge-label storage. This sample scans a node's child labels to find a shared prefix; lookup cost depends on key length and branching degree rather than being a strict constant per character without a more specialized child index.

Operational case

A parts index stores dock47, dock52, and doll61. The first two share dock; the third shares only do with them. Splitting at divergence leaves a shared do edge and two branches. A query for dock47 is an exact hit, while dock alone is only a path and must return false. This matters when user-entered part IDs can be valid prefixes of other IDs. Case normalization and Unicode rules must be fixed before insertion; otherwise two visually similar labels may take different compressed routes.

Working Python program

python
part_root = {}

def shared_length(first, second):
    length = 0
    while length < min(len(first), len(second)) and first[length] == second[length]:
        length += 1
    return length

def insert(part_code):
    current = part_root
    suffix = part_code
    while suffix:
        edge = next((label for label in current if label != "$end" and shared_length(label, suffix)), None)
        if edge is None:
            current[suffix] = {"$end": True}
            return
        width = shared_length(edge, suffix)
        if width < len(edge):
            old_child = current.pop(edge)
            current[edge[:width]] = {edge[width:]: old_child}
            edge = edge[:width]
        current = current[edge]
        suffix = suffix[width:]
    current["$end"] = True

def contains(part_code):
    current = part_root
    suffix = part_code
    while suffix:
        edge = next((label for label in current if label != "$end" and suffix.startswith(label)), None)
        if edge is None:
            return False
        suffix = suffix[len(edge):]
        current = current[edge]
    return "$end" in current

for part_code in ("dock47", "dock52", "doll61"):
    insert(part_code)
print(contains("dock47"), contains("dock"), contains("doll61"))
print(list(part_root))

Output

Output
True False True
['do']

Time, space, and tradeoff

For key length L, the sample may compare against several outgoing labels at each node. With a bounded alphabet and suitable child indexing, lookup follows O(L) symbols; this compact Python mapping does not guarantee that bound for arbitrary many-way labels. The total stored label characters are bounded by inserted key material, while node count can drop relative to a one-symbol-per-edge trie. Deletion must unmark a terminal and may merge a now-single-child path. This program shows insert and exact lookup only, not deletion or concurrent mutation.

Common Mistakes

  • Do not treat every traversable prefix as a complete stored key.
  • Do not split an edge without preserving its old child subtree.
  • Do not claim constant-time child selection for an unbounded linear label scan.

Connected lessons

Apply it: Project: own a maintenance index and work queue and Index and queue invariants.

Suffix arrays: indexed substring search and adjacent LCP handles a related query contract.

Front-coded lexicons: store shared prefixes within sorted term blocks adds a related indexing contract.

Level-order unary degree tries: encode child runs as bits adds a compact lookup contract.

Binary radix routing: choose the longest matching prefix adds a keyed lookup comparison.

Double-array tries: static incident-code transitions with BASE and CHECK examines a related structure with a different operation boundary.

Adaptive radix trees: grow byte-edge nodes as incident codes branch examines a related structure with a different operation boundary.

data structures
range-query-structures
Storage details