TY - GEN
T1 - Segment and fenwick trees for approximate order preserving matching
AU - Niquefa, Rafael
AU - Mendivelso, Juan
AU - Hernández, Germán
AU - Pinzón, Yoan
N1 - Publisher Copyright: © 2017, Springer International Publishing AG.
PY - 2017
Y1 - 2017
N2 - In this paper we combine two string searching related problems: the approximate string matching under parameters δ and γ, and the order preserving matching problem. Order-preserving matching regards the internal structure of the strings rather than their absolute values while matching under δ and γ distances permit a level of error. We formally define the δγ –order-preserving matching problem. We designed two algorithms for it based on the segment tree and the Fenwick tree, respectively. Also, we design and implement in C++ and an experimental setup to compare these algorithms with the naive solution and the updateBA algorithm introduced in [22]. The data structure based algorithms show better experimental performance due to their better lower bound of Ω (n lg n) complexity.
AB - In this paper we combine two string searching related problems: the approximate string matching under parameters δ and γ, and the order preserving matching problem. Order-preserving matching regards the internal structure of the strings rather than their absolute values while matching under δ and γ distances permit a level of error. We formally define the δγ –order-preserving matching problem. We designed two algorithms for it based on the segment tree and the Fenwick tree, respectively. Also, we design and implement in C++ and an experimental setup to compare these algorithms with the naive solution and the updateBA algorithm introduced in [22]. The data structure based algorithms show better experimental performance due to their better lower bound of Ω (n lg n) complexity.
KW - Binary indexed tree
KW - Fenwick tree
KW - Segment tree
KW - String searching
KW - Strings similarity metric
UR - https://www.scopus.com/pages/publications/85030029849
U2 - 10.1007/978-3-319-66963-2_13
DO - 10.1007/978-3-319-66963-2_13
M3 - Conference contribution
AN - SCOPUS:85030029849
SN - 9783319669625
T3 - Communications in Computer and Information Science
SP - 131
EP - 143
BT - Applied Computer Sciences in Engineering - 4th Workshop on Engineering Applications, WEA 2017, Proceedings
A2 - Figueroa-Garcia, Juan Carlos
A2 - Lopez-Santana, Eduyn Ramiro
A2 - Ferro-Escobar, Roberto
A2 - Villa-Ramirez, Jose Luis
PB - Springer Verlag
T2 - 4th Workshop on Engineering Applications, WEA 2017
Y2 - 27 September 2017 through 29 September 2017
ER -