Approximating Edit Distance Within Constant Factor in Truly Sub-quadratic Time
- 29 October 2020
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 67 (6), 1-22
- https://doi.org/10.1145/3422823
Abstract
Edit distance is a measure of similarity of two strings based on the minimum number of character insertions, deletions, and substitutions required to transform one string into the other. The edit distance can be computed exactly using a dynamic programming algorithm that runs in quadratic time. Andoni, Krauthgamer, and Onak (2010) gave a nearly linear time algorithm that approximates edit distance within approximation factor poly(log n). In this article, we provide an algorithm with running time Õ(n2−2/7) that approximates the edit distance within a constant factor.Keywords
Funding Information
- Grant Agency of the Czech Republic (19-27871X)
- European Research Council (616787)
- Simons Foundation (332622)
This publication has 18 references indexed in Scilit:
- New tabulation and sparse dynamic programming based techniques for sequence similarity problemsDiscrete Applied Mathematics, 2016
- Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound madePublished by Association for Computing Machinery (ACM) ,2016
- Quadratic Conditional Lower Bounds for String Problems and Dynamic Time WarpingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2015
- Tight Hardness Results for LCS and Other Sequence Similarity MeasuresPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2015
- Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)Published by Association for Computing Machinery (ACM) ,2015
- A sublinear algorithm for weakly approximating edit distancePublished by Association for Computing Machinery (ACM) ,2003
- Incremental String ComparisonSIAM Journal on Computing, 1998
- Algorithms for approximate string matchingInformation and Control, 1985
- A faster algorithm computing string edit distancesJournal of Computer and System Sciences, 1980
- The String-to-String Correction ProblemJournal of the ACM, 1974