Introducción al "String Matching"

El String Matching (o búsqueda de cadenas) es uno de los problemas más fundamentales y estudiados en las ciencias de la computación. En su forma más básica, consiste en encontrar todas las ocurrencias de una cadena de caracteres llamada patrón (\(P\)) dentro de una cadena más larga llamada texto (\(T\)).

Aunque la formulación del problema es sencilla, las soluciones varían enormemente en complejidad y eficiencia dependiendo de los requisitos específicos: ¿Buscamos una sola palabra o un diccionario completo? ¿Necesitamos una coincidencia exacta o permitimos errores ortográficos? ¿El patrón es fijo o es una expresión flexible?

Importancia y Aplicaciones

La eficiencia en la búsqueda de texto es crítica para una gran variedad de sistemas modernos. Algunas de las aplicaciones más comunes incluyen:

Editores de Texto e IDEs: La funcionalidad de "Buscar" (Ctrl+F) y "Reemplazar".
Motores de Búsqueda: Indexación y recuperación de documentos en la web.
Bioinformática: Búsqueda de secuencias de ADN o proteínas dentro de genomas extensos, donde a menudo se requieren coincidencias aproximadas.
Ciberseguridad: Los sistemas de detección de intrusos (IDS) buscan firmas de virus o patrones de ataque conocidos dentro del tráfico de red en tiempo real.
Procesamiento de Lenguaje Natural (NLP): Tokenización, análisis léxico y corrección ortográfica.

Notación Básica

Para facilitar la comprensión de los algoritmos descritos en esta sección, utilizaremos una notación estándar:

\(T\): El Texto donde se realiza la búsqueda.
\(P\): El Patrón (o patrones) que estamos buscando.
\(n\): La longitud del texto (\(|T|\)).
\(m\): La longitud del patrón (\(|P|\)).
\(\Sigma\): El alfabeto, es decir, el conjunto finito de caracteres disponibles (ej. ASCII, \(\{A, C, G, T\}\), binario).
\(|\Sigma|\): El tamaño del alfabeto (ej. 256 para ASCII extendido).

Categorías de Búsqueda

En este proyecto, exploramos cuatro enfoques principales para resolver problemas de String Matching:

1. Single String Matching (Búsqueda Exacta de un Patrón)

Es el escenario más clásico: buscar una única cadena fija dentro de un texto.

Enfoque ingenuo: Compara el patrón en cada posición, tomando tiempo \(O(nm)\).
Algoritmos avanzados: Utilizan pre-procesamiento del patrón para saltar caracteres innecesarios y lograr tiempos cercanos a \(O(n/m)\) en la práctica.
Ejemplos cubiertos: Boyer-Moore, Rabin-Karp, BNDM.

2. Multiple String Matching (Búsqueda de Múltiples Patrones)

Implica buscar simultáneamente un conjunto de patrones (un diccionario) en el texto. La idea es leer el texto una sola vez y reportar las ocurrencias de cualquiera de los patrones del conjunto.

Estrategia: Generalmente se construyen estructuras tipo árbol (Tries) o autómatas finitos que combinan todos los patrones.
Ejemplos cubiertos: Aho-Corasick, Wu-Manber, Commentz-Walter.

3. Approximate String Matching (Búsqueda Aproximada)

También conocida como "fuzzy string searching". Busca subcadenas en el texto que sean "similares" al patrón, permitiendo un cierto número de errores (\(k\)).

Métrica de Similitud: Se define comúnmente usando la Distancia de Levenshtein (inserciones, eliminaciones o sustituciones necesarias para convertir una cadena en otra).
Ejemplos cubiertos: Levenshtein Distance, Bitap, Algoritmos basados en programación dinámica.

Existe una herramienta CLI popular entre programadores que se llama "fzf", este consiste en una búsqueda aproximada de cadenas en listas de diferentes tipos, como: archivos, historial de comandos, procesos, marcadores, git commits, etc. Este es un ejemplo que selecciona archivos en todos los subdirectorios y los guarda en el archivo de texto selected:

find * -type f | fzf > selected

También es fácilmente integrable en distintos editores de texto como vim o vscode. Totalmente recomendado si quieres agilizar tu trabajo en la terminal :)

Link: fzf

4. Regular Expression Matching (Expresiones Regulares)

Permite buscar patrones definidos por una sintaxis formal (lenguaje regular) en lugar de una cadena fija. Es la forma más flexible de búsqueda, permitiendo comodines, repeticiones y alternativas.

Implementación: Se basa fuertemente en la teoría de Autómatas Finitos Deterministas (DFA) y No Deterministas (NFA).
Ejemplos cubiertos: Construcción de Thompson, Construcción de Glushkov.