Fully Functional Static and Dynamic Succinct Trees
Fully Functional Static and Dynamic Succinct Trees
复制标题
DOI：
10.1145/2601073
复制
发表时间：
2014-06-01
影响因子：
1.3
通讯作者：
Sadakane, Kunihiko
中科院分区：
文献类型：
--
作者：
Navarro, Gonzalo;Sadakane, Kunihiko
我们提出了新的序数树的新简洁表示，并匹配各种空间/时间下限。众所周知，任何N节点静态树都可以在2n + O（n）位中表示，因此在Word-Ram模型下可以在恒定时间内支持树上的许多操作。但是，数据结构很复杂且难以动态。我们提出了一种简单且灵活的数据结构，称为“最小范围 - 最大树”，该结构将文献中考虑的大量相关树木操作降低到几个在多鼠大小的树上恒定时间进行的原始词。结果扩展到任意大小的树，保留恒定时间并达到2N + O（N/Polylog（n））空间位。该空间对于支持的操作的核心子集是最佳的，并且明显低于任何先前的建议。对于动态情况，允许节点的插入/删除（Indels），现有数据结构支持一组非常有限的操作。我们的数据结构建立在最小范围的最小树上，以实现2N + O（nllog n）空间的位和O（log n）时间的时间，用于静态场景中支持的所有操作，以及Indels。我们还使用2N + O（n日志N/ log n）位提出了改进的数据结构，并为大多数操作改善了最佳O（log n/ log log n）的时间。我们将支持整个子树的支持扩展到可以将整个子树附加到他人的森林中，随着时间的流逝O（log（1+是）n的元素n）是> o的一个元素。之前尚未考虑过此类操作我们的技术具有独立的兴趣。即时推导可以改进的解决方案对连续元素的最小/最大查询范围有所不同，从而实现了N + O（N/Polylog（n））空间位。第二个存储一个支持操作总和和搜索和有限更新的数字，以最佳时间O（log n/ log log n）。第三个允许在所有操作中代表大小sigma的字母上的动态位图和序列，在零级熵界和时间O（log n log sigma-/log log n）（2）中支持等级/选择和indels。这次是位图和各个字母的最佳O（log n/ log log n）。这改善了最佳的现有界限，用于熵结合的动态序列存储，压缩全文索引以及burrows-wheeler变换的压缩空间结构。
We propose new succinct representations of ordinal trees and match various space/time lower bounds. It is known that any n-node static tree can be represented in 2n + o(n) bits so that a number of operations on the tree can be supported in constant time under the word-RAM model. However, the data structures are complicated and difficult to dynamize. We propose a simple and flexible data structure, called the range min-max tree, that reduces the large number of relevant tree operations considered in the literature to a few primitives that are carried out in constant time on polylog-sized trees. The result is extended to trees of arbitrary size, retaining constant time and reaching 2n + O(n/polylog(n)) bits of space. This space is optimal for a core subset of the operations supported and significantly lower than in any previous proposal.For the dynamic case, where insertion/deletion (indels) of nodes is allowed, the existing data structures support a very limited set of operations. Our data structure builds on the range min-max tree to achieve 2n + O(nllog n) bits of space and O(log n) time for all operations supported in the static scenario, plus indels. We also propose an improved data structure using 2n + O(n log log n/ log n) bits and improving the time to the optimal O(log n/ log log n) for most operations. We extend our support to forests, where whole subtrees can be attached to or detached from others, in time O(log(1+is an element of) n) for any is an element of> O. Such operations had not been considered before.Our techniques are of independent interest. An immediate derivation yields an improved solution to range minimum/maximum queries where consecutive elements differ by 1, achieving n + O(n/polylog(n)) bits of space. A second one stores an array of numbers supporting operations sum and search and limited updates, in optimal time O(log n/ log log n). A third one allows representing dynamic bitmaps and sequences over alphabets of size sigma, supporting rank/select and indels, within zero-order entropy bounds and time O(log n log sigma-/log log n)(2)) for all operations. This time is the optimal O(log n/ log log n) on bitmaps and polylogsized alphabets. This improves upon the best existing bounds for entropy-bounded storage of dynamic sequences, compressed full-text self-indexes, and compressed-space construction of the Burrows-Wheeler transform.