Radix tree and when it saves memory

Why this matters

A plain trie, the kind from lesson 02, stores one letter per node (a node is one box in the tree). That is simple, but it can waste a lot of nodes. Take one long word such as internationalization. A plain trie needs one node for every letter, twenty-one nodes in total counting the root, even though nothing else shares those letters. Most of those nodes have exactly one child and no word ending, so they carry no choice at all.

A radix tree (also called a compressed trie or a Patricia trie) fixes this. It joins each chain of single-child nodes into one edge (the line between two nodes), and the edge carries a piece of text as its label. The word internationalization then needs two nodes: the root and one node at the end of a single edge labelled with the whole word.

This lesson builds a radix tree in Python, explains the rule for which nodes survive, and counts the nodes saved on a real word list. It does not cover the ternary search tree, which is in another lesson of this module, and it does not repeat the insert and search from lesson 02 beyond what the radix version needs.

The idea: an edge can hold more than one letter

In a plain trie, each edge is one letter. In a radix tree, each edge is a label: a string of one or more letters. Walking down the tree now means reading a label and moving on, not moving one letter at a time.

Words of this kind are stored in the tree as paths of labels. Here is a short example with two words, car and cart, written as a plain trie and as a radix tree.

Plain trie (one letter per edge):      Radix tree (labels on edges):
 
root                                   root
 └─ c                                   └─ car  (word)
     └─ a                                   └─ t  (word)
         └─ r  (word)
             └─ t  (word)

The plain trie has five nodes: the root, c, a, r and t. The radix tree has three: the root, the node after car, and the node after cart. The chain c, a has no branch and no word ending in the middle, so the radix tree merges those letters into the label car.

A node may be removed from the plain trie only when it is not needed for any word. A node is needed when at least one of these is true:

it is the root, which every walk starts from,
a word ends at it, so the flag must be stored there,
it has two or more children, so a choice must be made there.

A node that is none of these has exactly one child and no word ending. Nothing is decided at that node, so its letters can be moved into the edge above or below it. The rule is easy to check by hand on a small tree. Later in this lesson, counting the nodes that pass the rule on the real word list gives the same number as the radix tree.

Building a radix tree by hand

Insertion is harder than in a plain trie, because a new word can disagree with an existing label in the middle. Three cases cover everything.

Case 1: the whole label matches. Insert car into a tree that already has the label car. Move down the edge and check the rest of the word. Nothing changes.

Case 2: the label and the word part ways in the middle. Insert cat into a tree that holds car. The labels match for ca and then differ: r in one, t in the other. The edge car must be split. The shared part ca becomes a new node, and the old remainder r hangs below it. The new word adds its own edge t next to it.

Here is what the dump method prints after inserting car, then cat. The program prints the tree with each word end marked [word] and indents each child under its parent.

ca
    r  [word]
    t  [word]

The shared label ca is now one node with two children. The lookups still work: car and cat are both found, and ca alone is not, because ca was never inserted as a word.

Case 3: the new word ends inside an existing label. Insert ca into a tree that holds car. The word ca matches the first two letters of the label, and then runs out. The node at the split point becomes a word end. This is a second kind of split: the split point is marked as a word, and r stays below it. The output is:

ca  [word]
    r  [word]

These three cases are the whole insert. The code below handles all of them in one loop.

The Python program

The program stores each node's children in a dictionary, with the edge label as the key. Python dictionaries keep the order in which keys were added, so the program sorts the labels when it prints the tree. Sorting makes the printed tree easy to read.

The program has two parts. The first builds a radix tree from a small list of words and prints it. The second part runs only when you pass a file of words on the command line. It builds a radix tree from that file and counts the nodes a plain trie would need. It needs the file path as its one argument.

import random
import sys
 
 
class Node:
    def __init__(self):
        self.children = {}  # label -> Node
        self.is_word = False
 
 
def common_prefix(a, b):
    i = 0
    while i < len(a) and i < len(b) and a[i] == b[i]:
        i += 1
    return i
 
 
class RadixTree:
    def __init__(self):
        self.root = Node()
 
    @staticmethod
    def _find_label(node, first):
        for label in node.children:
            if label[0] == first:
                return label
        return None
 
    def insert(self, word):
        node = self.root
        rest = word
        while True:
            if rest == "":
                node.is_word = True
                return
            label = self._find_label(node, rest[0])
            if label is None:
                leaf = Node()
                leaf.is_word = True
                node.children[rest] = leaf
                return
            common = common_prefix(label, rest)
            if common < len(label):
                child = node.children.pop(label)
                middle = Node()
                middle.children[label[common:]] = child
                node.children[label[:common]] = middle
                node = middle
            else:
                node = node.children[label]
            rest = rest[common:]
 
    def contains(self, word):
        node = self.root
        rest = word
        while rest != "":
            label = self._find_label(node, rest[0])
            if label is None or not rest.startswith(label):
                return False
            node = node.children[label]
            rest = rest[len(label):]
        return node.is_word
 
    def count_nodes(self):
        return self._count_nodes(self.root)
 
    def count_label_characters(self):
        return self._count_label_characters(self.root)
 
    def dump(self):
        self._dump(self.root, "")
 
    @staticmethod
    def _count_nodes(node):
        return 1 + sum(RadixTree._count_nodes(child) for child in node.children.values())
 
    @staticmethod
    def _count_label_characters(node):
        return sum(len(label) + RadixTree._count_label_characters(child)
                   for label, child in node.children.items())
 
    @staticmethod
    def _dump(node, indent):
        for label in sorted(node.children):
            child = node.children[label]
            print(indent + label + ("  [word]" if child.is_word else ""))
            RadixTree._dump(child, indent + "    ")
 
 
def plain_trie_nodes(words):
    prefixes = set()
    for w in words:
        for i in range(1, len(w) + 1):
            prefixes.add(w[:i])
    return len(prefixes) + 1
 
 
small = ["romane", "romanus", "romulus", "rubens", "ruber", "rubicon", "rubicundus"]
tree = RadixTree()
for w in small:
    tree.insert(w)
tree.dump()
print("plain trie nodes:", plain_trie_nodes(small))
print("radix nodes:", tree.count_nodes())
print("label characters:", tree.count_label_characters())
 
if len(sys.argv) > 1:
    with open(sys.argv[1], encoding="utf-8") as f:
        words = list(dict.fromkeys(line.strip() for line in f if line.strip()))
    big = RadixTree()
    for w in words:
        big.insert(w)
    word_set = set(words)
    wrong = sum(1 for w in words if not big.contains(w))
    rng = random.Random(7)
    for _ in range(5000):
        probe = words[rng.randrange(len(words))] + chr(ord("a") + rng.randrange(26))
        if big.contains(probe) != (probe in word_set):
            wrong += 1
    plain = plain_trie_nodes(words)
    radix = big.count_nodes()
    print("words:", len(words))
    print("plain trie nodes:", plain)
    print("radix nodes:", radix)
    print(f"nodes saved: {plain - radix} ({100.0 * (plain - radix) / plain:.1f}%)")
    print("label characters:", big.count_label_characters())
    print("wrong answers:", wrong)

Save the program as radix_tree.py. Run it with the file path as the argument:

python3 radix_tree.py /usr/share/keepassxc/wordlists/eff_large.wordlist

The output is:

r
    om
        an
            e  [word]
            us  [word]
        ulus  [word]
    ub
        e
            ns  [word]
            r  [word]
        ic
            on  [word]
            undus  [word]
plain trie nodes: 28
radix nodes: 14
label characters: 27
words: 7772
plain trie nodes: 25638
radix nodes: 11384
nodes saved: 14254 (55.6%)
label characters: 25637
wrong answers: 0

The class has four parts that matter.

Node holds children, a dictionary from an edge label to the child node, and is_word, the same flag as before. The key is now a whole string, not a single character.

insert follows the three cases from the previous section. It keeps a cursor node and the part of the word still to be placed, called rest. At each step it looks for an edge whose label starts with the same letter as rest. Because a node never has two edges that start with the same letter, that one letter is enough to pick the edge. If no such edge exists, it adds a leaf with the rest of the word as its label. If the label matches completely, it moves down. If the label stops matching in the middle, it splits the label, as in cases 2 and 3. The pop call removes the old edge from the dictionary, and the two lines after it put back two new edges in its place.

contains walks the tree in the same way. It fails if no edge starts with the next letter, or if the edge label is not a prefix of what is left of the word. When the word is used up, the answer is the flag on the final node.

count_nodes counts every node, including the root. count_label_characters adds up the length of every label. Both are recursive: each calls itself on the children of the node it is given.

The first part of the output comes from the small example, and the second part comes from the real list. The small example has seven words. Its plain trie has 28 nodes, and its radix tree has 14. Read the dump from the top: r is the only edge from the root, then om below it, and then an, which has two word ends e and us. The dump shows that romulus shares rom with the others but has its own label ulus.

Counting the saved nodes on a real list

The EFF large word list has 7,772 words, one per line, in the copy at the path above. Another copy can have a different count, and the numbers below would change with it. The program reads it, builds both structures, and counts the nodes.

The plain trie has 25,638 nodes. This count is one node for each distinct prefix of every word, plus the root.
The radix tree has 11,384 nodes.
The difference is 14,254 nodes, or 55.6 percent of the plain trie.

The program also checks the radix tree. It looks up every word, which must all be found, and it looks up 5,000 random strings, each one a word with one extra letter, and compares each answer with a set. A set is Python's collection that answers "is this value in the set" quickly, and it serves here as the trusted answer. The number of wrong answers is 0. The random strings come from a generator with a fixed seed, so every run tests the same 5,000 strings.

The rule from earlier in the lesson can also be checked by hand. A node stays in the radix tree when it is the root, a word ends there, or it has two or more children. Counting those nodes in the plain trie gives 11,384 for this list, the same number the radix tree reports. The same count for the small example gives 14, out of 28 plain nodes.

The counts above are node counts, not bytes. A node in Python is an object, and each object has a fixed cost in memory, so fewer objects means less memory. The saved cost is not the same as the saved characters. The label characters total 25,637 in the radix tree, which is one less than the plain trie's 25,638 nodes, because the root has no letter. So the letters are not saved: every letter still appears exactly once, but in a label rather than in its own node. The saving is in the number of objects.

The saving depends on the shape of the data. If most nodes have two or more children, every node is kept and nothing is saved. A radix tree saves the most when many words have long tails that no other word shares, as with the single word internationalization, where the plain trie costs twenty-one nodes and the radix tree costs two.

This lesson measured nodes only. Measuring the bytes a program uses needs a memory profiler, such as the tracemalloc module in the standard library, and that step is not covered here.

Common mistakes

These mistakes come from running the code in this lesson, or small changes to it. The output shown is the real output.

Mistake 1: adding a new edge instead of splitting

A tempting shortcut is to skip the split. When a label does not match the new word completely, the code could add the rest of the word as a second edge. That breaks the rule that each node has at most one edge per first letter. Here is a copy of the insert with the split replaced by that shortcut, run on car and then cat:

Python · editable

class Node:
    def __init__(self):
        self.children = {}
        self.is_word = False

def common_prefix(a, b):
    i = 0
    while i < len(a) and i < len(b) and a[i] == b[i]:
        i += 1
    return i

class RadixTree:
    def __init__(self):
        self.root = Node()

@staticmethod
    def _find_label(node, first):
        for label in node.children:
            if label[0] == first:
                return label
        return None

def insert(self, word):
        node = self.root
        rest = word
        while True:
            if rest == "":
                node.is_word = True
                return
            label = self._find_label(node, rest[0])
            if label is None:
                leaf = Node()
                leaf.is_word = True
                node.children[rest] = leaf
                return
            common = common_prefix(label, rest)
            if common < len(label):
                # Bug: adds the rest of the word as a second edge instead of splitting
                leaf = Node()
                leaf.is_word = True
                node.children[rest] = leaf
                return
            node = node.children[label]
            rest = rest[common:]

def contains(self, word):
        node = self.root
        rest = word
        while rest != "":
            label = self._find_label(node, rest[0])
            if label is None or not rest.startswith(label):
                return False
            node = node.children[label]
            rest = rest[len(label):]
        return node.is_word

def dump(self, node=None, indent=""):
        node = self.root if node is None else node
        for label in sorted(node.children):
            child = node.children[label]
            print(indent + label + ("  [word]" if child.is_word else ""))
            self.dump(child, indent + "    ")

t = RadixTree()
t.insert("car")
t.insert("cat")
print("contains car:", t.contains("car"))
print("contains cat:", t.contains("cat"))
t.dump()

The output is:

contains car: True
contains cat: False
car  [word]
cat  [word]

The word cat is in the tree but cannot be found. The search looks at the first edge that starts with c, which is car, and then stops because car is not a prefix of cat. The fix is the split from case 2, which turns the shared part of the label into a node.

Mistake 2: forgetting the file argument

The program reads the file named on the command line. Python keeps the command-line arguments in the list sys.argv. Index 0 is the name of the program, and index 1 is the first argument. A program that reads sys.argv[1] without checking the length fails when no argument is given. The two-line program below does that:

import sys
print(sys.argv[1])

Run as main.py with no argument, it prints:

Traceback (most recent call last):
  File "main.py", line 2, in <module>
    print(sys.argv[1])
          ~~~~~~~~^^^
IndexError: list index out of range

The fix is to pass the path of the file, as in the run command above. The radix program avoids the error by checking len(sys.argv) > 1 before it reads the file.

Mistake 3: reading the label characters as the saving

A student may look at the label characters total, 25,637, and conclude that the radix tree stores fewer letters than the plain trie. It does not. Each letter is stored once in both structures. The saving is in the nodes, which are the costly part in Python because each one is an object with its own dictionary. When you report a saving, name what you counted: nodes, characters or bytes.

Practice

Each exercise has an answer. Try the exercise first, then check your answer.

Exercise 1. How many plain trie nodes and how many radix nodes does the list cat and cats produce? Count the root in both totals.

Show the answer: The plain trie has five nodes: the root, c, ca, cat and cats. The radix tree has three: the root, the node for cat (a word), and a leaf with the label s (a word). The chain c, ca is merged into the one label cat.

Exercise 2. The word internationalization alone gives 21 plain nodes and 2 radix nodes. Explain in your own words why the radix tree has only two nodes.

Show the answer: The word has no other word to share letters with, so every node in the plain trie has exactly one child and no word ending except the last. Those nodes are not needed, so the whole word becomes one edge label below the root. The root and the leaf are the only nodes left.

Exercise 3. Build a radix tree for the list test, testing, tester and team. How many plain trie nodes and how many radix nodes do you get?

Show the answer: The plain trie has 12 nodes: the root and the eleven distinct prefixes t, te, tes, test, testi, testin, testing, teste, tester, tea and team. The radix tree has 6 nodes: the root, the node for te (a branch with two children), the node for test (a word with two children), and the three leaves that spell ing, er and am. Those three leaves are the labels under te and test. Running the insert code on this list prints the dump te, then am [word], then st [word], with er [word] and ing [word] below st.

Exercise 4. Insert car, care and cart into an empty radix tree, in that order. Draw the tree and count its nodes.

Show the answer: The tree has the root, a node for car (a word), and two leaves below it, labelled e (a word) and t (a word). That is 4 nodes. The plain trie for the same list has 6 nodes: the root and the five distinct prefixes c, ca, car, care and cart.

Exercise 5. Why does _find_label look only at the first letter of each label, and not at the whole label?

Show the answer: Each node never has two edges that start with the same letter, because an insert splits a label before that could happen. So the first letter of the word being searched picks at most one edge. Looking at the whole label would give the same answer, but it would take more work. The shortcut from mistake 1 broke this rule, and the search then found only the first of the two edges.

Summary

A radix tree stores a label on each edge, so a chain of single-child nodes becomes one edge.
A node stays in the radix tree only when it is the root, a word ends there, or it has two or more children.
An insert has three cases: the label matches, the label splits in the middle, or the word ends inside a label.
On the EFF list of 7,772 words, the radix tree has 11,384 nodes against 25,638 for the plain trie, which is 14,254 fewer, or 55.6 percent.
The saving is in node objects. The letters are stored once in both structures, so the label characters total is not smaller.