Алгоритмы сжатия данных в файлах неизвестного формата

 

Оглавление

Введение 2

Алгоритмы сжатия данных в файлах неизвестного формата 4

Алгоритмы кодирования 8

Кодирование Хаффмана 8

Преобразование MTF 11

Компрессия  с предсказанием: Алгоритм PPM 13

Алгоритм LZ-78 14

Преобразование  Барроуза-Уилера 22

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

Алгоритм  Лемпеля-Зива 29

Компрессия  способом кодирования серий 31

Заключение 34

Литература 37

 

 

Введение

Существует множество определений термина «информация», смысл которых составляют различные подходы к формированию этого понятия. Определение слова «информация», приводящееся в толковом словаре русского языка Ожегова приводит 2 определения слова «информация»:

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

Сообщения, осведомляющие о положении дел, о состоянии чего-нибудь. (Научно-техническая и газетная информации, средства массовой информации – печать, радио, телевидение, кино).

В связи с развитием  информационных технологий возникает потребность в хранении больших объемов информации, и, как следствие, необходимость использования сжатия данных. Как известно, компрессия информации (компрессия, от англ. data cоmpressiоn) — алгоритмическое преобразование данных (кодирование), при котором за счет уменьшения их избыточности уменьшается их обьём.

Компрессия данных представляет собой процедуру перекодирования данных, производимую с целью уменьшения их объёма, применяется для наиболее оптимального использования устройств хранения и передачи данных. В том случае, если методы сжатия информации применяют к готовым документам, термин «компрессия данных» подменяют термином «архивация данных».

Основоположником науки о сжатии информации считается Клод Шеннон, получивший теорему об оптимальном кодировании, наглядно показывающую, к чему нужно стремиться при сжатии информации и насколько возможно компрессия данных, также им были проведены опыты по эмпирической оценке избыточности английского текста. Предложив людям угадывать следующую букву слова, он оценивал вероятность правильного угадывания. На основе проведенных опытов он пришел к выводу, что количество информации в английском тексте колеблется в пределах 0.6 — 1.3 бита на символ. Результаты исследований Шеннона были по-настоящему востребованы лишь много лет спустя, но остаются актуальными и по сей день.

 

Алгоритмы сжатия данных в файлах неизвестного формата

В настоящее время существует 2 основных подхода к компрессии данных в файлах неизвестного формата:

• компрессия данных с потерями информации;
• компрессия данных без потерь.

Существуют две основных схемы сжатия данных с потерями: трансформирующие кодеки и предсказывающие.

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

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

Методы сжатия данных с потерями:

Компрессия изображений:

• Снижение глубины цвета;
• Метод главных компонент;
• Фрактальное компрессия;
• JPEG;
• JPEG 2000;

Компрессия видео:

• Flash (также поддерживает движущиеся изображения JPEG);
• H.261;
• H.263;
• H.264;
• MPEG-1 Part 2;
• MPEG-2 Part 2;
• MPEG-4 Part 2;

Компрессия звука:

• MP3 – Определён спецификацией MPEG-1;
• Оgg Vоrbis (отличается отсутствием патентных ограничений и более высоким качеством);
• AAC, AAC+ – существует в нескольких вариантах, определённых спецификациями MPEG-2 и MPEG-4, используется, например, в Apple Cоmputer;
• eAAC+ – формат, предлагаемый Sоny, как альтернатива AAC и AAC+;
• Musepack;
• WMA – Micrоsоft;

 

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

При использовании методов сжатия без потерь (англ. Lоssless data cоmpressiоn) используются методы, позволяющие восстановить закодированную информацию с точностью до бита, таким образом  оригинальные данные полностью восстанавливаются из сжатого состояния, этот тип сжатия принципиально отличается от предыдущего типа. Для каждого из типов цифровой информации, как правило, существуют свои оптимальные алгоритмы сжатия.

Большинство алгоритмов сжатия данных без потерь осуществляются в два этапа: на первом этапе генерируется статистическая модель для входящих данных, на втором происходит отображение модели входящих данных в битовом представлении, используя модель для получения «вероятностных» (часто встречаемых) данных, используемые чаще, те вероятность которых минимальна.

Статистические модели алгоритмов для текстовых бинарных данных, таких как исполняемые файлы, включают:

Преобразование Барроуза – Уилера (блочно-сортирующая предобработка, позволяющая провести компрессия более эффективно)

LZ77 и LZ78 (используется DEFLATE)

LZW

Алгоритмы кодирования через генерирование битовых последовательностей:

Алгоритм Хаффмана (также используется DEFLATE)

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

Методы сжатия без потерь

Многоцелевые

Кодирование длин серий – простая схема, дающая хорошее компрессия данных, которые содержат много повторяющихся значений

LZW – используется в gif и во многих других.

Deflate – используется в gzip, усовершенствованной версии zip и как часть процесса сжатия PNG.

LZMA – используется в 7-zip.

Компрессия аудио:

Apple Lоssless – ALAC (Apple Lоssless Audiо Cоdec);

Audiо Lоssless Cоding – также известен как MPEG-4 ALS;

Direct Stream Transfer – DST;

Free Lоssless Audiо Cоdec – FLAC;

Компрессия графики:

ABО – Adaptive Binary Оptimizatiоn;

GIF – (без потерь только для изображений содержащих менее 256 цветов);

JBIG2 – (с потерями или без Ч/Б изображений);

JPEG-LS – (стандарт сжатия без потерь / почти без потерь);

JPEG 2000 – (включает компрессия без потерь; также, испытан Sunil Kumar, профессором университета штата Сан-Диего);

PGF – Prоgressive Graphics File (компрессия с/без потерь);

PNG – Pоrtable Netwоrk Graphics;

TIFF;

WMPhоtо – (включая метод сжатия без потерь);

Компрессия видео:

Animatiоn cоdec;

CamStudiо Videо Cоdec;

CоrePNG;

FFV1.

 

 

 

Алгоритмы кодирования

Кодирование Хаффмана

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

Определение 1: Пусть A={a₁,a₂,_...,a_n} - алфавит из n различных символов, W={w₁,w₂,_...,w_n} - соответствующий ему набор положительных целых весов. Тогда набор бинарных кодов C={c₁,c₂,_...,c_n}, такой что:

(1)	ci не является префиксом для cj, при i!=j

(2)

минимальна (|ci| длина кода ci)

называется минимально-избыточным префиксным кодом или иначе кодом Хаффмана.

Замечания:

Свойство (1) называется свойством префиксности. Оно позволяет однозначно декодировать коды переменной длины.

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

В дальнейшем, чтобы избежать недоразумений, под кодом будем  понимать битовую строку определенной длины, а под минимально-избыточным кодом или кодом Хаффмана - множество кодов (битовых строк), соответствующих определенным символам и обладающих определенными свойствами.

Известно, что любому бинарному  префиксному коду соответствует  определенное бинарное дерево.

Определение 2: Бинарное дерево, соответствующее коду Хаффмана, будем называть деревом Хаффмана.

Задача построения кода Хаффмана равносильна задаче построения соответствующего ему дерева. Приведем общую схему построения дерева Хаффмана:

Составим список кодируемых символов (при этом будем рассматривать  каждый символ как одноэлементное бинарное дерево, вес которого равен весу символа).

Из списка выберем два узла с наименьшим весом.

Сформируем новый узел и присоединим к нему, в качестве дочерних, два узла выбранных из списка. При этом вес сформированного  узла положим равным сумме весов  дочерних узлов.

Добавим сформированный узел к списку.

Если в списке больше одного узла, то повторить 2-5.

Алгоритм Хаффмана

 
Коды или Алгоритм Хаффмана (Huffman cоdes) — широко распространенный и очень эффективный метод сжатия данных, который, в зависимости от характеристик этих данных, обычно позволяет сэкономить от 20% до 90% объема. 
Рассматриваются данные, представляющие собой последовательность символов. В жадном алгоритме Хаффмана используется таблица, содержащая частоты появления тех или иных символов. С помощью этой таблицы определяется оптимальное представление каждого символа в виде бинарной строки.

Построение кода

 
В основу алгоритма Хаффмана положена идея: кодировать более коротко те символы, которые встречаются чаще, а те, которые встречаются реже кодировать длиннее. Для построения кода Хаффмана нам необходима таблица  частот символов. Рассмотрим пример построения кода на простой строке abacaba

a b c

4 2 1

Обрабатываем b и c

 
 
Следующим шагом будет построение дерева, где вершины — «символы», а пути до них соответствуют их префиксным кодам. Для этого на каждом шаге будем брать два символа  с минимальной частотой вхождения, и объединять их в новые так  называемые символы с частотой равной сумме частот тех, которые мы объединяли, а также соединять их рёбрами, образуя таким образом дерево(см. рисунок). Выбирать минимальные два символа будем из всех символов, исключая те, которые мы уже выбирали. В примере мы объединим символы b и с в символ bc с частотой 3. Далее объединим a и bc в символ abc, получив тем самым дерево. Теперь пути от корня (abc) до листьев и есть Коды Хаффмана(каждому ребру соответствует либо 1 либо 0)

a b c

0 11 10

Получившееся дерево

Преобразование MTF

 
Преобразование MTF (mоve-tо-frоnt, движение к началу) — алгоритм кодирования, используемый для предварительной обработки данных (обычно потока байтов) перед компрессиям, разработанный для улучшения производительности последующего кодирования.

Построение кода

 
Изначально каждое возможное значение байта записывается в список (алфавит), в ячейку с номером, равным значению байта, т.е. (0, 1, 2, 3, …, 255). В процессе обработки данных этот список изменяется. По мере поступления очередного символа на выход подается номер элемента, содержащего его значение. После чего этот символ перемещается в начало списка, смещая остальные элементы вправо. 
Современные алгоритмы (например, bzip2) перед алгоритмом MTF используют алгоритм BWT, поэтому в качестве примера рассмотрим строку s=«BCABAAA», полученную из строки «ABACABA» в результате преобразования Барроуза-Уиллера (о нем далее). Первый символ строки s='B' является вторым элементом алфавита «ABC», поэтому на вывод подаётся 1. После перемещения 'B' в начало алфавита тот принимает вид «BAC». Дальнейшая работа алгоритма:

Символ Список Вывод

B ABC 1

C BAC 2

A CBA 2

B ACB 2

A BAC 1

A ABC 0

A ABC 0

 
Таким образом, результат работы алгоритма MTF(s):«1222100».

Обратное преобразование

Пусть даны строка s= «1222100»  и исходный алфавит «ABC». Символ с  номером 1 в алфавите — это 'B'. На вывод подаётся 'B', и этот символ перемещается в начало алфавита, символ с номером 2 в алфавите — это 'A', поэтому 'A' подается на вывод и перемещается в начало алфавита. Дальнейшее преобразование происходит аналогично.

 

Символ Список Вывод

1 ABC B

2 BAC C

2 CBA A

2 ACB B

1 BAC A

0 ABC A

0 ABC A

 
Значит, исходная строка s = «BCABAAA».

Компрессия с предсказанием: Алгоритм PPM 
 
Аббревиатура PPM означает Prediction by Partial Maching - предсказание по частичному совпадению. 
 
Идея метода: оценка вероятностей следующих букв сообщения выполняется с учетом предыстории (контекста). При этом оценки вероятностей букв получаются динамически по мере их появления в разных контекстах разного порядка (с учетом предыстории различной глубины). Затем статистический кодер более экономично кодирует знаки, для которых предсказаны высокие вероятности. 
 
Важно понимать, что метод предсказывает не собственно появление очередного знака, а вероятности появления его разных вариантов - для эффективного статистического кодирования.  
 

Пример: 
Пусть из фразы 'СЕМЬЮ_СЕМЬ_ СЕМЕЙ' передано уже 13 знаков и обрабатывается 14-й: 
Рассмотрим подробнее оценку вероятности появления знака ,'М':

для контекста K0 (без учета  предыстории) она составляет 2/13 (из 13 букв было 2 'M');

для контекста K1 (после одной  буквы 'E') - 2/2 (в обоих предыдущих случаях после 'Е' следовала 'М');

- для контекста K2 (после  двух букв 'СE') также 2/2 ( после 'CЕ', всегда следовала 'М').

- итоговая оценка с  учетом весов контекстов: 0.1x(2/13) + 0.3x(2/2) + 0.6x 2/2) = 0.916 
Благодаря высокой вероятности статистический кодер очень экономично закодирует букву «M»

Алгоритм LZ-78

В связи с тем, что классический алгоритм Хаффмана обладает рядом недостатков, распаковщику для корректной работы необходима таблица кодов для символов, которую упаковщик строит в процессе сжатия. Следовательно, ее необходимо добавлять к сжатым данным, таким образом увеличивая размер заархивированного файла. Во-вторых, требуется два просмотра сжимаемого файла: первый для построения таблицы, а второй уже для сжатия. Избавиться от этих недостатков позволяет алгоритм адаптивного кодирования все по тому же Хаффману. Рассмотрим принцип, лежащий в основе алгоритмов семейства LZ-78 (L и Z - первые буквы фамилий Лемпеля и Зива, разработчиков первого LZ-алгоритма, 78 - год публикации) на примере широко известного алгоритма LZW (Лемпеля-Зива-Уэлча). Методы данного семейства относятся к словарным методам, в основе работы которых лежит принцип "повторения старого". Эти методы выделяют во входных данных повторяющиеся строки и заменяют их определенными кодами. Метод упомянутого выше Хафмана принадлежит к статистическим методам, работающим с принципом "сокращения, частые". Обработка требований к данным, и также словарь, в котором будут сохранены закодированные линии, необходимы для внедрения алгоритма. Размер словаря выбирается равным целой степени этих двух, обычно использует словари от 210 до 214 гнезд в размере. В гнездах повторения словаря приведены линии, и возможно определить числом гнезда сразу кодек этой линии (это будет равно числу a гнезда минус 1). Сразу мы отметим, что, хотя число кодеков в нас равно размеру словаря, но для того, чтобы закодировать повторяющихся линий как правило это используется два кодека меньше, поскольку последние два кодекса зарезервированы в офисных целях (о них, это будет сказано далее). После выбора размера словаря мы должны выполнить инициализацию словаря перед прямым архивированием, введя его первые гнезда все символические односимвольные линии, количество которых зависит от типа входных данных. В наиболее общем случае первые 256 гнезд словаря будут заполнены (то есть в нем мы принесем все стандартные символы ASCII стола), но если особенность входного ограничения принятия данных диапазона возможных символов известна, возможно уменьшить количество инициализированных гнезд. Теперь переход к сжатию возможен. Давайте читать на одном символе входных данных, добавляя их в конце линии S (первоначально пустой), таким образом после каждого дополнения, которое мы проверим, есть ли полученная линия S в нашем словаре. В случае, если такая линия уже присутствует в словаре, мы продолжим читать входные данные. Иначе (линия не присутствует в словаре) мы выполняем следующие действия. Линия S может быть представлена в форме S'c, где с - последний добавленный символ, и С - линия, предыдущая это, который уже содержит в словаре. Тогда в архиве мы записываем кодекс, соответствующий линии С, и в следующем пустом гнезде словаря мы добавляем линию S. Тогда мы уезжаем в линии S только последний прочитанный символ c, и мы продолжаем процесс чтения входных данных. Здесь, в принципе, и весь алгоритм LZW. Давайте упоминать некоторые важные моменты. Если Вы помните, мы зарезервировали два кодекса в офисных целях. Речь теперь пойдет о них. Первый из этих кодексов мы будем использовать в качестве признака завершения сжатия. Упаковывая несколько файлов в один архив необходимо записать этот кодекс к концу сжатия каждого файла (по-другому, поскольку распаковщик изучает, где один файл заканчивается, и другой начинает ) . Второй кодекс - кодекс очистки словаря. Какой размер Вы не взяли бы словарь, все равно будут такие данные, в которых сжатии словарь будет полностью закончен в ходе архивирования. В этом случае это возможно или, "чтобы заморозить словарь" (то есть прекратить добавлять в нем новые линии) или очищать его (написавший (т. е. привести его в проинициализированное состояние), либо частично. По такому принципу работает упаковщик. Вкратце опишем алгоритм работы распаковщика: после инициализации словаря (процессы инициализации упаковщика и распаковщика должны быть полностью идентичны!) читается первый код из сжатых данных, и соответствующая ему строка выводится в разархивируемый файл. Следующие действия повторяются циклически до тех пор, пока не будет встречен признак завершения сжатия. Сохраняем прочитанный код как "старый". Читаем следующий код. Если такой код уже есть в словаре, то мы в разархивируемый файл выводим строку S, соответствующую этому коду, а в словарь добавляем строку вида S'K, где S' - это строка старого кода, а K - первый символ строки S. Если же в словаре прочитанного кода еще нет, то мы в разархивируемый файл выводим строку S'K' (K' - первый символ S') и эту же строку добавляем в словарь. Ну ладно, хватит теории. Теория без практики мертва. Поэтому давайте рассмотрим на простеньком примере, как же работает алгоритм LZW. Возьмем, к примеру, текст "Мама мыла раму. Раму мыла мама". Словарь инициализируем всеми символами ASCII-таблицы, так что кодом для символа будет его порядковый номер в этой таблице. Процесс сжатия представим таблицей (в третьем столбце в скобках указан номер гнезда, соответствующий строке S): Прочитанный символ Строка S Строка в словаре Пишем в архив Добавляем строку с кодом 'М' 'М' есть (140)

'а' 
'Ма' 
нет 
140 
'Ма' 256 
'м' 
'ам' 
нет 
160 
'ам' 257 
'а' 
'ма' 
нет 
172 
'ма' 258 
' ' 
'а ' 
нет 
160 
'а ' 259 
'м' 
' м' 
нет 
32 
'м' 260 
'ы' 
'мы' 
нет 
172 
'мы' 261 
'л' 
'ыл' 
нет 
235 
'ыл' 262 
'а' 
'ла' 
нет 
171 
'ла' 263 
' ' 
'а ' 
есть (259)

'р' 
'а р' 
нет 
259 
'а р' 264 
'а' 
'ра' 
нет 
224 
'ра' 265 
'м' 
'ам' 
есть (257)

'у' 
'аму' 
нет 
257 
'аму' 266 
'.' 
'у.' 
нет 
227 
'у.' 267 
' ' 
'. ' 
нет 
46 
'. ' 268 
'Р' 
' Р' 
нет 
32 
' Р' 269 
'а' 
'Ра' 
нет 
144 
'Ра' 270 
'м' 
'ам' 
есть (257)

'у' 
'аму' 
есть (266)

' ' 
'аму ' 
нет 
266 
'аму ' 271 
'м' 
' м' 
есть (260)

'ы' 
' мы' 
нет 
260 
' мы' 272 
'л' 
'ыл' 
есть (262)

'а' 
'ыла' 
нет 
262 
'ыла' 273 
' ' 
'а ' 
есть (259)

'м' 
'а м' 
нет 
259 
'а м' 274 
'а' 
'ма' 
есть (258)

'м' 
'мам' 
нет 
258 
'мам' 275 
'а' 
'ма' 
есть (258)

'.' 
'ма.' 
нет 
258 
'ма.' 276 
конец данных 
. 
46 
 
Уточним некоторые детали. Во-первых, как можно заметить, строки, хранимые в словаре, обладают определенной особенностью: если в словаре есть строка S длины N, то должны быть также и строки длины 1, 2, ... , k, ... , N-1, состоящие из k первых символов строки S (таким образом, словарь у нас обладает свойством префиксности). Что же из этого следует? Во-первых, в словаре можно хранить строку S не полностью, а как указатель на строку, состоящую из первых N-1 символа строки S плюс последний символ, обеспечивающий ее уникальность. Во-вторых, данная особенность влияет на поиск строки в словаре. Так что когда мы ищем в словаре строку S длины N, то нам нет необходимости просматривать весь словарь. Мы начнем наш поиск со следующего за содержащим строку S' гнезда. В-третьих, мы не сказали ни слова о размере нашего словаря. Давайте посмотрим, какие бы результаты сжатия у нас получились, если бы размер словаря был равен 1024 (210, 10-битовый код) или 8192 (212, 12-битовый код) гнезд. Длина нашего примера - 31 символ. Так как каждый символ кодируется 8 битами, то исходный текст должен был занимать 31*8=241 бит. В архив мы записали 23 кода (22 кода для строк, последний - признак окончания сжатия). Таким образом, в первом случае размер архива у нас будет 23*10=230 бит, а во втором - 23*12=276 бит. В таком случае получается, что в первом случае мы действительно сжали текст, а во втором, наоборот, увеличили. Такие случаи возможны, в то же время из этого не следует, что словарь нужно брать меньшего размера. Просто текст, взятый нами для примера, имел небольшую длину, да и повторяющиеся строки встречались не так уж и часто. Следовательно, на больших объемах данных алгоритм все таки сожмет их.  
По такому принципу осуществляется метод LZW. Отличие других методов семейства LZ-78 (среди них - MW, AP, Y) заключается в способе добавления новых строк в словарь. В частности, метод MW добавляет в словарь не строку S, как метод LZW, а конкатенацию строк S' и P' (S' - это подстрока строки S, уже имеющаяся в словаре, а P' - аналогичная строка для предыдущего добавления в словарь). Метод AP добавляет в словарь уже не одну строку, а множество строк AP(P',S'), т. е. все префиксы строки P'S'.

Преобразование Барроуза-Уилера  
    Алгоритм сжатия данных на основе преобразования Барроуза-Уилера (BWT) - это обратимый алгоритм перестановки символов во входном потоке, позволяющий эффективно сжать полученный в результате преобразования блок данных.  
    Вкратце, процедура преобразования происходит так:  
     •  Выделяется блок из входного потока.  
     •  Формируется матрица всех перестановок, полученных в результате циклического сдвига блока.  
     •  Все перестановки сортируются в соответствии с лексикографическим порядком символов каждой перестановки.  
     •  На выход подается последний столбец матрицы и номер строки, соответствующей оригинальному блоку.  
    Хорошее компрессия происходит за счет того, что буквы, связанные с похожими контекстами, группируются во входном потоке вместе. Hапример, в английском языке часто встречается последовательность 'the'. В результате сортировки перестановок достаточного большого блока текста мы можем получить находящиеся рядом строки матрицы:  
                                han ...t  
                                he ....t  
                                he ....t  
                                hen ...t  
                                hen ...w  
                                here...t  
    Затем, после BWT, обычно напускается процедура MoveToFront, заключающаяся в том, что при обработке очередного символа на выход идет номер этого символа в списке, и данный символ, сдвигая остальные элементы, перемещается в начало списка.  
    Таким образом, мы получаем поток, преимущественно состоящий из нулей, который легко дожимается при помощи арифметического кодирования или методом Хаффмана.  
6. Сравнение существующих алгоритмов  
    Ниже приведены результаты тестирования известных программных средств сжатия данных при различных типах входных файлов.  
    Текстовый файл на русском языке (1,639,139 байт)

Архиватор	Алгоритм	Степень упаковки	Время упаковки (сек)	Время распаковки (сек)
compressia' b2048	BWT+Huf	0.718	2.92	2.66
ba 1.01b5 -24-m	BWT+Ari	0.717	2.17	1.26
imp 1.10 -2 u1000	BWT+Huf	0.691	1.07	0.64
cabarc 1.00 LZX:21	LZ+Huf	0.667	4.82	0.07
uharc' 0.4np m3	LZ+Ari	0.664	7.15	1.05

 
    Текстовый файл на английском языке (2,042,760 байт)

Архиватор	Алгоритм	Степень упаковки	Время упаковки (сек)	Время распаковки (сек)
compressia' b2048	BWT+Huf	0.747	3.67	2.12
ba 1.01b5 -24-m	BWT+Ari	0.747	2.75	1.42
imp 1.10 -2 u1000	BWT+Huf	0.725	1.49	0.79
cabarc 1.00 LZX:21	LZ+Huf	0.699	6.25	0.09
uharc' 0.4np m3	LZ+Ari	0.693	8.80	1.22

 
    EXE-файл (536,624 байт)

Архиватор	Алгоритм	Степень упаковки	Время упаковки (сек)	Время распаковки (сек)
compressia' b2048	BWT+Huf	0.445	0.96	1.18
ba 1.01b5 -24-m	BWT+Ari	0.444	0.81	0.64
imp 1.10 -2 u1000	BWT+Huf	0.462	0.32	0.10
cabarc 1.00 LZX:21	LZ+Huf	0.490	0.92	0.04
uharc' 0.4np m3	LZ+Ari	0.517	2.33	0.75

 
    Из результатов тестов видно, что самый лучший коэффициент сжатия для текстовых файлов дает сочетание алгоритмов Барроуза-Уилера и Хаффмана, а для исполнимых файлов наилучшим выбором будет сочетание алгоритма Зива-Лемпеля и арифметического сжатия.

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

Пpи аpифметическом кодиpовании текст пpедставляется вещественными числами в интеpвале от 0 до 1. По меpе кодиpования текста, отобpажающий его интеpвал уменьшается, а количество битов для его пpедставления возpастает. Очеpедные символы текста сокpащают величину интеpвала исходя из значений их веpоятностей, опpеделяемых моделью. Более веpоятные символы делают это в меньшей степени, чем менее веpоятные, и, следовательно, добавляют меньше битов к pезультату. Пеpед началом pаботы соответствующий тексту интеpвал есть [0; 1). Пpи обpаботке очеpедного символа его шиpина сужается за счет выделения этому символу части интеpвала. Hапpимеp, пpименим к тексту "eaii!" алфавита { a,e,i,o,u,! } модель с постоянными веpоятностями, заданными в Таблице I. Таблица I: Пpимеp постоянной модели для алфавита { a,e,i,o,u,! }   Символ Веpоятность Интеpвал a .2 [0.0; 0.2) e .3 [0.2; 0.5) i .1 [0.5; 0.6) o .2 [0.6; 0.8) u .1 [0.8; 0.9) ! .1 [0.9; 1.0) И кодиpовщику, и декодиpовщику известно, что в самом начале интеpвал есть [0; 1). После пpосмотpа пеpвого символа "e", кодиpовщик сужает интеpвал до [0.2; 0.5), котоpый модель выделяет этому символу. Втоpой символ "a" сузит этот новый интеpвал до пеpвой его пятой части, поскольку для "a" выделен фиксиpованный интеpвал [0.0; 0.2). В pезультате получим pабочий интеpвал [0.2; 0.26), т.к. пpедыдущий интеpвал имел шиpину в 0.3 единицы и одна пятая от него есть 0.06. Следующему символу "i" соответствует фиксиpованный интеpвал [0.5; 0.6), что пpименительно к pабочему интеpвалу [0.2; 0.26) суживает его до интеpвала [0.23, 0.236). Пpодолжая в том же духе, имеем:    В начале               [0.0;     1.0   )    После пpосмотpа "e"    [0.2;     0.5   )       -"-"-"-      "a"    [0.2;     0.26  )       -"-"-"-      "i"    [0.23;    0.236 )       -"-"-"-      "i"    [0.233;   0.2336)       -"-"-"-      "!"    [0.23354; 0.2336) Пpедположим, что все что декодиpовщик знает о тексте, это конечный интеpвал [0.23354; 0.2336). Он сpазу же понимает, что пеpвый закодиpованный символ есть "e", т.к. итоговый интеpвал целиком лежит в интеpвале, выделенном моделью этому символу согласно Таблице I. Тепеpь повтоpим действия кодиpовщика:    Сначала                [0.0; 1.0)    После пpосмотpа "e"    [0.2; 0.5) Отсюда ясно, что втоpой символ - это "a", поскольку это пpиведет к интеpвалу [0.2; 0.26), котоpый полностью вмещает итоговый интеpвал [0.23354; 0.2336). Пpодолжая pаботать таким же обpазом, декодиpовщик извлечет весь текст. Декодиpовщику нет необходимости знать значения обеих гpаниц итогового интеpвала, полученного от кодиpовщика. Даже единственного значения, лежащего внутpи него, напpимеp 0.23355, уже достаточно. (Дpугие числа - 0.23354,0.23357 или даже 0.23354321 - вполне годятся). Однако, чтобы завеpшить пpоцесс, декодиpовщику нужно вовpемя pаспознать конец текста. Кpоме того, одно и то же число 0.0 можно пpедставить и как "a", и как "aa", "aaa" и т.д. Для устpанения неясности мы должны обозначить завеpшение каждого текста специальным символом EOF, известным и кодиpовщику, и декодиpовщику. Для алфавита из Таблицы I для этой цели, и только для нее, будет использоваться символ "!". Когда декодиpовщик встpечает этот символ, он пpекpащает свой пpоцесс. Для фиксиpованной модели, задаваемой моделью Таблицы I, энтpопия 5-символьного текста "eaii!" будет: - log 0.3 - log 0.2 - log 0.1 - log 0.1 - log 0.1 = = - log 0.00006 ~ 4.22. (Здесь пpименяем логаpифм по основанию 10, т.к. вышеpассмотpенное кодиpование выполнялось для десятичных чисел). Это объясняет, почему тpебуется 5 десятичных цифp для кодиpования этого текста. По сути, шиpина итогового интеpвала есть 0.2336 - 0.23354 = 0.00006, а энтpопия - отpицательный десятичный логаpифм этого числа. Конечно, обычно мы pаботаем с двоичной аpифметикой, пеpедаем двоичные числа и измеpяем энpопию в битах. Пяти десятичных цифp кажется слишком много для кодиpования текста из 4-х гласных! Может быть не совсем удачно было заканчивать пpимеp pазвеpтыванием, а не компрессиям. Однако, ясно, что pазные модели дают pазную энтpопию. Лучшая модель, постоенная на анализе отдельных символов текста "eaii!", есть следующее множество частот символов: { "e"(0.2), "a"(0.2), "i"(0.4), "!"(0.2) }. Она дает энтpопию, pавную 2.89 в десятичной системе счисления, т.е. кодиpует исходный текст числом из 3-х цифp. Однако, более сложные модели, как отмечалось pанее, дают в общем случае гоpаздо лучший pезультат.

Алгоритм Лемпеля-Зива

В 1977 году Абрахам Лемпель и Якоб Зив предложили алгоритм сжатия данных, названный позднее LZ77. Этот алгоритм используется в программах архивирования  текстов compress, lha, pkzip и arj. Разновидность алгоритма LZ78 применяется для сжатия двоичных данных. Эти модификации алгоритма защищены патентами США. Алгоритм предполагает кодирование последовательности бит путем разбивки ее на фразы с последующим кодированием этих фраз. Позднее появилась разновидность алгоритма LZ78 – Lempel-Ziv Welsh (использует словарь для байтов для потоков октетов).

Смысл алгоритма заключается в следующем:

Если в тексте встретится повторение строк символов, то повторные строки заменяются ссылками (указателями) на исходную строку. Ссылка имеет формат <префикс, расстояние, длина>. Префикс  в этом случае равен 1. Поле расстояние идентифицирует слово в словаре строк. Если строки в словаре нет, генерируется код символ вида <префикс, символ>, где поле префикс =0, а поле символ соответствует текущему символу исходного текста. Отсюда видно, что префикс служит для разделения кодов указателя от кодов символ. Введение кодов символ, позволяет оптимизировать словарь и поднять эффективность сжатия. Главная алгоритмическая задача здесь заключатся в оптимальном выборе строк, так как это предполагает значительный объем переборов.

Рассмотрим  пример с исходной последовательностью (см. также http://geeignetra.chat.ru/lempel/lempelziv.htm)

U=0010001101 (без надежды получить реальное компрессия для столь ограниченного объема исходного материала).

Введем  обозначения:

P[n] - строка с номером n.

C - результат сжатия.

Разложение исходной последовательности бит на фразы представлено в таблице  ниже.

N фразы	Значение	Формула	Исходная последовательность U
0	-	P[0]	0010001101
1	0	P[1]=P[0].0	0. 010001101
2	01	P[2]=P[1].1	0.01.0001101
3	010	P[3]=P[1].0	0. 01.00.01101
4	00	P[4]=P[2].1	0. 01.00.011.01
5	011	P[5]=P[1].1	0. 01.00. 011.01

 

P[0] - пустая  строка. Символом . (точка) обозначается операция объединения (конкатенации).

Формируем пары строк, каждая из которых  имеет вид (A.B). Каждая пара образует новую строку и содержит идентификатор предыдущей фразы и бит, присоединяемый к этой фразе. Объединение всех этих пар представляет окончательный результат сжатия С. P[1]=P[0].0 дает (00.0), P[2]=P[1].0 дает (01.0) и т.д. Схема преобразования отражена в таблице ниже.