Архивация и сжатие файлов

Можно сделать следующий шаг, повышающий степень сжатия, если объединить префикс и длину в одном байте. Пусть префикс-число F0...FF, где вторая цифра определяет длину length от 0 до 15. В этом случае выходной код будет двухбайтным, но мы сужаем диапазон представления длины с 255 до 15 символов и еще более ограничиваем себя в выборе префикса. Выходной же текст для нашего примера будет иметь вид:

F6 05 F2 01 F6 03 05 03 F4 FF

Длина-10 байт, степень сжатия-50%.

Далее, так как последовательность длиной от 0 до 3 мы условились не кодировать, код length удобно использовать со смещением на три, то есть 00=3, 0F=18, FF=258, упаковывая за один раз более длинные цепочки.

Если одиночные символы встречаются достаточно редко, хорошей может оказаться модификация алгоритма RLE вообще без префикса, только <length,symbol>. В этом случае одиночные символы также обязательно должны кодироваться в префиксном виде, чтобы декодировщик мог различить их в выходном потоке:

06 05 02 01 06 03 01 05 01 03 04 FF

Длина-12 байт, степень сжатия-60%.

Возможен вариант алгоритма, когда вместо длины length кодируется позиция относительно начала текста distance первого символа, отличающегося от предыдущего. Для нашего примера это будет выходная строка вида:

01 05 07 01 09 03 0F 05 10 03 11 FF

Таблица 1

Вывод по алгоритму RLE

 

Алгоритм	Степень сжатия	Скорость	Память	Сжатие без потерь	Проходы	РО	ВИ
RLE	2-3	10	10	Да	1	Нет	Возм.

 

Здесь и далее приняты следующие обозначения: РО - распространение ошибки, ВИ - возрастание избыточности. Степень сжатия, скорость и используемая оперативная память оцениваются по десятибалльной системе с точки зрения автора. Чем больше величина, тем лучше указанный параметр (выше скорость работы, выше степень сжатия и меньшая потребляемая память).

Работа: в реальном масштабе времени и в потоке.

Основное применение: РСХ, сжатие изображений.

 

Коды Хаффмана.

Наиболее эффективным кодом переменной длины, в котором ни одно слово не совпадает с началом другого (т.е. префиксный код) является код Хаффмана.

Пусть l1,...,lk-положительные целые числа (k>0). Для того, чтобы существовал префиксный код, длины слов которого равны l1,...,lk, необходимо и достаточно выполнение неравенства Крафта :

 

 

Все префиксные коды являются кодами со свойством однозначного декодирования, но не наоборот (например, однозначно декодируемый код 0, 01, 011, 0111, ... не является префиксным). Избыточность дешифрируемого кодирования неотрицательна. Для кода Хаффмана (Шеннона) избыточность не превышает 1, т.е. 0 £ R £ 1. Длина кода Шеннона равна

|ai| = é-log(p(ai))ù,

 

а длина кода Хаффмана не превышает величины |ai|.

Отсюда, в частности следует вывод, что чем больше длина Т символов входного алфавита (для которого строится код Хаффмана), тем меньше избыточность выходного текста и тем выше степень сжатия. Однако, как будет видно в дальнейшем, при этом значительно возрастают требования к памяти данных и к быстродействию программы, поскольку количество кодов равно количеству символов исходных букв. Избыточность кода Хаффмана в значительной мере зависит, как следует из приведенной формулы, от того, на сколько вероятности появления символов близки к отрицательным степеням числа 2. Для двухсимвольного алфавита, например, код Хаффмана никогда не сможет дать сокращения избыточности, пусть даже вероятности различаются на несколько порядков.

Рассмотрим построение кода Хаффмана на простом примере:

пусть есть текст ABACCADAА. При кодировке двоичным кодом постоянной длины вида:

 

A - 00, B - 01, C - 10, D - 11

 

мы получим сообщение 000100101000110000 длиной 18 бит. Теперь построим код Хаффмана, используя дерево Хаффмана.

Для этого первоначально требуется просмотреть весь исходный текст и получить вероятность (или, что проще - частоту) каждого входящего в него символа. Далее, возьмем два самых редких кода и объединим их в единый узел, частота появления которого равна сумме частот появления входящих в него символов. Рассматривая этот узел, как новый символ, объединяющий два предыдущих, будем повторять операцию слияния символов до тех пор, пока не останется ни одной буквы из входного алфавита. Получим дерево, где листьями являются символы входного алфавита, а узлами - соединение символов из листов-потомков данного узла. Рассматривая каждую левую ветвь как 0, а правую как 1 и спускаясь по дереву вниз до листьев, получим код любого символа:

 

A - 0, B - 110, C - 10, D - 111

 

Исходное сообщение после кодирования станет 011001010011100 (15 бит). Степень сжатия: 15/18 = 83%. Легко убедиться, что имея коды Хаффмана, можно однозначно восстановить первоначальный текст

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

Недостатком такого кодирования является тот факт, что вместе с закодированным сообщением необходимо передавать также и построенную таблицу кодов (дерево), что снижает величину сжатия. Однако существует динамический алгоритм построения дерева Хаффмана , при котором кодовая таблица обновляется самим кодировщиком и (синхронно и аналогично) декодировщиком в процессе работы после получения каждого очередного символа. Получаемые при этом коды оказываются квазиоптимальными, поэтому текст сжимается несколько хуже. Более того, возрастают сложность алгоритма и время работы программы (хотя она и становится однопроходной), поэтому, в настоящее время динамический алгоритм почти полностью уступил место статическому.

Следующим вариантом рассматриваемого алгоритма является фиксированный алгоритм Хаффмена, сочетающий в себе достоинства двух предыдущих - высокую скорость работы, простоту и отсутствие дополнительного словаря, создающего излишнюю избыточность. Идея его в том, чтобы пользоваться некоторым усредненным по многим текстам деревом, одинаковым для кодировщика и декодировщика. Такое дерево не надо строить и передавать вместе с текстом, а значит-отпадает необходимость первого прохода. Но, с другой стороны, усредненное фиксированное дерево оказывается еще более неоптимальным, чем динамическое. Поэтому, иногда может быть удобно иметь несколько фиксированных деревьев для разных видов информации.

Вариантами дерева Хаффмана следует также считать деревья, полученные для монотонных источников. Эти источники имеют два важных для наших целей свойства:нет необходимости вычислять частоты появления символов входного текста - как следствие, однопроходный алгоритм;дерево Хаффмана для таких источников может быть представлено в виде вектора из нескольких байтов, каждый из которых обозначает количество кодов дерева определенной длины, например: запись 1,1,0,2,4 говорит о том, что в дереве имеется по одному коду длин 1 и 2 бита, 0 кодов длиной 3 бита, 2 кода длиной 4 бита и 4 кода длиной 5 бит. Сумма всех чисел в записи даст количество символов в алфавите.

Основное применение: универсальный, сжатие текстов и бинарной информации. Динамический алгоритм построения кода Хаффмана используется в архиваторе ICE, статический - в LHA, ARJ. Статический алгоритм Шеннона-Фано используется архиватором PKZIP. Применяется для сжатия изображений (формат JPEG).

алгоритм архивация код

Метод «стопки книг» (MTF).

Сравнительно недавно появилась еще одна разновидность адаптивного алгоритма Хаффмана, описанная Рябко, а затем Бентли и названная, соответственно, алгоритмом стопки книг или “двигай вверх” (“MTF-MoveToFront”). Каждому символу (букве) присваивается код в зависимости от его положения в алфавите - чем ближе символ к началу алфавита - тем короче код (в качестве кода можно использовать, например, код дерева для монотонных источников). После кодирования очередного символа мы помещаем его в начало алфавита, сдвигая все остальные буквы на одну позицию вглубь. Через некоторое время наиболее часто встречаемые символы сгруппируются в начале, что и требуется для успешного кодирования. Работа алгоритма, действительно, напоминает перекладывание наиболее нужных книг из глубин библиотеки ближе к верху, вследствие чего потом их будет легче найти (аналогия с обыденной жизнью).

Таблица 2

Вывод по методу «стопки книг»

 

Алгоритм	Степень сжатия	Скорость	Память	Сжатие без потерь	Про-ходы	РО	ВИ
Стопка книг	3-5	7	8	Да	1	Да	Возм.

 

Арифметическое кодирование.

Арифметическое кодирование является методом, позволяющим упаковывать символы входного алфавита без потерь при условии, что известно распределение частот этих символов. Арифметическое кодирование является оптимальным, достигая теоретической границы степени сжатия H0. Однако, коды Хаффмана в предыдущем разделе мы тоже называли оптимальными. Как объяснить этот парадокс? Ответ заключается в следующем: коды Хаффмана являются неблочными, т.е каждой букве входного алфавита ставится в соответствие определенный выходной код. Арифметическое кодирование-блочное и выходной код является уникальным для каждого из возможных входных сообщений; его нельзя разбить на коды отдельных символов.

Текст, сжатый арифметическим кодером, рассматривается как некоторая двоичная дробь из интервала [0, 1). Результат сжатия можно представить как последовательность двоичных цифр из записи этой дроби. Каждый символ исходного текста представляется отрезком на числовой оси с длиной, равной вероятности его появления и началом, совпадающим с концом отрезка символа, предшествующего ему в алфавите. Сумма всех отрезков, очевидно должна равняться единице. Если рассматривать на каждом шаге текущий интервал как целое, то каждый вновь поступивший входной символ “вырезает” из него подинтервал пропорционально своей длине и положению.

Поясним работу метода на примере.

Пусть алфавит состоит из двух символов: “a” и “b” с вероятностями соответственно 3/4 и 1/4.

Рассмотрим (открытый справа) интервал [0, 1). Разобьем его на части, длина которых пропорциональна вероятностям символов. В нашем случае это [0, 3/4) и [3/4, 1).Суть алгоритма в следующем: каждому слову во входном алфавите соответствует некоторый подинтервал из [0, 1).Пустому слову соответствует весь интервал [0, 1). После получения каждого очередного символа арифметический кодер уменьшает интервал, выбирая ту его часть, которая соответствует вновь поступившему символу. Кодом сообщения является интервал, выделенный после обработки всех его символов, точнее, число минимальной длины, входящее в этот интервал. Длина полученного интервала пропорциональна вероятности появления кодируемого текста.

 

Рис. 1. Построение интервала для сообщения “АВГ...”.

 

Выполним алгоритм для цепочки “aaba”

Таблица 3

Построение арифметического кода

 

Просмотренная цепочка	Интервал
“”	[0, 1) = [0, 1)
“a”	[0, 3/4) = [0, 0.11)
“aa”	[0, 9/16) = [0, 0.1001)
“aab”	[27/64, 36/64) = [0.011011, 0.100100)
“aaba”	[108/256, 135/256) = [0.01101100, 0.10000111)

 

На первом шаге мы берем первые 3/4 интервала, соответствующие символу “а”, затем оставляем от него еще только 3/4. После третьего шага от предыдущего интервала останется его правая четверть в соответствии с положением и вероятностью символа ”b”. И, наконец, на четвертом шаге мы оставляем лишь первые 3/4 от результата. Это и есть интервал, которому принадлежит исходное сообщение.

В качестве кода можно взять любое число из диапазона, полученного на шаге 4. В качестве кода мы можем выбрать, например, самый короткий код из интервала, равный 0.1 и получить четырехкратное сокращение объема текста. Для сравнения, код Хаффмана не смог бы сжать подобное сообщение, однако, на практике выигрыш обычно невелик и предпочтение отдается более простому и быстрому алгоритму из предыдущего раздела.

Арифметический декодер работает синхронно с кодером: начав с интервала [0, 1), он последовательно определяет символы входной цепочки.В частности, в нашем случае он вначале разделит (пропорционально частотам символов) интервал [0, 1) на [0, 0.11) и [0.11, 1). Поскольку число 0.1 (переданный кодером код цепочки “aaba”) находится в первом из них, можно получить первый символ: “a”. Затем делим первый подинтервал [0, 0.11) на [0, 0.1001) и [0.1001, 0.1100) (пропорционально частотам символов). Опять выбираем первый, так как 0 < 0.1 < 0.1001. Продолжая этот процесс, мы однозначно декодируем все четыре символа.

При рассмотрении этого метода возникают две проблемы: во-первых, необходима вещественная арифметика, вообще говоря, неограниченной точности, и во-вторых, результат кодирования становится известен лишь при окончании входного потока. Дальнейшие исследования, однако, показали, что можно практически без потерь обойтись целочисленной арифметикой небольшой точности (16-32 разряда), а также добиться инкрементальной работы алгоритма: цифры кода могут выдаваться последовательно по мере чтения входного потока .