Streaming and Small Space Approximation Algorithms for Edit Distance and Longest Common Subsequence
Streaming and Small Space Approximation Algorithms for Edit Distance and Longest Common Subsequence
复制标题
DOI：
10.4230/lipics.icalp.2021.54
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Kuan Cheng;Alireza Farhadi;M. Hajiaghayi;Zhengzhong Jin;Xin Li;Aviad Rubinstein;Saeed Seddighin;Yu Zheng
中科院分区：
文献类型：
--
作者：
Kuan Cheng;Alireza Farhadi;M. Hajiaghayi;Zhengzhong Jin;Xin Li;Aviad Rubinstein;Saeed Seddighin;Yu Zheng
编辑距离（ED）和最长的常见序列（LC）是两个基本问题，在本文中量化了两个字符串的相似性。 11]（焦点10）和saks and seshadhri [64]（苏打水13）贡献是ED的常数因子近似算法。 1±ε。在这里，我们设计了所有三个问题的算法，其中ε> 0可以是任何恒定的，甚至是略微的算法在空间复杂性方面提高了先前的结果，其中所有已知的结果都需要使用至少ω（√N）。精心设计的递归以节省空间，这可能具有独立的兴趣。
The edit distance (ED) and longest common subsequence (LCS) are two fundamental problems which quantify how similar two strings are to one another. In this paper, we first consider these problems in the asymmetric streaming model introduced by Andoni, Krauthgamer and Onak [11] (FOCS’10) and Saks and Seshadhri [64] (SODA’13). In this model we have random access to one string and streaming access the other one. Our main contribution is a constant factor approximation algorithm for ED with memory Õ(n) for any constant δ > 0. In addition to this, we present an upper bound of Õε( √ n) on the memory needed to approximate ED or LCS within a factor 1 ± ε. All our algorithms are deterministic and run in polynomial time in a single pass. We further study small-space approximation algorithms for ED, LCS, and longest increasing sequence (LIS) in the non-streaming setting. Here, we design algorithms that achieve 1 ± ε approximation for all three problems, where ε > 0 can be any constant and even slightly sub-constant. Our algorithms only use poly-logarithmic space while maintaining a polynomial running time. This significantly improves previous results in terms of space complexity, where all known results need to use space at least Ω( √ n). Our algorithms make novel use of triangle inequality and carefully designed recursions to save space, which can be of independent interest. 2012 ACM Subject Classification Theory of computation → Design and analysis of algorithms