Name
Abstract | ||
|---|---|---|
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] of a text T, the distance between P and T[i,i+m-1] can be expressed as @?"j@D(P[j],T[i+j]), where @D 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 L"1 and L"2 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. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1016/j.jda.2010.09.005 | J. Discrete Algorithms |
Keywords | Field | DocType |
online algorithm,comparable offline counterpart,online approximate matching,approximate pattern matching,non-amortised approximate pattern,individual character,swap matching,distance function,parameterised matching,pattern p,rearrangement distance,real time,pattern matching,edit distance | Edit distance,Discrete mathematics,Online algorithm,Substring,Combinatorics,Metric (mathematics),Approximate string matching,3-dimensional matching,Bitap algorithm,Pattern matching,Mathematics | Journal |
Volume | Issue | ISSN |
9 | 1 | Journal of Discrete Algorithms |
Citations | PageRank | References |
8 | 0.60 | 15 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Raphaël Clifford | 1 | 268 | 28.57 |
| Benjamin Sach | 2 | 93 | 11.40 |