Pattern matching in the Hamming distance with thresholds
It has long been known that pattern matching in the Hamming distance metric can be done in O(min(vertical bar Sigma vertical bar.root m/log m)n log m) time, where n is the length of the text, m is the length of the pattern, and Sigma is the alphabet. The classic algorithm for this is due to Abrahamson and Kosaraju. This paper considers the following generalization, motivated by the situation where the entries in the text and pattern are analog, or distorted by additive noise, or imprecisely given for some other reason: in any alignment of the pattern with the text, two aligned symbols a and b contribute +1 to the similarity score if they differ by no more than a given threshold theta, otherwise they contribute zero. We give an O(min(vertical bar Sigma vertical bar.root m/log m)n log m) time algorithm for this more general version of the problem; the classic Hamming distance matching problem is the special case of theta = 0. (C) 2011 Elsevier B.V. All rights reserved,
pattern matching hamming distance algorithms convolution