Mejorando un Algoritmo para Búsqueda Aproximada
Carlos Avendaño, Claudia Feregrino and Gonzalo Navarro.
El problema de búsqueda aproximada en texto comprimido trata de encontrar todas las coincidencias de un patrón en un texto comprimido, sin necesidad de descomprimirlo y teniendo en consideración que la coincidencia del patrón con el texto puede tener un número limitado de diferencias. Este problema tiene diversas aplicaciones en recuperación de información, biología computacional y procesamiento de señales, entre otras. Una de las mejores soluciones a este problema es realizar una búsqueda multipatrón de un conjunto de piezas del patrón, seguida de una descompresión local y una verificación directa en las áreas descomprimidas. En este trabajo se presenta una mejora a esta solución en la parte de verificación, en lugar de realizar una descompresión y buscar el patrón se construyen autómatas de paralelismo de bits que reconozcan el patrón. Con esto se logra realizar todo el proceso de búsqueda sin necesidad de descomprimir el archivo de texto en ningún momento además de obtener tiempos competitivos con los mejores algoritmos clásicos de búsqueda aproximada disponibles actualmente.