Skip to main content

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

Project description

pyEliasFano

DOI

pyEliasFano offers quasi-succinct representations for monotone non-decreasing sequences of n integers from a universe [0 . . . m).

We currently support the following variants of Elias-Fano indexing:

  • pyEliasFano.EliasFano: the classical Elias-Fano representation occupying occupying 2n+nceil(log2(m)/n) bits
  • pyEliasFano.UniformlyPartitionedEliasFano: an uniformly-partitioned Elias-Fano representation

All variants support the following operations:

  • select(i): fast access to the i-th element of the integer sequence,
  • rank(x): queries the index position of x iff stored within the given Elias-Fano structure
  • nextGEQ(x): fast access to the smallest integer of the sequence that is greater or equal than x
  • nextLEQ(x): fast access to the largest integer of the sequence that is smaller or equal than x

Installation

Install from PyPi using

pip install pyEliasFano

Usage

from pyEliasFano import EliasFano, UniformlyPartitionedEliasFano

imports the module.

integers = sorted([123, 1343, 2141, 35312, 4343434])
ef0 = EliasFano(integers)
ef1 = UniformlyPartitionedEliasFano(integers)

creates a classical Elias-Fano structure ef0 as well as an uniformly-partitioned Elias-Fano structure ef1 for the sorted integers sequence.

Access

The ith element from the original integers sequence can be retrieved from an Elias-Fano structure ef using its select(i) method

ef0.select(3)
>>> 35312

ef0.select(0)
>>> 123

or using subscript operator

ef1[3]
>>> 35312

An Elias-Fano structure ef is also iterable.

You can easily loop through the stored elements stored

ef_iter = iter(ef0)

next(ef_iter)
>>> 123

next(ef_iter)
>>> 1343   

or return all stored elements at once

list(iter(ef0))
>>> [123, 1343, 2141, 35312, 4343434]

As a side note, the following assertion will always hold:

assert [ef.select(ef.rank(v)) for v in integers] == integers

Rank

Given an integer x, we can query the index position of x within an Elias-Fano structure ef using its rank(x) method.

For example,

ef0.rank(4343434)
>>> 4

ef1.rank(123)
>>> 0

As a side note, the following assertion will always hold:

assert [ef.rank(ef.select(i)) for i in range(len(integers))]

nextGEQ

Given an integer x, we can query the smallest integer stored within an Elias-Fano structure ef that is larger than or equal to x using the nextGEQ(x)method.

For example,

ef0.nextGEQ(1345)
>>> 2141

ef0.nextGEQ(4343434)
>>> 4343434

ef1.nextGEQ(2)
>>> 123

nextLEQ

Given an integer x, we can query the largest integer stored within an Elias-Fano structure ef that is smaller than or equal to x using the nextLEQ(x)method.

For example,

ef0.nextLEQ(4343420)
>>> 35312

ef0.nextLEQ(123)
>>> 123

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

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

Project details


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

pyEliasFano-0.0.8.tar.gz (12.9 kB view details)

Uploaded Source

Built Distribution

pyEliasFano-0.0.8-py3-none-any.whl (14.1 kB view details)

Uploaded Python 3

File details

Details for the file pyEliasFano-0.0.8.tar.gz.

File metadata

  • Download URL: pyEliasFano-0.0.8.tar.gz
  • Upload date:
  • Size: 12.9 kB
  • Tags: Source
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/3.4.2 importlib_metadata/4.8.1 pkginfo/1.7.1 requests/2.26.0 requests-toolbelt/0.9.1 tqdm/4.62.3 CPython/3.9.7

File hashes

Hashes for pyEliasFano-0.0.8.tar.gz
Algorithm Hash digest
SHA256 685a8e01ca5f3d1bbbb9d52d5a87c1b01fc14cde3c01d31dbc5c4fc997199f7e
MD5 7015b32c8dbc92722d6903cad6af94ec
BLAKE2b-256 c131da59c4823d985bbce42f7380f590993c1b9e3317ac0909cf910cdf61617c

See more details on using hashes here.

File details

Details for the file pyEliasFano-0.0.8-py3-none-any.whl.

File metadata

  • Download URL: pyEliasFano-0.0.8-py3-none-any.whl
  • Upload date:
  • Size: 14.1 kB
  • Tags: Python 3
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/3.4.2 importlib_metadata/4.8.1 pkginfo/1.7.1 requests/2.26.0 requests-toolbelt/0.9.1 tqdm/4.62.3 CPython/3.9.7

File hashes

Hashes for pyEliasFano-0.0.8-py3-none-any.whl
Algorithm Hash digest
SHA256 740cce3605917d9907444464402bde5bd4886b80fb039ff45c6cb3579610b8b5
MD5 8e5f7ce7893fe2806b46741b22fb0709
BLAKE2b-256 2799875ef0aceeaa75cef3b652bf6c3fa371bbfceb8a34397096ccaa79ec6e2e

See more details on using hashes here.

Supported by

AWS AWS Cloud computing and Security Sponsor Datadog Datadog Monitoring Fastly Fastly CDN Google Google Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Sentry Sentry Error logging StatusPage StatusPage Status page