Space-efficient representation of truncated suffix trees, with applications to Markov order estimation
Space-efficient representation of truncated suffix trees, with applications to Markov order estimation
复制标题
截断后缀树的空间有效表示，及其在马尔可夫阶估计中的应用
DOI：
10.1016/j.tcs.2015.06.013
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
G. Seroussi
中科院分区：
文献类型：
--
作者：
L. Vitale;Álvaro Martín;G. Seroussi
后缀树（ST）在许多文本处理应用中是有用的，例如，用于确定输入字符串x中任意长度的模式的出现次数。如果x的长度n很大，则表示ST所需的存储器可能成为实际的性能瓶颈。这个问题可以得到缓解，在一个非平凡的上限是已知的感兴趣的模式的长度的情况下，通过使用截断ST（TST）。然而，传统的TST实现仍然需要Ω（n）位的存储器，因为它们存储x。我们描述了一种新的TST表示，通过将重建TST边缘标签所需的所有信息存储在通常比x短得多的字符串y中来避免这种限制。我们应用TST的马尔可夫阶估计的实现，在估计的顺序上的上界K-N可以推导出或施加（例如，为了一致性）。新的表示允许在某些情况下的利益与次线性空间复杂度的估计器实现。在其他情况下，我们的实验表明，即使当新的表示没有渐近优势，它仍然实现了非常显着的内存节省在实践中。
Suffix trees (ST) are useful in many text processing applications, for example, to determine the number of occurrences of patterns of arbitrary length in an input string x. If the length n, of x, is large, the memory required to represent the ST may become a practical performance bottleneck. This problem can be alleviated, in cases where a nontrivial upper bound is known on the lengths of the patterns of interest, by using a truncated ST (TST). However, conventional TST implementations still require Ω (n) bits of memory, since they store x. We describe a new TST representation that avoids this limitation by storing all the information necessary to reconstruct the TST edge labels in a string y that is often much shorter than x. We apply TSTs to the implementation of Markov order estimators, where an upper bound k n on the estimated order can be derived or it is imposed (for consistency, for example). The new representation allows for estimator implementations with sublinear space complexity in some cases of interest. In other cases we show, experimentally, that even when the new representation does not have an asymptotic advantage, it still achieves very significant memory savings in practice.
影响因子：
2.5
作者：
MCCREIGHT, EM
通讯作者：
MCCREIGHT, EM