Bit-parallel (γ,δ)-matching and suffix automata

Abstract : (δ,γ)-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-P'i|≤δ and (ii) ∑1≤i≤m|Pi-P'i|≤γ. The problem makes sense for δ≤γ≤δm. Several techniques for (δ,γ)-matching have been proposed, based on bit-parallelism or on skipping characters. We first present an O(mn log(γ) / w) worst-case time and O(n) average-case time bit-parallel algorithm (being w the number of bits in the computer word). It improves the previous O(mn log(δm) / w) worst-case time algorithm of the same type. Second, we combine our bit-parallel algorithm with suffix automata to obtain the first algorithm that skips characters using both δ and γ. This algorithm examines less characters than any previous approach, as the others do just δ-matching and check the γ-condition on the candidates. We implemented our algorithms and drew experimental results on real music, showing that our algorithms are superior to current alternatives with high values of δ.
Document type :
Journal articles
Complete list of metadatas

Cited literature [24 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-00619564
Contributor : Maxime Crochemore <>
Submitted on : Monday, July 15, 2013 - 7:38:22 PM
Last modification on : Thursday, April 19, 2018 - 2:24:03 PM
Long-term archiving on : Wednesday, October 16, 2013 - 4:12:29 AM

File

jda04.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Maxime Crochemore, Costas S. Iliopoulos, Gonzalo Navarro, Yoan Pinzon, Alejandro Salinger. Bit-parallel (γ,δ)-matching and suffix automata. Journal of Discrete Algorithms, Elsevier, 2005, 3 (2-4), pp.198-214. ⟨10.1016/j.jda.2004.08.005⟩. ⟨hal-00619564⟩

Share

Metrics

Record views

328

Files downloads

172