prefix-codes 1.0.0

Python package implementing a number of prefix codes alongside their utilities.

Python package implementing a number of prefix codes as strings for educational purposes alongside some utilities.

How do I install this package?

As usual, just download it using pip:

pip install prefix_codes

Tests Coverage

Since some software handling coverages sometime get slightly different results, here’s three of them:

Available codes

The following codes are available as submodules (they are also installable by themselves) or imported.

It should be noted that some of the following codes are not prefix codes, but are still important codes.

• Unary coding.

• Reduced binary encoding.

• Minimal binary encoding.

• Gamma coding.

• Delta coding.

• Omega coding.

• Interpolative coding.

• Nibble e Byte coding.

• Truncated binary encoding.

• Golomb coding.

• Levenshtein coding.

Usage examples

The following codes are available and readily importable into your project:

from prefix_codes import unary, inverted_unary
from prefix_codes import gamma_coding
from prefix_codes import delta_coding
from prefix_codes import omega_coding, decode_omega_coding
from prefix_codes import levenshtein_coding, decode_levenshtein_coding
from prefix_codes import truncated_binary_encoding
from prefix_codes import reduced_binary_coding
from prefix_codes import minimal_binary_coding
from prefix_codes import interpolative_coding
from prefix_codes import nibble_coding, byte_coding
from prefix_codes import golomb_coding, optimal_golomb_coding, bernoulli_golomb_coding

Available utilities

Two utilities are available, one to determine if a given code is a prefix code and a second one, based on the Kraft-McMillan inequality, to determine if a given code is complete.

It should be noted that the second utility fails when the code’s words are quite long for float errors.

Usage examples

from prefix_codes import is_prefix_code, is_complete_prefix_code
from prefix_codes import unary, interpolative_coding

numbers = list(range(100))
unary_code = unary(numbers)
interpolative_code = interpolative_coding(numbers, 0, 100)
is_prefix_code(unary_code) # True
is_prefix_code(interpolative_code) # False
is_complete_prefix_code(unary_code) # True
is_complete_prefix_code(interpolative_code) # False

Elias-Fano semi-succint data structure

An educational version of Elias-Fano semi-succint data structure implemented using the codes above is also available.