2
\$\begingroup\$

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.

\$\endgroup\$
6
  • \$\begingroup\$ Why are you creating numbers instead of (bit)strings? \$\endgroup\$
    – Manuel
    Mar 16, 2021 at 20:17
  • \$\begingroup\$ Out of curiosity: Is it really "compressing" for the numbers in the range you're testing? \$\endgroup\$
    – Manuel
    Mar 16, 2021 at 20:23
  • \$\begingroup\$ @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. \$\endgroup\$
    – minseong
    Mar 16, 2021 at 20:26
  • 1
    \$\begingroup\$ Ah yes, you're encoding deltas. Which in your test are almost all 1. \$\endgroup\$
    – Manuel
    Mar 16, 2021 at 20:35
  • \$\begingroup\$ @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. \$\endgroup\$
    – minseong
    Mar 16, 2021 at 20:41

1 Answer 1

3
\$\begingroup\$

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)
\$\endgroup\$
13
  • \$\begingroup\$ 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. \$\endgroup\$
    – Manuel
    Mar 16, 2021 at 21:03
  • \$\begingroup\$ 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. \$\endgroup\$
    – minseong
    Mar 16, 2021 at 21:09
  • \$\begingroup\$ "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. \$\endgroup\$
    – Manuel
    Mar 16, 2021 at 21:12
  • \$\begingroup\$ The times were 360 for int, 270 for str, for my 469 element set \$\endgroup\$
    – minseong
    Mar 16, 2021 at 21:13
  • \$\begingroup\$ I now reverse the list instead of using a reverse iterator. \$\endgroup\$
    – Manuel
    Mar 16, 2021 at 21:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.