B
O
M

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.


Direcciones de Interés
1. Backwards Oracle Matching algorithm.
http://www-igm.univ-mlv.fr/~lecroq/string/bom.html