speed up Elias gamma compression

Question

I wrote some functions to compress and decompress a list of ints using Elias gamma encoding:

def _reverseBits(number: int) -> int:
    rev = 0
    while number:
        rev = rev << 1
        if number & 1:
            rev = rev ^ 1 # bitwise ^ 1 is faster than arithmetic + 1
        number = number >> 1
    return rev


def compress(numbers: List[int]) -> int:
    r'''Calculate the elias gamma encoded bitstream representation of the input list of numbers.

    >>> compress([5]) == 0b10100
    True
    >>> compress([15]) == 0b1111000
    True
    >>> compress([5, 15]) == 0b10100010100
    True
    '''
    bitstream = 0
    bitstream_length = 0
    previous_number = 0
    for number in numbers:
        delta = number - previous_number # store deltas, much smaller numbers
        N = delta.bit_length() - 1
        encoded_number = _reverseBits(delta) << N # reversed bitstream won't have leading zeroes problem in int container
        bitstream += encoded_number << bitstream_length
        bitstream_length += (N * 2 + 1)
        previous_number = number
    return bitstream


def decompress(bitstream: int) -> List[int]:
    r'''Convert the elias-encoded bitstream into a list of numbers.

    >>> decompress(0b10100010100)
    [5, 15]
    '''
    numbers = []
    cumulative_sum = 0
    while bitstream:
        N = 1
        while bitstream & 1 == 0: # count Elias leading zeroes
            bitstream = bitstream >> 1
            N += 1
        mask = (1 << N) - 1
        number = _reverseBits(bitstream & mask)
        number = number << N - number.bit_length()
        cumulative_sum += number
        numbers.append(cumulative_sum)
        bitstream = bitstream >> N
    return numbers

But it's very slow on huge input lists

start = 5000
size = int(4e6)
numbers = [i for i in range(start, start + size + 1)]

I started a test with a four-million size input list, all elements sequential, it took 13 minutes to encode and decode on my laptop.

I've thought about parallelising what I already have, but I don't think there's anywhere I can actually work it in.

Please could you help me review my algorithm and see if there are ways to improve or rework it to make my compress and decompress methods faster?

Or potentially, this might be the limit of Elias gamma encoding in Python...

---

I have also noticed a problem with mine, that memory does not seem to be freed after it finishes. tracemalloc.get_traced_memory() after running it shows a memory usage higher than the encoded int.

---

Elias gamma encoding encodes numbers like this

+--------+---------------+
| Number |  γ encoding   |
+--------+---------------+
|      1 |             1 |
|      2 |          0 10 |
|      3 |          0 11 |
|      4 |        00 100 |
|      5 |        00 101 |
|      6 |        00 110 |
|      7 |        00 111 |
|    ... |               |
|     15 |      000 1111 |
|     16 |   0000 1 0000 |
|    ... |               |
|     31 |   0000 1 1111 |
|     32 | 00000 10 0000 |

The leading zeroes inform the decoder how many of the following bits are part of the current number. So numbers of the input list are concatenated into a bitstream, and can be unambiguously decoded back into the same list of numbers. [1, 4, 3] encodes to 1 00100 011.

I am storing the bitstream in reverse inside of a python int, reversed so that there's no problems with the leading zeroes of the int container.

Even though the bit sequences in the table look large because of the leading zeroes, my compression only encodes the difference between the current list element and the previous (delta encoding), so that most of the time the number to encode and concatenate is much smaller than the actual list element.

My methods intentionally only work with sorted lists.

Answer 1

Rather strange to encode as a number instead of a (bit)string. And the way you do it takes quadratic time in the size of your list (because both the + and the << in bitstream += encoded_number << bitstream_length are linear). You could do it in linear time by building a string and then turning it into a number at the end.

This should take only a few seconds for your large test (removing the docstring just for brevity here):

def compress(numbers: List[int]) -> int:
    bitstream = []
    previous_number = 0
    for number in numbers:
        delta = number - previous_number # store deltas, much smaller numbers
        N = delta.bit_length() - 1
        encoded_number = bin(delta)[:1:-1] + '0' * N
        bitstream.append(encoded_number)
        previous_number = number
    bitstream.reverse()
    return int(''.join(bitstream), 2)

For decompression, I'd accordingly first turn the number into a string and then work with that.

Optimized version should take less than a second:

def compress(numbers: List[int]) -> int:
    bitstream = []
    append = bitstream.append
    memo = {}
    lookup = memo.get
    previous_number = 0
    for number in numbers:
        delta = number - previous_number # store deltas, much smaller numbers
        if not (encoded_number := lookup(delta)):
            N = delta.bit_length() - 1
            memo[delta] = encoded_number = bin(delta)[:1:-1] + '0' * N
        append(encoded_number)
        previous_number = number
    bitstream.reverse()
    return int(''.join(bitstream), 2)