论文标题
改进的额定时间编辑距离用于预处理字符串
Improved Sublinear-Time Edit Distance for Preprocessed Strings
论文作者
论文摘要
我们研究了在sublinear时间中近似两个字符串的编辑距离的问题，在一个或两个字符串被预处理的情况下，由Goldenberg，Rubinstein，Saha（STOC '20）发起。具体来说，在$（k，k）$ - 间隙编辑距离问题中，目标是区分两个字符串的编辑距离是最多是$ k $还是至少$ k $。我们获得以下结果： *在时间$ n^{1 + o（1）} $中预处理一个字符串之后，我们可以解决$（k，k \ cdot n^{o（1）}）$ - 时间$ $（n/k + k）\ cdot n^{o（1）} $。 *在时间$ n^{1+o（1）} $中分别预处理两个字符串后，我们可以求解$（k，k \ cdot n^{o（1）}）$ - 时间$ k \ cdot n^{o（1）} $。 关于差距或查询时间或预处理时间，这两种结果都在一些以前最著名的结果上得到改善。 我们的算法建立在Andoni，Krauthgamer和Onak（Focs '10）的框架上，以及Bringmann，Cassis，Fischer和Nakos（STOC '22）的最近的Sublinear时间算法。我们通过利用预处理的更快，更简单的解决方案来代替其算法中的许多复杂零件。
We study the problem of approximating the edit distance of two strings in sublinear time, in a setting where one or both string(s) are preprocessed, as initiated by Goldenberg, Rubinstein, Saha (STOC '20). Specifically, in the $(k, K)$-gap edit distance problem, the goal is to distinguish whether the edit distance of two strings is at most $k$ or at least $K$. We obtain the following results: * After preprocessing one string in time $n^{1+o(1)}$, we can solve $(k, k \cdot n^{o(1)})$-gap edit distance in time $(n/k + k) \cdot n^{o(1)}$. * After preprocessing both strings separately in time $n^{1+o(1)}$, we can solve $(k, k \cdot n^{o(1)})$-gap edit distance in time $k \cdot n^{o(1)}$. Both results improve upon some previously best known result, with respect to either the gap or the query time or the preprocessing time. Our algorithms build on the framework by Andoni, Krauthgamer and Onak (FOCS '10) and the recent sublinear-time algorithm by Bringmann, Cassis, Fischer and Nakos (STOC '22). We replace many complicated parts in their algorithm by faster and simpler solutions which exploit the preprocessing.
