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

Python compressed trie: merge single-child paths without losing terminal words

Last updated: 30 Sept 20264 min read
tutorial
IntermediateBy AITrove Editorial

A compressed trie stores a string label on each merged edge instead of retaining one node for every character of a single-child path.

Download Python source kit

Operation contract

The fixture first builds a bounded ASCII-word trie, then compresses paths only while the intermediate node is nonterminal and has exactly one child. A terminal prefix remains a node so a short accepted word can coexist with a longer word. Exact lookup consumes an entire edge label before moving to its child; ending midway through an edge is not an accepted word.

Failure and ownership boundary

Compression changes representation rather than changing accepted words. Insertion or deletion into the compressed structure needs edge splitting/merging policies not implemented here. The uncompressed construction still uses its original prefix memory before the compressed result is produced. Python trie: exact words, prefixes and node allocation and Python trie deletion: remove one word without losing its prefix neighbors describe the mutable version.

Working program

python
import re

def compressed_routes(words):
    if len(words) > 128 or any(not isinstance(word, str) or re.fullmatch(r"[A-Z]{1,32}", word) is None for word in words):
        raise ValueError("bounded route words required")
    root = {"terminal": False, "children": {}}
    for word in words:
        node = root
        for symbol in word:
            node = node["children"].setdefault(symbol, {"terminal": False, "children": {}})
        node["terminal"] = True
    def compress(node):
        result = {"terminal": node["terminal"], "edges": {}}
        for symbol, child in node["children"].items():
            label = symbol
            while not child["terminal"] and len(child["children"]) == 1:
                symbol, child = next(iter(child["children"].items())); label += symbol
            result["edges"][label] = compress(child)
        return result
    return compress(root)

def contains_route(root, word):
    if not isinstance(word, str) or re.fullmatch(r"[A-Z]{1,32}", word) is None:
        raise ValueError("route word rejected")
    position = 0; node = root
    while position < len(word):
        for label, child in node["edges"].items():
            if word.startswith(label, position):
                position += len(label); node = child; break
        else:
            return False
    return node["terminal"]

routes = compressed_routes(["DEL", "DELHI", "BOM"])
print("root labels:", sorted(routes["edges"]))
for word in ("DEL", "DELHI", "DE", "BOM"):
    print(word, contains_route(routes, word))

Output

Output
root labels: ['BOM', 'DEL']
DEL True
DELHI True
DE False
BOM True

Costs and limits

Construction visits stored prefixes and retains both the temporary trie and compressed output during conversion. Lookup checks outgoing labels and consumed characters; this ASCII alphabet bounds outgoing edge count to 26. Naive repeated label concatenation adds allocation work, so no universal memory or timing improvement is claimed.

Common Mistakes

  • Do not compress away a node that marks an accepted prefix word.
  • Ending inside an edge label is not exact membership.

Connected lessons

Python trie: exact words, prefixes and node allocation, Python trie deletion: remove one word without losing its prefix neighbors, Python strings and bytes: reject decoding errors before parsing records.

Follow the ownership and update boundary

Python compressed trie updates: split on insertion and compact after deletion.

python
compressed-trie
Storage details