Faster Compressed Suffix Trees for Repetitive Text Collections
Faster Compressed Suffix Trees for Repetitive Text Collections
复制标题
用于重复文本集合的更快压缩后缀树
DOI：
10.1007/978-3-319-07959-2_36
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Alberto Ordóñez Pereira
中科院分区：
文献类型：
--
作者：
G. Navarro;Alberto Ordóñez Pereira
最近的压缩后缀树的目标是高度重复的文本集合达到优秀的压缩性能，但操作时间在毫秒级。我们设计了一个新的后缀树表示这种情况下，仍然实现了非常低的空间使用，只有比以前最好的稍大，但支持微秒内的操作。这使数据结构处于与为标准文本集合设计的压缩后缀树相同的性能水平，这些压缩后缀树在重复集合中使用的空间比我们的新结构多很多倍。
Recent compressed suffix trees targeted to highly repetitive text collections reach excellent compression performance, but operation times in the order of milliseconds. We design a new suffix tree representation for this scenario that still achieves very low space usage, only slightly larger than the best previous one, but supports the operations within microseconds. This puts the data structure in the same performance level of compressed suffix trees designed for standard text collections, which on repetitive collections use many times more space than our new structure.