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 represent...

Full description

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

id	Unillanos2_b54baa57337969cefa5aeaa65e973487
oai_identifier_str	oai:repositorio.unillanos.edu.co:001/2651
network_acronym_str	Unillanos2
network_name_str	Repositorio Digital Universidad de los LLanos
repository_id_str
dc.title.spa.fl_str_mv	Una nueva aproximación al emparejamiento con preservación de orden
dc.title.translated.eng.fl_str_mv	A novel approach to approximate order preserving matching
title	Una nueva aproximación al emparejamiento con preservación de orden
spellingShingle	Una nueva aproximación al emparejamiento con preservación de orden Shrubs digestion cultivated forages nutrients nutritional supplementation Arbustos digestión forrajes cultivados nutrimentos suplementación nutricional
title_short	Una nueva aproximación al emparejamiento con preservación de orden
title_full	Una nueva aproximación al emparejamiento con preservación de orden
title_fullStr	Una nueva aproximación al emparejamiento con preservación de orden
title_full_unstemmed	Una nueva aproximación al emparejamiento con preservación de orden
title_sort	Una nueva aproximación al emparejamiento con preservación de orden
dc.creator.fl_str_mv	Mendivelso Moreno, Juan Carlos Niquefa Velásquez, Rafael Alberto Pinzón Ardila, Yoán José Hernández Pérez, Germán Jairo
dc.contributor.author.spa.fl_str_mv	Mendivelso Moreno, Juan Carlos Niquefa Velásquez, Rafael Alberto Pinzón Ardila, Yoán José Hernández Pérez, Germán Jairo
dc.subject.eng.fl_str_mv	Shrubs digestion cultivated forages nutrients nutritional supplementation
topic	Shrubs digestion cultivated forages nutrients nutritional supplementation Arbustos digestión forrajes cultivados nutrimentos suplementación nutricional
dc.subject.spa.fl_str_mv	Arbustos digestión forrajes cultivados nutrimentos suplementación nutricional
description	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.
publishDate	2017
dc.date.accessioned.none.fl_str_mv	2017-07-16 00:00:00 2022-06-13T17:42:08Z
dc.date.available.none.fl_str_mv	2017-07-16 00:00:00 2022-06-13T17:42:08Z
dc.date.issued.none.fl_str_mv	2017-07-16
dc.type.spa.fl_str_mv	Artículo de revista
dc.type.eng.fl_str_mv	Journal Article
dc.type.coar.fl_str_mv	http://purl.org/coar/resource_type/c_2df8fbb1
dc.type.driver.eng.fl_str_mv	info:eu-repo/semantics/article
dc.type.local.spa.fl_str_mv	Sección Artículos
dc.type.local.eng.fl_str_mv	Sección Articles
dc.type.version.eng.fl_str_mv	info:eu-repo/semantics/publishedVersion
dc.type.coar.eng.fl_str_mv	http://purl.org/coar/resource_type/c_6501
dc.type.content.eng.fl_str_mv	Text
dc.type.coarversion.eng.fl_str_mv	http://purl.org/coar/version/c_970fb48d4fbd8a85
format	http://purl.org/coar/resource_type/c_6501
status_str	publishedVersion
dc.identifier.issn.none.fl_str_mv	0121-3709
dc.identifier.uri.none.fl_str_mv	https://repositorio.unillanos.edu.co/handle/001/2651
dc.identifier.doi.none.fl_str_mv	10.22579/20112629.429
dc.identifier.eissn.none.fl_str_mv	2011-2629
dc.identifier.url.none.fl_str_mv	https://doi.org/10.22579/20112629.429
identifier_str_mv	0121-3709 10.22579/20112629.429 2011-2629
url	https://repositorio.unillanos.edu.co/handle/001/2651 https://doi.org/10.22579/20112629.429
dc.language.iso.eng.fl_str_mv	eng
language	eng
dc.relation.references.eng.fl_str_mv	Apostolico A, Galil Z. 1997. Pattern matching algorithms. Oxford University Press, USA. Cambouropoulos 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. Crochemore 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. Crochemore M, et al. Occurrence and Substring Heuristics for d-Matching. Fundamenta Informaticae. 2003;56(1):1–21. Clifford R, Iliopoulos C. Approximate string matching for music analysis. Soft Computing, 2004;8(9):597–603. Cantone D, Cristofaro S, Faro S. 2004. Efficient Algorithms for the δ- Approximate String Matching Problem in Musical Sequences. Proc. of the Prague Stringology Conference. Crochemore 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. Lee 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. Mendivelso J. 2010. Definition and solution of a new string searching variant termed δγ–parameterized matching. Master’s thesis. Universidad Nacional de Colombia. Mendivelso J, Lee I, Pinzon Y. 2012. Approximate function matching under δ-and γ-distances. String Processing and Information Retrieval. Springer. 348–359. Mendivelso 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. Mendivelso 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. Kim 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. Kubica 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. Crochemore M, Iliopoulos CS, Kociumaka T, Kubica M, et al. 2013. Order preserving suffix trees and their algorithmic applications. arXiv preprint arXiv:1303.6872. Crochemore 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. Chhabra T, Tarhio J. 2014. Order-preserving matching with filtration. Experimental Algorithms. Springer. 307–314. Faro S, Kulekci O. 2015. Efficient algorithms for the order preserving pattern matching problem. arXiv preprint arXiv:1501.04001. Crochemore M, Iliopoulos CS, Kociumaka T, Kubica M, Langiu A, Pissis SP, Radoszewski J, Rytter W, Walen T. 2015. Order-preserving indexing. Theoretical Computer Science. Hasan M M, Islam AS, Rahman MS, Rahman MS. Order preserving pattern matching revisited. Pattern Recognition Letters. 2015;55:15–21. Chhabra T, Kulekci MO, Tarhio J. 2015. Alternative algorithms for order-preserving matching. Proceedings of the Prague Stringology Conference. 36–46. Gawrychowski P, Uznanski P. 2015. Order-preserving pattern matching with k mismatches. Theoretical Computer Science.
dc.relation.bitstream.none.fl_str_mv	https://orinoquia.unillanos.edu.co/index.php/orinoquia/article/download/429/1020
dc.relation.citationedition.spa.fl_str_mv	Núm. 1 Sup , Año 2017
dc.relation.citationendpage.none.fl_str_mv	44
dc.relation.citationissue.spa.fl_str_mv	1 Sup
dc.relation.citationstartpage.none.fl_str_mv	37
dc.relation.citationvolume.spa.fl_str_mv	21
dc.relation.ispartofjournal.spa.fl_str_mv	Orinoquia
dc.rights.eng.fl_str_mv	Orinoquia - 2019
dc.rights.uri.eng.fl_str_mv	https://creativecommons.org/licenses/by/4.0/
dc.rights.accessrights.eng.fl_str_mv	info:eu-repo/semantics/openAccess
dc.rights.coar.eng.fl_str_mv	http://purl.org/coar/access_right/c_abf2
rights_invalid_str_mv	Orinoquia - 2019 https://creativecommons.org/licenses/by/4.0/ http://purl.org/coar/access_right/c_abf2
eu_rights_str_mv	openAccess
dc.format.mimetype.eng.fl_str_mv	application/pdf
dc.publisher.spa.fl_str_mv	Universidad de los Llanos
dc.source.eng.fl_str_mv	https://orinoquia.unillanos.edu.co/index.php/orinoquia/article/view/429
institution	Universidad de los Llanos
bitstream.url.fl_str_mv	https://dspace7-unillanos.metacatalogo.org/bitstreams/d41acad8-acdd-4fb6-8272-933cef4d49c2/download
bitstream.checksum.fl_str_mv	2653ba8541767e1147a294638d9e9a51
bitstream.checksumAlgorithm.fl_str_mv	MD5
repository.name.fl_str_mv	Repositorio Universidad de Los Llanos
repository.mail.fl_str_mv	repositorio@unillanos.edu.co
_version_	1812104616712601600
spelling	Mendivelso Moreno, Juan Carlos41cca984a4e0a0a795e636066cd6338d300Niquefa Velásquez, Rafael Albertob55268506227528a599a87af61ae7964300Pinzón Ardila, Yoán José6f82618d234b37dbeb966d06243ed7cc300Hernández Pérez, Germán Jairo66571677097cf76f6d8382e3c01917583002017-07-16 00:00:002022-06-13T17:42:08Z2017-07-16 00:00:002022-06-13T17:42:08Z2017-07-160121-3709https://repositorio.unillanos.edu.co/handle/001/265110.22579/20112629.4292011-2629https://doi.org/10.22579/20112629.429Un 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/pdfengUniversidad de los LlanosOrinoquia - 2019https://creativecommons.org/licenses/by/4.0/info:eu-repo/semantics/openAccesshttp://purl.org/coar/access_right/c_abf2https://orinoquia.unillanos.edu.co/index.php/orinoquia/article/view/429Shrubsdigestioncultivated foragesnutrientsnutritional supplementationArbustosdigestiónforrajes cultivadosnutrimentossuplementación nutricionalUna nueva aproximación al emparejamiento con preservación de ordenA novel approach to approximate order preserving matchingArtículo de revistaJournal Articleinfo:eu-repo/semantics/articleSección ArtículosSección Articlesinfo:eu-repo/semantics/publishedVersionhttp://purl.org/coar/resource_type/c_6501http://purl.org/coar/resource_type/c_2df8fbb1Texthttp://purl.org/coar/version/c_970fb48d4fbd8a85Apostolico A, Galil Z. 1997. Pattern matching algorithms. Oxford University Press, USA.Cambouropoulos 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.Crochemore 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.Crochemore M, et al. Occurrence and Substring Heuristics for d-Matching. Fundamenta Informaticae. 2003;56(1):1–21.Clifford R, Iliopoulos C. Approximate string matching for music analysis. Soft Computing, 2004;8(9):597–603.Cantone D, Cristofaro S, Faro S. 2004. Efficient Algorithms for the δ- Approximate String Matching Problem in Musical Sequences. Proc. of the Prague Stringology Conference.Crochemore 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.Lee 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.Mendivelso J. 2010. Definition and solution of a new string searching variant termed δγ–parameterized matching. Master’s thesis. Universidad Nacional de Colombia.Mendivelso J, Lee I, Pinzon Y. 2012. Approximate function matching under δ-and γ-distances. String Processing and Information Retrieval. Springer. 348–359.Mendivelso 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.Mendivelso 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.Kim 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.Kubica 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.Crochemore M, Iliopoulos CS, Kociumaka T, Kubica M, et al. 2013. Order preserving suffix trees and their algorithmic applications. arXiv preprint arXiv:1303.6872.Crochemore 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.Chhabra T, Tarhio J. 2014. Order-preserving matching with filtration. Experimental Algorithms. Springer. 307–314.Faro S, Kulekci O. 2015. Efficient algorithms for the order preserving pattern matching problem. arXiv preprint arXiv:1501.04001.Crochemore M, Iliopoulos CS, Kociumaka T, Kubica M, Langiu A, Pissis SP, Radoszewski J, Rytter W, Walen T. 2015. Order-preserving indexing. Theoretical Computer Science.Hasan M M, Islam AS, Rahman MS, Rahman MS. Order preserving pattern matching revisited. Pattern Recognition Letters. 2015;55:15–21.Chhabra T, Kulekci MO, Tarhio J. 2015. Alternative algorithms for order-preserving matching. Proceedings of the Prague Stringology Conference. 36–46.Gawrychowski P, Uznanski P. 2015. Order-preserving pattern matching with k mismatches. Theoretical Computer Science.https://orinoquia.unillanos.edu.co/index.php/orinoquia/article/download/429/1020Núm. 1 Sup , Año 2017441 Sup3721OrinoquiaPublicationOREORE.xmltext/xml2525https://dspace7-unillanos.metacatalogo.org/bitstreams/d41acad8-acdd-4fb6-8272-933cef4d49c2/download2653ba8541767e1147a294638d9e9a51MD51001/2651oai:dspace7-unillanos.metacatalogo.org:001/26512024-04-17 16:38:05.15https://creativecommons.org/licenses/by/4.0/Orinoquia - 2019metadata.onlyhttps://dspace7-unillanos.metacatalogo.orgRepositorio Universidad de Los Llanosrepositorio@unillanos.edu.co

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

Publicaciones similares