Программирование - об архивировании - алгоритмы, производящие сжатие без потерь.

__________________________________________

(C) N.B.
__________________________________________

       Немного относительно методов
             упаковки данных.

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

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

 LZW  -  История этого алгоритма начинает-
         ся с опубликования  в мае 1977 г.
Дж. Зивом (J. Ziv) и  А. Лемпелем (A. Lem-
pel) статьи в журнале "Информационные тео-
рии" под названием "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 символов, то для  нас не
будет  разницы  в  сжатии  текстового  или
другого файла.
   После подсчета частоты  вхождения  каж-
дого символа, необходимо просмотреть  таб-
лицу  кодов 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, т.к. сле-
дующий бит может быть как началом  следую-
щего кода, так и продолжением предыдущего.
   Необходимо добавить, что ключем к пост-
роению префиксных кодов служит обычное би-
нарное дерево, и,если внимательно рассмот-
реть предыдущий пример с построением дере-
ва, можно убедиться,что все получаемые ко-
ды там префиксные.
   И последнее примечание - алгоритм  Хаф-
фмана требует читать входной файл  дважды,
один раз считая частоты вхождения символов
и другой  раз, производя, непосредственно,
кодирование.

P.S. О "ключике", дающем  дорогу алгоритму
     Running. Прочитав обзорную информацию
     о Huffman-кодировании, подумайте  над
     тем, что на нашем бинарном дереве мо-
     жет быть и 257 листиков.
------------------------------------------