The string edit distance matching problem with moves Export

@article{citeulike:3610348, abstract = {The edit distance between two strings S and R is defined to be the minimum number of character inserts, deletes, and changes needed to convert R to S . Given a text string t of length n , and a pattern string p of length m , informally, the string edit distance matching problem is to compute the smallest edit distance between p and substrings of t .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 of O (log n log\* 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 into L 1 vector space using a simplified parsing technique, which we call edit-sensitive parsing (ESP).}, address = {New York, NY, USA}, author = {Cormode, Graham and Muthukrishnan, S.}, citeulike-article-id = {3610348}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=1219944.1219947}, citeulike-linkout-1 = {http://dx.doi.org/10.1145/1186810.1186812}, doi = {10.1145/1186810.1186812}, issn = {1549-6325}, journal = {ACM Trans. Algorithms}, keywords = {dynamic-programming, edit-distance}, number = {1}, posted-at = {2009-01-04 18:09:07}, priority = {2}, publisher = {ACM}, title = {The string edit distance matching problem with moves}, url = {http://dx.doi.org/10.1145/1186810.1186812}, volume = {3}, year = {2007} }

TY - JOUR ID - citeulike:3610348 L3 - citeulike-article-id:3610348 N2 - The edit distance between two strings S and R is defined to be the minimum number of character inserts, deletes, and changes needed to convert R to S . Given a text string t of length n , and a pattern string p of length m , informally, the string edit distance matching problem is to compute the smallest edit distance between p and substrings of t .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 of O (log n log* 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 into L 1 vector space using a simplified parsing technique, which we call edit-sensitive parsing (ESP). IS - 1 JF - ACM Trans. Algorithms SN - 1549-6325 AD - New York, NY, USA TI - The string edit distance matching problem with moves PB - ACM VL - 3 KW - dynamic-programming KW - edit-distance AU - Cormode, Graham AU - Muthukrishnan, S PY - 2007/// UR - http://dx.doi.org/10.1145/1186810.1186812 ER -