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.
Find every occurrence of he, she, his, hers in "ushers" in one pass. Start from the trie of the patterns. Each node stands for the string on the path to it; its failure link points to the deepest other node whose string is a suffix of that one, which is where the scan continues when the next letter fits nothing below. Failure links are computed in BFS order, because a node's link depends only on shallower nodes.
Check your understanding
The player pauses before each decision in this run and asks what happens next. Here are all 7, with their answers.
Where does the failure link of "he" point?
Answer: the root. To the longest proper suffix of "he" that is itself a path in the trie.
Where does the failure link of "hi" point?
Answer: the root. To the longest proper suffix of "hi" that is itself a path in the trie.
Where does the failure link of "sh" point?
Answer: "h". To the longest proper suffix of "sh" that is itself a path in the trie.
Where does the failure link of "her" point?
Answer: the root. To the longest proper suffix of "her" that is itself a path in the trie.
Where does the failure link of "his" point?
Answer: "s". To the longest proper suffix of "his" that is itself a path in the trie.
Where does the failure link of "she" point?
Answer: "he". To the longest proper suffix of "she" that is itself a path in the trie.
Where does the failure link of "hers" point?
Answer: "s". To the longest proper suffix of "hers" that is itself a path in the trie.
How it runs, step by step
Find every occurrence of he, she, his, hers in "ushers" in one pass. Start from the trie of the patterns. Each node stands for the string on the path to it; its failure link points to the deepest other node whose string is a suffix of that one, which is where the scan continues when the next letter fits nothing below. Failure links are computed in BFS order, because a node's link depends only on shallower nodes.
Aho-Corasick over 4 patterns.
Depth 1: a single letter has no shorter suffix but the empty string, so every depth-1 node fails to the root. The orange edges marked f are failure links.
Depth-one nodes fail to the root.
Node "he": drop its first letter and the longest suffix that is also in the trie is nothing at all, so it fails to the root. Found by following the parent's failure link to the root and looking for a e child there.
Failure link of he set.
Node "hi": drop its first letter and the longest suffix that is also in the trie is nothing at all, so it fails to the root. Found by following the parent's failure link to the root and looking for a i child there.
Failure link of hi set.
Node "sh": drop its first letter and the longest suffix that is also in the trie is "h", so that is its failure link. Found by following the parent's failure link to the root and looking for a h child there.
Failure link of sh set.
Node "her": drop its first letter and the longest suffix that is also in the trie is nothing at all, so it fails to the root. Found by following the parent's failure link to the root and looking for a r child there.
Failure link of her set.
Node "his": drop its first letter and the longest suffix that is also in the trie is "s", so that is its failure link. Found by following the parent's failure link to the root and looking for a s child there.
Failure link of his set.
Node "she": drop its first letter and the longest suffix that is also in the trie is "he", so that is its failure link. Found by following the parent's failure link to "h" and looking for a e child there. Patterns ending here: she, he; the shorter one ends at the failure node.
Failure link of she set.
Node "hers": drop its first letter and the longest suffix that is also in the trie is "s", so that is its failure link. Found by following the parent's failure link to the root and looking for a s child there.
Failure link of hers set.
Read 'u' at position 0. Nothing continues, back at the root.
Read u; state root.
Read 's' at position 1. Now at "s".
Read s; state s.
Read 'h' at position 2. Now at "sh".
Read h; state sh.
Read 'e' at position 3. Now at "she". "she", "he" end here: match at position 1.
Read e; state she.
Read 'r' at position 4. No r child from the current node: follow 1 failure link first. Now at "her".
Read r; state her.
Read 's' at position 5. Now at "hers". "hers" ends here: match at position 2.
Read s; state hers.
3 matches: she at 1, he at 2, hers at 2. The scan read each of the 6 letters once and never went back, because a failure link already knows the longest pattern prefix that survives a mismatch. Building the links is O(total pattern length), the scan is O(text + matches), and the number of patterns does not appear: that is why it is the algorithm behind grep -F with many words and intrusion detection systems.
3 matches found.
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