id: 02087053 dt: a an: 02087053 au: Crochemore, Maxime; Iliopoulos, Costas S.; Lecroq, Thierry; Plandowski, Wojciech; Rytter, Wojciech ti: Three heuristics for \$δ\$-matching: \$δ\$-BM algorithms. so: Apostolico, Alberto (ed.) et al., Combinatorial pattern matching. 13th annual symposium, CPM 2002, Fukuoka, Japan, July 3‒5, 2002. Proceedings. Berlin: Springer (ISBN 3-540-43862-9). Lect. Notes Comput. Sci. 2373, 178-189 (2002). py: 2002 pu: Berlin: Springer la: EN cc: ut: pattern matching; processing of large musical data ci: li: http://link.springer.de/link/service/series/0558/bibs/2373/23730178.htm ab: Summary: 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 \$\vert a-b\vert\$. 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. We also consider \$(δ,γ)\$-matching, where \$γ\$ is a bound on the total number of errors. 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 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 compacted suffix trees. rv: