Compressed Trie Search

Compressed trie search locates a string key in a trie where chains of single child nodes are collapsed into one edge.

Instead of storing one character per edge, a compressed trie stores a string fragment on each edge. This reduces memory usage and shortens traversal when many keys share long prefixes.

Problem

Given a compressed trie root root and a string key s, determine whether s is stored as a complete key.

Return true if present, otherwise false.

Structure

Each node contains outgoing edges indexed by their first character. Each edge has:

Each node may also store a terminal flag.

Algorithm

Start at the root and scan the query string from left to right. At each node, select the outgoing edge whose label starts with the next query character. The edge label must match the next part of the query exactly.

compressed_trie_search(root, s):
    node = root
    i = 0

    while i < length(s):
        c = s[i]

        if c not in node.edges:
            return false

        edge = node.edges[c]
        label = edge.label

        if s[i : i + length(label)] != label:
            return false

        i = i + length(label)
        node = edge.child

    return node.is_terminal

Example

Stored keys:

A compressed trie may look like:

(root)
  └─ "ca"
      ├─ "t" (terminal)
      │   └─ "alog" (terminal)
      └─ "r" (terminal)

Search for "catalog":

The final node is terminal, so the key exists.

Search for "cattle" fails after matching "cat" because no edge labeled "tle" continues from that node.

Correctness

Each edge label represents a compressed sequence of ordinary trie edges. Matching an edge label is equivalent to matching those characters one by one in the uncompressed trie.

If a required edge is missing, no stored key has the requested prefix. If an edge label does not match the query substring exactly, the query diverges from every stored key in that subtree.

After the full query is consumed, the terminal flag distinguishes a complete stored key from a proper prefix. Therefore the algorithm returns true exactly when the input string is stored.

Complexity

Let $L$ be the length of the query string.

The number of node visits can be much smaller than in an ordinary trie because one compressed edge may consume many characters.

Space complexity for iterative search:

When to Use

Compressed tries are useful when:

• keys are strings with long shared prefixes
• ordinary tries waste memory on unary paths
• prefix search and ordered traversal are needed
• memory locality matters

Compared with ordinary tries, compressed tries reduce node count while preserving prefix based lookup.

Implementation

class Edge:
    def __init__(self, label, child):
        self.label = label
        self.child = child

class CompressedTrieNode:
    def __init__(self):
        self.edges = {}
        self.is_terminal = False

def compressed_trie_search(root, s):
    node = root
    i = 0

    while i < len(s):
        c = s[i]

        if c not in node.edges:
            return False

        edge = node.edges[c]
        label = edge.label

        if not s.startswith(label, i):
            return False

        i += len(label)
        node = edge.child

    return node.is_terminal

type CompressedEdge struct {
	Label string
	Child *CompressedTrieNode
}

type CompressedTrieNode struct {
	Edges      map[rune]*CompressedEdge
	IsTerminal bool
}

func CompressedTrieSearch(root *CompressedTrieNode, s string) bool {
	node := root
	i := 0
	runes := []rune(s)

	for i < len(runes) {
		c := runes[i]

		edge, ok := node.Edges[c]
		if !ok {
			return false
		}

		label := []rune(edge.Label)

		if i+len(label) > len(runes) {
			return false
		}

		for j := range label {
			if runes[i+j] != label[j] {
				return false
			}
		}

		i += len(label)
		node = edge.Child
	}

	return node.IsTerminal
}