Uma nova abordagem al emparelhamento com preservação de ordem (Orinoquia, 2017)
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.
Keywords: Emparelhamento das cordas; Análise experimental dos algoritmos; Métrica de similaridade da cordas; algoritmos de busca da cordas