Compressed tries

In a plain trie, long words make long chains of nodes with one child each. A compressed trie replaces each chain with a single edge labelled with a whole string. It stores the same words with far fewer nodes, and the number of nodes no longer depends on how long the words are.

Nodes that do no work

Look at a node that is not the end of a word and has exactly one child. A search that reaches it has only one way to go. The node holds no information that its child does not hold. A chain of such nodes is common: in a dictionary of English words, most of the nodes near the bottom are like this, because once a few letters are read, usually only one word is left.

A compressed trie (also called a radix tree, or a Patricia trie) merges each such chain into one edge, and labels the edge with all of the chain’s letters. Step through “Merge the chains”.

The rules for a compressed trie are:

• An edge is labelled with a non-empty string, not just one letter.
• The labels of the edges below a node all start with different letters. So the next letter of a search picks at most one edge.
• Every node except the root is the end of a word or has at least two children.

At most 2n nodes

Proof. Every node with no children is the end of a word (otherwise the third rule would fail), so there are at most n such nodes, called leaves. Now count the nodes with two or more children, the branch nodes. Each branch node splits the paths below it into at least two, and in a tree with b leaves there are at most b − 1 such splits. So there are fewer than n branch nodes. Every other node is the end of a word, and each word has only one end node. Adding up: every node is the root, a word end, or a branch node, so there are at most 1 + n + (n − 1) = 2n nodes.

A plain trie can have one node per letter: 10,000 words of length 20 can need 200,000 nodes, where the compressed trie needs at most 20,000. The letters are still stored, on the edges. To avoid copying them, an edge can store three numbers instead of a string: which word the letters come from, and where they start and end in it.

Insert splits an edge

Searching a compressed trie works as before, but an edge is matched string by string. At each node, pick the edge whose label starts with the next letter, then check that the word continues with the whole label. Three cases:

• The word continues with the whole label: follow the edge.
• The word ends inside the label (searching for toa on the edge ast). Then no node stands for the word, so it is not stored, but it is a prefix of a stored word: starts_with says yes.
• The word and the label differ at some letter. Then the word is not there.

Insert follows the same walk. When the word and a label part ways in the middle, as toad does with ast in the second variant, the edge is split: a new node takes the shared part of the label (a), the old child hangs below it with the rest (st), and the rest of the word becomes a new edge (d). If the word ends exactly at the split, the new node itself is tagged and nothing else is added.

class RNode:
    def __init__(self):
        self.kids = {}     # first letter -> (label, RNode)
        self.end = False

def insert(root, word):
    node, i = root, 0
    while i < len(word):
        ch = word[i]
        if ch not in node.kids:
            leaf = RNode()
            leaf.end = True
            node.kids[ch] = (word[i:], leaf)   # a new edge
            return
        label, child = node.kids[ch]
        j = 0   # how many letters the word and label share
        while j < len(label) and i + j < len(word) and label[j] == word[i + j]:
            j += 1
        if j < len(label):                     # split the edge
            mid = RNode()
            mid.kids[label[j]] = (label[j:], child)
            node.kids[ch] = (label[:j], mid)
            child = mid
        node, i = child, i + j
    node.end = True

Each step reads letters of the word that it has not read before, so insert and search still cost O(L). Delete is the opposite of a split: after removing a word, a node that is no longer a word end and has only one child is merged with that child, joining the two labels.

Where they are used

• Network routers look up the longest stored prefix of an address’s bits, to choose where to send a packet. Their tables are compressed tries of bits (lesson 5 shows tries of bits).
• Databases and key-value stores: Redis keeps its keys in a radix tree, and Ethereum stores its state in a variant called a Merkle Patricia trie.
• Suffix trees: the compressed trie of all the suffixes (the endings) of one text. It finds any pattern in the text in time that depends only on the length of the pattern. STRG comes back to this idea.