Algoritmo Bitap

El algoritmo bitap (también conocido como algoritmo shift-or , shift-and o Baeza-Yates-Gonnet ) es un algoritmo de comparación aproximada de cadenas . El algoritmo determina 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 la distancia de Levenshtein : si la subcadena y el patrón se encuentran dentro de una distancia k dada, el algoritmo los considera iguales. El algoritmo comienza precalculando un conjunto de máscaras de bits que contienen un bit por cada elemento del patrón. Luego, puede realizar la mayor parte del trabajo con operaciones bit a bit , que son extremadamente rápidas. 

El algoritmo bitap es quizás más conocido por ser uno de los algoritmos subyacentes de la utilidad agrep de Unix , 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, su rendimiento es óptimo con patrones de longitud inferior a una constante (normalmente la longitud de palabra de la máquina en cuestión) y también prefiere entradas con un alfabeto pequeño . Sin embargo, una vez implementado para un alfabeto y una longitud de palabra m determinados , su tiempo de ejecución es totalmente predecible : se ejecuta en O ( mn ) operaciones, independientemente de la estructura del texto o del patrón. 

El algoritmo bitap para la búsqueda exacta de cadenas fue inventado por Bálint Dömölki en 1964.y ampliada por RK Shyamasundar en 1977., antes de ser reinventado por Ricardo Baeza-Yates y Gaston Gonneten 1989 (un capítulo de la tesis doctoral del primer autor)) que también lo extendió para manejar clases de caracteres, comodines y desajustes. En 1991, fue extendido por Manber y WuTambién permite realizar inserciones y eliminaciones (búsqueda de cadenas difusas completas). Este algoritmo fue mejorado posteriormente por Baeza-Yates y Navarro en 1996.

El algoritmo bitap para la búsqueda exacta de cadenas , en su forma más general, se ve así en pseudocódigo:

El algoritmo bitap_search recibe como entrada: texto como cadena de caracteres. Patrón como cadena de caracteres. Salida: cadena m := longitud( patrón ) Si m = 0, entonces devuelve texto. /* Inicializa el array de bits R. */ R := nuevo array[ m +1] de bits, inicialmente todos 0 R [0] := 1 para i := 0; i < longitud( texto ); i += 1 hacer /* Actualizar el array 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 devolver nulo

Bitap se distingue de otros algoritmos de búsqueda de cadenas conocidos por su mapeo natural a operaciones bit a bit simples, como en la siguiente modificación del programa anterior. Nótese que en esta implementación, de forma contraintuitiva, cada bit con valor  cero indica una coincidencia, y cada bit con valor  1 indica una no coincidencia. El mismo algoritmo puede escribirse 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 desplazar un valor a la izquierda implica un desplazamiento de ceros a la derecha, que es precisamente el comportamiento que necesitamos.

Nótese también que se requieren CHAR_MAXmáscaras de bits adicionales para convertir la (text[i] == pattern[k-1])condición de 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 ( m == 0 ) return text ; if ( m > 31 ) throw "¡El patrón es demasiado largo!" ; /* Inicializar el array 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 ); for ( i = 0 ; text [ i ] != '\0' ; ++ i ) { /* Actualizar el array de bits */ R |= pattern_mask [ text [ i ]]; R <<= 1 ; if ( 0 == ( R & ( 1UL << m ))) return ( text + i - m ) + 1 ; } return NULL ; }

Para realizar búsquedas de cadenas difusas mediante el algoritmo bitap, es necesario extender la matriz de bits R a una segunda dimensión. En lugar de tener una única matriz R que varía a lo largo del texto, ahora tenemos k matrices distintas R _{1.. k} . La matriz R _i contiene una representación de los prefijos del 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, una eliminación o una sustitución; consulte la distancia de Levenshtein para obtener más información sobre estas operaciones.

La implementación que se muestra a continuación realiza una coincidencia aproximada (devolviendo la primera coincidencia con hasta k errores) utilizando el algoritmo de bitap difuso. Sin embargo, solo considera las sustituciones, no las inserciones ni las eliminaciones ; es decir, una distancia de Hamming de k . Como antes, la semántica de 0 y 1 se invierte respecto a sus significados convencionales. 

#include <stdlib.h> #include <string.h> #include <limits.h> const char * bitap_fuzzy_bitwise_search ( const char * text , const char * pattern , int k ) { const char * result = NULL ; int m = strlen ( pattern ); unsigned long * R ; unsigned long pattern_mask [ CHAR_MAX + 1 ]; int i , d ; if ( pattern [ 0 ] == '\0' ) return text ; if ( m > 31 ) return "¡El patrón es demasiado largo!" ; /* Inicializar el array 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_patrón [ texto [ i ]]; R [ 0 ] <<= 1 ; para ( d = 1 ; d <= k ; ++ d ) { unsigned long tmp = R [ d ]; /* La sustitución es lo único que nos importa */ R [ d ] = ( old_Rd1 & ( R [ d ] | máscara_patrón [ texto [ i ]])) << 1 ; old_Rd1 = tmp ; } si ( 0 == ( R [ k ] & ( 1UL << m ))) { resultado = ( texto + i - m ) + 1 ; break ; } } free ( R ); return resultado ; }

• agrep
• TRE (informática)

1. ^ Bálint Dömölki, Un algoritmo para el análisis sintáctico, Lingüística Computacional 3, Academia Húngara de Ciencias, págs. 29-46, 1964.
2. ^ Bálint Dömölki, Un sistema compilador universal basado en reglas de producción,BIT Numerical Mathematics, 8(4), pp. 262-275,1968.doi:10.1007/BF01933436
3. ^ RK Shyamasundar, Análisis de precedencia utilizando el algoritmo de Dömölki,International Journal of Computer Mathematics, 6(2)pp 105–114, 1977.
4. ^ Ricardo Baeza-Yates. "Búsqueda eficiente de texto". Tesis doctoral, Universidad de Waterloo, Canadá, mayo de 1989.
5. ^ Udi Manber, Sun Wu. "Búsqueda rápida de texto con errores". Informe técnico TR-91-11. Departamento de Ciencias de la Computación,Universidad de Arizona, Tucson, junio de 1991. (PostScript comprimido con gzip)
6. ^ Ricardo Baeza-Yates, Gastón H. Gonnet. "Un nuevo enfoque para la búsqueda de texto". Communications of the ACM , 35(10): pp. 74–82, octubre de 1992.
7. ^ Udi Manber, Sun Wu. "Búsqueda rápida de texto que permite errores." Communications of the ACM , 35(10): pp. 83–91, octubre de 1992,doi:10.1145/135239.135244.
8. ^ R. Baeza-Yates y G. Navarro. Un algoritmo más rápido para la coincidencia aproximada de cadenas. En Dan Hirchsberg y Gene Myers, editores,Combinatorial Pattern Matching(CPM'96), LNCS 1075, páginas 1-23,Irvine, CA, junio de 1996.
9. ^ G. Myers. "Un algoritmo rápido de vector de bits para la coincidencia aproximada de cadenas basado en programación dinámica." Journal of the ACM 46 (3), mayo de 1999, 395–415.
10. libbitap es una implementación gratuita que muestra cómo se puede extender fácilmente el algoritmo para la mayoría de las expresiones regulares. A diferencia del código anterior, no impone ningún límite a la longitud del patrón.
11. Ricardo Baeza-Yates, Berthier Ribeiro-Neto. Recuperación de información moderna . 1999.ISBN​ 0-201-39829-X.
12. bitap.py - Implementación en Python del algoritmo Bitap con modificaciones de Wu-Manber.