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 classiﬁ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 − 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-diﬀerence, k-diﬀerence with transpositions, overlap matching, edit distance/LCS, ﬂ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.
|Translated title of the contribution||Online Approximate Matching with Non-local Distances|
|Title of host publication||Proceedings of the 20th Annual Symposium on Combinatorial Pattern Matching (CPM)|
|Publisher||Springer Berlin Heidelberg|
|Pages||142 - 153|
|Publication status||Published - 2009|
Bibliographical noteConference Proceedings/Title of Journal: Proceedings of the 20th Annual Symposium on Combinatorial Pattern Matching (CPM)
Other identifier: 2001009