преобразовать строку кода Хаффмана в двоичный файл

Question

У меня проблема с тем, как преобразовать строку кодирования Хаффмана в двоичный питон.

В этом вопросе ничего не говорится об алгоритме Хаффмана.

Это так:

Я могу получить закодированную строку Хаффмана, скажем, 01010101010. Примечание , это строка.

Но теперь я хочу сохранить строковое представление в настоящий двоичный файл.

В строке, закодированной Хаффманом, каждые 0 и 1 представляют собой байт .

Я хочу, чтобы каждые 0 и 1 были бит .

Как я могу сделать это в Python?

Редактировать 1:

Пожалуйста, прости, я не достаточно ясно описал свою проблему.

Позвольте мне объяснить мой текущий подход к записи в нули, а в двоичную систему.

Скажем, мы можем кодировать строку s = '010101010'.

1. Я использую int, чтобы преобразовать его в целое число
2. Затем используйте unichr, чтобы преобразовать его в строку, чтобы я мог записать его в файл
3. записать строку в файл в двоичном режиме

Также следует отметить, что мне нужно прочитать файл для декодирования кода Хаффмана.

Итак, мой подход,

1. чтение байтов из файла
2. восстановить их в int
3. преобразовать int в их строку двоичного представления.
4. расшифровать строку

И на шаге 2 проблема возникает, и я стал невежественным.

Поскольку некоторые строки Хаффмана могут быть короткими (например, 10), в то время как некоторые могут быть длинными (010101010101001). Это приводит к разной длине байта в значении int ( некоторая короткая строка может занимать всего один байт, в то время как длинные строки могут занимать два или даже больше )

Следующий код иллюстрирует мою проблему:

ss=['010101','10010101010'] 
# first one is short and takes only one byte in its int value
# second one is long and takes two bytes   

print 'write it to file'
with open('binary.bin','wb') as f:
    for s in ss:
        n=int(s,2)
        print n
        s=unichr(n)
        f.write(s)

print 'read it to file'
with open('binary.bin','rb') as f:
    for s in f.read(): 
        print ord(s)

Я читаю один байт за раз во второй с частью , но это на самом деле не правильно. Потому что строка 10010101010 занимает два байта.

Итак, когда я читаю эти байты из файла, сколько байтов я должен прочитать за раз?

Answer 1

Есть два разных «двоичных» представления в Python, которые вы можете использовать.

Bignum

Одно - это целое число bignum или произвольной точности.Этот тип называется long в Python 2.x и int в Python 3.x.Как следует из названия, это представление семантически представляет собой целое число произвольной длины, поэтому полезно, если вы планируете делать арифметику с результирующим числом.Для разбора строки двоичных цифр используйте

# Python 2
long(digit_str, 2)

или

# Python 3
int(digit_str, 2)

bitstring library

В качестве альтернативы, как предложил Марк B в комментариях, используйтеbitstring библиотека .В частности, для преобразования используйте функцию bitstring.pack .

Для кодирования Хаффмана использование bitstring, вероятно, предпочтительнее, чем хранение данных в byte -строке, посколькукак правило, не кратно 8 битам;bitstring позволяет вам манипулировать битовыми строками произвольной длины.Недостаток: bitstring не является частью стандартной библиотеки.

Answer 2

Один из возможных подходов (использование библиотеки bitstring ), который имеет некоторый смысл, но все же содержит некорректность:

Использование библиотеки bitstring (Благодаря Механическая улитка и Марк B )

Для записи в файл.

Шаги:

1. кодировать простой текст в строку двоичного представления
2. объединить все эти строки, чтобы сформировать одну длинную
3. , использовать bitstring.BitArray для преобразования в шестнадцатеричный формат
4. записать шестнадцатеричную строку в файл

Для чтения:

1. прочитать шестнадцатеричную строку из файла
2. преобразовать ее обратно в битовую строку, используя BitArray
3. начать декодирование

код:

ss=['01010100','10010101010','010101110101010101'] #encoded message


from bitstring import BitArray,BitStream
print 'write it to file'
with open('binary.bin','wb') as f:
    s=''.join(ss);
    b=BitArray(bin=s)                 
    f.write(b.tobytes())# thanks to Scott, tobytes() method is very useful

print 'read it to file'
b=BitArray(filename='binary.bin')
print b.bin

Answer 3

У вас есть строка, которую нужно преобразовать в число. int принимает необязательное 'base' в качестве аргумента. Так что для строки в вашем примере,

>>> int('01010101010', 2)
682

Если у вас есть число (не строка), не имеет смысла хотеть «настоящий» двоичный файл, так как число одно и то же, вы можете отобразить его в любой базе. Это означает, что двоичный файл 100 - это то же число, что и десятичный код 4, в вашей программе они не являются разными числами. Итак, как только вы превратите свою строку в число, вы можете возиться с битами в ней.