Сжатие Хаффмана - один из основных алгоритмов сжатия без потерь. (Алгоритмы без потерь - это те, которые могут сжимать и распаковывать данные без потери данных.)

Он опирается на основную идею представления наиболее часто повторяющейся подъединицы с наименьшим числом битов. В большинстве случаев эта повторяющаяся субъединица может быть персонажем, как мы предполагаем в этой статье.

Это широко используемый метод, и некоторые места, где он используется, - это изображения JPEG, файлы MP3 и сжатие последовательностей ДНК.

Лучший способ узнать об этом - сделать компрессор самостоятельно! Мы будем использовать python для создания (не самой эффективной, но работающей) модели компрессора Хаффмана.

Основы кодирования Хаффмана

Этот алгоритм использует повторяющиеся символы в наших интересах. Мы пытаемся представить эти повторяющиеся символы меньшим количеством бит, чем обычно. Например, предположим, что у нас есть большой текстовый файл, содержащий 1000 вхождений буквы «A» и только ~ 200 вхождений других алфавитов.

Обычно каждая буква занимает 8 бит данных (1 байт). Это будет означать, что общий размер данных будет 8 * количество символов. (в битах)

Но если бы был какой-то способ, которым мы могли бы попытаться представить 'A' таким образом, который занимал бы меньше 8 бит, скажем 2 бита, мы бы уменьшили наш размер (в идеале) на 1000 * (8–2) = 6000 бит.

Для файлов большего размера это было бы существенным изменением. Еще одна вещь, которую мы должны иметь в виду, это то, что «A» не будет единственной буквой, которая может быть представлена ​​менее чем в 8 битах. Например, у нас может быть ситуация, когда с «A» мы можем представить «C» и «D» с 3 битами каждый.

Так как же нам решить и выяснить, как представлять каждую букву? Что ж, благодаря Дэвиду А. Хаффману мы можем найти наиболее эффективный способ представления этих символов в двоичной форме, используя нечто, называемое деревом Хаффмана. Это дерево дает нам наиболее оптимальное представление двоичного кода, учитывая частоту каждого символа.

Например, предположим, что мы хотим сжать последовательность ДНК, у нас есть текстовый файл, содержащий строку «AGGACTAAAAACG»

Распределение каждой буквы составляет -

‘A’ : 7

‘G’ : 3

‘C’ : 2

‘T’ : 1

Наше дерево Хаффмана будет выглядеть примерно так -

Не волнуйтесь, если вы не знаете, как было создано это дерево, мы к этому немного подойдем. Но пока давайте посмотрим, насколько мы можем сжать эту строку, глядя на новые представления.

Обычно мы представляем «A», «G», «T» и «C» с 8 битами каждый. Но теперь новые представления -

A: 0 (1 бит)

G: 10 (2 бита)

C: 110 (3 бита)

T: 111 (3 бита)

Таким образом, что-то вроде "ACT" будет представлено как 0110111.

Вы можете видеть здесь, что мы представили «ACT» всего в 7 битах вместо обычных 24 битов, которые могли бы потребоваться. Точно так же наша исходная сжатая строка будет -

Размер = 7 * (1 бит) + 3 * (2 бита) + 2 * (3 бита) + 1 * (3 бита) = 22 бита!

Это хорошее сокращение по сравнению с нашим обычным (7 + 3 + 2 + 1) * 8 = 104 бита.

Надеюсь, это дало вам быстрое представление о том, как работает сжатие Хаффмана. Затем давайте посмотрим, как мы строим дерево Хаффмана.

Строительство деревьев Хаффмана

Первый и самый фундаментальный шаг построения дерева Хаффмана - это вычисление появления каждого символа. Поскольку мы будем использовать Python, структура данных словаря будет самым простым способом сделать это.

Теперь предположим, что это текущая таблица встречаемости символов. Что мы хотим сделать, так это сгруппировать два наименее встречающихся узла (символа) и соединить их. Это будет считаться новым узлом со значением вхождения, представляющим собой сумму значений обоих узлов, то есть общее количество вхождений обоих этих символов.

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

Мы повторяем этот шаг, пока не останется только один узел. Этот узел - наше дерево Хаффмана.

Теперь, чтобы найти новое представление каждого символа, мы добавляем 0 для каждого левого края и 1 для каждого правого края. Вот изображение, которое поможет вам понять, что это значит.

Код Python

Мы собираемся использовать кучу в качестве предпочтительной структуры данных для формирования нашего дерева Хаффмана. В python heapq - это библиотека, которая позволяет нам легко это реализовать.

Давайте начнем с создания функции с именем encode, которая принимает данные в строковом формате.

import heapq
def encode(data):
    key = dict()
    encoded = str()
    corp = dict()

Затем давайте посчитаем частоту каждого символа в данных и сохраним ее в нашем ключе.

# Count the frequency of characters in data
    for _ in data:
        corp[_]=corp.get(_,0)+1
        # corp.get returns a default value of 0 if key not found

Мы анализируем дерево, как обсуждалось ранее, и в каждой точке добавляем «0» к узлам слева и «1» справа.

while len(htree)>1:
        left_node = heapq.heappop(htree)
        right_node = heapq.heappop(htree)
for _ in left[1]:
            # Add a 0 to the encoding of all nodes on the left
            key[_] = '0' + key.get(_,"")
for _ in right[1]:
            # Add a 1 to the encoding of all nodes on the right
            key[_]= '1' + key.get(_,"")
# Join both as one node and push to tree
        heapq.heappush(htree(left_node[0]+right_node[0],
                       left_node[1]+right_node[1]))

Для понимания распечатываем кодировки -

for x in key:
        print(x,key[x])

Остальная часть кода довольно проста, где мы заполняем оставшиеся биты нулями и сохраняем закодированную строку.

''' 
Replace all our characters with their bit encodings and place     them in our string “encoding” 
'''
for char in data:
    encoded+=key[char]
        
# Here we’re just filling the left over bits with 0's
rem = len(encoded)%8
key[‘rem’] = rem
encoded+=’0'*rem
return encoded

Вот и все. Просто передайте строку в эту функцию, и она вернет сжатую строку в виде целого числа.

Помните, что для декодирования сжатых данных вам также понадобится ключ. Я привел весь код ниже, если вы хотите взглянуть на него и попробовать сами. Часть декодирования должна иметь смысл, поскольку это полная противоположность тому, что мы сделали выше.

Заключение

Теперь, когда вы знаете, как работает сжатие по Хаффману, позвольте мне предупредить вас, что это было всего лишь очень базовым представлением о сжатии и, возможно, не лучший способ его реализовать, если вы хотите создать реальный компрессор. Тем не менее, это хорошая отправная точка для понимания того, как все это работает.

Надеюсь, эта статья оказалась полезной. Любые исправления или предложения приветствуются в комментариях.