Fast Relative Lempel-Ziv Self-index for Similar Sequences
Fast Relative Lempel-Ziv Self-index for Similar Sequences
复制标题
DOI：
10.1007/978-3-642-29700-7_27
复制
发表时间：
2012-05
期刊：
影响因子：
--
通讯作者：
Huy Hoang Nhat Do;J. Jansson;K. Sadakane;W. Sung
中科院分区：
文献类型：
--
作者：
Huy Hoang Nhat Do;J. Jansson;K. Sadakane;W. Sung
生物技术和网络技术的最新进展不断产生大量类似字符串。人们现在面临的问题是，在支持快速模式搜索的同时要紧凑地存储它们。一种称为相对Lempel-Ziv压缩的压缩方案使用来自引用文本的文本替换来将每个字符串表示为来自引用字符串r的子字符串的连接。当每个字符串都在类似的toR中时，这个基本方案提供了良好的压缩比，但不提供任何模式搜索功能。在这里，我们描述了一种基于相对Lempel-Ziv压缩的新数据结构，该结构既节省空间，又支持快速模式搜索。
Recent advances in biotechnology and web technology are continuously generating huge collections of similar strings. People now face the problem of storing them compactly while supporting fast pattern searching. One compression scheme calledrelative Lempel–Ziv compressionuses textual substitutions from a reference text to represent each string inSas a concatenation of substrings from a reference stringR. This basic scheme gives a good compression ratio when every string inSis similar toR, but does not provide any pattern searching functionality. Here, we describe a new data structure based on relative Lempel–Ziv compression that is space-efficient and also supports fast pattern searching.