Example

$ \def\sa#1{\tt{#1}} \def\dd{\dot{}\dot{}} \def\aArbre{\mathcal{T}} \def\aSTree{\mathcal{ST}} \def\aSuff{\mathcal{S}} \def\aFact{\mathcal{F}} \def\Suff{\mathit{Suff}} $

Below are the trie $\aArbre(\Suff(\sa{aabab}))$ of suffixes of $\sa{aabab}$ (on the left) and its Suffix tree $\aSTree(\sa{aabab})$ (on the right). To get a complete linear-size structure, each factor of the word that labels an arc needs to be represented by a pair of integers such as (position, length).

Below (left) is $\aSuff(\sa{aabab})$, the Suffix automaton of $\sa{aabab}$. The right part shows the Factor automaton of $\sa{aabab}$ in which state 6 of $\aSuff(\sa{aabab})$ is merged with state 3.

Suffix Structures

Suffix structures that store the suffixes of a word are important data structures used to produce efficient indexes. Tries can be used as such but their size can be quadratic. One solution to cope with that is to compact the trie, resulting in the Suffix tree of the word. It consists in eliminating non-terminal nodes with only one outgoing edge and in labelling arcs by factors of the word accordingly. Eliminated nodes are sometimes called implicit nodes of the Suffix tree and remaining nodes are called explicit nodes.

A second solution to reduce the size of the Suffix trie is to minimise it, which means considering the minimal deterministic automaton accepting the suffixes of the word, its Suffix automaton.

It is known that $\aSuff(x)$ possesses fewer than $2|x|$ states and fewer than $3|x|$ arcs, for a total size $O(|x|)$, that is, linear in $|x|$. The Factor automaton $\aFact(x)$ of the word, minimal deterministic automaton accepting its factors, can even be smaller because all its states are terminal.

125 Problems in Text Algorithms

Example

Suffix Structures