Weighted Ancestors in Suffix Trees
Weighted Ancestors in Suffix Trees
复制标题
后缀树中的加权祖先
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Patrick K. Nicholson
中科院分区：
文献类型：
--
作者：
Paweł Gawrychowski;Moshe Lewenstein;Patrick K. Nicholson
经典的，无处不在的，前身的问题是为一组整数构建一个支持快速的先前查询的整数众所周知，如果权重为，则占用O（n polygog（n））空间的加权祖先问题的任何数据结构解决方案都必须具有ω（loglogn）查询时间，如果权重为从多项式的宇宙中绘制的是，加权祖先问题的最重要且经常是针对后缀树。 ：我们表明，可以使用o（n）额外空间对文本构建的后缀树进行预处理，以便可以在O（1）时间内回答查询。我们的改进的时代是基于许多数据结构工具和对后缀树组合结构的周期性洞察力。
The classical, ubiquitous, predecessor problem is to construct a data structure for a set of integers that supports fast predecessor queries. Its generalisation to weighted trees, a.k.a. the weighted ancestor problem, has been extensively explored and successfully reduced to the predecessor problem. It is known that any data structure solution for the weighted ancestor problem that occupies O(n polylog(n)) space must have Ω(loglogn) query time, if the weights are drawn from a polynomially bounded universe. Perhaps the most important and frequent application of the weighted ancestors problem is for suffix trees. It has been a long-standing open question whether the weighted ancestors problem has better bounds for suffix trees. We answer this question positively: we show that a suffix tree built for a text w[1..n] can be preprocessed using O(n) extra space, so that queries can be answered in O(1) time. Thus we improve the running times of several applications. Our improvement is based on a number of data structure tools and a periodicity-based insight into the combinatorial structure of a suffix tree.