Saltar a contenido

Múltiple Shift-And

Contexto de la Búsqueda de Patrones

El problema de la búsqueda de patrones es fundamental en la informática teórica y aplicada, consistiendo en localizar ocurrencias de uno o más patrones (\(P\)) dentro de un texto extenso (\(T\)). La eficiencia algorítmica es crítica, especialmente con el auge del Big Data en campos como la minería de datos, los sistemas de búsqueda y la bioinformática.

En el dominio de los algoritmos de búsqueda, el término "múltiple" se refiere a la capacidad de encontrar un conjunto de patrones (\(P = \{p_1, p_2,..., p_k\}\)) de forma simultánea. El "Algoritmo Múltiple Shift-And" se enmarca en este contexto.

Definición del Algoritmo

Para entender el algoritmo múltiple, primero tenemos que entender el algoritmo de búsqueda para un solo patrón a la vez. Shift-And opera mediante la simulación de un Autómata Finito No Determinista (AFND). Cada estado del autómata se codifica como un bit en un vector de bits.

La base de su funcionamiento es el bit-paralelismo, que utiliza operaciones a nivel de bit (bitwise operations) para simular múltiples cálculos simultáneamente en una única palabra de máquina (32 o 64 bits).

Operaciones Fundamentales

El algoritmo utiliza dos operaciones clave para actualizar el vector de estado (\(D\)):

  1. Corrimiento a la Izquierda (<<): Simula el avance del proceso de búsqueda, desplazando la "ventana" de coincidencia potencial una posición.
  2. Operación AND (&): Actúa como un filtro. El vector de estado desplazado se combina con una máscara de bits precomputada (\(B[T[j]]\)) específica para el carácter \(T[j]\), descartando los estados que no coinciden.

Fórmula de Actualización (Shift-And)

Para cada carácter \(T[j]\) del texto:

\[ D \leftarrow ((D \ll 1) + 1) \& B[T[j]] \]

Donde \(D\) tendrá el i-ésimo bit en 1 si y solo si el prefijo de largo i del patrón P coincide con el sufijo del actual prefijo de T. Tendrá el i-ésimo bit en 0 en otro caso.

La alternativa Shift-Or

Así como Shift-And ocupa la operación lógica \(And\), existe su versión ocupando \(Or\), el cuál evita tener que sumarle 1 a \(D\) a cambio de ocupar los bits al contrario, es decir, \(D\) tendrá el i-ésimo bit en 0 si y solo si el prefijo de largo i del patrón P coincide con el sufijo del actual prefijo de T. Tendrá el i-ésimo bit en 1 en otro caso.

El Algoritmo Wu-Manber (Generalización Múltiple)

El algoritmo de Wu-Manber es un ejemplo práctico del enfoque "múltiple shift-and". Es un algoritmo híbrido que combina las heurísticas de salto del algoritmo de Boyer-Moore con el bit-paralelismo del Shift-And para buscar múltiples patrones simultáneamente.

  • Estrategia: Las heurísticas de salto actúan como un filtro de alta eficiencia, y el bit-paralelismo se usa para verificar las coincidencias de forma ultrarrápida.
  • Estructuras Auxiliares:
  • Tabla SHIFT: Almacena la distancia de salto basada en bloques de \(B\) caracteres.
  • Tabla HASH: Asocia el valor hash de un bloque de \(B\) caracteres con los patrones que lo contienen.
  • Vectores de Bits (\(U(x)\)): Un vector de bits por carácter del alfabeto que indica dónde aparece ese carácter en la concatenación de patrones.

Complejidades Algorítmicas

El análisis de la complejidad es crucial para entender el rendimiento. El verdadero valor del Shift-And y sus variantes se revela en el rendimiento promedio.

Búsqueda de un solo Patrón (Shift-And Puro)

Aspecto Complejidad Condición
Preprocesamiento \(O(\sigma + m)\) \(\sigma\) es el tamaño del alfabeto, \(m\) es la longitud del patrón.
Búsqueda (Mejor Caso) \(O(n)\) Si la longitud del patrón \(m\) no excede el tamaño de la palabra de máquina \(w\) (\(m \leq w\)).
Búsqueda (Peor Caso) \(O(n \lceil m/w \rceil)\) Si \(m > w\), lo que demuestra la limitación del bit-paralelismo puro.

Búsqueda de Múltiples Patrones (Wu-Manber)

Aspecto Complejidad Nota
Peor Caso \(O(nm)\) Similar a la fuerza bruta.
Rendimiento Promedio Se acerca a \(O(n/B)\) \(B\) es el tamaño del bloque. El uso de heurísticas de salto permite omitir la mayoría de las comparaciones, lo que lo hace excepcionalmente rápido en la práctica.

Ejemplo de Uso

La implementación del Shift-And se basa en el uso eficiente de operaciones a nivel de hardware (bit-paralelismo) para simular el avance del autómata en un solo ciclo de reloj por carácter de texto.

Para empezar, el primer paso consta de:

Hacer una bitmask para cada palabra

std::map<char, std::vector<bool>> b;
int l = p.size();

// Inicializar la tabla
for (int i = 0; i < l; ++i) {
    char c = p[i];
    if (b.find(c) == b.end())
        b[c] = std::vector<bool>(l, false);
}

// Construir las máscaras de bits
for (int i = 0; i < l; ++i) {
    char c = p[i];
    b[c][i] = true;
}

Por ejemplo para el patrón alabar en su bit mask de "a" marcamos con un 1 las posiciones de la letra respectiva y marcamos un 0 si no tiene esa letra en las demás posiciones (esto se debe hacer por cada letra del patrón, para cada patrón buscado si queremos hacer el multiple shift-and), por lo que sus bit masks se verían así:

//Por conveniencia los guardamos al revez
var B = {
    'a' = 010101,
    'l' = 000010,
    'b' = 001000,
    'r' = 100000,
    '*' = 000000
}

Podemos apreciar que se añadió una máscara para el carácter '*', esa máscara se utilizará para todas las letras que no coincidan con ninguna de nuestro patrón.

El vector de estado (\(D\)) del algoritmo se actualiza con una generalización de la fórmula original, lo que permite seguir el rastro de la coincidencia para todos los patrones simultáneamente. Cabe destacar que \(D\) también se encuentra al revez.

Luego, iteramos por cada carácter de T, desde la posición 1 hasta n. En cada paso i (\(1 \leq i \leq n\)) actualizamos \(D\) en tiempo \(O(1)\)

  • Primero, hacemos shift a \(D\) a la izquierda por 1 (cualquier coincidencia de largo k en el paso anterior tiene el potencial de convertise en una coincidencia de largo k+1 en este paso).
  • Luego, el bit más a la derecha de \(D\) se fija en 1 (Podría haber una nueva coincidencia de largo 1).
  • Finalmente, aplicamos un \(AND\) a \(D\) y \(B\)[el i-ésimo carácter en T] (Para cualquier coincidencia de largo k en el paso anterior, es extendida a una coincidencia de largo k+1 si y solo si el k+1-ésimo carácter del patrón \(P\) coincide con el i-ésimo carácter del texto \(T\))
\[D \leftarrow ((D \ll 1) + 1) \& B[T[j]]\]

Para el texto "alabar a la alabarda" y el patrón "alabar" con Shift-And

Paso 1 Examinando el prefijo de T: "a"

\[ T[j] = "a" $$ $$ D = "000000" \]
\[ D = ((D \ll 1) + 1) \& B["a"] = "000001" AND "010101" = "000001" \]

Solo el ultimo bit de \(D\) es 1, significando que solo el prefijo de largo 1 de P coincide con el sufijo del actual prefijo de T.

Paso 2 Examinando el prefijo de T: "al"

\[ T[j] = "l"$$ $$ D = "000001" \]
\[ D = ((D \ll 1) + 1) \& B["l"] = "000011" AND "000010" = "000010" \]

El penúltimo bit de \(D\) es 1, lo que significa que el prefijo de largo 2 de P coincide con el sufijo del actual prefijo de T.

Paso 3 Examinando el prefijo de T: "ala"

\[ T[j] = "a" $$ $$ D = "000010" \]
\[ D = ((D \ll 1) + 1) \& B["a"] = "000101" AND "010101" = "000101" \]

Los prefijos de largo 1 y largo 3 de P coinciden con el sufijo del actual prefijo de T.

Paso 4 Examinando el prefijo de T: "alab"

\[ T[j] = "b" $$ $$ D = "000101" \]
\[ D = ((D \ll 1) + 1) \& B["b"] = "001011" AND "001000" = "0010000" \]

El prefijo de largo 5 de P coincide con el sufijo del actual prefijo de T.

Paso 5 Examinando el prefijo de T: "alaba"

\[ T[j] = "a" $$ $$ D = "0010000" \]
\[ D = ((D \ll 1) + 1) \& B["a"] = "0100001" AND "010101" = "0100001" \]

Los prefijos de largo 1 y largo 6 de P coinciden con el sufijo del actual prefijo de T.

Paso 6 Examinando el prefijo de T: "alabar"

\[ T[j] = "r" $$ $$ D = "0100001" \]
\[ D = ((D \ll 1) + 1) \& B["r"] = "1000011" AND "100000" = "100000" \]

Ahora, el valor de \(D\) queda tal que:

\[ D = "100000" \]

En este paso, como el primer bit de \(D\) está fijado en 1, hemos encontrado una ocurrencia de P dentro de T.

Paso 7 Examinando el prefijo de T: "labar "

\[T[j] = "­ㅤ­"\]
\[D = "100000"\]
\[D = ((D \ll 1) + 1) \& B["ㅤ"] = "0000001" AND "000000" = "000000"\]

No hay ningún prefijo de P que coincida con el sufijo del actual prefijo de T.

Paso 8 Examinando el prefijo de T: "abar a"

\[T[j] = "a"\]
\[D = "000000"\]
\[D = ((D \ll 1) + 1) \& B["a"] = "0000001" AND "010101" = "000001"\]

El prefijo de largo 1 de P coincide con el sufijo del actual prefijo de T.

Paso 9 Examinando el prefijo de T: "bar a "

\[T[j] = "ㅤ"\]
\[D = "000001"\]
\[D = ((D \ll 1) + 1) \& B["ㅤ"] = "0000011" AND "000000" = "000000"\]

No hay ningún prefijo de P que coincida con el sufijo del actual prefijo de T.

Paso 10 Examinando el prefijo de T: "ar a l"

\[T[j] = "l"\]
\[D = "000000"\]
\[D = ((D \ll 1) + 1) \& B["l"] = "000001" AND "000010" = "000000"\]

No hay ningún prefijo de P que coincida con el sufijo del actual prefijo de T.

Paso 11 Examinando el prefijo de T: "r a la"

\[T[j] = "a"\]
\[D = "000000"\]
\[D = ((D \ll 1) + 1) \& B["a"] = "000001" AND "010101" = "000001"\]

El prefijo de largo 1 de P coincide con el sufijo del actual prefijo de T.

Paso 12 Examinando el prefijo de T: " a la "

\[T[j] = "ㅤ"\]
\[D = "000001"\]
\[D = ((D \ll 1) + 1) \& B["ㅤ"] = "000011" AND "000000" = "000000"\]

No hay ningún prefijo de P que coincida con el sufijo del actual prefijo de T.

Paso 13 Examinando el prefijo de T: "a la a"

\[T[j] = "a"\]
\[D = "000000"\]
\[D = ((D \ll 1) + 1) \& B["a"] = "000001" AND "010101" = "000001"\]

El prefijo de largo 1 de P coincide con el sufijo del actual prefijo de T.

Paso 14 Examinando el prefijo de T: " la al"

\[T[j] = "l"\]
\[D = "000001"\]
\[D = ((D \ll 1) + 1) \& B["l"] = "000011" AND "000010" = "000010"\]

El prefijo de largo 2 de P coincide con el sufijo del actual prefijo de T.

Paso 15 Examinando el prefijo de T: "la ala"

\[T[j] = "a"\]
\[D = "000010"\]
\[D = ((D \ll 1) + 1) \& B["a"] = "000101" AND "010101" = "000101"\]

Los prefijos de largo 1 y largo 3 de P coinciden con el sufijo del actual prefijo de T.

Paso 16 Examinando el prefijo de T: "a alab"

\[T[j] = "b"\]
\[D = "000101"\]
\[D = ((D \ll 1) + 1) \& B["b"] = "001011" AND "001000" = "001000"\]

El prefijo de largo 4 de P coincide con el sufijo del actual prefijo de T.

Paso 17 Examinando el prefijo de T: " alaba"

\[T[j] = "a"\]
\[D = "001000"\]
\[D = ((D \ll 1) + 1) \& B["a"] = "010001" AND "010101" = "010001"\]

Los prefijos de largo 1 y largo 5 de P coinciden con el sufijo del actual prefijo de T.

Paso 18 Examinando el prefijo de T: "alabar"

\[T[j] = "r"\]
\[D = "010001"\]
\[D = ((D \ll 1) + 1) \& B["r"] = "100011" AND "100000" = "100000"\]

Nuevamente, el valor de \(D\) queda tal que:

\[D = "100000"\]

En este paso, como el primer bit de \(D\) está fijado en 1, hemos encontrado una segunda ocurrencia de P dentro de T.

Paso 19 Examinando el prefijo de T: "labard"

\[T[j] = "d"\]
\[D = "100000"\]
\[D = ((D \ll 1) + 1) \& B["d"] = "000001" AND "000000" = "000000"\]

No hay ningún prefijo de P que coincida con el sufijo del actual prefijo de T.

Paso 20 Examinando el prefijo de T: "abarda"

\[T[j] = "a"\]
\[D = "000000"\]
\[D = ((D \ll 1) + 1) \& B["a"] = "000001" AND "010101" = "000001"\]

El prefijo de largo 1 de P coincide con el sufijo del actual prefijo de T.

Todo este algoritmo se puede generalizar para poder alcanzar el Multiple shift-and, donde en cada paso se revisarán todas las máscaras respectivas de cada \(P = \{p_1, p_2,..., p_k\}\), por lo que en cada paso se harán \(k\) operaciones que cuestan \(O(1)\), resultando en total cada paso \(O(k)\), pero como \(k\) es constante, puede ser simplificado a \(O(1)\) si y solo si \(k\) < palabra de máquina.

Aqui se puede apreciar un video más gráfico de como funciona Shift-And:

El algoritmo Wu-Manber aplica un enfoque de filtrado y verificación.

Etapas del Algoritmo

  1. Preprocesamiento: Se construyen las tablas SHIFT y HASH basadas en bloques de caracteres (\(B\)) de los patrones.
  2. Escaneo: El algoritmo escanea el texto en pasos de tamaño \(B\).
  3. Utiliza la Tabla SHIFT para determinar cuánto avanzar, permitiendo saltos largos en porciones del texto que no pueden contener una coincidencia.
  4. Si se encuentra un bloque que podría ser el final de una ocurrencia, se pasa a la fase de verificación.
  5. Verificación Bit-Paralela: Se utiliza el principio del Shift-And con los Vectores de Bits (\(U(x)\)) para confirmar la coincidencia completa del patrón de forma ultrarrápida.

El algoritmo simula un único AFND que acepta cualquiera de los patrones del conjunto, rastreando la coincidencia de todos ellos simultáneamente.

Usos Comunes

Los algoritmos de búsqueda de múltiples patrones, en particular el Wu-Manber, tienen aplicaciones críticas donde la velocidad es esencial:

  1. Bioinformática y Genómica: El genoma se trata como un texto gigantesco. Estos algoritmos son esenciales para encontrar secuencias de ADN o ARN, genes, y otras regiones reguladoras. Se utilizan en clústeres de computación de alto rendimiento (HPC) para procesar datos a escala genómica (RNA-Seq y multi-omics).
  2. Redes y Seguridad: Requeridos para la detección de firmas de virus y patrones de intrusión en el tráfico de red a alta velocidad.
  3. Procesamiento de Texto a Gran Escala: Son la base de herramientas de línea de comandos de búsqueda como fgrep y agrep, permitiendo la búsqueda simultánea de miles de patrones en grandes archivos de texto.

Implementación

Multiple Shift-And

/**
* string text: Texto en el que se realizara la búsqueda
* vector<string> patron: Vector que contiene a todos los patrones buscados
**/

void multiple_shift_and(const std::string& text, const std::vector<std::string>& patron) {
int n = text.size();
std::vector<std::map<char, std::vector<bool>>> masks(patron.size());

//Construimos las mascaras para cada patron
for (size_t k = 0; k < patron.size(); ++k) {
    const std::string& p = patron[k];
    int m = p.size();

    // Para cada caracter del patrón
    for (int i = 0; i < m; ++i) {
        char c = p[i];

        // Si no existe la mascara para este caracter, crearla con 'false'
        if (masks[k].find(c) == masks[k].end()) {
            masks[k][c] = std::vector<bool>(m, false);
        }

        // Activar el bit correspondiente a la posición
        masks[k][c][m - i - 1] = true; //Orden invertido de la mascara
    }
}

//Establecemos los D iniciales para cada patron
std::vector<std::vector<bool>> D(patron.size());
    for (size_t k = 0; k < patron.size(); ++k) {
        D[k] = std::vector<bool>(patron[k].size(), false);
    }

    //Empezamos a recorrer el texto
    for (size_t j = 0; j < n; j++){
        char c = text[j];

        for (size_t k = 0; k < patron.size(); ++k){
            const std::string& p = patron[k];
            int m = p.size();
            std::vector<bool> nuevo_D(m, false);

            //Cargamos la mascara del caracter actual
            auto it = masks[k].find(c);
            std::vector<bool> mask_bits = (it != masks[k].end() ? it->second : std::vector<bool>(m,false));

            for (int i = 0; i < m - 1; ++i) {
                nuevo_D[i] = D[k][i + 1]; //Esto representa nuestro (D << 1)
            }
            nuevo_D[m - 1] = true; //Esto representa sumarle 1 a (D << 1)

            for (int i = 0; i < m; ++i) {
                nuevo_D[i] = nuevo_D[i] && mask_bits[i]; //Aplicamos el AND entre D y cada máscara correspondiente
            }
            D[k] = nuevo_D;

            //Si el ultimo bit esta activo, hay coincidencia e imprimimos su posicion
            if (D[k][0]) {
                std::cout << "Patrón \"" << p << "\" encontrado en posición " << static_cast<int>(j) - m + 1 << std::endl;
            }
        }

    }

}

Referencias