Compressed Tries — Patricia/Radix Trees (Conceptual)

Tries are elegant data structures. They enable O(m) lookup, insertion, and prefix queries where m is the length of the key—operations that hash tables cannot match for prefix-based problems. But elegance comes at a price: standard tries can be enormously wasteful with memory.

Consider storing the words "internationalization", "internationalize", and "international" in a standard trie. These three words share the prefix "international" (13 characters), yet the paths through the tree diverge only at the very end. A standard trie creates separate nodes for every single character, including long unary chains where nodes have exactly one child.

This observation leads to a powerful question: What if we could collapse those single-child chains into single nodes?

The answer is trie compression—a family of techniques that transform space-hungry standard tries into compact, efficient structures while preserving all their operational benefits.

Before we can appreciate compression, we must thoroughly understand the problem it solves. Standard tries—also called prefix trees—store strings by creating one node per character along the path from root to leaf.

The Structure of a Standard Trie:

Each node in a standard trie contains:

• A collection of child pointers (either an array of size |Σ| for alphabet Σ, or a hash map)
• An end-of-word marker (boolean flag indicating whether a complete word ends at this node)
• Optionally, the character leading to this node (though this can be implicit from the parent's pointer)

For a trie storing strings over a 26-letter alphabet using array-based children, each node requires:

• 26 pointers (8 bytes each on 64-bit systems) = 208 bytes
• End-of-word flag = 1 byte (typically padded)
• Additional overhead for alignment and object headers

Total per node: potentially 250+ bytes on modern systems.

Why This Happens: The Unary Chain Problem

The fundamental inefficiency arises from unary chains—sequences of nodes where each node has exactly one child. Consider storing these three words:

"apple"
"application"
"apply"

The paths look like this in a standard trie:

root
 └── a
     └── p
         └── p
             └── l
                 ├── e ✓ (end: "apple")
                 ├── i
                 │   └── c
                 │       └── a
                 │           └── t
                 │               └── i
                 │                   └── o
                 │                       └── n ✓ (end: "application")
                 └── y ✓ (end: "apply")

Notice the path from 'l' to 'i' to 'c' to 'a' to 't' to 'i' to 'o' to 'n' for "application". Each of those intermediate nodes (from 'i' down to 'o') has exactly one child. They perform no disambiguation—they simply extend a path. Yet each consumes the full memory footprint of a trie node.

In this example, 10 out of 14 nodes (approximately 70%) are either unary (single child) or could benefit from compression. Only branching nodes and leaf nodes with end markers are strictly necessary to distinguish between stored strings.

The Pattern Recognition:

Unary chains are especially prevalent when:

• The stored string set shares long common prefixes (e.g., URLs with "https://www.")
• Strings have long, unique suffixes that don't share structure with other strings
• The alphabet is large relative to the branching factor (e.g., Unicode strings)

In extreme cases—such as storing a single very long string—a standard trie degenerates into a linked list, with zero space benefit over simply storing the string directly.

The core insight of trie compression is deceptively simple: Replace every maximal unary chain with a single edge labeled with multiple characters.

Instead of creating nodes a→p→p→l where each arrow represents a single character, we create a single edge labeled "appl" from root to a node representing that entire prefix.

Before Compression (Standard Trie):

Each edge represents ONE character:
root ─a→ ● ─p→ ● ─p→ ● ─l→ ●

After Compression:

Edges represent STRINGS:
root ─"appl"→ ●

The compressed node retains all the semantics of the original path—it represents the complete prefix "appl"—while consuming the memory of only one node instead of four.

Visualizing the Transformation:

Let's see our earlier example after compression:

Standard Trie (before):

root
 └── a
     └── p
         └── p
             └── l
                 ├── e ✓
                 ├── i
                 │   └── c
                 │       └── a
                 │           └── t
                 │               └── i
                 │                   └── o
                 │                       └── n ✓
                 └── y ✓

Compressed Trie (after):

root
 └──"appl"─→ ●
              ├──"e"─→ ● ✓ ("apple")
              ├──"ication"─→ ● ✓ ("application")
              └──"y"─→ ● ✓ ("apply")

Node count reduction: 14 nodes → 5 nodes (64% reduction)

The compressed trie preserves all functionality: we can still search for "apple", check if a prefix "app" exists, and enumerate all words starting with "appl". But we do so with fewer than half the nodes.

To reason precisely about compressed tries, we need formal definitions. This terminology appears throughout the literature and is essential for understanding research papers, library documentation, and technical discussions.

Definition: Compressed Trie (Patricia Trie)

Given a set S of strings over alphabet Σ, a compressed trie T for S is a rooted tree where:

1. Edge labels are non-empty strings over Σ (possibly multi-character)
2. No two edges from the same node share a common prefix (this ensures deterministic traversal)
3. Every internal node has at least two children (the no-unary-chain invariant)
4. The set of root-to-leaf paths, when concatenating edge labels, equals exactly the set S (correctness)

A Patricia trie (Practical Algorithm to Retrieve Information Coded in Alphanumeric) is technically a specific implementation variant of compressed tries, but the terms are often used interchangeably in practice.

Definition: Radix Tree

A radix tree (also called radix trie) is a compressed trie where edge labels are constrained further. In a radix-2 tree (binary radix tree), each edge label is a sequence of bits. More generally, a radix-k tree operates over an alphabet of k symbols.

The term "radix tree" emphasizes the underlying number system interpretation, which is particularly relevant for:

• IP address routing (radix-2 on 32 or 128 bits)
• Integer keys (radix-10 or radix-2^k)
• Memory addressing schemes

Key Structural Properties:

Let T be a compressed trie storing n distinct strings. The following properties hold:

1. Maximum internal nodes: T has at most n-1 internal nodes.

   • Proof sketch: Each internal node has ≥2 children. With n leaves (one per string), this is a tree with n leaves and no unary internal nodes, which has at most n-1 internal nodes.

2. Maximum total nodes: T has at most 2n-1 nodes.

   • Direct consequence of property 1.

3. Node bound is tight: The bound 2n-1 is achieved when all strings differ at their very first character (maximum branching, no shared prefixes).

4. Space complexity: O(n) nodes regardless of string lengths.

   • This is the critical win: Standard tries use O(total characters), but compressed tries use O(number of strings).

These properties guarantee that compressed tries scale with the number of strings, not with the total length of strings. For datasets with long strings sharing common prefixes, this difference can be enormous.

The elegance of compressed tries is that they maintain the same O(m) time complexity for all operations where m is the key length—despite the structural transformation. Let's understand why.

Search Operation:

To search for key k in a compressed trie:

1. Start at the root with position p = 0 in k
2. At each node, find the outgoing edge whose label shares a prefix with k[p:]
3. If the edge label is a prefix of remaining k[p:], advance p by length of edge label and follow the edge
4. If remaining k[p:] is a prefix of edge label (k ends mid-edge), the key is present only if this is valid for your use case (prefix search)
5. If there's a mismatch, the key doesn't exist
6. Repeat until k is exhausted; check end-of-word marker

Time Complexity Analysis:

The key insight: we compare each character of k at most once. In standard tries, we compare one character per node visited. In compressed tries, we may compare multiple characters per node, but the total comparisons across all nodes equals exactly m. The path length (number of nodes) may be much shorter, but we spend more time at each node—the product is the same.

Insert Operation:

Insertion in compressed tries is more involved than in standard tries because we may need to split edges:

1. Search for the key until we find where it diverges
2. If divergence happens at a node, simply add a new edge for the remaining suffix
3. If divergence happens within an edge label (key and label share a prefix but then differ):
   • Split the edge at the divergence point
   • Create a new internal node at the split point
   • The original edge becomes two: root-of-subtree to new node, new node to original destination
   • Add the new key's remaining suffix as an additional edge from the new node

Example: Inserting "apply" into a trie containing "application"

Before:

root ──"application"──→ ● ✓

The key "apply" matches "appl" but diverges at 'y' vs 'i'. We split:

After:

root ──"appl"──→ ●
                 ├──"ication"──→ ● ✓
                 └──"y"──→ ● ✓

We created a new internal node at "appl", split the original edge, and added the new suffix "y".

Delete Operation:

Deletion requires the inverse of splitting—merging edges when a node becomes unary:

1. Find the node corresponding to the key
2. Unmark it as end-of-word
3. If the node has no children, remove it
4. If removal causes the parent to have only one child, merge the parent with that child (concatenate edge labels)
5. Propagate merging upward as needed

Prefix Search (StartsWith):

Prefix search follows the same logic as key search but succeeds whenever the prefix is fully matched, even if mid-edge:

1. If prefix ends exactly at a node: that node's subtree contains all strings with that prefix
2. If prefix ends mid-edge: follow that edge, and the subtree below contains all matching strings
3. If prefix mismatches: no strings with that prefix exist

Time complexity remains O(p) where p is prefix length.

The primary motivation for compression is space efficiency. Let's quantify the improvement precisely.

Standard Trie Space:

For a set S of n strings with total length L (summing all character counts):

• Number of nodes: O(L) in the worst case (no shared prefixes)
• Per-node overhead: O(|Σ|) for children pointers + O(1) for metadata
• Total space: O(L × |Σ|) for array-based children

With 26 lowercase letters and 8-byte pointers, that's 208 bytes per node.

Compressed Trie Space:

For the same set S:

• Number of nodes: O(n) guaranteed (at most 2n-1 nodes)
• Per-node overhead: O(|Σ|) or O(children count) + edge label storage
• Edge label storage: The total length of all edge labels equals L (we've just redistributed characters from nodes to edges)
• Total space: O(n × |Σ| + L) or O(n × average_branching + L) with hash map children

When Is Compression Most Beneficial?

The space advantage of compressed tries is greatest when:

1. Strings share long common prefixes: URLs ("https://www.example.com/..."), domain names, file paths, etc.

2. Average string length is much greater than √n: When L >> n, the reduction from O(L) nodes to O(n) nodes is dramatic.

3. Alphabet is large: With Unicode or extended ASCII, each node's children array is expensive. Fewer nodes = less waste.

4. String set is sparse relative to possible strings: Storing 1000 words out of a possible ≈10^20 combinations of 15-character ASCII strings.

Numerical Example:

Storing 100,000 URLs averaging 60 characters:

• Total characters L = 6,000,000
• Standard trie: Up to 6,000,000 nodes × 250 bytes ≈ 1.5 GB
• Compressed trie: ~200,000 nodes × 250 bytes + 6MB for edge labels ≈ 56 MB
• Compression ratio: ~27x

Theory is essential, but intuition comes from working through examples. Let's trace several scenarios to internalize how compressed tries behave.

Example 1: Progressive Insertions

Inserting words one at a time into an initially empty compressed trie:

Insert "test":

root ──"test"──→ ● ✓

Single word = single edge from root to a marked leaf.

Insert "testing":

root ──"test"──→ ●
                 ├──""──→ ● ✓ (end marker for "test" moves here)
                 └──"ing"──→ ● ✓

Wait—this isn't quite right. Let's reconsider.

Actually, "test" is a prefix of "testing". The trie becomes:

root ──"test"──→ ● ✓ ("test")
                 └──"ing"──→ ● ✓ ("testing")

The node for "test" is marked AND has a child. No need for epsilon edges.

Insert "team": "team" shares only "te" with "test"/"testing". We split:

root ──"te"──→ ●
               ├──"st"──→ ● ✓ ("test")
               │          └──"ing"──→ ● ✓ ("testing")
               └──"am"──→ ● ✓ ("team")

Insert "tea": "tea" shares "tea" with "team". We split:

root ──"te"──→ ●
               ├──"st"──→ ● ✓
               │          └──"ing"──→ ● ✓
               └──"a"──→ ● ✓ ("tea")
                         └──"m"──→ ● ✓ ("team")

Node count: 6 nodes for 4 words. A standard trie would need 15 nodes.

Example 2: Edge Cases

What happens with special inputs?

Single character strings: {"a", "b", "c"}

root
 ├──"a"──→ ● ✓
 ├──"b"──→ ● ✓
 └──"c"──→ ● ✓

No compression benefit—every string differs at first character. 4 nodes total.

Identical prefixes with single-character differences: {"aa", "ab", "ac"}

root ──"a"──→ ●
              ├──"a"──→ ● ✓
              ├──"b"──→ ● ✓
              └──"c"──→ ● ✓

5 nodes. Standard trie would have 7 nodes (root→a→{a,b,c}).

One very long string: {"supercalifragilisticexpialidocious"}

root ──"supercalifragilisticexpialidocious"──→ ● ✓

2 nodes total! Standard trie: 35 nodes.

It's worth pausing to understand why trie operations still work correctly after compression. The transformation might seem to lose information, but it doesn't.

The Fundamental Preservation:

A compressed trie preserves exactly one thing: the set of root-to-leaf (or root-to-end-marker) paths. Every distinct path through the standard trie—concatenating character labels—becomes exactly one distinct path through the compressed trie—concatenating edge labels.

Why Search Still Works:

Searching for key k means finding whether a path spelling k exists:

• Standard trie: Walk character by character, each step via a labeled edge
• Compressed trie: Walk chunk by chunk, each step via a multi-character edge

The path exists if and only if the sequence of characters matches. Whether we match one character per step or multiple characters per step, the total match is identical.

Why Prefix Queries Still Work:

For a prefix p:

• Standard trie: Navigate p character by character until exhausted; subtree below contains all extensions
• Compressed trie: Navigate p chunk by chunk; may end mid-edge (partial match of some edge); subtree below that edge contains all extensions

The only complication is handling mid-edge termination, but this is straightforward to implement.

Correctness Invariants:

A correctly implemented compressed trie maintains these invariants after every operation:

1. No unary internal nodes: Every internal node has ≥2 children
2. Distinct edge labels: No two edges from the same node share a prefix (this ensures deterministic traversal)
3. Path-string correspondence: Concatenating edge labels along any root-to-leaf path yields exactly one stored string
4. End marker correctness: A node is marked end-of-word iff some stored string ends exactly at that node

Violating any invariant leads to incorrect behavior:

• Unary node: Wasted space; indicates incomplete compression
• Shared prefix on edges: Ambiguous traversal; broken search
• Wrong path: Lost or phantom strings
• Wrong end markers: False positives or negatives on exact match

We've established a comprehensive understanding of what trie compression is and why it matters. Let's consolidate the key insights.

What's Next:

Now that we understand the what and why of trie compression, the next page dives into the how: the detailed mechanics of compacting single-child chains. We'll walk through the compression algorithm itself, exploring edge splitting, label management, and the subtle considerations that make implementations robust.