Faster Language Edit Distance, Connection to All-pairs Shortest Paths and Related Problems

Given a context free language L(G) over alphabet Σ and a string s ∈ Σ∗, the language edit distance problem seeks the minimum number of edits (insertions, deletions and substitutions) required to convert s into a valid member of L(G). The well-known dynamic programming algorithm solves this problem in O(n3) time (ignoring grammar size) where n is the string length [Aho, Peterson 1972, Myers 1985]. Despite its numerous applications in data management, machine learning, compiler optimization, com-putational biology, computer vision and linguistics, there is no algorithm known till date that computes or approximates language edit distance problem in true sub-cubic time. In this paper we give the first such algorithm that computes language edit distance almost optimally. For any arbitrary > 0, our algorithm runs in Õ ( n ω poly() ) time and returns an estimate within a mul-tiplicative approximation factor of (1 + ) with high probability, where ω is the exponent of ordinary matrix multiplication of n dimensional square matrices. It also computes the edit script. We further solve the local alignment problem; for all substrings of s, we can estimate their language edit distanc