Compressed Trie

data-structures string-algorithms

Definition

Compressed Trie

A compressed trie is a trie where non-branching chains are contracted into single edges.

Edges may be labelled by whole strings, and terminal nodes are preserved.

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.