Saltar a contenido

Fast Regular Expression Search

El algoritmo Fast Regular Expression Search (Navarro y Raffinot, 1999) extiende las ideas de Boyer–Moore a la búsqueda de expresiones regulares completas. En lugar de comparar carácter a carácter, construye un autómata finito que representa la expresión regular y un segundo autómata de filtrado, basado en los prefijos invertidos de las posibles coincidencias más cortas. Este autómata de filtro se utiliza para analizar el texto de derecha a izquierda, permitiendo saltar grandes secciones donde ningún match es posible, reduciendo así el número de comparaciones.

Un ejemplo muy concreto en el que podemos hacer uso de este algoritmo es cuando se desonce una parte concreta del patrón a buscar:

  • Concepcion o Concepción? -> Concepci?n

Boyer-Moore

El algoritmo de Boyer–Moore (1977) no compara carácter por carácter de izquierda a derecha, sino que examina el patrón desde el final hacia el principio y aprovecha la información de los fallos para saltar varias posiciones del texto, evitando comparaciones innecesarias. Para decidir cuánto avanzar, utiliza dos heurísticas: la de carácter erróneo (bad character rule), que alinea la última aparición del carácter que causó el fallo, y la de sufijo bueno (good suffix rule), que aprovecha coincidencias parciales al final del patrón.

Gracias a estas reglas de salto, Boyer–Moore logra una complejidad promedio sublineal, ya que en la práctica inspecciona muchos menos caracteres que los métodos ingenuos. Es el fundamento de varios algoritmos modernos de búsqueda y sus variantes simplificadas (como Horspool y Sunday), y su principio también inspira enfoques más avanzados, como la búsqueda rápida de expresiones regulares y de múltiples patrones.

Funcionamiento

En Fast Regular Expression Search, cuando el filtro detecta una zona potencialmente válida, el algoritmo ejecuta una verificación exacta con el autómata principal de la expresión regular para confirmar la coincidencia. Esta estrategia de “filtro y verificación” permite mantener la corrección completa del reconocimiento de expresiones regulares, pero con un rendimiento mucho más alto: en su peor caso el algoritmo tarda O(n*m) pero en promedio, el tiempo de búsqueda es lineal en el tamaño del texto y sublineal en la práctica, lo que convierte a este método en una de las formas más eficientes de búsqueda de patrones complejos en grandes volúmenes de datos.

Datos de entrada

  • Regex RRR sobre alfabeto Σ.
  • Texto T de tamaño n.

Preprocesamiento

  1. Construir un autómata para la regex
  2. El algoritmo asume que tienes un autómata finito (típicamente un DFA) que reconoce \(L(R)\).
  3. Longitud mínima de match ℓ\ellℓ
  4. Lenguaje de prefijos invertidos:
  5. Se crea un automata que reconoce el lenguaje invertido
  6. Esto es lo que permite hacer un “Boyer–Moore inverso” sobre el texto.
  7. Cómo construir ese autómata: Inviertes las direcciones de las transiciones. Desde los estados “finales originales” miras caminos hacia atrás de longitud hasta ℓ, y te quedas solo con el subgrafo que alcanza el estado inicial original en ≤ℓ pasos.
  8. Información adicional: shifts por estado
  9. Fase de búsqueda en el texto
  10. Ventana y recorrido: Usamos una ventana de tamaño ℓ que se “apoya” en una posición del texto.
  11. Termina cuando i>n.
  12. Verifica con el automata principal

Pseudocódigo

function PREPROCESS(R):
  A ← BUILD_AUTOMATON(R)
  ℓ ← MIN_ACCEPT_LENGTH(A)
  B ← BUILD_REVERSED_PREFIX_AUTOMATON(A, ℓ)
  SHIFT ← COMPUTE_SHIFT_TABLE(B, ℓ)
  return (A, B, SHIFT, ℓ)

function MIN_ACCEPT_LENGTH(A):
  for q in Q(A): dist[q] ← +∞
  dist[q0(A)] ← 0
  Qe ← queue(q0(A))
  while Qe not empty:
    u ← pop(Qe)
    for each a ∈ Σ(A), v = δ(A,u,a):
      if dist[v] > dist[u] + 1:
        dist[v] ← dist[u] + 1
        push(Qe,v)
  return min(dist[f] for f in F(A))

function BUILD_REVERSED_PREFIX_AUTOMATON(A, ℓ):
  AR ← REVERSE_AUTOMATON(A)
  BR ← BFS_TRUNCATE(AR, ℓ)
  B  ← DETERMINIZE_AND_MINIMIZE(BR)
  return B

function COMPUTE_SHIFT_TABLE(B, ℓ):
  for s in STATES(B):
    longest ← MAX_SUFFIX_LENGTH_LEADING_TO_ACCEPT(B, s, ℓ)
    SHIFT[s] ← max(1, ℓ - longest)
  return SHIFT

function RUN_AUTOMATON_FORWARD(A, T, start):
  q ← q0(A)
  pos ← start
  ends ← []
  while pos ≤ |T|:
    q ← δ(A, q, T[pos])
    if q ∈ F(A): append(ends, pos)
    pos ← pos + 1
  return ends

function FAST_REGEX_SEARCH(R, T):
  (A, B, SHIFT, ℓ) ← PREPROCESS(R)
  Occ ← []
  if ℓ = +∞: return Occ
  i ← ℓ
  while i ≤ |T|:
    s ← START_STATE(B)
    j ← i
    read ← 0
    while read < ℓ and TRANSITION_EXISTS(B, s, T[j]):
      s ← NEXT(B, s, T[j])
      j ← j - 1
      read ← read + 1
    if read = ℓ or STATE_IS_PREFIX_POSSIBLE(B, s):
      start ← i - ℓ + 1
      for e in RUN_AUTOMATON_FORWARD(A, T, start):
        append(Occ, (start, e))
    i ← i + SHIFT[s]
  return Occ

Implementación

Como el objetivo de esta explicación no es profundizar específicamente en la generación y uso de autómatas, se realiza una simplificación en la que el autómata simplemente consiste en un character simbolizado por "?" que puede corresponder a cualquier letra del alfabeto. De esta manera el autómata que reconoce el inverso es la palabra invertida con el character "?".

#include <bits/stdc++.h>
using namespace std;

vector<size_t> fast_search(const string &text, const string &pattern) {
    const int ALPHA = 256;
    int n = (int)text.size();
    int m = (int)pattern.size();

    vector<size_t> matches;
    if (m == 0 || n < m) return matches;

    vector<int> ultima_aparicion_char(ALPHA, -1);
    int ult_aparicion_comidin = -1;

    for (int i = 0; i < m; ++i) {
        if (pattern[i] == '?') {
            ult_aparicion_comidin = i;
        } else {
            unsigned char c = (unsigned char)pattern[i];
            ultima_aparicion_char[c] = i;
        }
    }

    vector<int> uitlima_aparicion_efectiva(ALPHA);
    for (int c = 0; c < ALPHA; ++c)
        uitlima_aparicion_efectiva[c] = max(ultima_aparicion_char[c], ult_aparicion_comidin);

    int i = m - 1;
    while (i < n) {
        int j = i;
        int k = m - 1;
        while (k >= 0 && (pattern[k] == '?' || pattern[k] == text[j])) {
            --k;
            --j;
        }

        if (k < 0) {
            matches.push_back((size_t)(i - m + 1));
            i += 1;
        } else {
            unsigned char c = (unsigned char)text[j];
            int shift = k - uitlima_aparicion_efectiva[c];
            if (shift < 1) shift = 1;
            i += shift;
        }
    }

    return matches;
}

int main() {
    string text = "Born to Run is the third studio album by the American singer-songwriter Bruce Springsteen, released on August 25, 1975, by Columbia Records - Born to Rin - Born to Ran ";
    string pattern = "Born to R?n";  // el '?' actúa como comodín

    auto matches = fast_search(text, pattern);

    cout << "Texto:   " << text << "\n";
    cout << "Patron:  " << pattern << "\n\n";
    cout << "Matches encontrados en posiciones (desde 0):\n";

    for (size_t pos : matches)
        cout << " - en posicion " << pos
             << " -> \"" << text.substr(pos, pattern.size()) << "\"\n";

    return 0;
}

Ejemplo

Texto = "a b x c d x x a b y d z a b z d" patron = "a b ? d"

  • Comienza la comparación en i = l (en el caso de este automata l = m):

1

  • Se realiza un salto del tamaño del sufijo del patrón (usando automata invertido):

2

  • Al encontrar la coincidencia informa la ubicación del inicio del patron en el texto:

3

  • Reporta

4

Matches encontrados en posiciones (desde 0):
 - en posicion 7 -> "abydef"
 - en posicion 14 -> "abzdef"

Referencias