A Bit-parallel Suffix Automaton Approach
for (delta,gamma)-Matching in Music Retrieval
Maxime Crochemore, Costas Iliopoulos, Gonzalo Navarro and Yoan Pinzón
(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 all 1<=i<=m, |P[i]-P'[i]| <= delta, and
(ii) sum(1<=i<=m) |P[i]-P'[i]| <= 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.