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 , так как следующий бит может быть как началом следующего кода, так и продолжением предыдущего.

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

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