Approximate Matching in the L 1 Metric

摘要: Approximate matching is one of the fundamental problems in pattern matching, and a ubiquitous problem real applications. The Hamming distance simple well studied example approximate motivated by typing, or noisy channels. Biological image processing applications assign different value to mismatches symbols. We consider L1 metric – k-L1-distance problem. Given text T=t0,...,tn−1 P=p0,...,pm−1 strings natural number, number k, we seek all locations i where from length m substring starting at not greater than i.e. $\sum_{j=0}^{m-1} |{t}_{i+j} - {p}_{j}| \leq k$. We provide an algorithm that solves time $O(n\sqrt{k\log k})$. applies bounded divide-and-conquer approach makes novel uses non-boolean convolutions.