El algoritmo bitap (también conocido como shift-or , shift-and o algoritmo Baeza-Yates-Gonnet ) es un algoritmo de coincidencia aproximada de cadenas . El algoritmo indica si un texto dado contiene una subcadena que es "aproximadamente igual" a un patrón dado, donde la igualdad aproximada se define en términos de distancia de Levenshtein : si la subcadena y el patrón están dentro de una distancia dada k entre sí, entonces el algoritmo los considera iguales. El algoritmo comienza precalculando un conjunto de máscaras de bits que contienen un bit para cada elemento del patrón. Luego es capaz de hacer la mayor parte del trabajo con operaciones bit a bit , que son extremadamente rápidas.
El algoritmo bitap es quizás más conocido como uno de los algoritmos subyacentes de la utilidad Unix agrep , escrita por Udi Manber , Sun Wu y Burra Gopal. El artículo original de Manber y Wu ofrece extensiones del algoritmo para abordar la coincidencia difusa de expresiones regulares generales .
Debido a las estructuras de datos que requiere el algoritmo, funciona mejor con patrones de longitud menor que una constante (normalmente la longitud de palabra de la máquina en cuestión) y también prefiere entradas en lugar de un alfabeto pequeño. Sin embargo, una vez que se ha implementado para un alfabeto determinado y una longitud de palabra m , su tiempo de ejecución es completamente predecible: se ejecuta en O ( mn ) operaciones, sin importar la estructura del texto o el patrón.
El algoritmo bitap para la búsqueda exacta de cadenas fue inventado por Bálint Dömölki en 1964 [1] [2] y ampliado por RK Shyamasundar en 1977 [3] , antes de ser reinventado por Ricardo Baeza-Yates y Gaston Gonnet [4] en 1989 (un capítulo de la tesis doctoral del primer autor [5] ) que también lo amplió para manejar clases de caracteres, comodines y desajustes. En 1991, fue ampliado por Manber y Wu [6] [7] para manejar también inserciones y eliminaciones (búsqueda de cadenas difusa completa). Este algoritmo fue mejorado posteriormente por Baeza-Yates y Navarro en 1996. [8]
El algoritmo bitap para la búsqueda exacta de cadenas , en su generalidad total, se ve así en pseudocódigo:
El algoritmo bitap_search tiene como entrada: texto como cadena. Patrón como cadena. Salida: cadena m := length( patrón ) Si m = 0 entonces devuelve texto /* Inicializar la matriz de bits R. */ R := nueva matriz [ m +1] de bits, inicialmente todos 0 R [0] := 1 para i := 0; i < longitud( texto ); i += 1 hacer /* Actualizar la matriz de bits. */ para k := m ; k ≥ 1; k -= 1 hacer R [k] := R [ k - 1] & ( texto [ i ] = patrón [ k - 1]) si R [ m ] entonces devuelve ( texto + i - m ) + 1 devuelve nulo
Bitap se distingue de otros algoritmos de búsqueda de cadenas conocidos en su mapeo natural a operaciones simples bit a bit, como en la siguiente modificación del programa anterior. Observe que en esta implementación, contrariamente a la intuición, cada bit con valor cero indica una coincidencia, y cada bit con valor 1 indica una no coincidencia. El mismo algoritmo se puede escribir con la semántica intuitiva para 0 y 1, pero en ese caso debemos introducir otra instrucción en el bucle interno para establecer R |= 1. En esta implementación, aprovechamos el hecho de que al desplazar un valor hacia la izquierda se desplazan ceros hacia la derecha, que es precisamente el comportamiento que necesitamos.
Tenga en cuenta también que necesitamos CHAR_MAXmáscaras de bits adicionales para convertir la (text[i] == pattern[k-1])condición en la implementación general en operaciones bit a bit. Por lo tanto, el algoritmo bitap funciona mejor cuando se aplica a entradas con alfabetos más pequeños.
#include <string.h> #include <limits.h> const char * bitap_bitwise_search ( const char * text , const char * pattern ) { int m = strlen ( pattern ); unsigned long R ; unsigned long pattern_mask [ CHAR_MAX + 1 ]; int i ; if ( pattern [ 0 ] == '\0' ) return text ; if ( m > 31 ) return "¡El patrón es demasiado largo!" ; /* Inicializar la matriz de bits R */ R = ~ 1 ; /* Inicializar las máscaras de bits del patrón */ for ( i = 0 ; i <= CHAR_MAX ; ++ i ) pattern_mask [ i ] = ~ 0 ; for ( i = 0 ; i < m ; ++ i ) pattern_mask [ pattern [ i ]] &= ~ ( 1UL << i ); para ( i = 0 ; texto [ i ] != '\0' ; ++ i ) { /* Actualizar la matriz de bits */ R |= máscara_de_patrón [ texto [ i ]]; R <<= 1 ; si ( 0 == ( R & ( 1UL << m ))) devolver ( texto + i - m ) + 1 ; } devolver NULL ; } Para realizar una búsqueda de cadenas difusas mediante el algoritmo bitap, es necesario ampliar la matriz de bits R a una segunda dimensión. En lugar de tener una única matriz R que cambia a lo largo del texto, ahora tenemos k matrices distintas R 1.. k . La matriz R i contiene una representación de los prefijos de patrón que coinciden con cualquier sufijo de la cadena actual con i o menos errores. En este contexto, un "error" puede ser una inserción, eliminación o sustitución; consulte la distancia de Levenshtein para obtener más información sobre estas operaciones.
La siguiente implementación realiza una comparación difusa (devolviendo la primera coincidencia con hasta k errores) utilizando el algoritmo bitap difuso. Sin embargo, solo presta atención a las sustituciones, no a las inserciones o eliminaciones; en otras palabras, una distancia de Hamming de k . Como antes, la semántica de 0 y 1 se invierte con respecto a sus significados convencionales.
#include <stdlib.h> #include <string.h> #include <limits.h> const char * bitap_fuzzy_bitwise_search ( const char * texto , const char * patrón , int k ) { const char * resultado = NULL ; int m = strlen ( patrón ); unsigned long * R ; unsigned long máscara_de_patrón [ CHAR_MAX + 1 ]; int i , d ; if ( patrón [ 0 ] == '\0' ) return texto ; if ( m > 31 ) return "¡El patrón es demasiado largo!" ; /* Inicializar la matriz de bits R */ R = malloc (( k + 1 ) * sizeof * R ); for ( i = 0 ; i <= k ; ++ i ) R [ i ] = ~ 1 ; /* Inicializar las máscaras de bits de patrón */ for ( i = 0 ; i <= CHAR_MAX ; ++ i ) pattern_mask [ i ] = ~ 0 ; for ( i = 0 ; i < m ; ++ i ) pattern_mask [ pattern [ i ]] &= ~ ( 1UL << i ); for ( i = 0 ; text [ i ] != '\0' ; ++ i ) { /* Actualizar las matrices de bits */ unsigned long old_Rd1 = R [ 0 ]; R [ 0 ] |= máscara_de_patrón [ texto [ i ]]; R [ 0 ] <<= 1 ; for ( d = 1 ; d <= k ; ++ d ) { unsigned long tmp = R [ d ]; /* La sustitución es todo lo que nos importa */ R [ d ] = ( old_Rd1 & ( R [ d ] | máscara_de_patrón [ texto [ i ]])) << 1 ; old_Rd1 = tmp ; } if ( 0 == ( R [ k ] & ( 1UL << m ))) { result = ( text + i - m ) + 1 ; break ; } } free ( R ); return result ; }