Resumen de Estructura y esquemas de búsqueda por similitud de cadenas de caracteres. Una aplicación para peticiones complejas de localización de palabras en archivos documentales

Margarita Díaz Roca

• ESTE TRABAJO TRATA ASPECTOS TEORICOS Y EXPERIMENTALES EN TORNO AL PROBLEMA DE LA BUSQUEDA DE LAS CADENAS MAS SIMILARES A UNA DADA, EL CONCEPTO DE SIMILITUD ES EN EL SENTIDO DE LA DISTANCIA DE LEVENSHTEIN, DL. EL OBJETIVO QUE SE PERSIGUE ES LA OPTIMIZACION DE LOS RECURSOS DE TIEMPO Y ESPACIO DE LOS ESQUEMAS DE BUSQUEDA Y DE LA ESTRUCTURA DE DATOS QUE LOS SOPORTA.

  SE DEFINE UNA NUEVA DISTANCIA QUE SE HA DENOMINADO DISTANCIA INVARIANTE TRASPOSICIONAL, DIT, DEBIDO AL HECHO DE QUE SU VALOR NO DEPENDE DE LAS OPERACIONES DE TRASPOSICION A QUE PUEDA SER SOMETIDA UNA CADENA. SI BIEN DIT NO PUEDE USARSE POR SI SOLA PARA LA DETERMINACION DE LAS CADENAS MAS SIMILARES, SU IMPORTANCIA DEVIENE DE LA CIRCUNSTANCIA DE QUE SU VALOR ENTRE DOS CADENAS ES SIEMPRE INFERIOR O IGUAL A LA DL ENTRE ESTAS DOS MISMAS CADENAS, SIENDO SU COSTE COMPUTACIONAL SENSIBLEMENTE INFERIOR; LO CUAL PUEDE SER APLICADO PARA LA CONSTRUCCION DE UN FILTRO ADAPTIVO DIT/DL QUE TENGA POR MISION REDUCIR EL NUMERO DE CADENAS DE LA BASE DE DATOS A LAS QUE SE LES CALCULA LA DL CON LA CADENA DE BUSQUEDA.

  SE DISEÑA UNA ESTRUCTURA, S-D, AL OBJETO DE COMPARTIR LAS COMPONENTES DE DIT Y NO TENER QUE CALCULAR COMPLETAMENTE LA DIT DE LA CADENA DE BUSQUEDA A TODAS Y CADA UNA DE LAS CADENAS DEL DICCIONARIO. EL ESQUEMA DE BUSQUEDA DE LAS CADENAS MAS SIMILARES QUE SE APOYA EN ESTA ESTRUCTURA, RECORRIENDOLA A TRAVES DE LAS COMPONENTES DE DIT, Y QUE USA ESTE VALOR COMO CRITERIO DE PODA SE DENOMINA ESQUEMA DECRECIENTE. SE ESTUDIAN NUEVAS ESTRATEGIAS PARA UN ESQUEMA DE BUSQUEDA CRECIENTE, DONDE EL RADIO DE BUSQUEDA, EN OPOSICION A LA EVOLUCION CLASICA DECRECIENTE, SIGUE UNA LINEA DE MODIFICACION CRECIENTE.

  ASIMISMO, SE PROPONE UN ESQUEMA DECRECIENTE CON RADIO ASCENDENTE TAL QUE EN FUNCION DEL INCREMENTO DEL RADIO DE BUSQUEDA DEFINE UNA FAMILIA DE ESQUEMAS INTERMEDIOS QUE CONECTAN A LOS ESQUEMAS CRECIENTE Y DECRECIENTE.

  PROLONGANDO LA LINEA DE OPTIMIZACION DE LAS REALIZACIONES DE LOS ESQUE