The algorithm

Given the statistical error measure, we can construct the tree using the following algorithm:

• Initialisation step:

  -

  The tree $T$ is initialised to a single node: $e$.

  -

  The set of candidate sequences $S$ is initialised to $\left\{ \sigma \vert \sigma \in \Sigma, \tilde{P}(\sigma)\geq \epsilon \right\}$.

• While there is still a sequence to be tested (that is, $S \not= \o$), do:

  1)

  Pick the first candidate sequence $s \in S$ and remove it from the set $S$.

  2)

  If $Err\left(s,\mathit{suffix}(s)\right)\geq\epsilon$ then add to $T$ the node corresponding to $s$.

  3)

  If $\vert s\vert<L$ then for every sequence $\sigma\in\Sigma$, if $\tilde{P}(\sigma s)\geq \epsilon$ add $\sigma s$ to the end of the candidate sequence set $S$.