2018/10/31 by Diptarka Chakraborty, Debarati Das, Elazar Goldenberg +3
Biochemistry, Genetics and Molecular Biology · Computer Science · Decision Sciences · #Algorithms and Data Compression #Approximation algorithm #Constant (computer programming) #Data Quality and Management #Edit distance #Genome Rearrangement Algorithms #Measure (data warehouse) #Quadratic equation #Similarity (geometry) #String (physics) #Time complexity #cs.DS
paper · pdf · doi:10.1145/3422823
published as Journal of the ACM, Volume 67, Issue 6, October 2020, Article No.: 36, Page number: 1-22
openalex created_date 2018/08/31 · openalex publication_date 2020/10/29 · arxiv created 2021/02/16 · arxiv updated 2021/02/17 · openalex updated_date 2026/08/05
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 Õ( n 2−2/7 ) that approximates the edit distance within a constant factor.