About
Contact
Help
Sending publications
How to publish
Advanced Search
View Item 
  •   Home
  • Facultad de Ciencias Físicas y Matemáticas
  • Artículos de revistas
  • View Item
  •   Home
  • Facultad de Ciencias Físicas y Matemáticas
  • Artículos de revistas
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse byCommunities and CollectionsDateAuthorsTitlesSubjectsThis CollectionDateAuthorsTitlesSubjects

My Account

Login to my accountRegister
Biblioteca Digital - Universidad de Chile
Revistas Chilenas
Repositorios Latinoamericanos
Tesis LatinoAmericanas
Tesis chilenas
Related linksRegistry of Open Access RepositoriesOpenDOARGoogle scholarCOREBASE
My Account
Login to my accountRegister

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

Artículo
Thumbnail
Open/Download
IconCrochemore_M.pdf (294.8Kb)
Publication date
2003
Metadata
Show full item record
Cómo citar
Crochemore, Maxime
Cómo citar
A bit-parallel suffix automaton approach for (delta, gamma)-matching in music retrieval
.
Copiar
Cerrar

Author
  • Crochemore, Maxime;
  • Iliopoulos, Costas;
  • Navarro, Gonzalo;
  • Pinzon, Yoan;
  • Salinger, Alejandro;
Abstract
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 All1 less than or equal to i less than or equal to m, \P-i - P-i'\ less than or equal to delta, and (ii) Sigma(1less than or equal toiless than or equal tom) \P-i - P-i'\ less than or equal to 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.
Identifier
URI: https://repositorio.uchile.cl/handle/2250/124638
ISSN: 0302-9743
Quote Item
STRING PROCESSING AND INFORMATION RETRIEVAL, PROCEEDINGS LECTURE NOTES IN COMPUTER SCIENCE 2857: 211-223 2003
Collections
  • Artículos de revistas
xmlui.footer.title
31 participating institutions
More than 73,000 publications
More than 110,000 topics
More than 75,000 authors
Published in the repository
  • How to publish
  • Definitions
  • Copyright
  • Frequent questions
Documents
  • Dating Guide
  • Thesis authorization
  • Document authorization
  • How to prepare a thesis (PDF)
Services
  • Digital library
  • Chilean academic journals portal
  • Latin American Repository Network
  • Latin American theses
  • Chilean theses
Dirección de Servicios de Información y Bibliotecas (SISIB)
Universidad de Chile

© 2020 DSpace
  • Access my account