Example

$ \def\sa#1{\tt{#1}} \def\dd{\dot{}\dot{}} \def\aArbre{\mathcal{T}} $

Below is the trie $\aArbre(\{\sa{aa},\sa{aba},\sa{abaaa},\sa{abab}\})$. States correspond to prefixes of words in the set. For example, state 3 corresponds to the prefix of length 2 of both $\sa{abaaa}$ and $\sa{abab}$. Terminal states (doubly circled) 2, 4, 6 and 7 correspond to the words in the set.

Trie

A trie $\aArbre$ on the alphabet $A$, a kind of digital tree, is an automaton whose paths from the initial state, the root, do not converge. A trie is used mostly to represent finite sets of words. If no word of the set is a prefix of another word of the set, words are associated with the leaves of the trie.

125 Problems in Text Algorithms

Example

Trie