Name
Abstract | ||
|---|---|---|
It has long been known that pattern matching in the Hamming distance metric can be done in O(min(|@S|,m/logm)nlogm) time, where n is the length of the text, m is the length of the pattern, and @S 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 @q, otherwise they contribute zero. We give an O(min(|@S|,m/logm)nlogm) time algorithm for this more general version of the problem; the classic Hamming distance matching problem is the special case of @q=0. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1016/j.ipl.2011.04.004 | Inf. Process. Lett. |
Keywords | Field | DocType |
classic algorithm,special case,hamming distance metric,classic hamming distance,general version,time algorithm,additive noise,similarity score,following generalization,pattern matching,convolution,hamming distance,algorithms | Discrete mathematics,Combinatorics,Convolution,Hamming(7,4),Hamming distance,Hamming weight,Pattern matching,Hamming graph,Mathematics,Alphabet,Special case | Journal |
Volume | Issue | ISSN |
111 | 14 | 0020-0190 |
Citations | PageRank | References |
2 | 0.41 | 5 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mikhail J. Atallah | 1 | 3828 | 340.54 |
| Timothy W. Duket | 2 | 2 | 0.41 |