Una nueva aproximación al emparejamiento con preservación de orden

Un problema importante en el análisis de mercado de valores y la recuperación de información musical es el emparejamiento con preservación de orden. Este problema es una variante recientemente introducida del problema de emparejamiento de cadenas en el que busca subcadenas en el texto cuya representación natural coincide con la representación natural del patrón. La representación natural de una cadena X es una cadena que contiene los rankings de los caracteres que ocurren en cada posición de X. Entonces, el emparejamiento con preservación de orden considera la estructura interna de las cadenas en lugar de sus valores absolutos. Pero tanto en el análisis de mercado de valores como en la recuperación de información musical, se requiere más flexibilidad: no sólo las subcadenas con exactamente la misma estructura son de interés, sino también las que son similares. En este artículo se propone una versión aproximada del problema de emparejamiento con preservación de orden basada en las distancias δγ que permiten un error individual entre el ranking de los símbolos correspondientes (delimitada por δ) y un error global de todas los rankings (delimitadas por γ). Se presenta un algoritmo que resuelve este problema en O(nm+m log m). Los resultados experimentales verifican la eficiencia del algoritmo propuesto.

• Autores: Mendivelso Moreno, Juan Carlos; Niquefa Velásquez, Rafael Alberto; Pinzón Ardila, Yoán José; Hernández Pérez, Germán Jairo
• Tipo de recurso: Article of journal
• Fecha de publicación: 2017
• Institución: Universidad de los Llanos
• Repositorio: Repositorio Digital Universidad de los LLanos
• Idioma: eng
• OAI Identifier: oai:repositorio.unillanos.edu.co:001/3903
• Acceso en línea: https://repositorio.unillanos.edu.co/handle/001/3903; https://doi.org/10.22579/20112629.429
• Palabra clave: String searching; Experimental algorithm analysis; Strings similarity metric; String searching algorithms; Emparelhamento das cordas; Análise experimental dos algoritmos; Métrica de similaridade da cordas; algoritmos de busca da cordas; Búsqueda de cadenas; Análisis experimental de algoritmos; Métrica de similitud de cadenas
• Rights: openAccess
• License: Orinoquia - 2019