The Prague Stringology Conference 2008
Domenico Cantone, Salvatore Cristofaro and Simone Faro
New Efficient Bit-Parallel Algorithms for the δ-Matching Problem with α-Bounded Gaps in Musical Sequences
| Abstract: |
| We present new efficient variants of the (δ,α)-Sequential-Sampling algorithm, recently introduced by the authors, for the δ-approximate stringmatching 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. |
| Download paper: |  |
 |
 |
| PostScript | BibTeX reference |
| Download presentation: |  |