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

 

Оглавление

Введение 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-й: 
Рассмотрим подробнее оценку вероятности появления знака ,'М':