使用 Elias-Fano 编码对排序整数进行压缩

主要观点:介绍用 Elias-Fano 编码压缩单调非递减整数列表,其接近理论下界被称为准简洁索引,可随机访问元素且时间接近常数,在列表交集等方面表现出色,还给出 Golang 实现及 Facebook 的 Folly 实现并邀请分享其他实现。
关键信息:

  • 用 Elias-Fano 编码表示单调非递减序列需将整数二进制编码后拆分,低位部分直接拼接,高位部分用一元编码,最终拼接得到编码。
  • 可通过select_1(i) - i获取高位部分进行Access(i)操作,通过select_0(hx) − hx找到位置后扫描获取NextGEQ(x)操作。
  • 相关学术文献提及 Elias-Fano 在列表交集等方面的优势及相关实现技术。
    重要细节:
  • {2,3,5,7,11,13,24}为例详细说明了 Elias-Fano 编码过程。
  • 给出 Golang 实现地址(https://github.com/amallia/go-ef)及 Facebook Folly 实现地址(https://github.com/facebook/f...)。
  • 列出参考文献[1]至[4]的相关信息及引用。
阅读 14
0 条评论