Búsqueda Aproximada Permitiendo Errores

Abstract

El problema de la búsqueda aproximada en texto consiste en buscar las ocurrencias de un patrón en un texto, permitiendo que las ocurrencias no sean necesariamente copias exactas del patrón, sino que sean su cientemente próximas de acuerdo a alguna métrica particular. El problema tiene gran importancia en áreas como recuperación de la información, biología computacional y bases de datos de texto. El algoritmo de Chang y Marr (1994) es un algoritmo teóricamente óptimo en la complejidad de tiempo promedio para este problema. Posteriormente, Fredriksson y Navarro (2004) diseñan un algoritmo teóricamente óptimo que además es competitivo en la práctica. Esto hace pensar que el desarrollo de algoritmos exactos para este problema está llegando a su límite. El objetivo de este trabajo es enfrentar el problema de búsqueda utilizando una formulación débil que tiene potenciales aplicaciones prácticas y admite soluciones más e cientes que aquellas que se obtienen con algoritmos exactos, a cambio de posibles errores en la respuesta. Denominamos nuestra formulación búsqueda aproximada permitiendo errores. La principal contribución de este trabajo es la introducción y de nición formal del problema de búsqueda aproximada permitiendo errores para el caso en-línea, es decir, cuando se asume que no hay tiempo o espacio su ciente como para preprocesar el texto. Se presentan algoritmos para esta formulación, apoyados por análisis teóricos y experimentales que permiten entender su competitividad con respecto a algoritmos exactos para búsqueda aproximada. Los algoritmos propuestos son probabilísticos, permitiendo perder ocurrencias con cierta probabilidad y disminuyendo el tiempo de ejecución a cambio. Por ejemplo, sobre lenguaje natural estos algoritmos pueden recuperar el 95 % de las ocurrencias ocupando sólo el 15 % del tiempo utilizado por algoritmos exactos similares. El trabajo se complementa con algunas extensiones de las ideas desarrolladas para el caso en línea a otros problemas relacionados. En particular, se estudia cómo adaptar las ideas planteadas al problema de búsqueda aproximada múltiple, donde varios patrones se buscan sobre un mismo texto y a la búsqueda fuera de línea, en la cual se permite preprocesar el texto. Ambas extensiones muestran la robustez de los conceptos introducidos en este trabajo.