The Prague Stringology Conference 2004
Domenico Cantone, Salvatore Cristofaro and Simone Faro
Efficient Algorithms for the δ-Approximate String Matching Problem in Musical Sequences
| Abstract: |
|
The δ-approximate string matching problem, recently
introduced in connection with applications to music retrieval, is
a generalization of the exact string matching problem for
alphabets of integer numbers. In the δ-approximate
variant, (exact) matching between any pair of symbols/integers a
and b is replaced by the notion of δ-matching =δ,
where a =δ b if and only if |a-b| ≤
δ for a given
value of the approximation bound δ. After surveying the state-of-the-art, we describe some new effective algorithms for the δ-matching problem, obtained by adapting existing string matching algorithms. The algorithms discussed in the paper are then compared with respect to a large set of experimental tests. From these, in particular it turns out that two of our newly proposed algorithms often achieve the best performances, especially in the case of large alphabets and short patterns, which typically occurs in practical situations in music retrieval. |
| Download paper: |  |
 |
| PostScript |