TY - CHAP
T1 - A bit-parallel suffix automaton approach for (δ,γ)-matching in music retrieval
AU - Crochemore, Maxime
AU - Iliopoulos, Costas S.
AU - Navarro, Gonzalo
AU - Pinzon, Yoan J.
PY - 2003
Y1 - 2003
N2 - (δ,γ)-Matching is a string matching problem with applications to music retrieval. The goal is, given a pattern P1...m and a text T1...n on an alphabet of integers, find the occurrences P' of the pattern in the text such that (i) ∀1 ≤ i ≤ m, |Pi - Pi′ ≤ δ, and (ii) Σ1≤i≤m |Pi - Pi| ≤ γ. Several techniques for (δ,γ)-matching have been proposed. In this paper we show that a classical string matching technique that combines bit-parallelism and suffix automata can be successfully adapted to this problem. This is the first character-skipping algorithm that skips characters using both δ and γ. We implemented our algorithm and drew experimental results on real music showing that our algorithm is superior to current alternatives.
AB - (δ,γ)-Matching is a string matching problem with applications to music retrieval. The goal is, given a pattern P1...m and a text T1...n on an alphabet of integers, find the occurrences P' of the pattern in the text such that (i) ∀1 ≤ i ≤ m, |Pi - Pi′ ≤ δ, and (ii) Σ1≤i≤m |Pi - Pi| ≤ γ. Several techniques for (δ,γ)-matching have been proposed. In this paper we show that a classical string matching technique that combines bit-parallelism and suffix automata can be successfully adapted to this problem. This is the first character-skipping algorithm that skips characters using both δ and γ. We implemented our algorithm and drew experimental results on real music showing that our algorithm is superior to current alternatives.
UR - https://www.scopus.com/pages/publications/0142218943
U2 - 10.1007/978-3-540-39984-1_16
DO - 10.1007/978-3-540-39984-1_16
M3 - Chapter
AN - SCOPUS:0142218943
SN - 3540201777
SN - 9783540201779
VL - 2857
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 211
EP - 223
BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
A2 - Nascimento, Mario A.
A2 - de Moura, Edleno S.
A2 - Oliveira, Arlindo L.
PB - Springer Verlag
ER -