Saltar a contenido

Wu-Manber

Descripción

El algoritmo Wu-Manber, desarrollado por Sun Wu y Udi Manber en 1994, es una técnica avanzada de búsqueda de cadenas que se utiliza principalmente para encontrar múltiples patrones dentro de grandes volúmenes de texto. A diferencia de algoritmos como Boyer-Moore o Knuth-Morris-Pratt, que se centran en la búsqueda de un solo patrón, Wu-Manber está optimizado para manejar múltiples patrones simultáneamente, lo que lo hace ideal para aplicaciones como sistemas antivirus, motores de búsqueda y detección de intrusos en redes.

Definición

Wu-Manber es un algoritmo diseñado para realizar búsquedas eficientes de múltiples patrones en grandes volúmenes de texto. Su objetivo es identificar rápidamente si alguno de los patrones de un conjunto aparece en un texto, lográndolo mediante estructuras de datos precalculadas, como tablas de desplazamiento y funciones hash. Estas estructuras permiten al algoritmo realizar "saltos inteligentes" sobre el texto, evitando comparaciones innecesarias. Los principios fundamentales de su funcionamiento se basan en los siguientes conceptos:

Búsqueda Basada en Bloques

Búsqueda basada en bloques

En lugar de operar sobre caracteres individuales, el algoritmo procesa el texto y los patrones en bloques de un tamaño fijo B (típicamente B=2 o B=3). Trabajar con bloques aumenta la especificidad de las unidades de comparación. Por ejemplo, la probabilidad de encontrar el bloque "th" en un texto en inglés es mucho menor que la de encontrar el carácter individual 't'. Esta mayor especificidad reduce la probabilidad de coincidencias aleatorias y, en consecuencia, permite al algoritmo calcular saltos más largos y seguros.

Adaptación de la Heurística "Bad-Character Shift"

El algoritmo Wu-Manber es una variante del algoritmo Boyer-Moore que adapta la heurística del "carácter erróneo" para la coincidencia de múltiples patrones.

  • En el Boyer-Moore original, cuando se produce un desajuste entre un carácter del texto y un carácter del patrón, la heurística permite desplazar el patrón hacia la derecha hasta que el carácter del texto se alinee con su última aparición en el patrón.
  • Wu-Manber generaliza este principio: en lugar de basar el desplazamiento en un único carácter, lo basa en un bloque de B caracteres ubicado al final de la ventana de escaneo.
  • El algoritmo precalcula en una tabla SHIFT la distancia de desplazamiento segura para cada posible bloque de caracteres. Si un bloque del texto no aparece en ninguno de los patrones, el algoritmo puede realizar un salto máximo de m - B + 1 posiciones, donde m es la longitud del patrón más corto.

El Rol de m: La Longitud Mínima del Patrón

El algoritmo establece el tamaño de su ventana de escaneo en m, donde m es la longitud del patrón más corto del conjunto P. Esta decisión de diseño es crucial para la eficiencia del algoritmo por dos razones principales:

  1. Estandarización del Pre-procesamiento: Durante esta fase, solo se consideran los primeros m caracteres de cada patrón (sin importar su longitud real) para construir las tablas de búsqueda. Esto simplifica y estandariza el proceso de construcción de las tablas.
  2. Dependencia del Rendimiento: La longitud máxima de los saltos está directamente limitada por el valor de m. Si un conjunto de patrones contiene un patrón muy corto (por ejemplo, de longitud 2 o 3), el valor de m será pequeño, lo que resultará en desplazamientos cortos y una degradación significativa del rendimiento general, incluso si la mayoría de los otros patrones son largos. Por lo tanto, el uso de m como tamaño de ventana fijo simplifica el diseño, garantizando que la ventana sea siempre lo suficientemente grande para contener una coincidencia del patrón más corto, pero también introduce una dependencia crítica del rendimiento en la longitud de dicho patrón.

Paso a Paso

Fase de Pre-Procesamiento

Antes de que el algoritmo Wu-Manber pueda escanear un texto, debe "estudiar" los patrones que va a buscar. Esta fase de preparación, o pre-procesamiento, consiste en construir un conjunto de tablas que permitirán realizar los saltos rápidos y las verificaciones eficientes durante el escaneo. El objetivo es tomar un conjunto de patrones P y producir tres tablas: SHIFT, HASH y PREFIX.

Paso 1: Determinar Parámetros Clave (m y B)

Ejemplo 1

El algoritmo primero necesita establecer dos valores fundamentales:

  • Calcular m (Longitud Mínima): Se inspecciona todo el conjunto de patrones P y se encuentra la longitud del patrón más corto. Este valor se almacena como m.
  • Definir B (Tamaño de Bloque): Se escoge un tamaño de bloque, comúnmente B = 2 o B = 3.

Todas las operaciones siguientes se basarán en estos dos valores y considerarán solo los primeros m caracteres de cada patrón.

Paso 2: Construir la Tabla SHIFT

Tabla SHIFT

Esta tabla es el "motor de saltos" del algoritmo. Almacena, para cada posible bloque de tamaño B, la distancia mínima que el algoritmo puede saltar de forma segura.

Inicialización:

  • Se crea la tabla SHIFT y se inicializan todas sus entradas (una para cada posible bloque de B caracteres) con el valor de salto máximo por defecto: m - B + 1.

Cálculo de Saltos Mínimos:

  • Se itera sobre cada patrón p en el conjunto P.
  • Se considera solo el prefijo de longitud m de ese patrón (p[0...m-1]).
  • Se "desliza" un bloque de tamaño B sobre este prefijo, desde el inicio (i = 0) hasta la penúltima posición de bloque (i = m - B).
  • Para cada bloque X encontrado en la posición i, se calcula su "distancia al final": distancia = m - B - i.
  • Se actualiza la tabla: SHIFT[X] = min(SHIFT[X], distancia).

Resultado Clave:

  • Los bloques que no aparecen en ningún patrón (en sus primeros m caracteres) conservan el salto máximo (m - B + 1).
  • Los bloques que sí aparecen tendrán un valor de salto menor.
  • Crucialmente, cualquier bloque que aparezca al final de un prefijo m (en la posición i = m - B) tendrá una distancia de 0.

Paso 3: Construir la Tabla HASH

Tabla HASH

Esta tabla se usa solo cuando la SHIFT devuelve 0 (una posible coincidencia). Actúa como un índice que nos dice cuáles patrones específicos debemos verificar.

Procedimiento:

  • Se itera nuevamente sobre cada patrón p en el conjunto P.
  • Se extrae el bloque que se encuentra exactamente al final del prefijo de m caracteres (es decir, el bloque en la posición i = m - B).
  • Se calcula el valor hash de este bloque sufijo.
  • Se añade el patrón p (o un puntero/índice a él) a la lista de candidatos correspondiente a ese valor hash en la tabla HASH.

Paso 4: Construir la Tabla PREFIX

Tabla PREFIX

Esta tabla es una optimización adicional para reducir el número de comparaciones completas. Almacena un "atajo" para verificar el inicio del patrón.

Procedimiento:

  • Se itera una vez más sobre cada patrón p.
  • Se extrae el primer bloque del patrón (es decir, el bloque en la posición i = 0).
  • Se calcula el hash de este bloque prefijo y se almacena en la tabla PREFIX, asociándolo con el patrón p.

Fase de Escaneo

Paso 1: Configuración Inicial de la Ventana

Ventana 1

Ventana 2

Se posiciona una ventana de escaneo sobre el texto. El tamaño de esta ventana es siempre m (la longitud del patrón más corto). La ventana comienza en el índice 0 del texto.

Paso 2: Extraer y Hashear el Bloque Final

En la posición actual de la ventana, el algoritmo solo mira el bloque de tamaño B que se encuentra al final de la ventana. Se calcula el valor hash de este bloque.

Paso 3: Consultar la Tabla SHIFT

El algoritmo utiliza el hash del bloque final (del Paso 2) para buscar un valor en la tabla SHIFT. Este valor, shift_val, determina la próxima acción.

Paso 4: Decidir (Saltar vs. Verificar)

Caso A (Desajuste): Si shift_val > 0

Descripción

  • Esto significa que el bloque de texto actual no es el final de ningún patrón.
  • El algoritmo salta de forma segura: desplaza toda la ventana de escaneo shift_val posiciones hacia la derecha en el texto.
  • Se repite el proceso desde el Paso 2 en la nueva posición.

Caso B (Posible Coincidencia): Si shift_val == 0

Caso B

  • Esto indica que el bloque de texto podría ser el final de uno o más patrones.
  • No se realiza un salto. En su lugar, se debe proceder a una verificación detallada (Paso 5).

Paso 5: Verificación de Coincidencia Completa (Solo si shift_val == 0)

Ejemplo 1

Ejemplo 2

Al encontrar un shift_val de 0, el algoritmo debe confirmar si realmente hay una coincidencia:

  • Consultar HASH: Se utiliza el mismo hash del bloque (del Paso 2) para consultar la tabla HASH. Esta tabla devuelve la lista de patrones "candidatos" que terminan con ese bloque.
  • Verificar Patrones: El algoritmo compara, carácter por carácter, cada uno de los patrones candidatos con la sección de texto correspondiente dentro de la ventana de escaneo.
  • Reportar Éxito: Si la comparación completa es exitosa, se reporta una coincidencia (se ha encontrado ese patrón en esa posición).

Paso 6: Avanzar y Repetir

  • Si estábamos en el Caso A (Salto), la ventana ya se movió.
  • Si estábamos en el Caso B (Verificación), independientemente de si se encontró una coincidencia o no, la ventana de escaneo se desplaza solo 1 posición hacia la derecha. Esto es crucial para no perder patrones que puedan estar superpuestos.

El proceso se repite desde el Paso 2 hasta que la ventana de escaneo haya llegado al final del texto.

Complejidades

Para analizar las complejidades del algoritmo, primero definimos las variables clave:

  • n: Longitud del texto en el que se busca.
  • k: Número total de patrones en el conjunto de búsqueda.
  • m: Longitud del patrón más corto del conjunto.
  • B: Tamaño del bloque (constante, usualmente 2 o 3).
  • |Σ|: Tamaño del alfabeto (por ejemplo, 256 para ASCII).
  • L: Suma total de las longitudes de todos los patrones (aproximadamente k * m, ya que el pre-procesamiento se enfoca en los prefijos de longitud m).

Complejidad Temporal (Tiempo)

La complejidad temporal se divide en dos fases: pre-procesamiento y escaneo.

1. Fase de Pre-procesamiento: O(k * m)

Derivación:

  • Encontrar m: Requiere una pasada sobre los k patrones → O(k)
  • Construir SHIFT: Iterar sobre cada patrón y sus bloques → O(k * m)
  • Construir HASH y PREFIX: Insertar sufijo y prefijo de cada patrón → O(k)

Resultado: El término dominante es O(k * m)

2. Fase de Escaneo (Caso Promedio): O(B * n / m)

Derivación:

  • La mayoría de los bloques no coinciden con sufijos de patrones → se usa el salto por defecto O(m)
  • Número de paradas ≈ n / m
  • Trabajo por parada ≈ O(B)

Resultado: O(B * n / m) → complejidad sublineal en promedio

Resultado: O(B * n / m) → complejidad sublineal en promedio

3. Fase de Escaneo (Peor Caso): O(n * k * m)

Derivación:

  • SHIFT = 0 en casi todas las posiciones → no hay saltos
  • HASH devuelve k patrones candidatos
  • Verificación de cada patrón → O(m)
  • Trabajo por parada → O(k * m)
  • Número de paradas → n

Resultado: O(n * k * m) → extremadamente raro en la práctica

Complejidad Espacial (Memoria): O(|Σ|^B + k * m)

Derivación:

  • Tabla SHIFT: O(|Σ|^B) → combinaciones posibles de bloques de tamaño B
  • Tablas HASH y PREFIX: O(k)
  • Almacenamiento de patrones: O(k * m)

Resultado total: O(|Σ|^B + k * m)

Nota: La alta complejidad espacial de la tabla SHIFT (O(|Σ|^B)) es la principal desventaja del algoritmo Wu-Manber cuando se usa con alfabetos grandes o bloques de tamaño B > 2.

Implementación del Algoritmo

Este proyecto incluye una implementación en C del algoritmo Wu-Manber basada en el repositorio: https://github.com/yangchiu/wumanber-c

Características de la Implementación

  • Lenguaje: C (estándar GNU99)
  • Alfabeto: Solo ASCII de 7 bits
  • Restricciones: La longitud mínima del patrón debe ser mayor a 3 caracteres
  • Tamaño de bloque: B = 2 (bloque de 2 caracteres)

Estructura del Proyecto

wumanber-c/
|- main.c                     # Programa principal
|- Makefile                   # Script de compilación
|- WuManber.h                 # Estructura principal del algoritmo
|- WuManberOperation.c/h      # Implementación del algoritmo
|- ShiftTable.c/h             # Tabla de desplazamiento
|- ShiftTableOperation.c/h    # Operaciones de la tabla SHIFT
|- PrefixTable.c/h            # Tabla de prefijos
|- PrefixTableOperation.c/h   # Operaciones de la tabla PREFIX
|- MatchingResult.h           # Estructura de resultados
|- RawOperation.c/h           # Operaciones de lectura de archivos
|- testcase/
    |- pattern1.txt           # Archivo de patrones de prueba 1
    |- pattern2.txt           # Archivo de patrones de prueba 2
    |- content1.txt           # Texto de prueba 1
    |- content2.txt           # Texto de prueba 2

Cómo Usar la Implementación

1. Compilación

Para compilar el proyecto, ejecuta el comando make en el directorio wumanber-c/:

cd wumanber-c
make

Esto generará el ejecutable a.out (en Linux/Mac) o a.exe (en Windows con MinGW).

2. Ejecución

El programa requiere dos argumentos:

  1. Archivo de patrones: Un archivo de texto con un patrón por línea
  2. Archivo de contenido: El texto en el que se buscarán los patrones
./a.out <archivo_patrones> <archivo_contenido>

Ejemplo de uso:

./a.out ./testcase/pattern2.txt ./testcase/content2.txt

3. Formato de Archivos

Archivo de Patrones (pattern2.txt):

dimensional
network
autoencoder

Archivo de Contenido (content2.txt):

High-dimensional data can be converted to low-dimensional codes by training
a multilayer neural network with a small central layer to reconstruct
high-dimensional input vectors. Gradient descent can be used for fine-tuning
the weights in such "autoencoder" networks...

4. Salida del Programa

El programa mostrará:

  • Los patrones leídos
  • El contenido a buscar
  • La longitud mínima de patrón (m)
  • Las coincidencias encontradas con sus posiciones

Ejemplo de salida:

- Total 3 patterns:
  - dimensional
  - network
  - autoencoder
- Min pattern length: 7
- find dimensional at position 6 ~ 16
- find dimensional at position 47 ~ 57
- find network at position 97 ~ 103
- find autoencoder at position 265 ~ 275

5. Uso De La Implementación

Para integrar el algoritmo en tu propio código:

#include "WuManber.h"
#include "WuManberOperation.h"
#include "MatchingResult.h"

// 1. Crear instancia de Wu-Manber
WuManber wuManber = malloc(sizeof(WuManberStruct));
WuManberOperation operation = WuManberOperationFactory();

// 2. Definir patrones
char* patterns[] = {"pattern1", "pattern2", "pattern3"};
int patternCount = 3;

// 3. Construir tablas (pre-procesamiento)
operation->buildShiftTable(wuManber, patterns, patternCount);
operation->buildPrefixTable(wuManber, patterns, patternCount);

// 4. Buscar en el texto
char* text = "texto donde buscar los patterns...";
MatchingResult results = operation->search(wuManber, text);

// 5. Procesar resultados
MatchingResult current = results->next;
while(current) {
  printf("Found '%s' at position %d ~ %d\n",
    current->pattern, current->start, current->end);
  current = current->next;
}

// 6. Liberar memoria
operation->destroy(wuManber);

Limitaciones de esta Implementación

  1. Alfabeto limitado: Solo funciona con ASCII de 7 bits (no soporta caracteres extendidos ni Unicode)
  2. Longitud mínima: Los patrones deben tener al menos 4 caracteres de longitud
  3. Memoria: Usa un array de tamaño fijo (65536 entradas) para las tablas hash, lo cual puede ser ineficiente
  4. Tamaño de bloque fijo: B = 2 (no configurable)

Mejoras actuales en el algoritmo

Maximización de la Distancia de Salto (Eficiencia Temporal)

  • Quick Wu Manber (QWM): Introduce una tabla adicional (Head table) basada en los primeros caracteres de los patrones. Esta mejora permite alcanzar la distancia máxima de salto m (la longitud del patrón más corto), en lugar de m − B + 1 como en el algoritmo original, resultando en saltos más largos y rápidos.
  • Quick Multiple Matching (QMM): Algoritmo "agresivo" que también logra el salto máximo m. Elimina la dependencia funcional entre las tablas SHIFT y HASH, lo que mejora la velocidad. Sin embargo, debe consultar ambas tablas en cada paso del escaneo, no solo cuando SHIFT = 0.

Optimización de la Verificación (Eficiencia Temporal)

  • Improved WM (Chen Zhen & Wu Di): Introduce dos tablas SHIFT para reducir la probabilidad de detenerse a realizar comparaciones exactas de cadenas. Esta mejora evita la verificación la mayoría de las veces.
  • Address Filtering Based Wu-Manber (AFWM): Acelera la verificación cuando SHIFT = 0. Utiliza la tabla PREFIX y ordena los patrones candidatos por sus punteros de dirección en memoria, filtrando la lista de candidatos de forma más eficiente y reduciendo el número de comparaciones completas.

Solución a Limitaciones Fundamentales (Memoria y Concurrencia)

  • BLAST (B-Layered bad-character Shift Tables): Modificación significativa que abandona el uso de bloques de caracteres (B > 1) y utiliza múltiples tablas SHIFT en capas basadas en caracteres individuales (B = 1). Esta mejora reduce drásticamente el coste de memoria (de 64KB a 1KB) y mejora la velocidad de búsqueda (hasta un 212% más rápido).
  • High Concurrence Wu Manber (HCWM): Aborda la degradación del rendimiento cuando hay patrones cortos mezclados con largos. Agrupa los patrones por longitud y los procesa en paralelo, evitando que los patrones cortos ralenticen el proceso.
  • Variantes con Reglas de Boyer-Moore: Incorporan las reglas de "carácter erróneo" y "sufijo bueno" de Boyer-Moore, añadiendo tablas como GBSHIFT para aumentar la distancia de salto después de una verificación.

Aceleración por Hardware

La investigación también ha explorado el uso de hardware moderno. Algoritmos competidores como MPSSEF no modifican Wu-Manber, sino que lo superan usando extensiones SIMD (SSE). Esta mejora cambia el enfoque de "evitar comparaciones" a "acelerar comparaciones", realizando concordancia de cadenas empaquetadas donde múltiples caracteres se comparan en un solo ciclo de reloj. Es especialmente efectivo en aplicaciones modernas con miles de patrones, como los sistemas de detección de intrusos.

Referencias

Paper Original

Referencias Académicas

Material Complementario