Compressed Trie

Definition

Compressed Trie

A compressed trie represents the same set of strings as a trie, but removes every non-root, non-terminal node with exactly one child. Each resulting chain becomes one edge whose label concatenates the original labels:

$$u\stackrel{a_1}{\to }{v}_1\stackrel{a_2}{\to }\cdots \stackrel{a_r}{\to }v⟼u\stackrel{a_1{a}_2\cdots a_r}{\to }v.$$

The root, branching nodes, and terminal nodes remain. Edges carry non-empty strings, and outgoing edges still have distinct first characters. Reading a root-to-node path spells the same string before and after compression; membership still requires ending at a terminal node.

In the diagram, a, b, and ba disappear, but an remains because it is stored. Compression shortens paths in edges, not in characters: an edge labelled bar still requires checking three characters.

Examples

Word membership

Let

$$S=\{\text{bear},\text{bell},\text{bid},\text{bull},\text{buy}\}.$$

The string $\text{bull}$ is in $S$ because it follows the edge labels

$$\epsilon \stackrel{b}{\to }\text{b}\stackrel{u}{\to }\text{bu}\stackrel{ll}{\to }\text{bull}$$

and ends in a terminal node. The string $\text{be}$ is not in $S$ if the node for $\text{be}$ is not terminal, even though it is a shared prefix of $\text{bear}$ and $\text{bell}$.

Preserving stored prefixes

If $S=\{\text{an},\text{ant}\}$, then the node for $\text{an}$ must remain terminal. The compressed trie may contain an edge labelled $\text{an}$ from the root and then an edge labelled $\text{t}$ to $\text{ant}$.

Thus, compression removes only non-terminal one-child nodes. It does not hide a stored string that is a prefix of another stored string.

Suffix trees

A suffix tree can be viewed as a compressed trie built from all suffixes of one string, usually after adding a fresh letter so that no suffix is a prefix of another suffix.