pyEliasFano 0.0.7

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. Note that indexing in EliasFano structures is 1-based!

Rank and Select

ef.select(3)

returns the integer stored at index position 3. 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 5.

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.4774741},
    version      = {0.0.6},
    publisher    = {Zenodo},
    url          = {https://github.com/rmrschub/pyEliasFano}
    }

License

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