A Unified Algorithm for Accelerating Edit-Distance Computation via Text-Compression
A Unified Algorithm for Accelerating Edit-Distance Computation via Text-Compression
复制标题
一种通过文本压缩加速编辑距离计算的统一算法
DOI：
10.4230/lipics.stacs.2009.1804
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Oren Weimann
中科院分区：
文献类型：
--
作者：
D. Hermelin;G. M. Landau;Shir Landau Feibish;Oren Weimann
我们提出了一个使用直线程序来加速两个可压缩字符串之间的编辑距离计算的统一框架。对于总长度为$N$的两个具有总长度为$n$的直线程序表示的字符串，我们给出了计算这两个字符串在任何有理评分函数下的编辑距离的$O(n^{1.4}N^{1.2})$time的算法和任意评分函数的$O(n^{1.34}N^{1.34})$time的算法。这改进了最近的Tiskin算法，该算法运行在$O(NN^{1.5})$time，并且只适用于有理评分函数。此外，在文章的最后部分，我们展示了如何将经典的四俄罗斯技术结合到我们的SLP编辑距离方案中，在任意记分函数的情况下，对于任何一对字符串，我们都可以获得简单的$Omega(\lg N)$加速。
We present a unified framework for accelerating edit-distance computation between two compressible strings using straight-line programs. For two strings of total length $N$ having straight-line program representations of total size $n$, we provide an algorithm running in $O(n^{1.4}N^{1.2})$ time for computing the edit-distance of these two strings under any rational scoring function, and an $O(n^{1.34}N^{1.34})$ time algorithm for arbitrary scoring functions. This improves on a recent algorithm of Tiskin that runs in $O(nN^{1.5})$ time, and works only for rational scoring functions. Also, in the last part of the paper, we show how the classical four-russians technique can be incorporated into our SLP edit-distance scheme, giving us a simple $\Omega(\lg N)$ speed-up in the case of arbitrary scoring functions, for any pair of strings.
DOI：
--
发表时间：
2016
期刊：
影响因子：
--
作者：
Shuhei Denzumi
通讯作者：
Shuhei Denzumi