The Library
The string edit distance matching problem with moves
Tools
UNSPECIFIED (2002) The string edit distance matching problem with moves. In: 13th Annual ACM/SIAM Symposium on Discrete Algorithms, SAN FRANCISCO, CA, JAN 0608, 2002. Published in: PROCEEDINGS OF THE THIRTEENTH ANNUAL ACMSIAM SYMPOSIUM ON DISCRETE ALGORITHMS pp. 667676. ISBN 089871513X.
Full text not available from this repository, contact author.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. A well known dynamic programming algorithm takes time O(nm) to solve this problem, and it is an important open problem in Combinatorial Pattern Matching to significantly improve this bound.
We relax the problem so that (a) we allow an additional operation, namely, substring moves, and (b) we approximate the string edit distance upto a factor of O(log n log* n).(1) Our result is a near linear time deterministic algorithm for this version of the problem. 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 L1 vector space using a simplified parsing technique we call Edit Sensitive Parsing (ESP). This embedding is approximately distance preserving, and we show many applications of this embedding to string proximity problems including nearest neighbors, outliers, and streaming computations with strings.
Item Type:  Conference Item (UNSPECIFIED)  

Subjects:  Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software Q Science > QA Mathematics 

Series Name:  SIAM PROCEEDINGS SERIES  
Journal or Publication Title:  PROCEEDINGS OF THE THIRTEENTH ANNUAL ACMSIAM SYMPOSIUM ON DISCRETE ALGORITHMS  
Publisher:  SIAM  
ISBN:  089871513X  
Official Date:  2002  
Dates: 


Number of Pages:  10  
Page Range:  pp. 667676  
Publication Status:  Published  
Title of Event:  13th Annual ACM/SIAM Symposium on Discrete Algorithms  
Location of Event:  SAN FRANCISCO, CA  
Date(s) of Event:  JAN 0608, 2002 
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item 