Efficient Implementation of Rank and Select Functions for Succinct Representation
Efficient Implementation of Rank and Select Functions for Succinct Representation
复制标题
高效实现排序和选择函数以实现简洁表示
DOI：
10.1007/11427186_28
复制
发表时间：
2005
影响因子：
22.7
通讯作者：
Kunsoo Park
中科院分区：
文献类型：
--
作者：
Dong Kyue Kim;J. Na;Ji Eun Kim;Kunsoo Park
简洁表示是一种空间有效的方法，可以用O（n）位来表示n个离散对象。为了在恒定时间内直接访问简洁表示的数据结构的第i个对象，通常使用两个基本函数，rank和select。然而，很少有人努力分析这些功能的实际行为，尽管他们的简洁表示的重要性。
本文分析了Clark算法的性能，指出Clark算法的性能随位串中1个数的减少而变差，并存在需要大量运算的最坏情况。然后，我们提出了两个算法，克服了克拉克的缺点。这些算法需要恒定的时间来选择，一个使用o（n）位来获得额外的空间，另一个在最坏的情况下使用n + o（n）位。实验结果表明，我们的算法计算选择速度比克拉克的。
Succinct representation is a space-efficient method to represent n discrete objects by O(n) bits. In order to access directly the ith object of succinctly represented data structures in constant time, two fundamental functions, rank and select are commonly used. However, little efforts were made on analyzing practical behaviors of these functions despite their importance for succinct representations.
In this paper we analyze the behavior of Clark's algorithm which is the only one to support select in constant time using o(n)-bit space of extra space, and show that the performance of Clark's algorithm gets worse as the number of 1's in a bit-string becomes fewer and there exists a worst case in which a large amount of operations are needed. Then, we propose two algorithms that overcome the drawbacks of Clark's. These algorithms take constant time forselect, and one uses o(n) bits for extra space and the other uses n + o(n) bits in the worst case. Experimental results show that our algorithms compute select faster than Clark's.
DOI：
--
发表时间：
2003-01
期刊：
--
影响因子：
--
作者：
R. Grossi;Ankur Gupta;J. Vitter
通讯作者：
R. Grossi;Ankur Gupta;J. Vitter