Fast Space-Efficient Approximations of Language Edit Distance and RNA Folding: An Amnesic Dynamic Programming Approach

摘要

Dynamic programming is a basic, and one of the most systematic techniques for developing polynomial time algorithms with overwhelming applications. However, it often suffers from having high running time and space complexity due to (a) maintaining a table of solutions for a large number of sub-instances, and (b) combining/comparing these solutions to successively solve larger sub-instances. In this paper, we consider a canonical cubic time and quadratic space dynamic programming, and show how improvements in both its time and space uses are possible. As a result, we obtain fast small-space approximation algorithms for the fundamental problems of context free grammar recognition (the basic computer science problem of parsing), the language edit distance (a significant generalization of string edit distance and parsing), and RNA folding (a classical problem in bioinformatics). For these problems, ours are the first algorithms that break the cubic-time barrier of any combinatorial algorithm, and quadratic-space barrier of “any” algorithm significantly improving upon their long-standing space and time complexities. Our technique applies to many other problems as well including string edit distance computation, and finding longest increasing subsequence. Our improvements come from directly grinding the dynamic programming and looking through the lens of language edit distance which generalizes both context free grammar recognition, and RNA folding. From known conditional lower bound results, neither of these problems can have an exact combinatorial algorithm (one that does not use fast matrix multiplication) running in truly subcubic time. Moreover, for language edit distance such an algorithm cannot exist even when nontrivial multiplicative approximation is allowed. We overcome this hurdle by designing an additive-approximation algorithm that for any parameter k > 0, uses O(nk log n) space and O(n²k log n) time and provides an additive O(nk log n)approximation. In particular, in Õ(n)¹ space and Õ(n²) time it can solve deterministically whether a string belongs to a context free grammar, or ϵ-far from it for any constant ϵ > 0. We also improve the above results to obtain an algorithm that outputs an ϵ · n-additive approximation to the above problems with space complexity O(n2/3 log n). The space complexity remains sublinear in n, as long as ϵ = o(n^-1/₄ ). Moreover, we provide the first MapReduce and streaming algorithms for them with multiple passes and sublinear space complexity.