Delphi World - Сжатие по алгоритму Хаффмана
Delphi World - это проект, являющийся сборником статей и малодокументированных возможностей  по программированию в среде Delphi. Здесь вы найдёте работы по следующим категориям: delphi, delfi, borland, bds, дельфи, делфи, дэльфи, дэлфи, programming, example, программирование, исходные коды, code, исходники, source, sources, сорцы, сорсы, soft, programs, программы, and, how, delphiworld, базы данных, графика, игры, интернет, сети, компоненты, классы, мультимедиа, ос, железо, программа, интерфейс, рабочий стол, синтаксис, технологии, файловая система...
Сжатие по алгоритму Хаффмана

Huffman - Сначала кажется что создание файла меньших размеров из исходного без кодировки последовательностей или исключения повтора байтов будет невозможной задачей. Но давайте мы заставим себя сделать несколько умственных усилий и понять алгоритм Хаффмана ( Huffman ). Потеряв не так много времени мы приобретем знания и дополнительное место на дисках.

Сжимая файл по алгоритму Хаффмана первое что мы должны сделать - это необходимо прочитать файл полностью и подсчитать сколько раз встречается каждый символ из расширенного набора ASCII. Если мы будем учитывать все 256 символов, то для нас не будет разницы в сжатии текстового и EXE файла.

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

Мы имеем файл длинной в 100 байт и имеющий 6 различных символов в себе. Мы подсчитали вхождение каждого из символов в файл и получили следующее :

        |-----------------|-----|-----|-----|-----|-----|-----|
        |     cимвол      |  A  |  B  |  C  |  D  |  E  |  F  |
        |-----------------|-----|-----|-----|-----|-----|-----|
        | число вхождений |  10 |  20 |  30 |  5  |  25 |  10 |
        |-----------------|-----|-----|-----|-----|-----|-----|

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

        |-----------------|-----|-----|-----|-----|-----|-----|
        |     cимвол      |  C  |  E  |  B  |  F  |  A  |  D  |
        |-----------------|-----|-----|-----|-----|-----|-----|
        | число вхождений |  30 |  25 |  20 |  10 |  10 |  5  |
        |-----------------|-----|-----|-----|-----|-----|-----|

Мы возьмем из последней таблицы символы с наименьшей частотой. В нашем случае это D (5) и какой либо символ из F или A (10), можно взять любой из них например A.

Сформируем из "узлов" D и A новый "узел", частота вхождения для которого будет равна сумме частот D и A :

   Частота         30    10     5     10     20     25
   Символа          C     A     D      F      B      E
                          |     |
                          |--|--|
                            ||-|
                            |15|  = 5 + 10
                            |--|

Номер в рамке - сумма частот символов D и A. Теперь мы снова ищем два символа с самыми низкими частотами вхождения. Исключая из просмотра D и A и рассматривая вместо них новый "узел" с суммарной частотой вхождения. Самая низкая частота теперь у F и нового "узла". Снова сделаем операцию слияния узлов :

   Частота         30    10     5     10     20     25
   Символа          C     A     D      F      B      E
                          |     |      |
                          |     |      |
                          | |--||      |
                          |-|15||      |
                            ||-|       |
                             |         |
                             |    |--| |
                             |----|25|-| = 10 + 15
                                  |--|

Рассматриваем таблицу снова для следующих двух символов ( B и E ). Мы продолжаем в этот режим пока все "дерево" не сформировано, т.е. пока все не сведется к одному узлу.

   Частота         30    10     5     10     20     25
   Символа          C     A     D      F      B      E
                    |     |     |      |      |      |
                    |     |     |      |      |      |
                    |     | |--||      |      |      |
                    |     |-|15||      |      |      |
                    |       ||-|       |      |      |
                    |        |         |      |      |
                    |        |    |--| |      | |--| |
                    |        |----|25|-|      |-|45|-|
                    |             ||-|          ||-|
                    |    |--|      |             |
                    |----|55|------|             |
                         |-||                    |
                           |   |------------|    |
                           |---| Root (100) |----|
                               |------------|

Теперь когда наше дерево создано, мы можем кодировать файл. Мы должны всенда начнинать из корня ( Root ). Кодируя первый символ (лист дерева С) Мы прослеживаем вверх по дереву все повороты ветвей и если мы делаем левый поворот, то запоминаем 0-й бит, и аналогично 1-й бит для правого поворота. Так для C, мы будем идти влево к 55 ( и запомним 0 ), затем снова влево (0) к самому символу. Код Хаффмана для нашего символа C - 00. Для следующего символа ( А ) у нас получается - лево,право,лево,лево , что выливается в последовательность 0100. Выполнив выше сказанное для всех символов получим

   C = 00   ( 2 бита )
   A = 0100 ( 4 бита )
   D = 0101 ( 4 бита )
   F = 011  ( 3 бита )
   B = 10   ( 2 бита )
   E = 11   ( 2 бита )

Каждый символ изначально представлялся 8-ю битами ( один байт ), и так как мы уменьшили число битов необходимых для представления каждого символа, мы следовательно уменьшили размер выходного файла. Сжатие складывется следующим образом :

       |----------|----------------|-------------------|--------------|
       | Частота  |  первоначально |  уплотненные биты | уменьшено на |
       |----------|----------------|-------------------|--------------|
       |  C 30    |  30 x 8 = 240  |    30 x 2 = 60    |      180     |
       |  A 10    |  10 x 8 =  80  |    10 x 3 = 30    |       50     |
       |  D 5     |   5 x 8 =  40  |     5 x 4 = 20    |       20     |
       |  F 10    |  10 x 8 =  80  |    10 x 4 = 40    |       40     |
       |  B 20    |  20 x 8 = 160  |    20 x 2 = 40    |      120     |
       |  E 25    |  25 x 8 = 200  |    25 x 2 = 50    |      150     |
       |----------|----------------|-------------------|--------------|
     Первоначальный размер файла : 100 байт - 800 бит;
            Размер сжатого файла :  30 байт - 240 бит;

       240 - 30% из 800 , так что мы сжали этот файл на 70%.

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

В нашей методике сжатия и каждом узле находятся 4 байта указателя, по этому, полная таблица для 256 байт будет приблизительно 1 Кбайт длинной.

Таблица в нашем примере имеет 5 узлов плюс 6 вершин ( где и находятся наши символы ) , всего 11. 4 байта 11 раз - 44. Если мы добавим после небольшое количество байтов для сохранения места узла и некоторую другую статистику - наша таблица будет приблизительно 50 байтов длинны.

Добавив к 30 байтам сжатой информации, 50 байтов таблицы получаем, что общая длинна архивного файла вырастет до 80 байт. Учитывая , что первоначальная длинна файла в рассматриваемом примере была 100 байт - мы получили 20% сжатие информации.

Не плохо. То что мы действительно выполнили - трансляция символьного ASCII набора в наш новый набор требующий меньшее количество знаков по сравнению с стандартным.

Что мы можем получить на этом пути?

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

    Мы получим что можно иметь только :
                 4 - 2 разрядных кода;
                 8 - 3 разрядных кодов;
                16 - 4 разрядных кодов;
                32 - 5 разрядных кодов;
                64 - 6 разрядных кодов;
               128 - 7 разрядных кодов;

     Необходимо еще два 8 разрядных кода.
                 4 - 2 разрядных кода;
                 8 - 3 разрядных кодов;
                16 - 4 разрядных кодов;
                32 - 5 разрядных кодов;
                64 - 6 разрядных кодов;
               128 - 7 разрядных кодов;
             --------
               254

Итак мы имеем итог из 256 различных комбинаций которыми можно кодировать байт. Из этих комбинаций лишь 2 по длинне равны 8 битам. Если мы сложим число битов которые это представляет, то в итоге получим 1554 бит или 195 байтов. Так в максимуме , мы сжали 256 байт к 195 или 33%, таким образом максимально идеализированный Huffman может достигать сжатия в 33% когда используется на уровне байта.

Все эти подсчеты производились для не префиксных кодов Хаффмана т.е. кодов, которые нельзя идентифицировать однозначно. Например код A - 01011 и код B - 0101. Если мы будем получать эти коды побитно, то получив биты 0101 мы не сможем сказать какой код мы получили A или B , так как следующий бит может быть как началом следующего кода, так и продолжением предыдущего.

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

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

Проект Delphi World © Выпуск 2002 - 2017
Автор проекта: Эксклюзивные курсы программирования