Hекотоpые методы сжатия данных

N.B.  Здесь рассматриваются только алгоритмы производящие сжатие без потерь,
      т.е. допускающие восстановление исходной информации "байт в байт".

 Running -  Это самый простой из  методов упаковки информации . Предположите
            что Вы имеете строку текста, и в конце строки стоит 40 пробелов.
алицо явная избыточность имеющейся информации.  Проблема сжатия этой строки
решается  очень просто - эти  40  пробелов ( 40 байт ) сжимаются в 3 байта с
помощью упаковки их по методу повторяющихся символов (running). Первый байт,
стоящий  вместо  40  пробелов в  сжатой  строке , фактически  будет  явлться
пробелом ( последовательность была из пробелов ) . Второй байт - специальный
байт "флажка" который указывает что мы должны развернуть предыдущий в строке
байт в  последовательность  при  восстановлении  строки . Третий байт - байт
счета ( в нашем случае это будет 40 ). Как Вы сами можете видеть, достаточно
чтобы любой раз, когда мы имеем последовательность  из  более 3-х одинаковых
символов, заменять их выше  описанной  последовательностью , чтобы на выходе
получить блок информации меньший по размеру, но  допускающий  восстановление
информации в исходном виде.
      Оставляя все сказанное выше истинным , добавлю  лишь то, что в  данном
методе основной проблемой является выбор того самого байта "флажка", так как
в реальных  блоках  информации  как  правило  используются все 256 вариантов
байта и нет возможности иметь 257 вариант - "флажок". а  первый  взгляд эта
проблема кажется неразрешимой , но к  ней  есть ключик , который  Вы найдете
прочитав о кодировании с помощью алгоритма Хаффмана ( Huffman ).


 LZW   -   История  этого алгоритма начинается с опубликования в мае 1977 г.
           Дж. Зивом ( J. Ziv ) и А. Лемпелем ( A. Lempel ) статьи в журнале
" Информационные теории " под названием " IEEE  Trans ". В  последствии этот
алгоритм  был доработан Терри А. Велчем ( Terry A. Welch ) и в окончательном
варианте отражен в статье " IEEE Compute " в июне 1984 . В этой статье  опи-
сывались  подробности алгоритма и некоторые  общие проблемы с которыми можно
столкнуться при его реализации. Позже этот алгоритм  получил  название - LZW
( Lempel - Ziv - Welch ) .
    Алгоритм LZW представляет собой алгоритм кодирования последовательностей
неодинаковых символов. Возьмем для примера строку " Объект TSortedCollection
порожден от TCollection.".  Анализируя эту строку мы можем видеть, что слово
"Collection"  повторяется  дважды. В этом слове 10 символов - 80 бит. И если
мы сможем заменить это слово  в  выходном файле, во втором его включении, на
ссылку на первое включение, то получим сжатие информации. Если рассматривать
входной блок информации размером не более 64К и ограничится длинной кодируе-
мой строки в 256 символов, то учитывая байт "флаг" получим, что строка из 80
бит заменяется  8+16+8 = 32 бита. Алгоритм LZW как-бы "обучается" в процессе
сжатия файла. Если  существуют  повторяющиеся  строки в файле , то они будут
закодированны в таблицу. Очевидным  преимуществом алгоритма является то, что
нет  необходимости  включать  таблицу кодировки в сжатый файл. Другой важной
особенностью является то, что сжатие по алгоритму LZW является однопроходной
операцией  в  противоположность  алгоритму  Хаффмана ( Huffman ) ,  которому
требуется два прохода.


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