Sorted integers compression with Elias-Fano encoding

January 6, 2018 compression elias-fano data structures In the previous post we discovered how to compress a set of integers by representing it as a bitmap and then compressing the latter using a succinct representation. This post instead is about compression of monotone non-decreasing integers lists by using Elias-Fano encoding. It may sound like a niche algorithm, something that solves such an in

[causeless]

"@taku910 ソートされた整数列(転置インデックスのポジションリストとか)の圧縮に elias-fano-encoding という手法があることを知った。Quasi-succinct で、試したところ、ありがちな手…" via https://twitter.com/taku910/status/1268223802770485248