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.