Baeza–Yates–Gonnet (BYG)

---

Introducción

El algoritmo de Baeza–Yates–Gonnet (BYG) es una técnica de búsqueda de patrones en texto basada en operaciones a nivel de bit, lo que permite realizar coincidencias rápidas mediante enmascaramientos y desplazamientos binarios. Propuesto en 1992 por Ricardo Baeza-Yates y Gaston Gonnet, este método representa el patrón de búsqueda como un conjunto de máscaras de bits, una por cada carácter posible del alfabeto.

Este algoritmo fue un precursor directo del Bitap y del agrep, y se considera una de las primeras implementaciones prácticas de búsqueda eficiente usando aritmética de bits.

---

Fundamento teórico

En lugar de comparar carácter por carácter, el BYG utiliza una palabra de máquina (por ejemplo, 64 bits) para procesar múltiples posiciones del patrón simultáneamente.
Cada bit representa si un carácter específico del patrón coincide en cierta posición.

Durante la búsqueda, se mantiene un registro D que representa las coincidencias parciales.
Para cada nuevo carácter del texto T[i], se actualiza D con la siguiente operación:

\[ D = ((D \ll 1) | 1) \& \text{mask}[T[i]] \]

Si el bit más significativo de D se activa (es decir, se vuelve 0), se ha encontrado una coincidencia completa del patrón.

---

Ejemplo

Supongamos:

Texto (T):   A C A G A C A T
Patrón (P):  A C A

1. Se construye una máscara por carácter del patrón:

Carácter	Máscara binaria	Máscara decimal
A	101	5
C	010	2
G	000	0
T	000	0

1. Inicialmente D = 0b111111...1111 (sin coincidencias).

2. Por cada carácter del texto, se actualiza D y se verifica si el bit más alto indica una coincidencia.

---

Implementación en C++

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int searchBYG(const string &text, const string &pattern) {
    int n = text.size();
    int m = pattern.size();
    if (m == 0 || m > 63) return 0;

    unordered_map&lt;char, uint64_t&gt; mask;
    for (char c = 0; c < 127; ++c)
        mask[c] = ~0ULL;

    for (int i = 0; i < m; ++i)
        mask[pattern[i]] &= ~(1ULL &lt;&lt; i);

    uint64_t D = ~0ULL;
    uint64_t matchBit = 1ULL &lt;&lt; (m - 1);
    int matches = 0;

    for (int i = 0; i &lt; n; ++i) {
        D = (D &lt;&lt; 1) | mask[text[i]];
        if ((D &amp; matchBit) == 0)
            matches++;
    }

    return matches;
}

int main() {
    string T = "ACAGACAT";
    string P = "ACA";
    cout &lt;&lt; "Coincidencias: " &lt;&lt; searchBYG(T, P) &lt;&lt; endl;
    return 0;
}

Salida esperada:

Coincidencias: 2

---

Visualización del proceso

La siguiente figura ilustra cómo se actualizan los bits en cada paso:

(Ejemplo ilustrativo: cada fila representa el valor del registro D tras procesar un carácter del texto.)

---

Complejidad

Etapa	Complejidad temporal	Complejidad espacial
Preprocesamiento	O(Σ + m)	O(Σ)
Búsqueda	O(n)	O(1)

Donde Σ es el tamaño del alfabeto (por ejemplo, 256 para ASCII).

---

Extensión: búsqueda aproximada

El algoritmo BYG puede ampliarse para admitir k errores (inserciones, eliminaciones o sustituciones) manteniendo varios registros D[k], cada uno representando los alineamientos con k errores.

Fórmula general:

D[0] = ((D[0] << 1) | 1) & mask[c]
D[i] = ((D[i] << 1) | 1) & mask[c] | D[i-1] | ((D[i-1] << 1) | 1) | (D[i-1] >> 1)

Este enfoque fue la base del algoritmo de Myers (1999).

---

Referencias

• R. Baeza-Yates & G. Gonnet, “A new approach to text searching”, Communications of the ACM, 35(10):74–82, 1992.
• G. Navarro & M. Raffinot, Flexible Pattern Matching in Strings, Cambridge University Press, 2002.
• D. Myers, “A fast bit-vector algorithm for approximate string matching”, Information Processing Letters, 1999.
• agrep: Approximate GREP for fast text search, University of Arizona.

---