pyEliasFano 0.0.5

pyEliasFano offers quasi-succinct represenations for monotone non-decreasing sequences of integers.

pyEliasFano

pyEliasFano offers a quasi-succinct represenation for a monotone non-decreasing sequence of n integers from the universe [0 . . . m) occupying 2n+nceil(log2(m/n)) bits.

by Antonio Mallia, 2018

It supports the following operations:

• select(k): nearly constant time access to the k-th element,
• rank(x): access to the index within the structure for given integer x.
• nextGEQ(x): fast access to the smallest integer of the sequence that is greater or equal than a given x
• nextLEQ(x): fast access to the largest integer of the sequence that is smaller or equal than a given x

Installation

pip install pyEliasFano

Usage

from pyEliasFano import EliasFano

imports the module.

integers = sorted([123, 1343, 2141, 35312, 4343434])
ef = EliasFano(integers)

creates an Elias-Fano structure for the sorted integers list.

Rank and Select

ef.select(2)

returns the integer stored at index position 2. Here we get 2141.

ef.rank(4343434)

returns the index position for the given integer if stored within the Elias-Fano structure. Here, we get 4.

nextGEQ and nextLEQ

ef.nextGEQ(1345)

returns the smallest integer stored in the Elias-Fano structure that is larger than the given integer.

ef.nextLEQ(4343420)

returns the largest integer stored in the Elias-Fano structure that is smaller than the given integer. Here, we get 35312.

Citation

@misc{rmrschub_2021_pyEliasFano,
    author       = {René Schubotz},
    title        = {{pyEliasFano: Quasi-succinct represenations for monotone non-decreasing sequences of integers.}},
    month        = may,
    year         = 2021,
    doi          = {10.5281/zenodo.4761443},
    version      = {0.0.1},
    publisher    = {Zenodo},
    url          = {https://github.com/rmrschub/pyEliasFano}
    }

License

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.