Compressed suffix trees: Efficient computation and storage of LCP-values
Compressed suffix trees: Efficient computation and storage of LCP-values
复制标题
压缩后缀树：LCP 值的高效计算和存储
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Enno Ohlebusch
中科院分区：
文献类型：
--
作者：
Simon Gog;Enno Ohlebusch
后缀树是字符串处理中非常重要的数据结构，但典型的实现遭受巨大的空间消耗。在大规模应用中，因此使用压缩后缀树（CST）。CST由三个（压缩）组件组成：后缀数组，最长公共前缀（LCP）数组和用于模拟后缀树上的导航操作的数据结构。LCP-array存储字典序相邻后缀的LCPs的长度，并且它可以在线性时间内计算。在这篇文章中，我们提出了一个新的LCP阵列构造算法，是快速和非常空间有效的。在实践中，我们的算法优于替代算法。此外，我们引入了一个新的压缩表示的LCP阵列。
The suffix tree is a very important data structure in string processing, but typical implementations suffer from huge space consumption. In large-scale applications, compressed suffix trees (CSTs) are therefore used instead. A CST consists of three (compressed) components: the suffix array, the longest common prefix (LCP)-array and data structures for simulating navigational operations on the suffix tree. The LCP-array stores the lengths of the LCPs of lexicographically adjacent suffixes, and it can be computed in linear time. In this article, we present a new LCP-array construction algorithm that is fast and very space efficient. In practice, our algorithm outperforms alternative algorithms. Moreover, we introduce a new compressed representation of LCP-arrays.