We present new efficient variants of the (δ, α)-Sequential-Sampling algorithm, recently introduced by the authors, for the δ-approximate string matching problem with α-bounded gaps. These algorithms, which have practical applications in music information retrieval and analysis, make use of the well-known technique of bit-parallelism. An extensive comparison with the most efficient algorithms present in the literature for the same search problem shows that our newly proposed solutions achieve very good results in practice, in terms of both space and time complexity, and, in most cases, they outperform existing algorithms. Moreover, we show how to adapt our algorithms to other variants of the approximate matching problem with gaps, which are particularly relevant for their applications in other fields than music (e.g., molecular biology).
New efficient bit-parallel algorithms for the (delta,alpha)-matching problem with applications in music information retrieval
CANTONE, Domenico;FARO, SIMONE
2009-01-01
Abstract
We present new efficient variants of the (δ, α)-Sequential-Sampling algorithm, recently introduced by the authors, for the δ-approximate string matching problem with α-bounded gaps. These algorithms, which have practical applications in music information retrieval and analysis, make use of the well-known technique of bit-parallelism. An extensive comparison with the most efficient algorithms present in the literature for the same search problem shows that our newly proposed solutions achieve very good results in practice, in terms of both space and time complexity, and, in most cases, they outperform existing algorithms. Moreover, we show how to adapt our algorithms to other variants of the approximate matching problem with gaps, which are particularly relevant for their applications in other fields than music (e.g., molecular biology).File | Dimensione | Formato | |
---|---|---|---|
2009 CantoneCristofaroFaro IJFCS.pdf
solo gestori archivio
Tipologia:
Versione Editoriale (PDF)
Licenza:
Non specificato
Dimensione
347 kB
Formato
Adobe PDF
|
347 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.