Вы когда-нибудь задумывались, как работают программы сжатия данных, такие как WinRAR или WinZip? А вы когда-нибудь спрашивали себя, можем ли мы сжимать данные, почему бы не хранить и не использовать их таким образом? Если да, добро пожаловать в третью главу серии: Коды Хаффмана.

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

Молодец, Шерлок, мы и подумать не могли! Но не будьте такими самонадеянными, потому что самые простые идеи обычно самые красноречивые. Рассмотрим текстовый файл, состоящий из 10 000 символов. Предполагая, что вы используете 8 бит для хранения одного символа, текст будет занимать 80 000 бит на вашем компьютере. Но если мы сможем найти способ использовать меньшее количество битов для хранения одного символа, мы сможем снизить требования к хранению файла.

Коды префиксов

Давайте немного упростим наши ограничения, чтобы мы могли произвести некоторые вычисления. У нас все еще есть текст длиной 10 000 символов, но у нас всего 6 букв от a до f. Мы можем представить 6 букв с помощью 3-бит, если мы используем коды фиксированной длины для каждого символа, и весь текст будет занимать 30 000 бит в памяти.

Как вы можете догадаться, есть и другие способы представления символов. Вместо того, чтобы использовать 3 бита для каждого символа, мы можем использовать коды переменной длины, которые могут работать значительно лучше за счет хранения. Для этого мы будем следовать двум правилам:

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

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

Используя коды переменной длины, если вы хотите написать слово «добавить», вам нужно написать 0 111 111, что требует на 2 бита меньше по сравнению с его >фиксированной длины аналог 000 011 011. Давайте посчитаем, используя частоты и коды переменной длины для нашего длинного текста в 10 000 символов.

Мы уменьшили требуемое пространство для нашего текста с 30 000 бит до 22 400 бит, улучшение чуть больше, чем на 25%. Достижимы гораздо более высокие проценты, но этого достаточно для данного примера.

Построение кодов Хаффмана

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

Двоичное дерево поможет нам получить наши коды переменной длины. На каждом шаге мы берем два письма с наименьшей частотой, объединяем их под родительским узлом и назначаем их общую частоту их родительскому узлу (в этом нам может помочь приоритетная очередь). Мы будем продолжать делать это до тех пор, пока все буквы не будут объединены под одним корнем. Вот окончательное дерево, построенное для нашего примера текстового файла (частоты даны в процентах):

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

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

Теперь давайте напишем код. Сжатие текста должно быть простым: все, что вам нужно сделать, это заменить каждый символ соответствующим кодом. Итак, я поделюсь только функцией декомпрессии, которую я использовал для решения вопроса HackerRank, о котором упоминал в начале поста.

void decodeHuffman(HuffmanTreeNode* root, string encoded) {
    HuffmanTreeNode* runner = root;
    for (char current : encoded) {
        if (current = '0') {
            runner = runner->left;
        } else {
            runner = runner->right;
        }
        if (runner->isLeaf()) {
            cout << runner->data;
            runner = root;
        }
    }
}

Мы перебираем каждый символ (который может быть либо «0», либо «1») в закодированной строке и выбираем соответствующий маршрут в построенном дереве. Всякий раз, когда мы сталкиваемся с конечным узлом, мы знаем, что нашли букву. Затем мы сбрасываем наш указатель и делаем то же самое, пока весь текст не будет декодирован.

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

Если мы можем выполнять сжатие данных без потерь, то почему бы не всегда использовать сжатые данные на наших компьютерах? Потому что со сжатыми данными не очень легко работать. На самом деле нам нужно постоянно выполнять дополнительные операции, если мы хотим работать со сжатыми данными, что было бы не очень эффективно. Например, когда мы использовали коды фиксированной длины для хранения нашего текста, мы знаем, что каждая буква ровно на 3 бита от предыдущей и следующей букв. Можете ли вы сказать, сколько битов отстоит следующая буква, не расшифровывая ее сначала, когда вы используете коды переменной длины? Конечно, нет. Вот почему мы используем фиксированные форматы для хранения данных, даже если они содержат некоторую избыточность.

На сегодня все, остаток вечера потрачу на прослушивание Iron Maiden. Я надеюсь, что этот короткий пост был поучительным, и увидимся в следующем разделе.