Substring compression problems
Substring compression problems
复制标题
子串压缩问题
DOI：
--
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
S. Muthukrishnan
中科院分区：
文献类型：
--
作者：
Graham Cormode;S. Muthukrishnan
我们启动了一个新的字符串匹配问题，称为substring压缩问题。给定一个可以预处理的字符串s，问题是要快速找到s（subString压缩查询或SCQ）的任何查询子字符串的压缩表示或压缩大小，或找到其压缩最小的S的长度L子字符串（至少可压缩的底带或LCS问题）。从Lempel和Ziv的开创性纸开始25年前，出现了许多不同的方法来压缩整个字符串。确定底带可压缩性是一种自然变体，在算法和算法上具有挑战性，但以前尚未研究过。此外，字符串的可压缩性正在作为比较生物序列和分析其信息含量的工具。但是，通常，整个序列的可压缩性不像序列的部分那样提供信息。因此，底带的压缩性可能是序列分析的更合适的基础。我们介绍了第一种已知的，几乎最佳的基因构成压缩问题算法--- SCQ，LCS及其概括 - 确切或证明是近似的。我们的精确算法通过后缀树利用字符串中的结构，而我们的近似算法依赖于我们在lempel-Ziv压缩和弦划分之间发现的新关系。
We initiate a new class of string matching problems called Substring Compression Problems. Given a string S that may be preprocessed, the problem is to quickly find the compressed representation or the compressed size of any query substring of S (Substring Compression Query or SCQ) or to find the length l substring of S whose compression is the least (Least Compressible Substring or LCS problem).Starting from the seminal paper of Lempel and Ziv over 25 years ago, many different methods have emerged for compressing entire strings. Determining substring compressibility is a natural variant that is combinatorially and algorithmically challenging, yet surprisingly has not been studied before. In addition, compressibility of strings is emerging as a tool to compare biological sequences and analyze their information content. However, typically, the compressibility of the entire sequence is not as informative as that of portions of the sequences. Thus substring compressibility may be a more suitable basis for sequence analysis.We present the first known, nearly optimal algorithms for substring compression problems---SCQ, LCS and their generalizations---that are exact or provably approximate. Our exact algorithms exploit the structure in strings via suffix trees and our approximate algorithms rely on new relationships we find between Lempel-Ziv compression and string parsings.
DOI：
--
发表时间：
--
期刊：
--
影响因子：
--
作者：
Systems Biology
通讯作者：
Systems Biology