Algoritmo de bits

El algoritmo bitap (también conocido como shift-or, shift-and o Baeza-Yates-Gonnet algoritmo) es un algoritmo de coincidencia de cadenas aproximada. El algoritmo indica si un texto determinado contiene una subcadena que es "aproximadamente igual" a una subcadena. 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 determinada 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. Entonces 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 mejor conocido como 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 requeridas por el algoritmo, funciona mejor en patrones de longitud menor que una constante (normalmente la longitud de la palabra de la máquina en cuestión) y también prefiere las entradas a un alfabeto pequeño. Sin embargo, una vez que se ha implementado para un alfabeto y una longitud de palabra determinados m, su tiempo de ejecución es completamente predecible: se ejecuta en operaciones O(mn), sin importar 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 ampliado por R. K. Shyamasundar en 1977, antes de ser reinventado por Ricardo Baeza-Yates y Gaston Gonnet en 1989 (un capítulo de la tesis doctoral del primer autor ) que también lo amplió para manejar clases de caracteres, comodines y discrepancias. En 1991, Manber y Wu lo ampliaron para manejar también inserciones y eliminaciones (búsqueda completa de cadenas difusas). Este algoritmo fue mejorado posteriormente por Baeza-Yates y Navarro en 1996.

Búsqueda exacta

El algoritmo bitap para la búsqueda de cadenas exactas, en general, se ve así en pseudocódigo:

algoritmo bitap_search es entrada: texto como una cuerda.
 patrón como una cuerda.
 Producto: cuerda
 m:= longitudpatrón)

 si m = 0 entonces Regreso texto/* Inicia la matriz de bits R. */
 R:= nuevo array[m+1] de bit, inicialmente todo 0
 R[0]:= 1

 para i:= 0; i longitud(texto); i += 1 do/* Actualizar la matriz de bits. */
 para k:= m; k ≥ 1; k -= 1 do R[k]:= R[k - 1] "texto[i= patrón[k - 1])

 si R[m] entonces Regreso ()texto + i - m) + 1

 Regreso nulo

Bitap se distingue de otros algoritmos de búsqueda de cuerdas conocidos en su cartografía natural sobre operaciones simples bitwise, como en la siguiente modificación del programa anterior. Observe que en esta implementación, de manera contraintuitiva, cada bit con valor cero indica un partido, y cada bit con valor 1 indica un no-objetivo. 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 interior para establecer R |= 1. En esta implementación, aprovechamos el hecho de que cambiar un valor en ceros a la derecha, que es precisamente el comportamiento que necesitamos.

Observe también que necesitamos CHAR_MAX máscaras de bits adicionales para convertir la condición (text[i] == patrón[k-1]) 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 Identificando.h #include - No.  const char *bitap_bitwise_search()const char *texto, const char *patrón) {} int m = strlen()patrón); no firmado largo R; no firmado largo patrón_mask[CHAR_MAX+1]; int i;  si ()patrón[0] == '0') Regreso texto; si ()m ■ 31) Regreso "¡El patrón es demasiado largo!";  /* Inicia la matriz de bits R */ R = ~1;  /* Inicia la masajillas patrón */ para ()i=0; i . CHAR_MAX; ++i) patrón_mask[i] = ~0; para ()i=0; i c) m; ++i) patrón_mask[patrón[i]] " ~()1UL c) c) i);  para ()i=0; texto[i] ! '0'; ++i) {} /* Actualizar la matriz de bits */ R ← patrón_mask[texto[i]] R " 1;  si ()0 == ()R " ()1UL c) c) m)) Regreso ()texto + i - m) + 1; }  Regreso NULL; }

Búsqueda difusa

Para realizar una búsqueda difusa de cadenas utilizando 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 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 pattern 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 Distancia de Levenshtein para obtener más información sobre estas operaciones.

La siguiente implementación realiza una coincidencia difusa (devuelve la primera coincidencia con hasta k errores) utilizando el algoritmo bitap difuso. Sin embargo, sólo 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 respecto de sus significados convencionales.

 #include ■stdlib.h #include Identificando.h #include - No.  const char *bitap_fuzzy_bitwise_search()const char *texto, const char *patrón, int k) {} const char *resultado = NULL; int m = strlen()patrón); no firmado largo *R; no firmado largo patrón_mask[CHAR_MAX+1]; int i, d;  si ()patrón[0] == '0') Regreso texto; si ()m ■ 31) Regreso "¡El patrón es demasiado largo!";  /* Inicia la matriz de bits R */ R = malloc(()k+1) * tamaño *R); para ()i=0; i . k; ++i) R[i] = ~1;  /* Inicia la masajillas patrón */ para ()i=0; i . CHAR_MAX; ++i) patrón_mask[i] = ~0; para ()i=0; i c) m; ++i) patrón_mask[patrón[i]] " ~()1UL c) c) i);  para ()i=0; texto[i] ! '0'; ++i) {} /* Actualizar los arrays de bits */ no firmado largo old_Rd1 = R[0];  R[0] ← patrón_mask[texto[i]] R[0] " 1;  para ()d=1; d . k; ++d) {} no firmado largo tmp = R[d]; * La sustitución es todo lo que nos importa */ R[d] = ()old_Rd1 " ()R[d] Silencio patrón_mask[texto[i]) c) c) 1; old_Rd1 = tmp; }  si ()0 == ()R[k] " ()1UL c) c) m)) {} resultado = ()texto+i - m) + 1; descanso; } }  gratis()R); Regreso resultado; }

Enlaces externos y referencias

1. ^ Bálint Dömölki, Un algoritmo para el análisis sintético, Linguística computacional 3, Academia Húngara de Ciencias pp. 29–46, 1964.
2. ^ Bálint Dömölki, Un sistema compilador universal basado en las reglas de producción, Matemáticas Numéricas BIT, 8(4), pp 262–275, 1968. doi:10.1007/BF01933436
3. ^ R. K. Shyamasundar, Precedence parsing using Dömölki's algoritmo, International Journal of Computer Mathematics, 6(2)pp 105–114, 1977.
4. ^ Ricardo Baeza-Yates. "Eficiente búsqueda de texto". PhD Thesis, University of Waterloo, Canada, May 1989.
5. ^ Udi Manber, Sun Wu. "Fast text search with errors." Informe técnico TR-91-11. Department of Computer Science, University of Arizona, Tucson, June 1991. (Gzipped PostScript)
6. ^ Ricardo Baeza-Yates, Gastón H. Gonnet. "Un nuevo enfoque para la búsqueda de textos." Comunicaciones de la ACM, 35(10): págs. 74 a 82, octubre de 1992.
7. ^ Udi Manber, Sun Wu. "Fast text search allowing errors." Comunicaciones de la ACM, 35(10): pp. 83–91, October 1992, doi:10.1145/135239.135244.
8. ^ R. Baeza-Yates y G. Navarra. Un algoritmo más rápido para ajustar la cadena aproximada. En Dan Hirchsberg y Gene Myers, editores, Combinación de patrón combinado (CPM'96), LNCS 1075, pages 1–23, Irvine, CA, June 1996.
9. ^ G. Myers. "Un algoritmo rápido de bit-vector para una combinación aproximada de cadena basado en programación dinámica". Journal of the ACM 46 3), mayo de 1999, 395-415.
10. libbitap, una implementación libre 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 coloca límite en la longitud del patrón.
11. Ricardo Baeza-Yates, Berthier Ribeiro-Neto. Modern Information Retrieval1999 ISBN 0-201-39829-X.
12. bitap.py - Implementación de pitón del algoritmo de bitap con modificaciones Wu-Manber.