Mendivelso Moreno, Juan CarlosNiquefa Velásquez, Rafael AlbertoPinzón Ardila, Yoán JoséHernández Pérez, Germán Jairo2017-07-162022-06-132017-07-162022-06-132017-07-160121-3709https://repositorio.unillanos.edu.co/handle/001/2651Un 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.A problem with important applications in stock market analysis and music information retrieval is order-preserving matching. This problem is a recently introduced variant of the string matching problem that searches for substrings in the text whose natural representation matches the natural representation of the pattern. The natural representation of a string X is a string that contains the rankings of the characters occurring at each position of X. Then, order-preserving matching regards the internal structure of the strings rather than their absolute values. But both stock market analysis and music information retrieval require more flexibility: not only the substrings with exactly the same structure are of interest, but also the ones that are similar. In this paper, we propose an approximate version of order-preserving matching based on the δγ- distances that permit an individual error between the ranking of corresponding symbols (bounded by δ) and a global error of all the positions (bounded by γ). We present an algorithm that solves this problem in O(nm+m log m). Experimental results verify the efficiency of the proposed algorithm.application/pdfengOrinoquia - 2019Shrubsdigestioncultivated foragesnutrientsnutritional supplementationArbustosdigestiónforrajes cultivadosnutrimentossuplementación nutricionalArtículo de revistainfo:eu-repo/semantics/openAccess10.22579/20112629.4292011-2629https://doi.org/10.22579/20112629.429http://purl.org/coar/access_right/c_abf2