%0 Journal Article
%T New Algorithms for ¦Ä¦Ã-Order Preserving Matching
%A Germ¨¢n Hern¨¢ndez
%A Juan Mendivelso
%A Rafael Niquefa
%A Yoan Pinz¨®n
%J -
%D 2018
%R https://doi.org/10.14483/23448393.13248
%X Abstract (en_US) Context: Order-preserving matching regards the relative order of strings. However, its application areas require more flexibility in the matching paradigm. We advance in this direction in this paper that extends our previous work [27]. Method: We define ¦Ã -order preserving matching as an approximate variant of order-preserving matching. We devise two solutions for it based on segment and Fenwick trees: segtreeBA and bitBA. Results: We experimentally show the efficiency of our algorithms compared to the ones presented in [26] (naiveA and updateBA). Also, we present applications of our approach in music retrieval and stock market analysis. Conclusions: Even though the worst-case time complexity of the proposed algorithms (namely, O(nm log m)) is higher than the £¿(nm)-time complexity of updateBA, their ¦¸ (n log n) lower bound makes them more efficient in practice. On the other hand, we show that our approach is useful to identify similarity in music melodies and stock price trends through real application examples. Abstract (es_ES) Contexto: El emparejamiento de cadenas seg¨²n el orden compara la estructura de las cadenas de texto. Sin embargo, sus ¨¢reas de aplicaci¨®n requieren mayor flexibilidad en el criterio de comparaci¨®n. Este art¨ªculo avanza en esta direcci¨®n al extender [27]. M¨¦todo: Se define la b¨²squeda de orden ¨C ¦Ã como una variante aproximada del problema de emparejamiento de cadenas seg¨²n orden. Se proponen dos soluciones basadas en ¨¢rboles de segmentos y ¨¢rboles Fenwick: segtree BA and bit BA. Resultados: La eficiencia de los algoritmos propuestos se muestra experimentalmente compar¨¢ndolos con los algoritmos presentados en [26] (naive A y update BA). Adem¨¢s, se presentan aplicaciones. Conclusiones: A pesar de que la complejidad en tiempo de peor-caso de los algoritmos propuestos (a decir, O (nm log m)) es mayor que la complejidad de update BA (£¿ (nm)), su cota baja ¦¸(n log n) los hace m¨¢s eficientes en la pr¨¢ctica. Tambi¨¦n se muestran aplicaciones del enfoque propuesto en recuperaci¨®n de m¨²sica y an¨¢lisis del mercado de acciones con ejemplos reales
%K String searching
%K experimental algorithm analysis
%K strings similarity metric.
%U https://revistas.udistrital.edu.co/index.php/reving/article/view/13248