# speed up Elias gamma compression

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 = 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.

• Why are you creating numbers instead of (bit)strings? Mar 16, 2021 at 20:17
• Out of curiosity: Is it really "compressing" for the numbers in the range you're testing? Mar 16, 2021 at 20:23
• @Manuel hugely, for example the 4 million element list was compressed to 277x smaller. More modest lists, for example of 469 elements, achieve 184x compression. Mar 16, 2021 at 20:26
• Ah yes, you're encoding deltas. Which in your test are almost all 1. Mar 16, 2021 at 20:35
• @Manuel i used int instead of str or bitarray because it uses up way less memory. It was also way faster for inputs <500 elements, but I haven't actually compared speeds on gigantic inputs. Mar 16, 2021 at 20:41

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)

• How "small", and what times did you get for both? In my own testing, mine's always faster, even when the list only has a single number. Mar 16, 2021 at 21:03
• When I tried with strings before, I was using string concatenation. I had no idea building a list of strings like this would be so fast. Mar 16, 2021 at 21:09
• "100 ms faster" doesn't say much, what were the times? Btw I improved it a little further now. String concatenation the way I guess you tried might become quadratic, too. Mar 16, 2021 at 21:12
• The times were 360 for int, 270 for str, for my 469 element set Mar 16, 2021 at 21:13
• I now reverse the list instead of using a reverse iterator. Mar 16, 2021 at 21:14