We present a new efficient algorithm for the δ-approximate matching problem with α-bounded gaps. The δ-approximate matching problem, recently introduced in connection with applications in music retrieval, generalizes the exact string matching problem by relaxing the notion of matching. Here we consider the case in which matchings may contain bounded gaps.An extensive comparison with the only (to our knowledge) other solution existing in the literature for the same problem, due to Crochemore et al., indicates that our algorithm is more efficient, especially in the cases of large alphabets and long patterns. In addition, our algorithm computes the total number of approximate matchings for each position of the text, requiring only O(m)-space, where m is the length of the pattern.
An Efficient Algorithm for δ-Approximate-Matching with α-Bounded Gaps in Musical Sequences
CANTONE, Domenico;FARO, SIMONE
2005-01-01
Abstract
We present a new efficient algorithm for the δ-approximate matching problem with α-bounded gaps. The δ-approximate matching problem, recently introduced in connection with applications in music retrieval, generalizes the exact string matching problem by relaxing the notion of matching. Here we consider the case in which matchings may contain bounded gaps.An extensive comparison with the only (to our knowledge) other solution existing in the literature for the same problem, due to Crochemore et al., indicates that our algorithm is more efficient, especially in the cases of large alphabets and long patterns. In addition, our algorithm computes the total number of approximate matchings for each position of the text, requiring only O(m)-space, where m is the length of the pattern.File | Dimensione | Formato | |
---|---|---|---|
Cantone-Cristofaro-Faro-WEA2005.pdf
solo gestori archivio
Tipologia:
Versione Editoriale (PDF)
Licenza:
Non specificato
Dimensione
200.15 kB
Formato
Adobe PDF
|
200.15 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.