• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>International Workshop on Experimental and Efficient Algorithms(WEA 2005); 20050510-13; Santorini Island(GR) >Efficient Implementation of Rank and Select Functions for Succinct Representation
【24h】

Efficient Implementation of Rank and Select Functions for Succinct Representation

机译：简洁表示的秩和选择函数的有效实现

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

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 for select, 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.
机译：简洁表示是一种节省空间的方法，可以用O（n）位表示n个离散对象。为了在恒定时间内直接访问简洁表示的数据结构的第i个对象，通常使用排名和选择这两个基本功能。但是，尽管这些功能对于简洁的表示很重要，但在分析这些功能的实际行为方面却付出了很少的努力。在本文中，我们分析了克拉克算法的行为，该算法是唯一支持使用额外空间的o（n）位空间在恒定时间内进行选择的算法，并表明克拉克算法的性能随着1的数量增加而变差。位串中的“ 0”变少，并且存在最坏的情况，其中需要大量的操作。然后，我们提出了两种克服了Clark缺点的算法。这些算法的选择时间恒定，一种在最坏的情况下使用o（n）位用于额外空间，另一种使用n + o（n）位。实验结果表明，我们的算法计算选择速度比Clark更快。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号