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

Maxime Crochemore; Costas S. Iliopoulos; Gonzalo Navarro; Yoan J. Pinzon

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

Maxime Crochemore ^{1, 2} Costas S. Iliopoulos ² Gonzalo Navarro ³ Yoan J. Pinzon ⁴

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

Abstract : (δ,γ)-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.

Document type :

Conference papers

Domain :

Computer Science [cs] / Data Structures and Algorithms [cs.DS]

Complete list of metadatas

https://hal-upec-upem.archives-ouvertes.fr/hal-00619985
Contributor : Maxime Crochemore <>
Submitted on : Friday, December 18, 2015 - 9:21:38 AM
Last modification on : Thursday, April 19, 2018 - 2:24:03 PM
Long-term archiving on : Saturday, March 19, 2016 - 11:40:15 AM

SPIRE2003.pdf

Files produced by the author(s)

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

File

Identifiers

Collections

Citation

Export

Metrics

252

112

Contact

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

File

Identifiers

Collections

Citation

Export

Share

Metrics

252

112

Contact