Unicode

Комментарии к задаче про кодирование Хаффмана.

Судя по вопросам на консультации я понял, что про бинарные строки на лекциях вам не рассказывали (или никто не слушал). Посему здесь приводится краткая справка.

Бинарные данные в python и небольшое описание unicode

В python3 есть три типа, предназначенных для работы со строками: str, bytes, bytearray.

Первый тип, str, вам известен. Это обычные строки в кодировке unicode (всё хранится в utf-32, до версии 3.3 — в utf-16).

bytes и bytearray хранят данные без привязки к кодировке. Различие между ними в том, что bytes — неизменяемый, bytearray — изменяемый.

Рассмотрим на примере разницу между str и bytearray.

Спецификация utf-8 примерно такова: если код символа влезает в 7 бит (ASCII), то он записывается одним байтом. Если нет — несколькими.

Убедимся в этом:

>>> bytearray('Hi!', 'utf-8')
bytearray(b'Hi!')
>>> list(map(bin, _))
['0b1001000',  # H
 '0b1101001',  # i
 '0b100001']   # !
>>> bytearray('Ай!', 'utf-8')
bytearray(b'\xd0\x90\xd0\xb9!')
>>> list(map(bin, _))
['0b11010000',  # А
 '0b10010000',  #
 '0b11010000',  # й
 '0b10111001',  #
 '0b100001']    # !

Как видно, русские буквы 'Ай' закодировались двумя байтами (кстати, из-за этого в utf-8, чтобы прочитать iй символ строки, нужно прочитать и все предыдущие).

В utf-16 на каждый символ отводится минимум по 2 байта:

>>> bytearray('Hi!', 'utf-16')
bytearray(b'\xff\xfeH\x00i\x00!\x00')
>>> list(map(bin, _))
['0b11111111',
 '0b11111110',
 '0b1001000',   # H
 '0b0',         #
 '0b1101001',   # i
 '0b0',         #
 '0b100001',    # !
 '0b0']         #
>>> bytearray('Ай!', 'utf-16')
bytearray(b'\xff\xfe\x10\x049\x04!\x00')
>>> list(map(bin, _))
['0b11111111',
 '0b11111110',
 '0b10000',     # А
 '0b100',       #
 '0b111001',    # й
 '0b100',       #
 '0b100001',    # !
 '0b0']         #
>>> bytearray([54, 131]).decode('utf-16')
'茶'  # китайский иероглиф 'cha' — чай

И русские 'Ай', и латинские 'Hi' кодируются двумя байтами.

Можно проверить, что символы с кодом, превосходящим 2**16 - 1 кодируются 4 байтами. Проблема с тем, что для чтения iго символа нужно читать предыдущие, сохраняется.

utf-32 использует ровно по 4 байта на каждый символ. Это гаррантирует доступ к iму символу без необходимости чтения предыдущих.

Работа с бинарными данными

Итак, в контексте задачи о кодировании, мы хотим уметь работать не с байтами, а с битами.

Архитектура компьютера не позволяет работать с ними напрямую, но у нас есть битовые операции. Конкретно нам понадобятся сдвиги:

x >> y сдвигает все биты числа x на y позиций вправо: bin(10) == '0b1010', bin(10 >> 1) == '0b101'.
x << y сдвигает все биты числа x на y позиций влево: bin(10) == '0b1010', bin(10 << 1) == '0b10100'.

Теперь легко написать функцию, которая преобразует строку '001010' в b'(', или, что тоже самое, bytes([40]): '001010' -> (0 << 7) + (0 << 6) + (1 << 5) + (0 << 4) + (1 << 3) + (0 << 2) + (0 << 1) + (0 << 0) == 40

def to_bytes(data):
    output = bytearray()
    position = 7
    buffer = 0
    
    for i in data:
        if i == '1':
            i = 1
        elif i == '0':
            i = 0
        else:
            raise RuntimeError('wrong byte ' + i)
        buffer += i << position
        position -= 1
        if position < 0:
            output.append(buffer)
            position = 7
            buffer = 0
    if position != 7:
        output.append(buffer)
    return output

def from_bytes(data):
    output = ''
    
    for i in data:
        c = bin(i)[2:]
        output += '0' * (8 - len(c) % 8) + c
    
    return output

Заметьте, что from_bytes(to_bytes('00000001000001')) == '0000000100000100'. С нулями в конце вам предстоит бороться самостоятельно.

Запись и чтение бинарных данных

Все умеют f = open('input.txt', 'r') и f = open('output.txt', 'w'). Так вы работаете с обычными текстовыми файлами.

Чтобы работать с бинарными файлами, их нужно открывать соответственно так: f = open('input', 'rb') и f = open('output', 'wb').

Эффективность

Очевидно, создать обычную строку из нулей и единиц и потом преобразовать ее в bytearray — плохая идея. При кодировании файла из, к примеру, четырех символов, если каждый символ запишется двумя битами, у вас будет строка из висьми символов, то есть 64 бита до преобразования ее в bytearray. Если сразу записывать в bytearray, размер данных не привысит 8 бит. Так что если вы возьметесь записывать кодированный файл, делайте это эффективно.

Предлагаемая структура архивированного файла

В целом, вы можете придумать свою структуру архивированного файла. Я предложу свой велосипед, который хорошо себя показал.

Первые 128 бит — md5 хэш от исходного файла, чтобы проверить правильность после декодирования.
Далее 3 бита — количество лишних нулей на конце следующего блока.
Далее идет описание дерева Хаффмана, с помошью которого было произведено кодирование. Записать его в бинарном формате достаточно просто, можно нагуглить. В принципе я могу рассказать это на следующей консультации (там у вас как раз одна пара, потом окно).
Далее 3 бита — количество лишних нулей на конце следующего блока.
Далее, собственно, код.