Bit-parallel Suffix (delta,gamma)-Matching Suffix Automata
Maxime Crochemore, Costas Iliopoulos, Gonzalo Navarro, Yoan Pinzon and
Alejandro Salinger
(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 with high values of delta.