Saltar a contenido

Set Backward Oracle Matching

1. Definición

El Set Backward Oracle Matching (SBOM) es un algoritmo eficiente para la búsqueda de múltiples patrones dentro de un texto. Pertenece a la familia de algoritmos de búsqueda de cadenas que utilizan un enfoque de escaneo "hacia atrás" y "saltos" (shifts) grandes, similar al algoritmo Boyer-Moore, pero extendido para trabajar con un conjunto de patrones en lugar de uno solo.

Su principal innovación radica en la construcción de un Oráculo de Factores (Factor Oracle) a partir de los inversos de los prefijos de longitud lmin de todos los patrones del conjunto. Este oráculo permite al algoritmo:

  • Reconocer rápidamente cualquier subcadena de los patrones invertidos.
  • Determinar el desplazamiento óptimo para la ventana de búsqueda después de un desajuste, lo que reduce significativamente el número de comparaciones de caracteres necesarias.

Características clave

  • Múltiples Patrones: Diseñado para encontrar simultáneamente todas las ocurrencias de un conjunto P de patrones {p₁, p₂, ..., pₖ} en un texto T.
  • Orientación Hacia Atrás: Tanto la construcción de su estructura auxiliar como la fase de escaneo del texto se realizan con una lógica "inversa" o "de derecha a izquierda".
  • Oráculo de Factores: Utiliza esta estructura de autómata finito para su eficiencia. Es una representación compacta que almacena información sobre todas las subcadenas (factores) de los patrones invertidos.

2. Ejemplo de Uso

Conjunto de Patrones P: {"ORO", "PLATA", "DIAMANTE"} Texto T: "EL TESORO ESCONDIDO CONTENÍA ORO Y PLATA. UN ANILLO DE ORO CON UN DIAMANTE MUY GRANDE."

Paso 1: Invertir los Patrones y Construir el Oráculo

  1. Determinar lmin: La longitud del patrón más corto (lmin) es 3 (de "ORO").
  2. Tomar Prefijos de longitud lmin: Se toman los prefijos de longitud 3 de todos los patrones del conjunto P.
  3. "ORO" -> "ORO"
  4. "PLATA" -> "PLA"

  5. "DIAMANTE" -> "DIA"

  6. Invertir esos Prefijos: Este es el paso clave.

  7. "ORO" (invertido) -> "ORO"
  8. "PLA" (invertido) -> "ALP"

  9. "DIA" (invertido) -> "AID"

  10. Construir el Oráculo: El Oráculo de Factores se construye a partir de este conjunto: {"ORO", "ALP", "AID"}.

Paso 2: Búsqueda en el Texto

El algoritmo desliza una ventana de tamaño lmin = 3 a lo largo del texto.

  1. Inicio: El texto es "EL TESORO ESCONDIDO CONTENÍA ORO Y PLATA..."
  2. La ventana se posiciona al principio.
  3. Compara el final de la ventana con el oráculo. No encuentra coincidencia.

  4. El oráculo indica un salto.

  5. Primera coincidencia ("ORO"):

  6. Cuando la ventana llega a "CONTENÍA **ORO** Y PLATA.", el algoritmo escanea la ventana de derecha a izquierda (leyendo O, R, O).
  7. El Oráculo de Factores reconoce la secuencia "ORO".
  8. Se activa la Verificación. El algoritmo comprueba los patrones completos en F(Current) (que incluiría "ORO") contra el texto. Confirma "ORO".
  9. Coincidencia encontrada "ORO" en la posición 25.

  10. El salto es de 1 para buscar superposiciones.

  11. Segunda Coincidencia ("PLATA"):

  12. La ventana se desplaza.
  13. Cuando la ventana cubre "Y **PLA**TA. UN...", el escaneo hacia atrás (leyendo A, L, P) coincide con "ALP" en el oráculo.
  14. Se activa la Verificación. El algoritmo comprueba los patrones en F(Current) (que incluiría "PLATA") contra el texto y confirma la coincidencia completa de "PLATA".
  15. Coincidencia encontrada "PLATA" en la posición 31.

  16. El salto es de 1.

  17. Tercera Coincidencia ("ORO"):

  18. La ventana se desplaza.
  19. Llega a "...ANILLO DE **ORO** CON UN...", el oráculo reconoce "ORO" (leyendo O, R, O hacia atrás).
  20. Se activa la Verificación. Confirma "ORO".
  21. Coincidencia encontrada "ORO" en la posición 46.

  22. El salto es de 1.

  23. Cuarta Coincidencia ("DIAMANTE"):

  24. La ventana se desplaza.
  25. En "...CON UN **DIA**MANTE...", el escaneo hacia atrás (leyendo A, I, D) coincide con "AID" en el oráculo.
  26. Se activa la Verificación. El algoritmo comprueba los patrones en F(Current) (que incluiría "DIAMANTE") y confirma la coincidencia completa de "DIAMANTE".
  27. Coincidencia encontrada "DIAMANTE" en la posición 53.
  28. El salto es de 1.

3. Implementación del Algoritmo

Aqui se muestra una implementacion de SBOM en python. Notar que esta implementacion contiene un error en el calculo de los saltos o shifts, por ello, en esta seccion se explica el funcionamiento correcto del algoritmo en pseudocodigo.

class FactorOracle:
    """Oráculo de Factores para reconocimiento de subcadenas"""

    def __init__(self):
        self.states = [{}]  # Lista de diccionarios de transiciones
        self.supply = [None]  # Supply function (enlaces de fallo)
        self.terminal = [False]  # Estados terminales
        self.labels = [""]  # Etiquetas de estados (cadenas que representan)
        self.pattern_indices = [[]]  # Índices de patrones asociados a cada estado

    def add_state(self, label="", is_terminal=False, pattern_idx=None):
        """Agrega un nuevo estado al oráculo"""
        state_id = len(self.states)
        self.states.append({})
        self.supply.append(None)
        self.terminal.append(is_terminal)
        self.labels.append(label)

        if pattern_idx is not None:
            self.pattern_indices.append([pattern_idx])
        else:
            self.pattern_indices.append([])

        return state_id

    def add_transition(self, from_state, char, to_state):
        """Agrega una transición entre estados"""
        self.states[from_state][char] = to_state

    def get_transition(self, state, char):
        """Obtiene el estado destino de una transición"""
        return self.states[state].get(char, None)


def build_trie(reversed_patterns):
    """
    Construye un Trie con los patrones invertidos
    Retorna el oráculo y un mapeo de estados terminales a índices de patrones
    """
    oracle = FactorOracle()

    for pattern_idx, pattern in enumerate(reversed_patterns):
        current_state = 0

        # Use enumerate to correctly handle repeated characters in the pattern
        for i, char in enumerate(pattern):
            next_state = oracle.get_transition(current_state, char)

            if next_state is None:
                # Crear nuevo estado
                next_state = oracle.add_state(
                    label=oracle.labels[current_state] + char,
                    is_terminal=False,
                    pattern_idx=None
                )
                oracle.add_transition(current_state, char, next_state)

            current_state = next_state

        # Marcar el último estado como terminal y asociar el índice del patrón
        oracle.terminal[current_state] = True
        if pattern_idx not in oracle.pattern_indices[current_state]:
            oracle.pattern_indices[current_state].append(pattern_idx)

    return oracle


def compute_supply_function(oracle):
    """
    Calcula la función Supply (similar a enlaces de fallo en Aho-Corasick)
    Para cada estado, encuentra el sufijo propio más largo
    """
    oracle.supply[0] = -1  # El supply del estado inicial es θ (representado como -1)

    # BFS para calcular supply de cada estado
    queue = [0]
    visited = {0}

    while queue:
        state = queue.pop(0)

        for char, next_state in oracle.states[state].items():
            if next_state not in visited:
                visited.add(next_state)
                queue.append(next_state)

                # Calcular supply para next_state
                # Buscar el sufijo propio más largo
                label = oracle.labels[next_state]
                supply_state = 0

                for i in range(1, len(label)):
                    suffix = label[i:]
                    temp_state = 0
                    found = True

                    for c in suffix:
                        temp_state = oracle.get_transition(temp_state, c)
                        if temp_state is None:
                            found = False
                            break

                    if found and temp_state != next_state:
                        supply_state = temp_state

                oracle.supply[next_state] = supply_state


def add_external_transitions(oracle):
    """
    Agrega transiciones externas siguiendo el supply path
    Esto hace que el oráculo reconozca todos los factores
    """
    for state in range(len(oracle.states)):
        alphabet = set()

        # Recolectar todos los caracteres posibles
        for s in range(len(oracle.states)):
            alphabet.update(oracle.states[s].keys())

        for char in alphabet:
            if oracle.get_transition(state, char) is None:
                # Buscar en el supply path
                current = oracle.supply[state]

                while current is not None and current >= 0:
                    target = oracle.get_transition(current, char)
                    if target is not None:
                        oracle.add_transition(state, char, target)
                        break
                    current = oracle.supply[current] if current >= 0 else None


def build_factor_oracle(reversed_patterns):
    """Construye el oraculo de factores completo"""
    oracle = build_trie(reversed_patterns)
    compute_supply_function(oracle)
    add_external_transitions(oracle)
    return oracle


def verify_pattern(pattern, text, pos):
    """Verifica si un patrón completo está en el texto en la posición dada"""
    if pos + len(pattern) > len(text):
        return False

    for i in range(len(pattern)):
        if text[pos + i] != pattern[i]:
            return False

    return True


def sbom_search(text, patterns):
    if not patterns:
        return []

    #Preprocesamiento
    lmin = min(len(p) for p in patterns)

    # Tomar prefijos de longitud lmin e invertirlos
    reversed_prefixes = []
    for pattern in patterns:
        prefix = pattern[:lmin]
        reversed_prefix = prefix[::-1]
        reversed_prefixes.append(reversed_prefix)

    #Construir el oraculo
    oracle = build_factor_oracle(reversed_prefixes)

    # Búsqueda
    matches = []
    pos = 0
    n = len(text)

    while pos <= n - lmin:
        current_state = 0
        j = lmin

        #Escanear hacia atrás
        while j >= 1 and current_state is not None:
            char = text[pos + j - 1]  # Ajuste de índice (j-1 para 0-indexing)
            current_state = oracle.get_transition(current_state, char)
            j -= 1

        #Verificar si se leyó la ventana completa
        if current_state is not None:
            supply_state = current_state
            found_any = False

            while supply_state is not None and supply_state >= 0:
                for pattern_idx in oracle.pattern_indices[supply_state]:
                    pattern = patterns[pattern_idx]
                    if verify_pattern(pattern, text, pos):
                        matches.append((pattern, pos))
                        found_any = True

                supply_state = oracle.supply[supply_state] if supply_state >= 0 else None

            #Si encontramos alguna coincidencia, permitir superposición mínima
            if found_any:
                pos += 1
                continue

        #Modo conservador: avanzar una posición para no omitir coincidencias.
        #Es la opción más segura aunque incorrecta en base a el funcionamiento real del algoritmo, deberia calcular un salto "inteligente".
        pos += 1

    return matches

A. Construcción Detallada del Oráculo

  1. Construir el Trie: Se crea un trie (OR_trie) con los inversos de los prefijos de longitud lmin de todos los patrones (ej. {"ORO", "ALP", "AID"})
  2. Estados corresponden a prefijos de los patrones invertidos

  3. Estados terminales marcan patrones completos

  4. Calcular función Supply (S_OR): Para cada estado, se calcula su "supply state"

  5. Es el estado que representa el sufijo propio más largo
  6. Similar a los enlaces de fallo en Aho-Corasick

  7. El supply del estado inicial es θ (vacío)

  8. Agregar transiciones externas:

  9. Para cada estado q y cada carácter σ:
  10. Si no existe transición directa desde q con σ:
  11. Se busca en el supply path hasta encontrar una transición con σ
  12. Se crea una transición externa desde q hasta el destino encontrado

B. Algoritmo de Búsqueda

funcion SBOM_Buscar(Texto T, ConjuntoPatrones P):
    // --- Preprocesamiento ---
    // Obtener la longitud del patrón más corto
    lmin = longitud_minima(P)

    // Construir el Oráculo con los prefijos invertidos de longitud lmin
    Oraculo = construir_Oraculo_Multiple(prefijos_invertidos(P, lmin))

    // Mapear estados finales a los índices de patrones originales
    F = mapear_estados_a_patrones(Oraculo, P, lmin)

    // --- Búsqueda ---
    pos = 0 // El puntero 'pos' es el *inicio* de la ventana
    n = longitud(T)

    // El bucle principal se mueve hasta que la ventana de 'lmin' ya no cabe
    mientras pos <= n - lmin:
        Actual = Oraculo.estado_inicial()
        j = lmin // 'j' es el puntero de lectura, empieza al final de la ventana

        // Escanear hacia atrás (desde pos+lmin hasta pos+1)
        mientras j >= 1 Y Actual != NULO:
            // Leer el texto de derecha a izquierda: t[pos+j]
            Actual = Oraculo.transicion(Actual, T[pos + j])
            j = j - 1 // Mover el puntero de lectura hacia la izquierda

        // fin mientras (escaneo)

        // Comprobar si se leyó la ventana completa sin fallar
        si Actual != NULO Y j == 0 Y T[pos+1...pos+lmin] == L(Actual).reversa: //

            // VERIFICACIÓN MANUAL OBLIGATORIA
            // El Oráculo solo garantiza un factor, no un patrón completo.
            para patron_indice en F[Actual]:
                si verificar_patron_en_texto(P[patron_indice], T, pos):
                    reportar_coincidencia(P[patron_indice], pos)

            // Salto de 1 para buscar superposiciones
            j = 1 //

        // fin si

        // Calcular el salto
        // Si hubo coincidencia verificada, j=1 (salto de 1).
        // Si hubo fallo, 'j' tiene el punto del fallo (salto más grande).
        pos = pos + j

    // fin mientras (búsqueda)

Verificación de Coincidencias Completas

Un aspecto crucial del SBOM es que el oráculo de factores reconoce factores (subcadenas) pero no garantiza que sean prefijos de patrones completos.

El hecho de que el oráculo reconozca una secuencia y que esta coincida con la etiqueta del oráculo (T[...] == L(Actual).reversa) no es suficiente.

El algoritmo aún debe realizar la Verificación Manual :

  • Para cada índice i en F(Current) (los patrones asociados a ese estado):
  • Comparar el patrón completo pⁱ (ej. "DIAMANTE") contra el texto en la pos actual.
  • Reportar solo si hay coincidencia exacta.

Razón: El oráculo puede aceptar caminos de longitud lmin que terminan en estados terminales pero que no corresponden a ningún prefijo de los patrones originales. La verificación explícita previene falsos positivos.

4. Referencias y Lecturas Adicionales

Libros

  • [Navarro & Raffinot, 2002] Navarro, G., & Raffinot, M. (2002). Flexible Pattern Matching in Strings: Practical On-Line Search Algorithms for Texts and Biological Sequences. Cambridge University Press.

Recursos Adicionales y Tutoriales