A
Y
U
D
A

INTRODUCCIÓN
Factor Oracle es una estructura de datos reciente; los primeros artículos que se publicaron datan del año 1999. Se trata de un autómata que acepta, como mínimo, todos los factores de la cadena de entrada. Por su construcción puede que reconozca otras palabras que no son factores de la cadena pero que sí que son aceptadas. Esto imposibilita la utilización directa de esta estructura para problemas como el String-Matching. Sin embargo tiene la ventaja de ser mucho más sencilla en su construcción y utilización.

Definición
Sea S una cadena de longitud m. Factor Oracle de S es un autómata que cumple:
a) Es acíclico.
b) Reconoce, como mínimo, todos los factores de S.
c) Tiene el mínimo nombre de estados posibles (0..m).
d) Tiene un número lineal de transiciones, entre m y 2m-1.
e) Todos sus estados son finales
f) Cada estado i+1 está asociado con el prefijo pref(i), es decir, S[1..i]. Es decir, que el prefijo pref(i) se reconocerá en el estado i+1.

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. Factor Oracle, Suffix Oracle.
http://algo.inria.fr/seminars/sem99-00/raffinot.html
2. Backwards Oracle Matching algorithm.
http://www-igm.univ-mlv.fr/~lecroq/string/bom.html