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.
int
instead ofstr
orbitarray
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. \$\endgroup\$