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

Материал из DRKB


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


Running[править | править код]

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

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


LZW[править | править код]

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

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

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


P.S. О "ключике" дающем дорогу алгоритму Running.

Прочитав обзорную информацию о Huffman кодировании подумайте над тем, что на нашем бинарном дереве может быть и 257 листиков.

Литература:

1) Описание архиватора Narc фирмы Infinity Design Concepts, Inc.;
2) Чарльз Сейтер, 'Сжатие данных', "Мир ПК", N2 1991;


Source: http://delphiclub.ru
ID: 04178

См. также[править | править код]