Name
Title | ||
|---|---|---|
A Bit-Parallel Suffix Automation Approach for (delta, gamma)-Matching in Music Retrieval |
Abstract | ||
|---|---|---|
(delta, gamma)-Matching is a string matching problem with applications to music retrieval. The goal is, given a pattern P-1...m and a text T-1...n on an alphabet of integers, find the occurrences P' of the pattern in the text such that (i) For All1 less than or equal to i less than or equal to m, \P-i - P-i'\ less than or equal to delta, and (ii) Sigma(1less than or equal toiless than or equal tom) \P-i - P-i'\ less than or equal to gamma. Several techniques for (delta, gamma)-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 delta and gamma. We implemented our algorithm and drew experimental results on real music showing that our algorithm is superior to current alternatives. |
Year | DOI | Venue |
|---|---|---|
2003 | 10.1007/978-3-540-39984-1_16 | Lecture Notes in Computer Science |
Keywords | DocType | Volume |
string matching | Conference | 2857 |
ISSN | Citations | PageRank |
0302-9743 | 0 | 0.34 |
References | Authors | |
9 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Maxime Crochemore | 1 | 2655 | 281.75 |
| Costas S. Iliopoulos | 2 | 1534 | 167.43 |
| Gonzalo Navarro | 3 | 6088 | 345.16 |
| Yoan J. Pinzon | 4 | 158 | 16.81 |