Practical Entropy-Compressed Rank/Select Dictionary
Practical Entropy-Compressed Rank/Select Dictionary
复制标题
DOI：
10.1137/1.9781611972870.6
复制
发表时间：
2006-09
期刊：
影响因子：
--
通讯作者：
Daisuke Okanohara;K. Sadakane
中科院分区：
文献类型：
--
作者：
Daisuke Okanohara;K. Sadakane
等级/选择字典是有序集的数据结构S⊂{0,1。 Select（i，s）（s中的第i元素），这是字符串，树木，图形等简洁数据结构的基本组成部分。但是，在这些数据结构中，仅考虑了不对称的行为，并且他们对真实数据的性能不满足。在本文中，我们提出了四个新颖的等级/选择词典：ESP，Recrank，Vcode和Sdarray，如果S中的元素数很小，并且实际上接近NH0（S）（H0（s）≤，则每个字典都很小1在实践中，S）的经验熵是，它们的查询时间优于现有结构。在大小和查询时间方面，现有实现。
Rank/Select dictionaries are data structures for an ordered set S ⊂ {0,1, . . ., n − 1} to compute rank(x, S) (the number of elements in S that are no greater than x), and select(i, S) (the i-th smallest element in S), which are the fundamental components of succinct data structures of strings, trees, graphs, etc.. In these data structures, however, only asymptotic behavior has been considered and their performance for real data is not satisfactory. In this paper, we propose four novel Rank/Select dictionaries: esp, recrank, vcode and sdarray, each of which is small if the number of elements in S is small, and indeed close to nH0(S) (H0(S) ≤ 1 is the zero-th order empirical entropy of S) in practice. Furthermore, their query times are superior to those of existing structures. Experimental results reveal the characteristics of our data structures and also show that these data structures are superior to existing implementations, both in terms of size and query time.