Uma nova abordagem al emparelhamento com preservação de ordem
DOI:
https://doi.org/10.22579/20112629.429Palavras-chave:
Emparelhamento das cordas, Análise experimental dos algoritmos, Métrica de similaridade da cordas, algoritmos de busca da cordasResumo
Um grande problema na análise do mercado de ações e na recuperação de informações musicais é o emparelhamento com a preservação de ordem. Esse problema é uma variante recentemente introduzida do problema de correspondência de cordas que procura por substrings no texto cuja representação natural corresponde à representação natural do padrão. A representação natural de uma corda X é uma corda que contém as classificações dos caracteres que ocorrem em cada posição de X. Então, a correspondência de preservação de ordem considera a estrutura interna das cordas em vez de seus valores absolutos. Mas na análise do mercado de ações, bem como na recuperação da informação musical, é necessária mais flexibilidade: não são apenas as sub-cordas com exatamente a mesma estrutura que interessam, mas também as que são semelhantes. Neste artigo, propomos uma versão aproximada da emparelhamento com preservação de ordem com base nas distâncias δγ- que permitem um erro individual entre a classificação de símbolos correspondentes (delimitada por δ) e um erro global de Todas as posições (delimitadas por γ). Apresentamos um algoritmo que resolve este problema em O(nm+m log m). Os resultados experimentais verificaram a eficiência do algoritmo proposto.Downloads
Referências
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.
