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

для контекста 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) и т.д. Схема преобразования отражена в таблице ниже.