| Journal: | Ingeniería (Bogotá) |
| Database: | |
| System number: | 000538095 |
| ISSN: | 0121-750X |
| Authors: | Mendivelso, Juan1 Niquefa, Rafael2 Pinzón, Yoan3 Hernández, Germán1 |
| Institutions: | 1Universidad Nacional de Colombia, Bogotá. Colombia 2Politécnico Grancolombiano, Bogotá. Colombia 3Pontificia Universidad Javeriana, Cali, Bogotá. Colombia |
| Year: | 2018 |
| Season: | May-Ago |
| Volumen: | 23 |
| Number: | 2 |
| Pages: | 190-202 |
| Country: | Colombia |
| Language: | Español |
| Spanish abstract | 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-δϒ 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 bitBA. Resultados: La eficiencia de los algoritmos propuestos se muestra experimentalmente comparándolos con los algoritmos presentados en 26 (naiveA y updateBA). 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 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. |
| English abstract | Context: Order-preserving matching regards comparing the relative order of symbols within different 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. |
| Keyword: | Análisis experimental de algoritmos, Búsqueda de texto, Métrica de similitud. |
| Keyword: | String searching, Experimental algorithm analysis, Strings similarity metric, Language: English |
| Full text: | Texto completo (Ver HTML) Texto completo (Ver PDF) |
