Definition and solution of a new approximate variant of the order preserving matching problem

En esta tesis se combinan dos problemas de búsqueda de cadenas: la búsqueda aproximada de cadenas bajo parámetros δγ, y el emparejamiento con preservación de orden. Uno permite un nivel de error en la búsqueda, mientras que el otro considera la estructura interna de las cadenas en lugar de sus valores absolutos. Se define formalmente el Emparejamiento con preservación de orden bajo distancias δγ. Se diseñaron e implementaron en C++ cuatro algoritmos que resuelven el problema, y una configuración experimental para compararlos. El algoritmo más simple, tiene complejidad O(nm lg m). El segundo tiene una complejidad de O(nm). El tercero y el cuarto se basan en estructuras de datos: árbol de segmentos y árbol de fenwick respectivamente. Ambos tienen complejidad O(nm lg n). Los resultados experimentales muestran que los algoritmos basados en estructuras de datos tiene un mejor rendimiento en muchos casos. El de mejor rendimiento experimental es del basado en el árbol Fenwick, seguido por el basado en árboles de segmentos. Estos resultados se pueden explicar debido a su complejidad Ω(n lg n). Se muestran aplicaciones en música y finanzas.

• Autores: Niquefa Velasquez, Rafael
• Fecha de publicación: 2017
• Institución: Universidad Nacional de Colombia
• Repositorio: Universidad Nacional de Colombia
• Idioma: spa
• OAI Identifier: oai:repositorio.unal.edu.co:unal/59919
• Acceso en línea: https://repositorio.unal.edu.co/handle/unal/59919; http://bdigital.unal.edu.co/57743/
• Palabra clave: 0 Generalidades / Computer science, information and general works; 02 Bibliotecología y ciencias de la información / Library and information sciences; 5 Ciencias naturales y matemáticas / Science; Stringology; Order Preserving Pattern Matching; Approximate Matching; Delta Gamma Matching; Búsqueda de cadenas; Análisis experimental de algoritmos; Árbol de Fenwick; Árbol indexado binario; Árbol de segmentos
• Rights: openAccess
• License: Atribución-NoComercial 4.0 Internacional