Matching Numeric Strings under Noise

Veli Mäkinen, Gonzalo Navarro and Esko Ukkonen

Numeric string is a sequence of symbols from an alphabet Sigma subset of U, where U is some numerical universe closed under addition and subtraction. Given two numeric strings A=a(1)...a(m) and B=b(1) \cdots b(n) and a distance function d(A,B) that gives the score of the best (partial) matching of A and B, the transposition invariant distance is min {d(A+t,B), t in U}, where A+t = (a(1)+t)(a(2)+t)...(a_(m)+t). The corresponding matching problem is to find occurrences j of A in B where d(A+t,B(j'...j)) is smaller than some given threshold and B(j'...j) is a substring of B. In this paper, we give efficient algorithms for matching numeric strings --- with and without transposition invariance --- under noise; we consider distance functions d(A,B) such that symbols a in A and b in B can be matched if |b-a| <= delta, or the kappa largest differences |b-a| can be discarded.