Алгоритм Хаффмана на пальцах

http://en.nerdaholyc.com/huffman-coding-on-a-string/
  • Перевод
Вы вероятно слышали о Дэвиде Хаффмане и его популярном алгоритме сжатия. Если нет, то поищите информацию в интернете — в этой статье я не буду вас грузить историей или математикой. Сегодня я хочу просто попытаться показать вам практический пример применения алгоритма к символьной строке.

Примечание переводчика: под символом автор подразумевает некий повторяющийся элемент исходной строки — это может быть как печатный знак (character), так и любая битовая последовательность. Под кодом подразумевается не ASCII или UTF-8 код символа, а кодирующая последовательность битов.

К статье прикреплён исходный код, который наглядно демонстрирует, как работает алгоритм Хаффмана — он предназначен для людей, которые плохо понимают математику процесса. В будущем (я надеюсь) я напишу статью, в которой мы поговорим о применении алгоритма к любым файлам для их сжатия (то есть, сделаем простой архиватор типа WinRAR или WinZIP).

Идея, положенная в основу кодировании Хаффмана, основана на частоте появления символа в последовательности. Символ, который встречается в последовательности чаще всего, получает новый очень маленький код, а символ, который встречается реже всего, получает, наоборот, очень длинный код. Это нужно, так как мы хотим, чтобы, когда мы обработали весь ввод, самые частотные символы заняли меньше всего места (и меньше, чем они занимали в оригинале), а самые редкие — побольше (но так как они редкие, это не имеет значения). Для нашей программы я решил, что символ будет иметь длину 8 бит, то есть, будет соответствовать печатному знаку.

Мы могли бы с той же простотой взять символ длиной в 16 бит (то есть, состоящий из двух печатных знаков), равно как и 10 бит, 20 и так далее. Размер символа выбирается, исходя из строки ввода, которую мы ожидаем встретить. Например, если бы я собрался кодировать сырые видеофайлы, я бы приравнял размер символа к размеру пикселя. Помните, что при уменьшении или увеличении размера символа меняется и размер кода для каждого символа, потому что чем больше размер, тем больше символов можно закодировать этим размером кода. Комбинаций нулей и единичек, подходящих для восьми бит, меньше, чем для шестнадцати. Поэтому вы должны подобрать размер символа, исходя из того по какому принципу данные повторяются в вашей последовательности.

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

Предположим, у нас есть строка «beep boop beer!», для которой, в её текущем виде, на каждый знак тратится по одному байту. Это означает, что вся строка целиком занимает 15*8 = 120 бит памяти. После кодирования строка займёт 40 бит (на практике, в нашей программе мы выведем на консоль последовательность из 40 нулей и единиц, представляющих собой биты кодированного текста. Чтобы получить из них настоящую строку размером 40 бит, нужно применять битовую арифметику, поэтому мы сегодня не будем этого делать).

Чтобы лучше понять пример, мы для начала сделаем всё вручную. Строка «beep boop beer!» для этого очень хорошо подойдёт. Чтобы получить код для каждого символа на основе его частотности, нам надо построить бинарное дерево, такое, что каждый лист этого дерева будет содержать символ (печатный знак из строки). Дерево будет строиться от листьев к корню, в том смысле, что символы с меньшей частотой будут дальше от корня, чем символы с большей. Скоро вы увидите, для чего это нужно.

Чтобы построить дерево, мы воспользуемся слегка модифицированной очередью с приоритетами — первыми из неё будут извлекаться элементы с наименьшим приоритетом, а не наибольшим. Это нужно, чтобы строить дерево от листьев к корню.

Для начала посчитаем частоты всех символов:
Символ Частота
'b' 3
'e' 4
'p' 2
' ' 2
'o' 2
'r' 1
'!' 1


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


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

Повторим те же шаги и получим последовательно:





Ну и после того, как мы свяжем два последних элемента, получится итоговое дерево:


Теперь, чтобы получить код для каждого символа, надо просто пройтись по дереву, и для каждого перехода добавлять 0, если мы идём влево, и 1 — если направо:


Если мы так сделаем, то получим следующие коды для символов:
Символ Код
'b' 00
'e' 11
'p' 101
' ' 011
'o' 010
'r' 1000
'!' 1001


Чтобы расшифровать закодированную строку, нам надо, соответственно, просто идти по дереву, сворачивая в соответствующую каждому биту сторону до тех пор, пока мы не достигнем листа. Например, если есть строка «101 11 101 11» и наше дерево, то мы получим строку «pepe».

Важно иметь в виду, что каждый код не является префиксом для кода другого символа. В нашем примере, если 00 — это код для 'b', то 000 не может оказаться чьим-либо кодом, потому что иначе мы получим конфликт. Мы никогда не достигли бы этого символа в дереве, так как останавливались бы ещё на 'b'.

На практике, при реализации данного алгоритма сразу после построения дерева строится таблица Хаффмана. Данная таблица — это по сути связный список или массив, который содержит каждый символ и его код, потому что это делает кодирование более эффективным. Довольно затратно каждый раз искать символ и одновременно вычислять его код, так как мы не знаем, где он находится, и придётся обходить всё дерево целиком. Как правило, для кодирования используется таблица Хаффмана, а для декодирования — дерево Хаффмана.

Входная строка: «beep boop beer!»
Входная строка в бинарном виде: «0110 0010 0110 0101 0110 0101 0111 0000 0010 0000 0110 0010 0110 1111 0110 1111 0111 0000 0010 0000 0110 0010 0110 0101 0110 0101 0111 0010 0010 000»
Закодированная строка: «0011 1110 1011 0001 0010 1010 1100 1111 1000 1001»
Как вы можете заметить, между ASCII-версией строки и закодированной версией существует большая разница.

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

Все исходники были откомпилированы и проверены с использованием стандарта C99. Удачного программирования!

Скачать исходный код

Чтобы прояснить ситуацию: данная статья только иллюстрирует работу алгоритма. Чтобы использовать это в реальной жизни, вам надо будет поместить созданное вами дерево Хаффмана в закодированную строку, а получатель должен будет знать, как его интерпретировать, чтобы раскодировать сообщение. Хорошим способом сделать это, является проход по дереву в любом порядке, который вам нравится (я предпочитаю обход в глубину) и конкатенировать 0 для каждого узла и 1 для листа с битами, представляющими оригинальный символ (в нашем случае, 8 бит, представляющие ASCII-код знака). Идеальным было бы добавить это представление в самое начало закодированной строки. Как только получатель построит дерево, он будет знать, как декодировать сообщение, чтобы прочесть оригинал.
Поделиться публикацией
AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама
Комментарии 41
  • +1
    Лично для меня сохранение/восстановление дерева было едва ли не более интересной задачей, чем само сжатие.

    Кстати, а как алгоритм закодирует строку «ааааааааааааааааааа»?
    • +2
      Вероятность вхождения — 1. По идее, каждая «а» заменится на 0.
      • +2
        Глубина дерева 0, «а» будет прямо в корне.
      • –2
        // упаковка дерева _tree в буффер _buf
        // _pos нужен для рекурсии
        int ZipTree(Element *_buf, Element *_tree, int _pos)
        {
        Element *c;
        _buf[_pos] = *_tree; // кладем листик в массив
        c = &_buf[_pos]; // запоминаем место, куда положили
        _pos++; // едем дальше

        if(_tree->left)
        {
        c->left = (Element *)_pos; // меняем адрес на локальный
        _pos = ZipTree(_buf, _tree->left, _pos); // кладем оставшуюся левую сторону дерева
        }
        if(_tree->right)
        {
        c->right = (Element *)_pos;
        _pos = ZipTree(_buf, _tree->right, _pos);
        }

        return _pos;
        }

        Смысл в том, что нужно все указатели на листья перевести в относительную форму(относительно начала массива или файла.
        Распаковка так-же просто. Заменяем локальные адреса на реальные адреса в памяти.

        Недавно реализовывал этот алгоритм. Интереса ради.
        То-же думал над упаковкой дерева. Но все оказалось слишком просто :-(

        Алгоритм так себе.
        Для сжатия изображений подходит слабо.
        Те, где цветов мало сжимает достойно. Но никак не лучше LZW.
        Фотографии сжимает всего на 10-20%. Что недостаточно.

        Зато прост в реализации.
        • 0
          Неэкономно будет, да и некрасиво это, записывать в архив реализацию дерева, а не информацию о нём.

          Лично я делал так.
          Рекурсивный проход по дереву в глубину слева направо.
          Если лист, пишем в вывод 1(бит) и сам символ.
          Если узел, пишем левую ветку, правую ветку, 0(бит).
          В результате у нас n символов и n-1 бит

          При считывании используем принцип обратной польской записи.
          Считали 1, считали символ, сформировали лист — положили в стек.
          Считали 0 — достали из стека два элемента, соединили в узел дерева(первый правый, второй левый), положили в стек.
          Конец записи — в стеке должен остаться один элемент, он и есть дерево целиком.
          • +1
            Алгоритм так себе.
            Для сжатия изображений подходит слабо.
            Те, где цветов мало сжимает достойно. Но никак не лучше LZW.
            Фотографии сжимает всего на 10-20%. Что недостаточно.

            Зато прост в реализации.

            То-то все его используют направо и налево. Например, для сжатия изображений (png, jpeg), произвольных файлов (zip, gzip, zlib)

            deflate = lz77 (кодирование последовательностей) + huffman (энтропийное кодирование)
            jpeg = dct и квантование (препроцессинг) + huffman (энтропийное кодирование)

            Алгоритм Хаффмана — это оптимальный префиксный код; другого префиксного кода, более эффективного, не существует. Обычно он чуть слабее, но некоторых случаях он (на один бит) эффективнее, чем второй широко используемый сегодня алгоритм энтропийного кодирования — арифметическое кодирование. Однако, алгоритм Хаффмана всегда значительно быстрее арифметического кодирования.
        • 0
          Мм.., круто!
          • +3
            Конечно хорошо, что постарались, но сколько можно про Хаффмана писать на хабре?

            habrahabr.ru/post/142242/
            habrahabr.ru/post/132289/
            • +2
              Ничего личного, по заказу ОРТ bobuk:
              Очень популярное, буквально на пальцах, объяснение того, как работает алгоритм компрессии Хаффмана. Действительно, более доступного разжевывания не встречал. Никто не хочет перевести на русский?


              К слову, одна Ваша ссылка изобилует математикой, а вторая написана так страшно, что лично я бы ничего не понял (да и сейчас не слишком понятно, хотя как работает алгоритм я вроде как знаю). Мой вариант рассказывает именно что максимально просто, так что не надо думать, всё уже разжёвано.
            • +4
              Мне кажется объяснение Хаффмана на пальцах, заняло бы меньше времени нежели перевод статьи :}
              • +3
                Зачем использовалась очередь с приоритетами? Есть более простые реализации.

                Все символы исходного алфавита сортируются и помещаются в очередь №1. Все вершины, получившиеся в результате операции связывания, помещаются в очередь №2 (их сортировать не нужно, они уже идут в правильном порядке).

                Когда по алгоритму нам нужно найти вершину с минимальным приоритетом, мы просто сравниваем первые элементы этих двух очередей и выбираем нужный.
                • –3
                  Наконец-то доступно объяснили про этот алгоритм. Спасибо!
                  • 0
                    за что заминусовали комментарий благодарного человека? зы. Когда-нибудь Хаффман напишет алгоритм, применяя который можно будет понять логику минусования кармы на Хабре. Это действительно будет прорыв
                    • 0
                      Дэвид Хаффман уже больше ничего не напишет :(
                  • 0
                    Когда-то писали этот алгоритм на ассемблере (в соответсвующем курсе в университете). Самым сложным оказалось тестирование. Буквально чудо какое-то, что модули кодирования и декодирования состыковались без проблем — иначе пришлось бы по битам проверять что и где не так происходит.
                    Мы, кстати, в заголовок заархивированного файла сохраняли таблицу частот, по которой затем восстанавливали дерево для декодирования.
                    • 0
                      Хоть Вы и не автор, а всего лишь переводчик, но пожалуйста, поясните следующий момент:

                      «Предположим, у нас есть строка «beep boop beer!», для которой, в её текущем виде, на каждый знак тратится по одному байту»

                      Откуда Вы взяли 1 байт? В строке всего 5 различных символов: «b»,«e»,«p»,«o»,«r». Для их кодирования 8 бит слишком много: даже 3 бит хватит с избытком.
                      • 0
                        Каюсь, забыл про пробел и символ окончания (хотя не до конца понял, зачем он нужен). Но даже для 7 символов 3 бит хватит.
                        • +1
                          Ну закодированная последовательность может быть любой длины (в битах). Например, выше был пример с «ааааааааа». Если эту строку кодировать прямо, получится (биты) 00000000 0, что ни в какой файл записать не удастся. Реально вы запишете что-то вроде 00000000 00000000. И дерево, в котором записано, что «0» — «а». И как определить длину исходной последовательности?

                          Есть ровно два способа — хранить длину где-то или кодировать специальный символ «конец».

                          Если использовать второй способ, последовательность на выходе будет 00000000 0100000 и таблица «0» — «а», «1» — конец, вопросов при распаковке не возникнет.
                          • 0
                            Спасибо за пояснение. Мне кажется, что, когда описывается алгоритм, не стоит углубляться во всякие специфичные вещи, как то какая-то файловая система. Я, к примеру, работаю с ПЛИСами, и могу записать сколько угодно бит. По сети тоже можно передавать произвольное количество бит. Но это всего лишь моё мнение.
                            P.S. Мне, кстати, способ с заданием длины последовательности кажется более логичным.
                            • 0
                              Да дело не в файлах. Я на примере файловой системы пытался продемонстрировать явную неопределённость, «где заканчивать». Абсолютно такая же проблема есть и у арифметического кодирования, там она даже более ярко выражена — даже при кодировании не сразу очевидно, как маркировать конец потока.

                              Ну вот и как вы, передавая по сети поток из произвольного количества бит, объявите конец последовательности? Часто алгоритм Хаффмана используют для известных систем с известной статистикой символов, т.е. на приёмнике и передатчике есть статическая таблица, которая по каналу связи не передаётся. И вот тут куда логичнее использовать именно специальный символ-сообщение «конец последовательности».
                              • 0
                                Спасибо. Я понял смысл символа конец сообщения. Просто в моих задачах, а я весьма и весьма плотно работаю с сжатием данных, мне всегда удавалось без него обходиться.
                        • +1
                          В текущем виде для кодирования строки применяется кодировка ASCII (ну или UTF-8, для латиницы нет разницы), в которой для каждого знака отводится ровно 1 байт. То есть, Вы думаете, что мы взяли какой-то уже подготовленный формат из небольшого количества возможных значений, а речь идёт как раз об обычной строке текста.
                          • 0
                            Тогда к чему написано это: «Примечание переводчика: под символом автор подразумевает некий повторяющийся элемент исходной строки — это может быть как печатный знак (character), так и любая битовая последовательность»?
                            • +1
                              А это почти определение из теории информации :) правда, оно как-то плохо сочетается со стилем остальной части статьи.
                              • 0
                                Все мои критические комментарии как раз к этому и сводятся. Что либо используем стиль «а сейчас мы соединим два кружочка», либо следуем принятой терминологии.
                              • 0
                                Потому что автор пользуется терминами symbol и character, которые на русский язык оба как «символ», и, чтобы избежать путаницы, мне пришлось ввести это примечание. Чуть ниже автор поясняет, что именно в данном примере, на котором рассматривается алгоритм, размер символа он решил приравнять к размеру печатного знака, потому что кодируем мы именно их.
                              • 0
                                Ну и говорить о сжатии, сравнивая результат сжатия с заведомо избыточной кодировкой, тоже не совсем корректно.
                                • 0
                                  Почему? Разве сжатие перестаёт от этого быть сжатием? Сжатие текста — распространённое жизненное явление и именно на нём архиваторы, да, показывают как правило наилучшие результаты.
                                  • 0
                                    В данном примере двухкратного сжатия можно достичь и без использования алгоритма Хаффмана, разве нет?
                                    • 0
                                      А алгоритм Хаффмана дал трёхкратное. А bzip2 вообще увеличит размер с 15 байт до 52. Как это всё связано? Теперь нельзя использовать для наглядных примеров данные, которые могут быть обработаны и другими алгоритмами?
                                      • 0
                                        Я к тому, что из статьи абсолютно непонятно, какую реальную эффективность обеспечивает описываемый алгоритм. Если вы скажете, что каждый символ кодируется двумя байтами, то ваш «Хаффман» даст шестикратное сжатие, что совсем неверно.
                                        • 0
                                          Там в самом начале сказано — речь не о математике, истории или использовании алгоритма) Исключительно описание его работы.
                                      • 0
                                        Есть разница между эффективным префиксным кодом и непрефиксным с фиксированной длиной последовательности.

                                        Даже в этом примере из статьи префиксный код лучше. Не лучше он только в случае, когда частоты всех символов абсолютно одинаковы ;)
                                        • 0
                                          … и число символов является степенью 2. (забыл, забыл)
                              • 0
                                Ну и потом в первой таблице вы считаете, не частоту, а количество символов. Понятно, что легко преобразовать одно в другое, но, по-моему, при описании алгоритма, важно соблюдать терминологию.
                                • 0
                                  Тут на самом деле нет терминологической путаницы. Автор использует слово «frequency» (частота), и возможно, сам не знает, что я сейчас расскажу, но тем не менее он использует его относительно обоснованно :)
                                  При различных расчётах встречаемости каких-либо данных сложилась ситуация, что использовать настоящие частоты неудобно. Например, вы работаете со словарём употребляемости слов в языке. Если использовать честные частоты, то как только вы решаете добавить какое-то слово из нового текста, добавленного в корпус, надо будет пересчитывать частоты всех без исключения слов.
                                  Поэтому используется абсолютная величина, которая называется частотой (в русском языке её часто называют «частотность», но встречаются оба вариант) и понимается как «количество попаданий этого слова на весь корпус». При публикации итогового словаря, данные для удобства использования совместно с другими источниками нормируются — например, в величину ipm (instances per million) — но при работе использовать удобнее абсолютные значения, которые тоже называются частотой. Просто за скобкой остаётся дополнение, что величина 42 — это «42 совпадения на один полный источник данных».
                                  • 0
                                    Не знаю, может где-то так и принято, но у нас в институте за такое карают. Равно, как и за вероятность в процентах. И за многое многое другое. Не хочу начинать тут философский спор, но я считаю, что хороший программист должен обладать дисциплинированным разумом и не позволять себе такую путаницу.

                                    Это всего лишь моё мнение. Ещё раз подчеркну, что по-моему не стоит устраивать спор на эту тему в комментариях.
                                • 0
                                  Если длина символа — 8 бит, то даже в самом оптимальном случае, для строки аааааааааааааааа, Хаффман сожмет текст не более чем в 8 раз (т.е. не более чем во столько раз, сколько бит в символе).
                                  • 0
                                    Какой получается время работы? Похоже на О(nlog(n)) + время на создание таблицы символ-частота вхождения
                                    • 0
                                      Если для кодирования пользоваться деревом, то O(n*log(n)), если хэш-таблицей, в которой время поиска считается константным, то O(n).
                                    • +2
                                      Как оказалось, исходная статья как минимум сменила свой адрес нахождения. Также как и исходный код к статье. Однако здесь я нашёл копию исходной статьи, а также копию исходных кодов к ней. Возможно, что кому-нибудь эта информация и поможет.

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