Icono govco
 

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

Vista sencilla de ítem
dc.contributor.authorMendivelso Moreno, Juan Carlosspa
dc.contributor.authorNiquefa Velásquez, Rafael Albertospa
dc.contributor.authorPinzón Ardila, Yoán Joséspa
dc.contributor.authorHernández Pérez, Germán Jairospa
dc.date.accessioned2017-07-16 00:00:00
dc.date.accessioned2022-06-13T17:42:08Z
dc.date.available2017-07-16 00:00:00
dc.date.available2022-06-13T17:42:08Z
dc.date.issued2017-07-16
dc.description.abstractUn 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.spa
dc.description.abstractA 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.eng
dc.format.mimetypeapplication/pdfeng
dc.identifier.doi10.22579/20112629.429
dc.identifier.eissn2011-2629
dc.identifier.issn0121-3709
dc.identifier.urihttps://repositorio.unillanos.edu.co/handle/001/2651
dc.identifier.urlhttps://doi.org/10.22579/20112629.429
dc.language.isoengeng
dc.publisherUniversidad de los Llanosspa
dc.relation.bitstreamhttps://orinoquia.unillanos.edu.co/index.php/orinoquia/article/download/429/1020
dc.relation.citationeditionNúm. 1 Sup , Año 2017spa
dc.relation.citationendpage44
dc.relation.citationissue1 Supspa
dc.relation.citationstartpage37
dc.relation.citationvolume21spa
dc.relation.ispartofjournalOrinoquiaspa
dc.relation.referencesApostolico A, Galil Z. 1997. Pattern matching algorithms. Oxford University Press, USA.eng
dc.relation.referencesCambouropoulos E, Crochemore M, Iliopoulos C, Mouchard L, Pinzon Y. Algorithms for computing approximate repetitions in musical sequences. International Journal of Computer Mathematics, 2002;79(11):1135–1148.eng
dc.relation.referencesCrochemore M, Iliopoulos C, Lecroq T, Plandowski W, Rytter W. 2002. Three Heuristics for δ-Matching, δ-BM Algorithms. Proceedings of the 13th Annual Symposium on Combinatorial Pattern Matching. Springer-Verlag London, UK,178–189.eng
dc.relation.referencesCrochemore M, et al. Occurrence and Substring Heuristics for d-Matching. Fundamenta Informaticae. 2003;56(1):1–21.eng
dc.relation.referencesClifford R, Iliopoulos C. Approximate string matching for music analysis. Soft Computing, 2004;8(9):597–603.eng
dc.relation.referencesCantone D, Cristofaro S, Faro S. 2004. Efficient Algorithms for the δ- Approximate String Matching Problem in Musical Sequences. Proc. of the Prague Stringology Conference.eng
dc.relation.referencesCrochemore M, Iliopoulos C, Navarro G, Pinzon Y, Salinger A. Bit-parallel (δ,γ)-Matching and Suffix Automata. Journal of Discrete Algorithms. 2005;3( 2-4):198–214.eng
dc.relation.referencesLee I, Clifford R, Kim S-R. 2006. Algorithms on extended (δ,γ)-matching. Computational Science and Its Applications-ICCSA. Springer. 1137–1142. Lee I, Mendivelso J, Pinzon Y. 2008. δγ–parameterized matching. String Processing and Information Retrieval. Springer. 236–248.eng
dc.relation.referencesMendivelso J. 2010. Definition and solution of a new string searching variant termed δγ–parameterized matching. Master’s thesis. Universidad Nacional de Colombia.eng
dc.relation.referencesMendivelso J, Lee I, Pinzon Y. 2012. Approximate function matching under δ-and γ-distances. String Processing and Information Retrieval. Springer. 348–359.eng
dc.relation.referencesMendivelso J, Pino C, Niño L, Pinzon Y. Approximate abelian periods to find motifs in biological sequences. Lecture Notes in Bioinformatics, Computational Intelligence Methods for Bioinformatics and Biostatistics. 2015;8623:121-130.eng
dc.relation.referencesMendivelso J, Pinzon Y. 2014. A novel approach to approximate parikh matching for comparing composition in biological sequences. Proceedings of the 6th International Conference on Bioinformatics and Computational Biology.eng
dc.relation.referencesKim J, Eades P, Fleischer R, Hong S H, Iliopoulos C S, Park K, Puglisi S J, Tokuyama T. Order-preserving matching. Theoretical Computer Science. 2014;525:68–79.eng
dc.relation.referencesKubica M, Kulczynski T, Radoszewski J, Rytter W, Walen T. A linear time algorithm for consecutive permutation pattern matching. Information Processing Letters. 2013;113(12):430–433.eng
dc.relation.referencesCrochemore M, Iliopoulos CS, Kociumaka T, Kubica M, et al. 2013. Order preserving suffix trees and their algorithmic applications. arXiv preprint arXiv:1303.6872.eng
dc.relation.referencesCrochemore M, Iliopoulos CS, Kociumaka T, Kubica M, Langiu A, Pissis SP, Radoszewski J, Rytter W, Walen T. 2013a. Order-preserving incomplete suffix trees and order-preserving indexes. String Processing and Information Retrieval. Springer. 84–95.eng
dc.relation.referencesChhabra T, Tarhio J. 2014. Order-preserving matching with filtration. Experimental Algorithms. Springer. 307–314.eng
dc.relation.referencesFaro S, Kulekci O. 2015. Efficient algorithms for the order preserving pattern matching problem. arXiv preprint arXiv:1501.04001.eng
dc.relation.referencesCrochemore M, Iliopoulos CS, Kociumaka T, Kubica M, Langiu A, Pissis SP, Radoszewski J, Rytter W, Walen T. 2015. Order-preserving indexing. Theoretical Computer Science.eng
dc.relation.referencesHasan M M, Islam AS, Rahman MS, Rahman MS. Order preserving pattern matching revisited. Pattern Recognition Letters. 2015;55:15–21.eng
dc.relation.referencesChhabra T, Kulekci MO, Tarhio J. 2015. Alternative algorithms for order-preserving matching. Proceedings of the Prague Stringology Conference. 36–46.eng
dc.relation.referencesGawrychowski P, Uznanski P. 2015. Order-preserving pattern matching with k mismatches. Theoretical Computer Science.eng
dc.rightsOrinoquia - 2019eng
dc.rights.accessrightsinfo:eu-repo/semantics/openAccesseng
dc.rights.coarhttp://purl.org/coar/access_right/c_abf2eng
dc.rights.urihttps://creativecommons.org/licenses/by/4.0/eng
dc.sourcehttps://orinoquia.unillanos.edu.co/index.php/orinoquia/article/view/429eng
dc.subjectShrubseng
dc.subjectdigestioneng
dc.subjectcultivated forageseng
dc.subjectnutrientseng
dc.subjectnutritional supplementationeng
dc.subjectArbustosspa
dc.subjectdigestiónspa
dc.subjectforrajes cultivadosspa
dc.subjectnutrimentosspa
dc.subjectsuplementación nutricionalspa
dc.titleUna nueva aproximación al emparejamiento con preservación de ordenspa
dc.title.translatedA novel approach to approximate order preserving matchingeng
dc.typeArtículo de revistaspa
dc.typeJournal Articleeng
dc.type.coarhttp://purl.org/coar/resource_type/c_6501eng
dc.type.coarversionhttp://purl.org/coar/version/c_970fb48d4fbd8a85eng
dc.type.contentTexteng
dc.type.driverinfo:eu-repo/semantics/articleeng
dc.type.localSección Artículosspa
dc.type.localSección Articleseng
dc.type.versioninfo:eu-repo/semantics/publishedVersioneng
dspace.entity.typePublication

Archivos

Colecciones

Revista Orinoquia