Skip to main content

Online Approximate Matching with Non-local Distances

Rapha?Online Approximate Matching with Non-local Distances. Proceedings of the 20th Annual Symposium on Combinatorial Pattern Matching (CPM). June 2009. PDF, 193 Kbytes.


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 classii??ed 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 a?? 1] of a text T , the distance between P and T [i, i + m a?? 1] is equal to I#_j a??(P [j], T [i + j a?? 1]), where a?? 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-dii??erence, k-dii??erence with transpositions, overlap matching, edit distance/LCS, i??ipped 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.

Bibtex entry.

Publication Admin