АЛГОРИТМ ХАФФМАНА

Сжимая  файл  по алгоритму Хаффмана первое что мы должны сделать - это
необходимо  прочитать  файл  полностью  и подсчитать сколько раз встречается
каждый  символ  из  расширенного  набора  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 , так как следующий бит
может  быть  как  началом  следующего  кода, так и продолжением предыдущего.
     Необходимо  добавить,  что  ключем к построению префиксных кодов служит
обычное  бинарное  дерево  и  если внимательно рассмотреть предыдущий пример
с  построением  дерева ,  можно  убедится ,  что  все  получаемые  коды  там
префиксные.
     Одно  последнее  примечание - алгоритм  Хаффмана требует читать входной
файл  дважды , один  раз  считая  частоты  вхождения  символов , другой  раз
производя непосредственно кодирование.