کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
431342 | 688509 | 2011 | 15 صفحه PDF | دانلود رایگان |
It has recently been shown how to construct online, non-amortised approximate pattern matching algorithms for a class of problems whose distance functions can be classified as being local. Informally, a distance function is said to be local if for a pattern P of length m and any substring T[i,i+m−1]T[i,i+m−1] of a text T, the distance between P and T[i,i+m−1]T[i,i+m−1] can be expressed as ∑jΔ(P[j],T[i+j])∑jΔ(P[j],T[i+j]), where Δ is any distance function between individual characters. We show in this work how to tackle online approximate matching when the distance function is non-local. We give new 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 and L1L1 and L2L2 rearrangement distances. The resulting online algorithms bound the worst case running time per input character to within a log factor of their comparable offline counterpart.
Journal: Journal of Discrete Algorithms - Volume 9, Issue 1, March 2011, Pages 67–81