Utilización de un índice métrico para búsqueda aproximada de patrones

Abstract

Uno de los problemas abiertos en la búsqueda de patrones combinatoria es la indexación de texto para permitir búsqueda aproximada sobre él. Presentamos aquí una implementación de un método nuevo y simple de indexación para el problema de búsqueda aproximada de patrones. El esquema aprovecha las propiedades métricas que posee la distancia de edición y puede ser aplicado a cualquier otra métrica existente entre strings. Consideramos un espacio métrico donde los elementos son los sufijos del texto, construimos un índice métrico, y las búsquedas aproximadas se ven como consultas por proximidad sobre ese espacio métrico.