Name
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−Pi′|⩽δ, and (ii) ∑1⩽i⩽m|Pi−Pi′|⩽γ. 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(mnlog(γ)/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(mnlog(δ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 δ. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1016/j.jda.2004.08.005 | Journal of Discrete Algorithms |
Keywords | DocType | Volume |
Bit-parallelism,Approximate string matching,MIDI music retrieval | Journal | 3 |
Issue | ISSN | Citations |
2 | 1570-8667 | 7 |
PageRank | References | Authors |
0.66 | 14 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Maxime Crochemore | 1 | 2655 | 281.75 |
| Costas S. Iliopoulos | 2 | 1534 | 167.43 |
| Gonzalo Navarro | 3 | 647 | 35.74 |
| Yoan J. Pinzon | 4 | 158 | 16.81 |
| Alejandro Salinger | 5 | 151 | 12.53 |