Как упаковать произвольную битовую последовательность в Python?

Question

Я хочу закодировать / сжать некоторые двоичные данные изображения в виде последовательности битов. (Эта последовательность, как правило, имеет длину, которая не вписывается аккуратно в целый ряд стандартных целочисленных типов.)

Как я могу сделать это, не теряя места? (Я понимаю, что, если последовательность битов не имеет "хорошей" длины, всегда будет небольшое количество [< 1 байт] оставшегося пространства в самом конце.)

Я полагаю, что для каждого символа, который я хочу кодировать, потребуется не более 3 битов. Есть ли в Python какие-либо встроенные инструменты для такой работы?

Answer 1

Там нет ничего очень удобного, но есть сторонние модули, такие как bitstring и bitarray, которые предназначены для этого.

from bitstring import BitArray
s = BitArray('0b11011')
s += '0b100'
s += 'uint:5=9'
s += [0, 1, 1, 0, 1]
...
s.tobytes()

Чтобы объединить последовательность 3-битных чисел (то есть диапазон 0->7), вы можете использовать

>>> symbols = [0, 4, 5, 3, 1, 1, 7, 6, 5, 2, 6, 2]
>>> BitArray().join(BitArray(uint=x, length=3) for x in symbols)
BitArray('0x12b27eab2')
>>> _.tobytes()
'\x12\xb2~\xab '

Некоторые связанные вопросы:

• Каков наилучший способ манипулирования битовым полем в Python?
• Python Bitstream реализации

Answer 2

Вы пробовали просто сжать всю последовательность с помощью bz2? Если последовательность длинная, вы должны использовать bz2.BZ2Compressor, чтобы разрешить частичную обработку, в противном случае используйте bz2.compress для всего этого. Сжатие, вероятно, не будет идеальным, но обычно будет очень близко при работе с разреженными данными.

надеюсь, это поможет.

Answer 3

Поскольку у вас есть отображение от символов к 3-битной строке, bitarray делает хорошую работу по кодированию и декодированию списков символов в и из массивов битов:

from bitarray import bitarray
from random import choice

symbols = {
    '0' : bitarray('000'),
    'a' : bitarray('001'),
    'b' : bitarray('010'),
    'c' : bitarray('011'),
    'd' : bitarray('100'),
    'e' : bitarray('101'),
    'f' : bitarray('110'),
    'g' : bitarray('111'),
}

seedstring = ''.join(choice(symbols.keys()) for _ in range(40))

# construct bitarray using symbol->bitarray mapping
ba = bitarray()
ba.encode(symbols, seedstring)

print seedstring
print ba

# what does bitarray look like internally?
ba_string = ba.tostring()
print repr(ba_string)
print len(ba_string)

Печать:

egb0dbebccde0gfdfbc0d0ccfcg0acgg0ccfga00
bitarray('10111101000010001010101001101110010100... etc.
'\xbd\x08\xaanQ\xf4\xc9\x88\x1b\xcf\x82\xff\r\xee@'
15

Вы можете видеть, что этот список из 40 символов (120 бит) кодируется в 15-байтовый битовый массив.

Answer 4

Обратите внимание, что это точно решит вашу проблему, но это приведет к преобразованию списка целых чисел в упакованную байтовую строку. Каждое целое число в списке должно занимать только указанное количество бит:

      from typing import List

def pack_bytes(data:List[int], bit_width:int) -> bytes:
    """Convert list if integers to packed byte string.
    Each integer should only consume the specified number of bits
    """

    packed_bytes = bytearray()
    buffer = 0
    bits_buffered = 0
    for sample in data:
        bit_mask = 0x01
        for i in range(bit_width):
            bit = (sample & bit_mask) >> i
            bit_mask <<= 1
            buffer |= (bit << bits_buffered)
            bits_buffered += 1

            if bits_buffered == 8:
                packed_bytes.append(buffer)
                buffer = 0
                bits_buffered = 0
    if bits_buffered != 0:
        packed_bytes.append(buffer)

    return packed_bytes

Пример:

      data = [0, 1, 2, 3, 4, 5, 6]

packed_data = pack_bytes(data, bit_width=4)
print(' '.join(f'0x{x:02X}' for x in packed_data))
# 0x10 0x32 0x54 0x06