The edit distance between two stringsSandRis defined to be the minimum number of character inserts, deletes and changes needed to convertRtoS. Given a text stringtof lengthn, and a pattern stringpof lengthm, informally, the string edit distance matching problem is to compute the smallest edit distance betweenpand substrings oft.We relax the problem so that (a) we allow an additional operation, namely,

substring moves, and (b) we allow approximation of this string edit distance. Our result is a near linear time deterministic algorithm to produce a factor ofO(lognlog^{*}n) approximation to the string edit distance with moves. This is the first known significantly subquadratic algorithm for a string edit distance problem in which the distance involves nontrivial alignments. Our results are obtained by embedding strings intoL_{1}vector space using a simplified parsing technique we callEdit Sensitive Parsing(ESP).

[ bib | http | Alternate Version | .pdf ] Back

*This file was generated by
bibtex2html 1.92.*