__________________________________________
(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 листиков.
------------------------------------------
Other articles:
