Affiliations: Institut Gaspard Monge, Université Marne-la-Vallée, 77454 Marne-la-Vallée CEDEX 2, France | Dept. of Computer Science, King's College London, London WC2R 2LS, UK | School of Computing, Curtin University of Technology, GPO Box 1987 U, WA, Australia | LIFAR-ABISS, Faculté des Sciences et Techniques,
Université de Rouen, 76821 Mont-Saint-Aignan CEDEX, France | Instytut Informatyki, Uniwersytet Warszawski, Banacha 2, 02-097, Warszawa, Poland | Dept. of Computer Science, New Jersey Institute of Technology, USA
Abstract: We consider a version of pattern matching useful in processing large
musical data: δ-matching, which consists in finding matches which are
δ-approximate in the sense of the distance measured as maximum
difference between symbols. The alphabet is an interval of integers, and the
distance between two symbols a, b is measured as |a-b|. We also consider
(δ, γ)-matching, where γ is a bound on the total sum of the
differences. We first consider "occurrence heuristics" by adapting exact
string matching algorithms to the two notions of approximate string matching.
The resulting algorithms are efficient in practice. Then we consider
"substring heuristics". We present δ-matching algorithms fast on the
average providing that the pattern is "non-flat" and the alphabet interval is
large. The pattern is "flat" if its structure does not vary substantially.
The algorithms, named δ-BM1, δ-BM2 and δ-BM3 can be
thought as members of the generalized Boyer-Moore family of algorithms. The
algorithms are fast on average. This is the first paper on the subject,
previously only "occurrence heuristics" have been considered. Our substring
heuristics are much stronger and refer to larger parts of texts (not only to
single positions). We use δ-versions of suffix tries and subword graphs.
Surprisingly, in the context of δ-matching subword graphs appear to be
superior compared with compact suffix trees.
