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.