INTRODUCCIÓN
The Boyer-Moore type algorithms match some suffixes of the pattern but it is
possible to match some prefixes of the pattern by scanning the character of the
window from right to left and then improve the length of the shifts. This is make
possible by the use of the suffix oracle of the reverse pattern. This data structure
is a very compact automaton which recognizes at least all the suffixes of a word and
slightly more other words The string-matching algorithm using the oracle of the reverse
pattern is called the Backward Oracle Matching algorithm.
Definición
- Version of the Reverse Factor
algorithm using the suffix oracle of xR instead of the
suffix automaton of xR;
- fast in practice for very long patterns and small alphabets;
- preprocessing phase in O(m) time and space
complexity;
- searching phase in O(mn) time
complexity;
- optimal in the average
Algoritmo On-line
Factor Oracle se puede construir on-line, es decir, sin tener que conocer todos los
caractéres que nos quedan por leer de la secuencia de entrada. El algoritmo lee carácter
a carácter de la cadena de entrada y construye el autómata de forma incremental.
De forma general diremos que en cada paso i leeremos el carácter S[i] de la cadena de
entrada y construiremos un nuevo estado i+1 creando las transiciones que hayan de incidir.
Esta transiciones harán que el autómata acepte todos los factores que acaben en el nuevo
carácter S[i].
Este algoritmo hace uso también de los suffix links. Cada estado i+1 tendrá un suffix
link que apuntará al sufijo más largo de S[0..i] que ya es reconocido por el autómata que
tenemos construido en ese momento, A(i-1).
Texto adaptado del capítulo 4 (Factor Oracle)
del PFC "Estructures de dades per a la biología computacional; Suffix Trees, CDAWG i Factor Oracle"
(2003) de Romina Goyo Garrido.