Faster Algorithm for Computing the Edit Distance between SLP-Compressed Strings
Faster Algorithm for Computing the Edit Distance between SLP-Compressed Strings
复制标题
用于计算 SLP 压缩字符串之间编辑距离的更快算法
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Paweł Gawrychowski
中科院分区：
文献类型：
--
作者：
Paweł Gawrychowski
给定两个字符串描述的SLP的总大小为n，我们展示了如何计算它们的编辑距离在$mathcal{O}（nNsqrt{logfrac{N}{n}}）$时间，其中N是字符串长度的总和。结果可以推广到任意有理评分函数，从而改进了已有的$mathcal{O}（nNlogN）$ [10]和$mathcal{O}（nNlogfrac{N}{n}）$ [4]时间解.这让我们更接近Lifshits [7]所提出的$mathcal{O}（nN）$复杂度。我们解决方案中的基本工具是一个线性时间过程，用于计算向量和单位蒙格矩阵的最大积，这可能是独立感兴趣的。
Given two strings described by SLPs of total size n, we show how to compute their edit distance in $mathcal{O}(nNsqrt{logfrac{N}{n}})$ time, where N is the sum of the strings length. The result can be generalized to any rational scoring function, hence we improve the existing $mathcal{O}(nNlog N)$ [10] and $mathcal{O}(nNlogfrac{N}{n})$ [4] time solutions. This gets us even closer to the $mathcal{O}(nN)$ complexity conjectured by Lifshits [7]. The basic tool in our solution is a linear time procedure for computing the max-product of a vector and a unit-Monge matrix, which might be of independent interest.