A bit-parallel suffix automaton approach for $(\delta,\gamma)$-matching in music retrieval

Maxime Crochemore (1, 2) , Costas S. Iliopoulos (2) , Gonzalo Navarro (3) , Yoan J. Pinzon (4)

1 LIGM - Laboratoire d'Informatique Gaspard-Monge
2 Department of Computer Science [London]
3 Universidad de Chile - Department of Computer Science
4 Laboratorio de Cómputo Especializado

(δ,γ)-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) ∀ 1 ≤ i ≤ m, |P i  − P′ i | ≤ δ, and (ii) ∑ 1 ≤ i ≤ m |P i  − P′ i | ≤ γ. Several techniques for (δ,γ)-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 δ and γ. We implemented our algorithm and drew experimental results on real music showing that our algorithm is superior to current alternatives.

Domaines: Algorithme et structure de données [cs.DS]

Maxime Crochemore, Costas S. Iliopoulos, Gonzalo Navarro, Yoan J. Pinzon. A bit-parallel suffix automaton approach for $(\delta,\gamma)$-matching in music retrieval. 10th String Processing and Information Retrieval (SPIRE'2003), 2003, Manaus, Brazil. pp.211-223, ⟨10.1007/978-3-540-39984-1_16⟩. ⟨hal-00619985⟩