Radix Tree, Suffix Tree, Aho-Corasick
A trie spends a node on every letter, and most of those nodes have one child and decide nothing. A radix tree folds each such chain into a single edge labelled with the whole substring, so the tree has at most twice as many nodes as words and a lookup compares a label at a time. A suffix tree is the radix tree of all the suffixes of one word with a terminator, and it answers whether any substring occurs by one walk from the root. Aho-Corasick keeps the trie of many patterns uncompressed and adds a failure link to every node, pointing to the longest suffix of its string that is also in the trie; a text is then scanned once, left to right, never backing up, and every pattern is reported wherever it ends.
The trie of car, cart, care, cat has 6 letter nodes. Many of them sit in chains: one child each, no word ending there, so a lookup walks through them without ever deciding anything. A radix tree folds each such chain into one edge carrying the whole substring. Same words, same lookups, far fewer nodes.
Check your understanding
The player pauses before the one decision in this run and asks what happens next. Here it is, with the answer.
The edge "c" starts a chain with no branches. What label does the compressed edge get?
Answer: ca, one edge for the whole chain. Every letter along the chain joins the label; the chain stops at the first branch or word end.
How it runs, step by step
The trie of car, cart, care, cat has 6 letter nodes. Many of them sit in chains: one child each, no word ending there, so a lookup walks through them without ever deciding anything. A radix tree folds each such chain into one edge carrying the whole substring. Same words, same lookups, far fewer nodes.
Compressing a trie of 4 words into a radix tree.
From the root, the edge "c" leads into a chain of 1 node that each have one child and end no word. Nobody can branch off inside it, so the whole chain becomes a single edge labelled "ca". 1 node gone.
Fold the chain into the edge ca.
1 chain folded: 6 letter nodes became 5, and every remaining node is either a branch point or the end of a word. That is the bound: a radix tree of n words has at most 2n - 1 nodes whatever their length. Lookup compares a whole edge label at a time, which is why routers keep IP prefixes in one, under the name Patricia trie.
5 nodes after compression.
Remember
- Radix tree: fold every chain of single-child, non-terminal nodes into one edge labelled with the substring.
- Suffix tree: the radix tree of all suffixes plus a terminator; a substring query is one walk from the root.
- Aho-Corasick: failure links point to the longest suffix that is also in the trie; the scan never backs up.
Topics covered
Where this is used
NetworkingIP routing tables
A forwarding table holds prefixes like 10.1.0.0/16 and must find the longest one matching a destination address, which is a walk down a trie over address bits. Linux keeps it as a compressed trie in net/ipv4/fib_trie.c, so a lookup follows a handful of edges rather than one level per bit. Because only the branch a route lands on changes, adding or withdrawing a route stays cheap while the table is being queried millions of times a second.
DatabasesRedis streams and tracking tables
Redis ships its own radix tree, rax, and uses it for stream entry IDs, a consumer group's pending-entry list and the client-side caching tracking table. A stream ID is a millisecond timestamp followed by a counter, so thousands of consecutive entries share a long prefix that the radix tree stores once on a single edge instead of one node per byte. Keeping the IDs in tree order is also what turns a range read over a stream into a walk rather than a scan.
SecurityIntrusion detection signatures
Suricata and Snort check every packet payload against tens of thousands of rule content strings at line rate, and both ship Aho-Corasick as their multi-pattern engine: Suricata's ac and ac-ks settings, Snort's ac_bnfa. The cost of a scan depends on the payload length and the number of hits, not on how many patterns are loaded, so adding a rule grows the automaton rather than the per-packet work. Searching once per signature instead would multiply the work by the size of the ruleset.
BioinformaticsGenome alignment
MUMmer aligns whole genomes by finding maximal unique matches, and its classic engine builds a suffix tree of the reference and then streams the query sequence down it, so matches of any length are found without ever re-reading the reference. Building the index once and reusing it for every query is what makes this worth it on a text of a billion characters over a four-letter alphabet. Later versions moved to suffix arrays for the usual reason: the tree's per-node pointers cost several times more memory than the array holding the same information.
Why it works this way
Why edge labels are stored as offsets, not copied strings
The code above builds a label by concatenating characters, which is clear but copies the text onto the edges and costs as much memory as the trie it replaced. Real implementations store a pair of indices into the original string, so an edge of any length costs two integers. Combined with the fact that every internal node now has at least two children, which caps the internal nodes at one fewer than the leaves, that is what makes a suffix tree linear in the length of the text.
Why a suffix tree needs the terminator
Without it, a suffix that is also a prefix of a longer suffix ends in the middle of an edge instead of at a node: in banana, the suffix na stops partway along the edge spelling nana. Marking it would mean marking a position inside a label, which the tree has no place to record. Appending a character that appears nowhere else forces every suffix to end at its own leaf, so leaves and suffixes correspond exactly and every subtree is a clean set of occurrences.
Why failure links must be built breadth-first
A node's failure link is computed by walking its parent's failure link, and the parent is one level shallower. BFS finishes every node at depth d before touching depth d + 1, so the parent's link is already final when the child reads it. Build the same links depth-first and you read pointers that are still null, which produces an automaton that looks fine and silently misses matches.
Why a node inherits the output of its failure node
The scan reports only what is stored at the state it is in, but a shorter pattern can end at the same position as a longer one. With the patterns she and he, scanning she lands on the she node, which knows nothing about he. Merging the failure node's output into each node fixes it, because following failure links from the current state enumerates exactly those suffixes of the current match that are themselves in the trie. Leaving out that one line is the classic Aho-Corasick bug: it passes any test whose patterns do not nest.
Read more
- Radix treeWikipedia
- Suffix treeWikipedia
- Aho-Corasick algorithmWikipedia
- Aho-Corasick algorithmcp-algorithms
- Suffix tree and Ukkonen's algorithmcp-algorithms