El algoritmo bitap (también conocido como el algoritmo shift-or , shift-and o Baeza-Yates-Gonnet ) es un algoritmo de coincidencia de cadenas aproximado . El algoritmo dice 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 calculando previamente un conjunto de máscaras de bits que contienen un bit para cada elemento del patrón. Entonces es capaz de hacer la mayor parte del trabajo con operaciones bit a bit., que son extremadamente rápidos.
El algoritmo bitap es quizás mejor conocido como uno de los algoritmos subyacentes de la utilidad agrep de Unix , escrito por Udi Manber , Sun Wu y Burra Gopal . El artículo original de Manber y Wu ofrece extensiones del algoritmo para hacer frente a la coincidencia difusa de expresiones regulares generales .
Debido a las estructuras de datos requeridas por el algoritmo, funciona mejor en patrones de menos de una longitud constante (normalmente la longitud de la palabra de la máquina en cuestión) y también prefiere las entradas sobre un alfabeto pequeño. Sin embargo, una vez que se ha implementado para un alfabeto dado y una longitud de palabra m , su tiempo de ejecución es completamente predecible: se ejecuta en operaciones O ( mn ), 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 completa de cadenas difusas). Este algoritmo fue posteriormente mejorado por Baeza-Yates y Navarro en 1996 [8] y más tarde por Gene Myers para patrones largos en 1998 [9].
exacta búsqueda
El algoritmo bitap para la búsqueda de cadenas exactas , en total generalidad, se ve así en pseudocódigo:
algoritmo bitap_search es entrada: texto como una cadena. patrón como una cuerda. salida: cadena m : = longitud ( patrón ) si m = 0 entonces devuelve el texto / * Inicializa la matriz de bits R. * / R : = nueva matriz [ m +1] de bit, inicialmente todos 0 R [0]: = 1 para i : = 0; itexto ); yo + = 1 hacer / * Actualiza 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 ] luego de regreso ( texto + i - m ) + 1 devolver nulo
Bitap se distingue de otros algoritmos de búsqueda de cadenas bien conocidos en su mapeo natural en operaciones simples de 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 ciclo interno para establecer R |= 1
. En esta implementación, aprovechamos el hecho de que desplazar a la izquierda un valor cambia en ceros a la derecha, que es precisamente el comportamiento que necesitamos.
Tenga en cuenta también que necesitamos CHAR_MAX
má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 sobre alfabetos más pequeños.
#include #include const char * bitap_bitwise_search ( const char * texto , const char * patrón ) { int m = strlen ( patrón ); unsigned long R ; máscara_patrón larga sin firmar [ CHAR_MAX + 1 ]; int i ; if ( patrón [ 0 ] == '\ 0' ) devolver texto ; if ( m > 31 ) devuelve "¡El patrón es demasiado largo!" ; / * Inicializar la matriz de bits R * / R = ~ 1 ; / * Inicializar las máscaras de bits del patrón * / para ( i = 0 ; i <= CHAR_MAX ; ++ i ) pattern_mask [ i ] = ~ 0 ; for ( i = 0 ; i < m ; ++ i ) pattern_mask [ patrón [ i ]] & = ~ ( 1UL << i ); for ( i = 0 ; text [ i ] ! = '\ 0' ; ++ i ) { / * Actualizar la matriz de bits * / R | = pattern_mask [ text [ i ]]; R << = 1 ; if ( 0 == ( R & ( 1UL << m ))) return ( texto + i - m ) + 1 ; } return NULL ; }
Búsqueda difusa
Para realizar una búsqueda de cadenas difusas utilizando el algoritmo bitap, es necesario extender la matriz de bits R a una segunda dimensión. En lugar de tener una sola matriz R que cambia a lo largo del texto, ahora tenemos k matrices distintas R 1 .. k . Array R i contiene una representación de los prefijos de patrón que coinciden con cualquier sufijo de la cadena actual con io 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 coincidencia 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 de sus significados convencionales.
#include #include #include const char * bitap_fuzzy_bitwise_search ( const char * text , const char * patrón , int k ) { const char * result = NULL ; int m = strlen ( patrón ); unsigned long * R ; máscara_patrón larga sin firmar [ CHAR_MAX + 1 ]; int i , d ; if ( patrón [ 0 ] == '\ 0' ) devolver texto ; if ( m > 31 ) devuelve "¡El patrón es demasiado largo!" ; / * Inicializa la matriz de bits R * / R = malloc (( k + 1 ) * sizeof * R ); para ( i = 0 ; i <= k ; ++ i ) R [ i ] = ~ 1 ; / * Inicializar las máscaras de bits del patrón * / para ( i = 0 ; i <= CHAR_MAX ; ++ i ) pattern_mask [ i ] = ~ 0 ; for ( i = 0 ; i < m ; ++ i ) pattern_mask [ patrón [ 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 todo lo que nos importa * / R [ d ] = ( old_Rd1 & ( R [ d ] | pattern_mask [ text [ i ]])) << 1 ; old_Rd1 = tmp ; } if ( 0 == ( R [ k ] & ( 1UL << m ))) { resultado = ( texto + i - m ) + 1 ; romper ; } } libre ( R ); devolver resultado ; }
Ver también
Enlaces externos y referencias
- ^ Bálint Dömölki, Un algoritmo para el análisis sintáctico, Lingüística computacional 3, Academia de Ciencias de Hungría, págs. 29–46, 1964.
- ^ Bálint Dömölki, Un sistema de compilación universal basado en reglas de producción,BIT Numerical Mathematics, 8 (4), pp 262-275, 1968.doi:10.1007 / BF01933436
- ^ RK Shyamasundar, Análisis de precedencia utilizando el algoritmo de Dömölki,International Journal of Computer Mathematics, 6 (2) pp 105-114, 1977.
- ^ Ricardo Baeza-Yates. "Búsqueda de texto eficiente". Tesis de doctorado, Universidad de Waterloo, Canadá, mayo de 1989.
- ^ 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 [ enlace muerto permanente ] )
- ^ Ricardo Baeza-Yates, Gastón H. Gonnet. "Un nuevo enfoque para la búsqueda de texto". Communications of the ACM , 35 (10): págs. 74–82, octubre de 1992.
- ^ Udi Manber, Sun Wu. "Búsqueda de texto rápida que permite errores". Communications of the ACM , 35 (10): págs. 83–91, octubre de 1992,doi:10.1145 / 135239.135244.
- ^ 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.
- ^ G. Myers. "Un algoritmo de vector de bits rápido para la coincidencia aproximada de cadenas basado en programación dinámica". Journal of the ACM 46 (3), mayo de 1999, 395–415.
- libbitap , una implementación gratuita que muestra cómo el algoritmo se puede extender fácilmente para la mayoría de las expresiones regulares. A diferencia del código anterior, no pone límite a la longitud del patrón.
- Ricardo Baeza-Yates, Berthier Ribeiro-Neto. Recuperación de información moderna . 1999. ISBN 0-201-39829-X .
- bitap.py : implementación en Python del algoritmo Bitap con modificaciones de Wu-Manber.