A Fully Compressed Algorithm for Computing the Edit Distance of Run-Length Encoded Strings
A Fully Compressed Algorithm for Computing the Edit Distance of Run-Length Encoded Strings
复制标题
计算游程编码字符串编辑距离的全压缩算法
DOI：
10.1007/s00453-011-9592-4
复制
发表时间：
2010
期刊：
影响因子：
1.1
通讯作者：
K. Chao
中科院分区：
文献类型：
--
作者：
Kuan;K. Chao
字符串学的一个最新趋势是探索利用文本压缩来加速字符串之间的相似性计算的可能性。在这方面的研究中，游程编码是最早研究的压缩方案之一。尽管它的编码性质很简单，但在这项工作之前唯一的积极结果是计算输入距离(最长公共子序列的对偶)，这需要O(MnlogMn)时间，其中And表示输入字符串的游程数。计算两个游程长度编码字符串之间的编辑距离的最坏情况下的时间复杂性仍然取决于未压缩的字符串长度。在本文中，我们提出了第一个完全压缩的算法，它的运行时间完全依赖于压缩字符串的长度，从而打破了这一基础差距。具体地说，给定两个压缩的字符串，m≤n，我们给出了一个计算字符串编辑距离的ANO(Mn2)时间算法。我们的方法还给出了在nrun Ino(Mn2)时间内mrun模式的近似匹配的第一个完全压缩解。
A recent trend in stringology explores the possibility of utilizing text compression to speed up similarity computation between strings. In this line of investigation, run-length encoding is one of the earliest studied compression schemes. Despite its simple coding nature, the only positive result before this work is the computation of the in-del distance (dual of longest common subsequence), which requiresO(mnlogmn) time, wheremandndenote the number of runs of the input strings. The worst-case time complexity of computing the edit distance between two run-length encoded strings still depends on the uncompressed string lengths. In this paper, we break the foundational gap by providing its first “fully compressed” algorithm whose running time depends solely on the compressed string lengths. Specifically, given two strings, compressed intomandnruns,m≤n, we present anO(mn2)-time algorithm for computing the edit distance of the strings. Our approach also yields the first fully compressed solution to approximate matching of a pattern ofmruns in a text ofnruns inO(mn2) time.
DOI：
--
发表时间：
2016
期刊：
影响因子：
--
作者：
Shuhei Denzumi
通讯作者：
Shuhei Denzumi