Online Approximate Matching with Non-local Distances
Raphaël Clifford, Benjamin Sach, Online Approximate Matching with Non-local Distances. Proceedings of the 20th Annual Symposium on Combinatorial Pattern Matching (CPM). June 2009. PDF, 193 Kbytes.Abstract
A black box method was recently given that solves the problem of online approximate matching for a class of problems whose distance functions can be classified as being local. A distance function is said to be local if for a pattern P of length m and any substring T [i, i + m − 1] of a text T , the distance between P and T [i, i + m − 1] is equal to Σ_j ∆(P [j], T [i + j − 1]), where ∆ is any distance function between individual characters. We extend this line of work by showing how to tackle online approximate matching when the distance function is non-local. We give solutions which are applicable to a wide variety of matching problems including function and parameterised matching, swap matching, swap-mismatch, k-difference, k-difference with transpositions, overlap matching, edit distance/LCS, flipped bit, faulty bit and L1 and L2 rearrangement distances. The resulting unamortised online algorithms bound the worst case running time per input character to within a log factor of their comparable offline counterpart.