Еще 10-15 лет назад архиваторы использовались в основном для экономии места на жестких дисках и для того, чтобы уместить максимум данных на дискету. Однако времена изменились. Дискетами как средством переноса и хранения информации уже давно никто не пользуется, а стоимость накопителей стала настолько низкой, что никто даже не задумывается о сжатии данных с целью экономии места. Кроме того, объемы данных стали такими большими, что их архивация и разархивация с целью экономии места просто нецелесообразна, поскольку отнимает очень много времени. Ну действительно, сегодня объемы данных на накопителях пользователей измеряются терабайтами. А теперь представьте себе, сколько потребуется времени, чтобы заархивировать один терабайт данных. На это уйдет не один и даже не два часа, а как минимум часов 10-12, то есть компьютер придется оставить включенным на всю ночь.

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

Дело в том, что изменилось назначение архиваторов. Сегодня они используются преимущественно для выкладывания данных в Сеть. Большинство драйверов на сайтах производителей выкладываются именно в архивах, и большая часть программ на различных ресурсах также заархивированы. Кстати, и сам пользователь прежде чем выложить какиелибо данные в Сеть (например, на файлообменные ресурсы), запаковывает данные в архив.

Что касается российского рынка, то у нас наиболее распространенными являются три архиватора: WinRAR, WinZip и 7-Zip, представленные как в 32-, так и 64-битной версиях. Именно их мы и будем сравнивать в данной статье. Однако прежде кратко рассмотрим некоторые теоретические аспекты работы архиваторов.

Алгоритмы сжатия информации

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

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

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

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

Алгоритм RLE

Один из самых старых и самых простых методов сжатия информации - это алгоритм RLE (Run Length Encoding), то есть алгоритм кодирования серий последовательностей. Этот метод очень прост в реализации и представляет собой один из алгоритмов архивации, а суть его заключается в замене серии (группы) повторяющихся байтов на один кодирующий байт и счетчик числа их повторений. То есть группа одинаковых байтов заменятся на пару: <счетчик повторений, значение>, что сокращает избыточность данных.

В данном алгоритме признаком счетчика служат единицы в двух верхних битах считанного байта. К примеру, если первые два бита - это 11, то остальные 6 бит отводятся на счетчик, который может принимать значения от 1 до 64. Соответственно серию из 64 повторяющихся байтов можно определить всего двумя байтами, то есть сжать в 32 раза.

Есть и другой вариант реализации этого алгоритма, когда признаком счетчика является 1 в первом байте счетчика. В этом случае счетчик может принимать максимальное значение, равное 127, - а следовательно максимальная степень сжатия будет равна 64.

Понятно, что алгоритм RLE эффективен только тогда, когда имеется большое количество длинных групп одинаковых байтов. Если же байты не повторяются, то использование метода RLE приводит к увеличению объема файла.

Метод RLE, как правило, весьма эффективен для сжатия растровых графических изображений (BMP, PCX, TIF, GIF), поскольку они содержат очень много длинных серий повторяющихся последовательностей байтов.

Ограничение информационного алфавита

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

В дальнейшем под информационным алфавитом мы будем подразумевать набор символов, используемый для кодирования информационной последовательности. К примеру, пусть имеется некоторое текстовое сообщение. Для кодировки каждой буквы этого сообщения используется ASCII-таблица, состоящая из 256 символов. При этом под кодирование каждого символа отводится ровно 8 бит (1 байт). В данном случае информационный алфавит - это все 256 символов кодировочной ASCII-таблицы.

Понятно, что в исходном текстовом сообщении могут применяться не все 256 символов ASCII-таблицы. К примеру, если речь идет о текстовом сообщении на русском языке, в котором нет цифр, то достаточно 64 символов (33 строчные и 31 заглавная буквы). Если добавить к этому знаки препинания, знаки абзаца и перехода на новую строку, станет понятно, что число символов не превысит 100. В этом случае можно использовать не 8-, а 7-битное кодирование символов, что позволяет получить таблицу из 128 символов. То есть мы как бы ограничиваем информационный алфавит, за счет чего можно уменьшить разрядность каждого колируемого символа. Можно пойти дальше - точно определить количество применяемых символов в текстовом сообщении. Если, к примеру, выяснится, что в сообщении задействуются всего 30 символов (включая символы перехода на новую строку), то можно использовать 5-битную кодировочную таблицу, содержащую 32 символа, и тогда степень сжатия текстового сообщения станет еще большей. Действительно, если в исходном сообщении применяется 8-битное кодирование символов, а в сжатом - 5-битное, то коэффициент сжатия будет 8/5.

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

У метода ограниченного алфавита есть и другие недостатки. Если исходное информационное сообщение содержит большое количество разнообразных символов, то понизить разрядность представления символов алфавита не удастся и данный способ просто не сработает. Предположим, к примеру, что в исходном информационном сообщении содержится 129 символов из 256-символьного алфавита. Воспользоваться 7-битным кодированием символов в данном случае не удастся, поскольку 7 бит позволят закодировать только 128 символов. Поэтому для 129 символов придется обратиться к тому же 8-битному кодированию, как и в исходном 256-символьном алфавите.

Коды переменной длины

Одним из главных недостатков рассмотренного нами гипотетического метода ограничения алфавита является то, что в нем применяется равномерный код, когда все символы информационного алфавита имеют одинаковую длину (8, 7 бит или меньше). Было бы логичнее использовать такую систему кодирования, при которой длина кода символа зависит от частоты его появления в информационном сообщении. То есть, если в исходном информационном сообщении некоторые символы встречаются чаще других, то для них оптимально использовать короткие коды, а для редко встречающихся -более длинные.

В качестве гипотетического примера рассмотрим следующее информационное сообщение: «авиакатастрофа» , которое содержит 14 символов. Предположим, что у нас имеется алфавит из 14 символов, который позволяет нам закодировать это сообщение. Если используется равномерный код, то на каждый символ алфавита потребуется 4 бита (длина кода в 4 бита позволит сформировать 16 символов). Однако нетрудно заметить, что в нашем информационном сообщении символ «а» встречается пять раз, символ «т» - два раза, а остальные символы - по одному разу. Если для символа «а» мы будем использовать код длиной 2 бит, для символа «т» - длиной 3 бита, а для остальных символов - длиной 4 бита, то мы наверняка сможем сэкономить. Нужно лишь понять, как именно строить коды переменной длины и как именно длина кода должна зависеть от частоты появления символа в информационном сообщении.

Если все символы входят в информационное сообщение с одинаковой частотой (равновероятны), то при информационном алфавите из N символов для кодирования каждого символа потребуется ровно log 2 N бит. Фактически это случай равномерного кода.

Если же символы имеют разную вероятность появления в информационном сообщении, то, согласно теории К. Шеннона, символу, вероятность появления которого равна p, оптимально и, что особенно важно, теоретически допустимо ставить в соответствие код длиной –log 2 p . Возвращаясь к нашему примеру с информационным сообщением «авиакатастрофа» и учитывая, что вероятность появления символа «а» (p(a)) составляет 5/14, вероятность появления символа «т» - 2/14, а вероятность появления всех остальных символов - 1/14, мы получим, что: для символа «a» оптимальная длина кода равна –log 2 (5/14) = 1,48 бит; для символа «т» - –log 2 (2/14) = 2,8 бит, а для всех остальных символов она составляет –log 2 (1/14) = 3,8. Поскольку в нашем случае длина кода может иметь только целочисленное значение, то, округляя, получим, что для символа «а» оптимально использовать код длиной 2 бита, для символа «т» - длиной 3 бита, а для остальных - длиной 4 бита.

Давайте посчитаем степень сжатия при использовании такого кодирования. Если бы применялся равномерный код на базе 14-символьного алфавита, то для кодирования слова «авиакатастрофа» потребовалось бы 56 бит. При использовании кодов переменной длины потребуется 5×2 бита + 2×3 бита + 7×4 бита = 44 бита, то есть коэффициент сжатия составит 1,27.

Теперь рассмотрим алгоритмы получения кодов переменной длины.

Префиксное кодирование

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

Поясним это свойство префиксных кодов на конкретном примере. Пусть имеется система из трех префиксных кодов: {0, 10, 11}. Как видим, более короткий код 0 не совпадает с началом более длинных кодов 10 и 11. Пусть код 0 задает символ «а», код 10 - символ «м», а код 11 - символ «р». Тогда слово «рама» кодируется последовательностью 110100. Попробуем раскодировать эту последовательность. Поскольку первый бит - это 1, то первый символ может быть только «м» или «р» и определяется значением второго бита. Поскольку второй бит - это 1, то первый символ - это «р». Третий бит - это 0, и он однозначно соответствует символу «а». Четвертый бит - это 1, то есть нужно смотреть на значение следующего бита, который равен 0, тогда третий символ - это «м». Последний бит - это 0, что однозначно соответствует символу «а». Таким образом, свойство префиксных кодов, заключающееся в том, что более короткие по длине коды не могут совпадать с началом более длинных кодов, позволяет однозначно декодировать закодированное префиксными кодами переменной длины информационное сообщение.

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

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

Для рассмотренного примера системы из трех префиксных кодов: {0, 10, 11}, которые задают символы «а», «м» и «р», кодовое дерево показано на рис. 1.

Рис. 1. Кодовое дерево для системы
из трех префиксных кодов: {0, 10, 11}

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

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

Алгоритм Шеннона-Фано

Данный алгоритм получения префиксных кодов независимо друг от друга предложили Р. Фано и К. Шеннон, заключается он в следующем. На первом шаге все символы исходной информационной последовательности сортируются по убыванию или возрастанию вероятностей их появления (частоты их появления), после чего упорядоченный ряд символов в некотором месте делится на две части так, чтобы в каждой из них сумма частот символов была примерно одинакова. В качестве демонстрации рассмотрим уже знакомое нам слово «авиакатастрофа» .

Если символы, составляющие данное слово, отсортировать по убыванию частоты их появления, то получим следующую последовательность: {а(5), т(2), в(1), и(1), к(1), с(1), р(1), о(1), ф(1)} (в скобках указывается частота повторяемости символа в слове). Далее, нам нужно разделить эту последовательность на две части так, чтобы в каждой из них сумма частот символов была примерно одинаковой (насколько это возможно). Понятно, что раздел пройдет между символами «т» и «в», в результате чего образуется две последовательности: {а(5), т(2)} и {в(1), и(1), к(1), с(1), р(1), о(1), ф(1)}. Причем суммы частот повторяемости символов в первой и второй последовательностях будут одинаковы и равны 7.

На первом шаге деления последовательности символов мы получаем первую цифру кода каждого символа. Правило здесь простое: для тех символов, которые оказались в последовательности слева, код будет начинаться с «0», а для тех, что справа - с «1».

В частности, последовательность {а(5), т(2)} разделится на два отдельных символа: a(5) и т(2) (других вариантов деления нет). Тогда вторая цифра кода для символа «a» - это «0», а для символа «т» - «1». Поскольку в результате деления последовательности мы получили отдельные элементы, то они более не делятся и для символа «a» получаем код 00, а для символа «т» - код 01.

Последовательность {в(1), и(1), к(1), с(1), р(1), о(1), ф(1)} можно разделить либо на последовательности {в(1), и(1), к(1)} и {с(1), р(1), о(1), ф(1)}, либо на {в(1), и(1), к(1)}, {с(1)} и {р(1), о(1), ф(1)}.

В первом случае суммы частот повторяемости символов в первой и второй последовательностях будут 3 и 4 соответственно, а во втором случае - 4 и 3 соответственно. Для определенности воспользуемся первым вариантом.

Для символов полученной новой последовательности {в(1), и(1), к(1)} (это левая последовательность) первые две цифры кода будут 10, а для последовательности {с(1), р(1), о(1), ф(1)} - 11.

В нашем примере (рис. 2 и 3) получается следующая система префиксных кодов: «a» - 00, «т» - 01, «в» - 100, «и» - 1010, «к» - 1011, «с» - 1100, «р» - 1101, «о» - 1110, «ф» - 1111. Как нетрудно заметить, более короткие коды не являются началом более длинных кодов, то есть выполняется главное свойство префиксных кодов.

Рис. 2. Демонстрация алгоритма Шеннона-Фано

Рис. 3. Кодовое дерево для слова «авиакатастрофа»
в алгоритме Шеннона-Фано

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

Алгоритм Хаффмана - это еще один алгоритм получения префиксных кодов переменной длины. В отличие от алгоритма Шеннона-Фано, который предусматривает построение кодового дерева сверху вниз, данный алгоритм подразумевает построение кодового дерева в обратном порядке, то есть снизу вверх (от листовых узлов к корневому узлу).

На первом этапе, как и в алгоритме Шеннона-Фано, исходная последовательность символов сортируется в порядке убывания частоты повторяемости символов (элементов последовательности). Для рассмотренного ранее примера со словом «авиакатастрофа» получим следующую отсортированную последовательность элементов: {а(5), т(2), в(1), и(1), к(1), с(1), р(1), о(1), ф(1)}.

Далее два последних элемента последовательности заменяются на новый элемент S1, которому приписывается повторяемость, равная сумме повторяемостей исходных элементов. Затем производится новая сортировка элементов последовательности в соответствии с их повторяемостью. В нашем случае два последних элемента o(1) и ф(1) заменяются на элемент S1(2), а вновь отсортированная последовательность примет вид: {а(5), т(2), S1(2), в(1), и(1), к(1), с(1), р(1)}.

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

Рис. 4. Демонстрация алгоритма Хаффмана
на примере слова «авиакатастрофа»

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

Рис. 5. Построение кодового дерева
в алгоритме Хаффмана
(замещение элементов «o» и «ф»
новым элементом S1)

Полное кодовое дерево, построенное по алгоритму Хаффмана для слова «авиакатастрофа» , показано на рис. 6.

Рис. 6. Полное кодовое дерево для слова «авиакатастрофа»,
построенное по алгоритму Хаффмана

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

Если теперь попытаться написать слово «авиакатастрофа» в кодировке Хаффмана, то получим 41-битную последовательность 0 1101 11000 0 11001 0 111 0 1010 111 1011 1000 1001 0. Интересно отметить, что при использовании префиксных кодов Шеннона-Фано мы также получим 41-битную последовательность для слова «авиакатастрофа». То есть в конкретном примере эффективность кодирования Хаффмана и Шеннона-Фано одинакова. Но если учесть, что реальный информационный алфавит - это 256 символов (а не 14, как в нашем примере), а реальные информационные последовательности - это любые по своему содержанию и длине файлы, то возникает вопрос об оптимальном префиксном коде, то есть коде, который позволяет получить минимальную по длине выходную последовательность.

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

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

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

Как мы уже отмечали, согласно критерию Шеннона, оптимальным является такой код, в котором под каждый символ отводится код длиной –log 2 p бит. И если, к примеру, вероятность какого-то символа составляет 0,2, то оптимальная длина его кода будет равна –log 2 0,2 = 2,3 бит. Понятно, что префиксные коды не могут обеспечить такую длину кода, а потому не являются оптимальными. Вообще длина кода, определяемая критерием Шеннона, - это лишь теоритический предел. Вопрос лишь в том, какой способ кодирования позволяет максимально приблизиться к этому теоретическому пределу. Префиксные коды переменной длины эффективны и достаточно просты в реализации, однако существуют и более эффективные способы кодирования, в частности алгоритм арифметического кодирования.

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

Идея алгоритма арифметического кодирования заключается в следующем. Как и во всех рассмотренных ранее способах кодирования, каждый символ исходной информационной последовательности характеризуется его вероятностью. Исходной незакодированной последовательности ставится в соответствие полуинтервал i . Hah !»

Для пущей наглядности посмотрим на схему, где видны соответствия повторяемых последовательностей и их первых вхождений:

Пожалуй, единственным неясным моментом здесь будет последовательность «Hahahahaha!», ведь цепочке символов «ahahaha» соответствует короткая цепочка «ah». Но здесь нет ничего необычного, мы использовали кое-какой приём, позволяющий алгоритму иногда работать как описанный ранее RLE.

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

С этим разобрались. Теперь заменим найденные повторы на ссылки в словарь. Будем записывать ссылку в формате , где P - позиция первого вхождения цепочки в строке, L - её длина.

«The compression and t de leave i . Hah !»

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

«The compression and t de leave i . Hah !»

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

Пришло время определиться с размером окна и максимальной длиной кодируемой фразы. Поскольку мы имеем дело с текстом, редко когда в нём будут встречаться особо длинные повторяющиеся последовательности. Так что выделим под их длину, скажем, 4 бита - лимита на 15 символов за раз нам вполне хватит.

А вот от размера окна уже зависит, насколько глубоко мы будем искать одинаковые цепочки. Поскольку мы имеем дело с небольшими текстами, то в самый раз будет дополнить используемое нами количество бит до двух байт: будем адресовать ссылки в диапазоне из 4096 байт, используя для этого 12 бит.

По опыту с RLE мы знаем, что не всякие значения могут быть использованы. Очевидно, что ссылка может иметь минимальное значение 1, поэтому, чтобы адресовать назад в диапазоне 1..4096, мы должны при кодировании отнимать от ссылки единицу, а при декодировании прибавлять обратно. То же самое с длинами последовательностей: вместо 0..15 будем использовать диапазон 2..17, поскольку с нулевыми длинами мы не работаем, а отдельные символы последовательностями не являются.

Итак, представим наш закодированный текст с учётом этих поправок:

«The compression and t de leave i . Hah !»

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

Разделяем на группы:

«The comp»
«ression »
«and t de»
« leave »
«i . Hah »

Компонуем группы:

«{0,0,0,0,0,0,0,0} The comp{0,0,0,0,0,0,0,0} ression {0,0,0,0,0,1,0,0} and t de{1,0,0,0,0,0,1,0} leave {0,1,0,0,0,0,0,1} i . Hah {0} !»

Таким образом, если при распаковке мы встречаем бит 0, то мы просто читаем символ в выходной поток, если же бит 1, мы читаем ссылку, а по ссылке читаем последовательность из словаря.

Теперь нам остаётся только сгруппировать результат в массив байтов. Условимся, что мы используем биты и байты в порядке от старшего к младшему. Посмотрим, как пакуются в байты ссылки на примере :

В итоге наш сжатый поток будет выглядеть так:

0000: 00 54 68 65 20 63 6f 6d 70 00 72 65 73 73 69 6f #The comp#ressio
0010: 6e 20 04 61 6e 64 20 74 01 31 64 65 82 01 5a 6c n #and t##de###l
0020: 65 61 76 65 01 b1 20 41 69 02 97 2e 20 48 61 68 eave## #i##. Hah
0030: 00 15 00 21 00 00 00 00 00 00 00 00 00 00 00 00 ###!

Возможные улучшения

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

«The long goooooong. The loooooower bound.»

Найдём последовательности только для слова «loooooower»:

«The long goooooong. The wer bound.»

Для кодирования такого результата нам понадобится четыре байта на ссылки. Однако, более экономично было бы сделать так:

«The long goooooong. The l wer bound.»

Тогда мы потратили бы на один байт меньше.

Вместо заключения

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

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

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

Базовая классификация обратимых алгоритмов сжатия

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

Кодирование серий последовательностей (RLE);

Статистические методы сжатия;

Словарные (эвристические) методы сжатия.

Сжатие способом кодирования серий: алгоритм RLE

Наиболее известный простой подход и алгоритм сжатия информации обратимым путем - это кодирование серий последовательностей (Run Length Encoding - RLE). Суть методов данного подхода состоит в замене цепочек или серий повторяющихся байтов или их последовательностей на один кодирующий байт и счетчик числа их повторений . Проблема всех аналогичных методов заключается в определении способа, при помощи которого распаковывающий алгоритм мог бы отличить в результирующем потоке байтов кодированную серию от других - некодированных последовательностей байтов. Решение проблемы достигается обычно простановкой меток в начале кодированных цепочек. Такими метками могут быть, например, характерные значения битов в первом байте кодированной серии, значения первого байта кодированной серии и т.п. Данные методы, как правило, достаточно эффективны для сжатия растровых графических изображений (BMP, PCX, TIF, GIF), т.к. последние содержат достаточно много длинных серий повторяющихся последовательностей байтов. Недостатком метода RLE является достаточно низкая степень сжатия или стоимость кодирования файлов с малым числом серий и, что еще хуже - с малым числом повторяющихся байтов в сериях.

В основе алгоритма RLE лежит идея выявления повторяющихся последовательностей данных и замены их более простой структурой, в которой указывается код данных и коэффициент повторения. Например, пусть задана такая последовательность данных, что подлежит сжатию: 1 1 1 1 2 2 3 4 4 4 . В алгоритме RLE предлагается заменить ее следующей структурой: 1 4 2 2 3 1 4 3 , где первое число каждой пары чисел - это код данных, а второе - коэффициент повторения. Если для хранения каждого элемента данных входной последовательности отводится 1 байт, то вся последовательность будет занимать 10 байт памяти, тогда как выходная последовательность (сжатый вариант) будет занимать 8 байт памяти. Понятно, что алгоритм RLE будет давать лучший эффект сжатия при большей длине повторяющейся последовательности данных. В случае рассмотренного выше примера, если входная последовательность будет иметь такой вид: 1 1 1 1 1 1 3 4 4 4, то коэффициент сжатия будет равен 60%. В связи с этим большая эффективность алгоритма RLE достигается при сжатии графических данных (в особенности для однотонных изображений).

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

Статистические алгоритмы (Хаффмана, Шеннона-Фано, арифметические) Статистические алгоритмы используют статистическую модель данных, и качество сжатия информации напрямую зависит от того, насколько хороша эта модель. Учет статистических свойств данных в простейшем случае означает использование для кодирования неравномерных кодов – часто встречающиеся символы кодируются короткими кодами, а редко – длинными. Т.е., такие алгоритмы нуждаются в знании вероятностей появления символов в изображении, оценкой чего может являться в простом случае частота появления символов во входных данных. Как правило, эти вероятности неизвестны. Целью кодирования является преобразование входного потока в поток бит минимальной длины, что достигается уменьшением энтропии (хаотичности) входного потока путем учета частот символов.

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

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

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

С учетом этого статистические алгоритмы можно разделить на три класса:

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

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

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

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

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

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

Алгоритм RLE (Run Length Encoding, упаковка, кодирование длин серий), является самым быстрым, простым и понятным алгоритмом сжатия данных и при этом иногда оказывается весьма эффективным. Именно подобный алгоритм используется для сжатия изображений в файлах PCX .

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

Например: пусть имеется (шестнадцатиричный) текст из 20 байт:

05 05 05 05 05 05 01 01 03 03 03 03 03 03 05 03 FF FF FF FF

Выберем в качестве префикса байт FF. Тогда на выходе архиватора мы получим последовательность

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

Ее длина-18 байт, то есть достигнуто некоторое сжатие. Однако, нетрудно заметить, что при кодировании некоторых символов размер выходного кода возрастает (например, вместо 01 01 - FF 02 01). Очевидно, одиночные или дважды (трижды) повторяющиеся символы кодировать не имеет смысла - их надо записывать в явном виде. Получим новую последовательность:

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

длиной 13 байт. Достигнутая степень сжатия: 13/20*100 = 65%.

Нетрудно заметить, что префикс может совпасть с одним из входных символов. В этом случае входной символ может быть заменен своим “префиксным” представлением, например:

FF то же самое, что и FF 01 FF (три байта вместо одного).

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

Можно сделать следующий шаг, повышающий степень сжатия, если объединить префикс и длину в одном байте. Пусть префикс-число 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 вообще без префикса, только . В этом случае одиночные символы также обязательно должны кодироваться в префиксном виде, чтобы декодер мог различить их в выходном потоке:

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

Алгоритм RLE

Первый вариант алгоритма

Данный алгоритм необычайно прост в реализации. Групповое кодирование - от английского Run Length Encoding (RLE) - один из самых старых и самых простых алгоритмов архивации графики. Изображение в нем (как и в нескольких алгоритмах, описанных ниже) вытягивается в цепочку байт по строкам растра. Само сжатие в RLE происходит за счет того, что в исходном изображении встречаются цепочки одинаковых байт . Замена их на пары <счетчик повторений, значение> уменьшает избыточность данных.

Алгоритм декомпрессии при этом выглядит так:

Initialization(...);
do {
if(является счетчиком(byte)) {
counter = Low6bits(byte)+1;
for(i=1 to counter)
De
}
else {
DecompressedFile.WriteByte(byte)
} while(ImageFile.EOF());

В данном алгоритме признаком счетчика (counter) служат единицы в двух верхних битах считанного файла:

Соответственно оставшиеся 6 бит расходуются на счетчик, который может принимать значения от 1 до 64. Строку из 64 повторяющихся байтов мы превращаем в два байта, т.е. сожмем в 32 раза.

Упражнение: Составьте алгоритм компрессии для первого варианта алгоритма RLE.

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

Вопрос для самоконтроля: Предложите два-три примера “плохих” изображений для алгоритма RLE. Объясните, почему размер сжатого файла больше размера исходного файла.

Данный алгоритм реализован в формате PCX. См. пример в приложении.

Второй вариант алгоритма

Второй вариант этого алгоритма имеет больший максимальный коэффициент архивации и меньше увеличивает в размерах исходный файл.

Алгоритм декомпрессии для него выглядит так:

Initialization(...);
do {
byte = ImageFile.ReadNextByte();
counter = Low7bits(byte)+1;
if(если признак повтора(byte)) {
value = ImageFile.ReadNextByte();
for (i=1 to counter)
CompressedFile.WriteByte(value)
}
else {
for(i=1 to counter){
value = ImageFile.ReadNextByte();
CompressedFile.WriteByte(value)
}
CompressedFile.WriteByte(byte)
} while(ImageFile.EOF());

Признаком повтора в данном алгоритме является единица в старшем разряде соответствующего байта:

Как можно легко подсчитать, в лучшем случае этот алгоритм сжимает файл в 64 раза (а не в 32 раза, как в предыдущем варианте), в худшем увеличивает на 1/128. Средние показатели степени компрессии данного алгоритма находятся на уровне показателей первого варианта.

Упражнение: Составьте алгоритм компрессии для второго варианта алгоритма RLE.

Похожие схемы компрессии использованы в качестве одного из алгоритмов, поддерживаемых форматом TIFF, а также в формате TGA.

Характеристики алгоритма RLE:

Коэффициенты компрессии: Первый вариант: 32, 2, 0,5. Второй вариант: 64, 3, 128/129. (Лучший, средний, худший коэффициенты)

Класс изображений: Ориентирован алгоритм на изображения с небольшим количеством цветов: деловую и научную графику.

Симметричность: Примерно единица.

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

Алгоритм LZW

Название алгоритм получил по первым буквам фамилий его разработчиков - Lempel, Ziv и Welch. Сжатие в нем, в отличие от RLE, осуществляется уже за счет одинаковых цепочек байт.

Алгоритм LZ

Существует довольно большое семейство LZ-подобных алгоритмов, различающихся, например, методом поиска повторяющихся цепочек. Один из достаточно простых вариантов этого алгоритма, например, предполагает, что во входном потоке идет либо пара <счетчик, смещение относительно текущей позиции>, либо просто <счетчик> “пропускаемых” байт и сами значения байтов (как во втором варианте алгоритма RLE). При разархивации для пары <счетчик, смещение> копируются <счетчик> байт из выходного массива, полученного в результате разархивации, на <смещение> байт раньше, а <счетчик> (т.е. число равное счетчику) значений “пропускаемых” байт просто копируются в выходной массив из входного потока. Данный алгоритм является несимметричным по времени, поскольку требует полного перебора буфера при поиске одинаковых подстрок. В результате нам сложно задать большой буфер из-за резкого возрастания времени компрессии. Однако потенциально построение алгоритма, в котором на <счетчик> и на <смещение> будет выделено по 2 байта (старший бит старшего байта счетчика - признак повтора строки / копирования потока), даст нам возможность сжимать все повторяющиеся подстроки размером до 32Кб в буфере размером 64Кб.

При этом мы получим увеличение размера файла в худшем случае на 32770/32768 (в двух байтах записано, что нужно переписать в выходной поток следующие 2 15 байт), что совсем неплохо. Максимальный коэффициент сжатия составит в пределе 8192 раза. В пределе, поскольку максимальное сжатие мы получаем, превращая 32Кб буфера в 4 байта, а буфер такого размера мы накопим не сразу. Однако, минимальная подстрока, для которой нам выгодно проводить сжатие, должна состоять в общем случае минимум из 5 байт, что и определяет малую ценность данного алгоритма. К достоинствам LZ можно отнести чрезвычайную простоту алгоритма декомпрессии.

Упражнение: Предложите другой вариант алгоритма LZ, в котором на пару <счетчик, смещение> будет выделено 3 байта, и подсчитайте основные характеристики своего алгоритма.

Алгоритм LZW

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

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

Функция InitTable() очищает таблицу и помещает в нее все строки единичной длины.

InitTable();
CompressedFile.WriteCode(СlearCode);
CurStr=пустая строка;
while(не ImageFile.EOF()){ //Пока не конец файла
C=ImageFile.ReadNextByte();
if(CurStr+C есть в таблице)
CurStr=CurStr+С;//Приклеить символ к строке
else {
code=CodeForString(CurStr);//code-не байт!
AddStringToTable (CurStr+С);
CurStr=С; // Строка из одного символа
}
}
code=CodeForString(CurStr);
CompressedFile.WriteCode(code);
CompressedFile.WriteCode(CodeEndOfInformation);

Как говорилось выше, функция InitTable() инициализирует таблицу строк так, чтобы она содержала все возможные строки, состоящие из одного символа. Например, если мы сжимаем байтовые данные, то таких строк в таблице будет 256 (“0”, “1”, ... , “255”). Для кода очистки (ClearCode) и кода конца информации (CodeEndOfInformation) зарезервированы значения 256 и 257. В рассматриваемом варианте алгоритма используется 12-битный код, и, соответственно, под коды для строк нам остаются значения от 258 до 4095. Добавляемые строки записываются в таблицу последовательно, при этом индекс строки в таблице становится ее кодом.

Функция ReadNextByte() читает символ из файла. Функция WriteCode() записывает код (не равный по размеру байту) в выходной файл. Функция AddStringToTable() добавляет новую строку в таблицу, приписывая ей код. Кроме того, в данной функции происходит обработка ситуации переполнения таблицы. В этом случае в поток записывается код предыдущей найденной строки и код очистки, после чего таблица очищается функцией InitTable() . Функция CodeForString() находит строку в таблице и выдает код этой строки.

Пример:

Пусть мы сжимаем последовательность 45, 55, 55, 151, 55, 55, 55. Тогда, согласно изложенному выше алгоритму, мы поместим в выходной поток сначала код очистки <256>, потом добавим к изначально пустой строке “45” и проверим, есть ли строка “45” в таблице. Поскольку мы при инициализации занесли в таблицу все строки из одного символа, то строка “45” есть в таблице. Далее мы читаем следующий символ 55 из входного потока и проверяем, есть ли строка “45, 55” в таблице. Такой строки в таблице пока нет. Мы заносим в таблицу строку “45, 55” (с первым свободным кодом 258) и записываем в поток код <45>. Можно коротко представить архивацию так:

“45” - есть в таблице;
“45, 55” - нет. Добавляем в таблицу <258>“45, 55”. В поток: <45>;
“55, 55” - нет. В таблицу: <259>“55, 55”. В поток: <55>;
“55, 151” - нет. В таблицу: <260>“55, 151”. В поток: <55>;
“151, 55” - нет. В таблицу: <261>“151, 55”. В поток: <151>;
“55, 55” - есть в таблице;
“55, 55, 55” - нет. В таблицу: “55, 55, 55” <262>. В поток: <259>;

Последовательность кодов для данного примера, попадающих в выходной поток: <256>, <45>, <55>, <55>, <151>, <259>.

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

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

Алгоритм декомпрессии, осуществляющий эту операцию, выглядит следующим образом:

code=File.ReadCode();
while(code != СodeEndOfInformation){
if(code = СlearСode) {
InitTable();
code=File.ReadCode();
if(code = СodeEndOfInformation)
{закончить работу};
ImageFile.WriteString(StrFromTable(code));
old_code=code;
}
else {
if(InTable(code)) {
ImageFile.WriteString(FromTable(code));
AddStringToTable(StrFromTable(old_code)+
FirstChar(StrFromTable(code)));
old_code=code;
}
else {
OutString= StrFromTable(old_code)+
FirstChar(StrFromTable(old_code));
ImageFile.WriteString(OutString);
AddStringToTable(OutString);
old_code=code;
}
}
}

Здесь функция ReadCode() читает очередной код из декомпрессируемого файла. Функция InitTable() выполняет те же действия, что и при компрессии, т.е. очищает таблицу и заносит в нее все строки из одного символа. Функция FirstChar() выдает нам первый символ строки. Функция StrFromTable() выдает строку из таблицы по коду. Функция AddStringToTable() добавляет новую строку в таблицу (присваивая ей первый свободный код). Функция WriteString() записывает строку в файл.

Замечание 1 . Как вы могли заметить, записываемые в поток коды постепенно возрастают. До тех пор, пока в таблице не появится, например, в первый раз код 512, все коды будут меньше 512. Кроме того, при компрессии и при декомпрессии коды в таблице добавляются при обработке одного и того же символа, т.е. это происходит “синхронно”. Мы можем воспользоваться этим свойством алгоритма для того, чтобы повысить степень компрессии. Пока в таблицу не добавлен 512 символ, мы будем писать в выходной битовый поток коды из 9 бит, а сразу при добавлении 512 - коды из 10 бит. Соответственно декомпрессор также должен будет воспринимать все коды входного потока 9-битными до момента добавления в таблицу кода 512, после чего будет воспринимать все входные коды как 10-битные. Аналогично мы будем поступать при добавлении в таблицу кодов 1024 и 2048. Данный прием позволяет примерно на 15% поднять степень компрессии:

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

Заметим также, что реально нам достаточно хранить в таблице только пару <код предыдущей подстроки, добавленный символ>. Этой информации вполне достаточно для работы алгоритма. Таким образом, массив от 0 до 4095 с элементами <код предыдущей подстроки; добавленный символ; список ссылок на строки, начинающиеся с этой строки> решает поставленную задачу поиска, хотя и очень медленно.

На практике для хранения таблицы используется такое же быстрое, как в случае списков, но более компактное по памяти решение - хэш-таблица. Таблица состоит из 8192 (2 13) элементов. Каждый элемент содержит <код предыдущей подстроки; добавленный символ; код этой строки>. Ключ для поиска длиной в 20 бит формируется с использованием двух первых элементов, хранимых в таблице как одно число (key). Младшие 12 бит этого числа отданы под код, а следующие 8 бит под значение символа.

В качестве хэш-функции при этом используется:

Index(key)= ((key >> 12) ^ key) & 8191;

Где >> - побитовый сдвиг вправо (key >> 12 - мы получаем значение символа), ^ - логическая операция побитового исключающего ИЛИ, & логическое побитовое И.

Таким образом, за считанное количество сравнений мы получаем искомый код или сообщение, что такого кода в таблице нет.

Подсчитаем лучший и худший коэффициенты компрессии для данного алгоритма. Лучший коэффициент, очевидно, будет получен для цепочки одинаковых байт большой длины (т.е. для 8-битного изображения, все точки которого имеют, для определенности, цвет 0). При этом в 258 строку таблицы мы запишем строку “0, 0”, в 259 - “0, 0, 0”, ... в 4095 - строку из 3839 (=4095-256) нулей. При этом в поток попадет (проверьте по алгоритму!) 3840 кодов, включая код очистки. Следовательно, посчитав сумму арифметической прогрессии от 2 до 3839 (т.е. длину сжатой цепочки) и поделив ее на 3840*12/8 (в поток записываются 12-битные коды), мы получим лучший коэффициент компрессии.

Упражнение: Вычислить точное значение лучшего коэффициента компрессии. Более сложное задание: вычислить тот же коэффициент с учетом замечания 1.

Худший коэффициент будет получен, если мы ни разу не встретим подстроку, которая уже есть в таблице (в ней не должно встретиться ни одной одинаковой пары символов).

Упражнение: Составить алгоритм генерации таких цепочек. Попробовать сжать полученный таким образом файл стандартными архиваторами (zip, arj, gz). Если вы получите сжатие, значит алгоритм генерации написан неправильно.

В случае, если мы постоянно будем встречать новую подстроку, мы запишем в выходной поток 3840 кодов, которым будет соответствовать строка из 3838 символов. Без учета замечания 1 это составит увеличение файла почти в 1.5 раза.

LZW реализован в форматах GIF и TIFF.

Характеристики алгоритма LZW:

Коэффициенты компрессии: Примерно1000, 4, 5/7 (Лучший, средний, худший коэффициенты). Сжатие в 1000 раз достигается только на одноцветных изображениях размером кратным примерно 7 Мб.

Класс изображений: Ориентирован LZW на 8-битные изображения, построенные на компьютере. Сжимает за счет одинаковых подцепочек в потоке.

Симметричность: Почти симметричен, при условии оптимальной реализации операции поиска строки в таблице.

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

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

Классический алгоритм Хаффмана

Один из классических алгоритмов, известных с 60-х годов. Использует только частоту появления одинаковых байт в изображении. Сопоставляет символам входного потока, которые встречаются большее число раз, цепочку бит меньшей длины. И, напротив, встречающимся редко - цепочку большей длины. Для сбора статистики требует двух проходов по изображению.

Для начала введем несколько определений.

Определение . Пусть задан алфавит Y ={a 1 , ..., a r }, состоящий из конечного числа букв. Конечную последовательность символов из Y

будем называть словом в алфавите Y , а число n - длиной слова A . Длина слова обозначается как l(A).

Пусть задан алфавит W , W ={b 1 , ..., b q }. Через B обозначим слово в алфавите W и через S (W ) - множество всех непустых слов в алфавите W .

Пусть S =S(Y ) - множество всех непустых слов в алфавите Y , и S" - некоторое подмножество множества S . Пусть также задано отображение F , которое каждому слову A, A? S(Y ) , ставит в соответствие слово

B=F(A), B? S(W ) .

Слово В будем назвать кодом сообщения A, а переход от слова A к его коду - кодированием .

Определение . Рассмотрим соответствие между буквами алфавита Y и некоторыми словами алфавита W :

a 1 - B 1 ,
a 2 - B 2 ,
. . .
a r - B r

Это соответствие называют схемой и обозначают через S . Оно определяет кодирование следующим образом: каждому слову из S" (W ) =S (W ) ставится в соответствие слово , называемое кодом слова A. Слова B 1 ... B r называются элементарными кодами . Данный вид кодирования называют алфавитным кодированием.

Определение . Пусть слово В имеет вид

B=B" B"

Тогда слово B" называется началом или префиксом слова B, а B" - концом слова B. При этом пустое слово L и само слово B считаются началами и концами слова B .

Определение . Схема S обладает свойством префикса, если для любых i и j (1? i , j? r, i? j ) слово B i не является префиксом слова B j .

Теорема 1. Если схема S обладает свойством префикса, то алфавитное кодирование будет взаимно однозначным.

Предположим, что задан алфавит Y ={a 1 ,..., a r } (r >1 ) и набор вероятностей p 1 , . . . , p r появления символов a 1 ,..., a r . Пусть, далее, задан алфавит W , W ={b 1 , ..., b q } (q >1 ). Тогда можно построить целый ряд схем S алфавитного кодирования

a 1 - B 1 ,
. . .
a r - B r

обладающих свойством взаимной однозначности.

Для каждой схемы можно ввести среднюю длину l ср , определяемую как математическое ожидание длины элементарного кода:

- длины слов.

Длина l ср показывает, во сколько раз увеличивается средняя длина слова при кодировании со схемой S .

Можно показать, что l ср достигает величины своего минимума l * на некоторой S и определена как

Определение . Коды, определяемые схемой S с l ср = l * , называются кодами с минимальной избыточностью , или кодами Хаффмана.

Коды с минимальной избыточностью дают в среднем минимальное увеличение длин слов при соответствующем кодировании.

В нашем случае, алфавит Y ={a 1 ,..., a r } задает символы входного потока, а алфавит W ={0,1}, т.е. состоит всего из нуля и единицы.

Алгоритм построения схемы S можно представить следующим образом:

Шаг 1. Упорядочиваем все буквы входного алфавита в порядке убывания вероятности. Считаем все соответствующие слова B i из алфавита W ={0,1} пустыми.

Шаг 2. Объединяем два символа a i r-1 и a i r с наименьшими вероятностями p i r-1 и p i r в псевдосимвол a" {a i r-1 a i r } c вероятностью p i r-1 +p i r . Дописываем 0 в начало слова B i r-1 (B i r-1 =0B i r-1 ), и 1 в начало слова B i r (B i r =1B i r ).

Шаг 3. Удаляем из списка упорядоченных символов a i r-1 и a i r , заносим туда псевдосимвол a" {a i r-1 a i r }. Проводим шаг 2, добавляя при необходимости 1 или ноль для всех слов B i , соответствующих псевдосимволам, до тех пор, пока в списке не останется 1 псевдосимвол.

Пример: Пусть у нас есть 4 буквы в алфавите Y ={a 1 ,..., a 4 } (r =4 ), p 1 =0.5, p 2 =0.24, p 3 =0.15, p 4 =0.11 . Тогда процесс построения схемы можно представить так:

Производя действия, соответствующие 2-му шагу, мы получаем псевдосимвол с вероятностью 0.26 (и приписываем 0 и 1 соответствующим словам). Повторяя же эти действия для измененного списка, мы получаем псевдосимвол с вероятностью 0.5. И, наконец, на последнем этапе мы получаем суммарную вероятность 1.

Для того, чтобы восстановить кодирующие слова, нам надо пройти по стрелкам от начальных символов к концу получившегося бинарного дерева. Так, для символа с вероятностью p 4 , получим B 4 =101, для p 3 получим B 3 =100, для p 2 получим B 2 =11, для p 1 получим B 1 =0. Что означает схему: a 1 - 0,
a 2 - 11
a 3 - 100
a 4 - 101 Эта схема представляет собой префиксный код, являющийся кодом Хаффмана. Самый часто встречающийся в потоке символ a 1 мы будем кодировать самым коротким словом 0, а самый редко встречающийся a 4 длинным словом 101.

Для последовательности из 100 символов, в которой символ a 1 встретится 50 раз, символ a 2 - 24 раза, символ a 3 - 15 раз, а символ a 4 - 11 раз, данный код позволит получить последовательность из 176 бит (). Т.е. в среднем мы потратим 1.76 бита на символ потока.

Доказательства теоремы, а также того, что построенная схема действительно задает код Хаффмана, смотри в .

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

На практике используются его разновидности. Так, в некоторых случаях резонно либо использовать постоянную таблицу, либо строить ее “адаптивно”, т.е. в процессе архивации/разархивации. Эти приемы избавляют нас от двух проходов по изображению и необходимости хранения таблицы вместе с файлом. Кодирование с фиксированной таблицей применяется в качестве последнего этапа архивации в JPEG и в рассмотренном ниже алгоритме CCITT Group 3.

Характеристики классического алгоритма Хаффмана:

Коэффициенты компрессии: 8, 1,5, 1 (Лучший, средний, худший коэффициенты).

Класс изображений: Практически не применяется к изображениям в чистом виде. Обычно используется как один из этапов компрессии в более сложных схемах.

Симметричность: 2 (за счет того, что требует двух проходов по массиву сжимаемых данных).

Характерные особенности: Единственный алгоритм, который не увеличивает размера исходных данных в худшем случае (если не считать необходимости хранить таблицу перекодировки вместе с файлом).

Алгоритм Хаффмана с фиксированной таблицей CCITTGroup 3

Близкая модификация алгоритма используется при сжатии черно-белых изображений (один бит на пиксел). Полное название данного алгоритма CCITT Group 3. Это означает, что данный алгоритм был предложен третьей группой по стандартизации Международного Консультационного Комитета по Телеграфии и Телефонии (Consultative Committee International Telegraph and Telephone). Последовательности подряд идущих черных и белых точек в нем заменяются числом, равным их количеству. А этот ряд, уже в свою очередь, сжимается по Хаффману с фиксированной таблицей.

Определение : Набор идущих подряд точек изображения одного цвета называется серией .Длина этого набора точек называется длиной серии .

В таблице, приведенной ниже, заданы два вида кодов:

Коды завершения серий - заданы с 0 до 63 с шагом 1.
Составные (дополнительные) коды - заданы с 64 до 2560 с шагом 64.

Каждая строка изображения сжимается независимо. Мы считаем, что в нашем изображении существенно преобладает белый цвет, и все строки изображения начинаются с белой точки. Если строка начинается с черной точки, то мы считаем, что строка начинается белой серией с длиной 0. Например, последовательность длин серий 0, 3, 556, 10, ... означает, что в этой строке изображения идут сначала 3 черных точки, затем 556 белых, затем 10 черных и т.д.

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

Алгоритм компрессии выглядит так:

for(по всем строкам изображения) {
Преобразуем строку в набор длин серий;
for(по всем сериям) {
if(серия белая) {
L= длина серии;
while(L > 2623) { // 2623=2560+63
L=L-2560;
ЗаписатьБелыйКодДля(2560);
}
if(L > 63) {
L2=МаксимальныйСостКодМеньшеL(L);
L=L-L2;
ЗаписатьБелыйКодДля(L2);
}
ЗаписатьБелыйКодДля(L);
//Это всегда код завершения
}
else {
[Код аналогичный белой серии,
с той разницей, что записываются
черные коды]
}
}
// Окончание строки изображения
}

Поскольку черные и белые серии чередуются, то реально код для белой и код для черной серии будут работать попеременно.

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

((<Б-2560>)*[<Б-сст.>]<Б-зв.>(<Ч-2560>)*[<Ч-сст.>]<Ч-зв.>) +

[(<Б-2560>)*[<Б-сст.>]<Б-зв.>]

Где ()* - повтор 0 или более раз, () + .- повтор 1 или более раз, - включение 1 или 0 раз.

Для приведенного ранее примера: 0, 3, 556, 10... алгоритм сформирует следующий код: <Б-0><Ч-3><Б-512><Б-44><Ч-10>, или, согласно таблице, 0011010110 0110010100101101 0000100 (разные коды в потоке выделены для удобства). Этот код обладает свойством префиксных кодов и легко может быть свернут обратно в последовательность длин серий. Легко подсчитать, что для приведенной строки в 569 бит мы получили код длиной в 33 бита, т.е. коэффициент сжатия составляет примерно 17 раз.

Вопрос: Во сколько раз увеличится размер файла в худшем случае? Почему? (Приведенный в характеристиках алгоритма ответ не является полным, поскольку возможны большие значения худшего коэффициента сжатия. Найдите их.)

Заметим, что единственное “сложное” выражение в нашем алгоритме: L2=МаксимальныйДопКодМеньшеL(L) - на практике работает очень просто: L2=(L>>6)*64, где >> - побитовый сдвиг L влево на 6 битов (можно сделать то же самое за одну побитовую операцию & - логическое И).

Упражнение: Дана строка изображения, записанная в виде длин серий - 442, 2, 56, 3, 23, 3, 104, 1, 94, 1, 231, размером 120 байт ((442+2+..+231)/8). Подсчитать коэффициент компрессии этой строки алгоритмом CCITT Group 3.

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

Таблица кодов завершения:

Длина серии	Код белой подстроки	Код черной подстроки	Длина серии	Код белой подстроки	Код черной подстроки
0	00110101	0000110111	32	00011011	000001101010
1	00111	010	33	00010010	000001101011
2	0111	11	34	00010011	000011010010
3	1000	10	35	00010100	000011010011
4	1011	011	36	00010101	000011010100
5	1100	0011	37	00010110	000011010101
6	1110	0010	38	00010111	000011010110
7	1111	00011	39	00101000	000011010111
8	10011	000101	40	00101001	000001101100
9	10100	000100	41	00101010	000001101101
10	00111	0000100	42	00101011	000011011010
11	01000	0000101	43	00101100	000011011011
12	001000	0000111	44	00101101	000001010100
13	000011	00000100	45	00000100	000001010101
14	110100	00000111	46	00000101	000001010110
15	110101	000011000	47	00001010	000001010111
16	101010	0000010111	48	00001011	000001100100
17	101011	0000011000	49	01010010	000001100101
18	0100111	0000001000	50	01010011	000001010010
19	0001100	00001100111	51	01010100	000001010011
20	0001000	00001101000	52	01010101	000000100100
21	0010111	00001101100	53	00100100	000000110111
22	0000011	00000110111	54	00100101	000000111000
23	0000100	00000101000	55	01011000	000000100111
24	0101000	00000010111	56	01011001	000000101000
25	0101011	00000011000	57	01011010	000001011000
26	0010011	000011001010	58	01011011	000001011001
27	0100100	000011001011	59	01001010	000000101011
28	0011000	000011001100	60	01001011	000000101100
29	00000010	000011001101	61	00110010	000001011010
30	00000011	000001101000	62	00110011	000001100110
31	00011010	000001101001	63	00110100	000001100111

Таблица составных кодов:

Длина серии	Код белой подстроки	Код черной подстроки	Длина серии	Код белой подстроки	Код черной подстроки
64	11011	0000001111	1344	011011010	0000001010011
128	10010	000011001000	1408	011011011	0000001010100
192	01011	000011001001	1472	010011000	0000001010101
256	0110111	000001011011	1536	010011001	0000001011010
320	00110110	000000110011	1600	010011010	0000001011011
384	00110111	000000110100	1664	011000	0000001100100
448	01100100	000000110101	1728	010011011	0000001100101
512	01100101	0000001101100	1792	00000001000	совп. с белой
576	01101000	0000001101101	1856	00000001100	- // -
640	01100111	0000001001010	1920	00000001101	- // -
704	011001100	0000001001011	1984	000000010010	- // -
768	011001101	0000001001100	2048	000000010011	- // -
832	011010010	0000001001101	2112	000000010100	- // -
896	011010011	0000001110010	2176	000000010101	- // -
960	011010100	0000001110011	2240	000000010110	- // -
1024	011010101	0000001110100	2304	000000010111	- // -
1088	011010110	0000001110101	2368	000000011100	- // -
1152	011010111	0000001110110	2432	000000011101	- // -
1216	011011000	0000001110111	2496	000000011110	- // -
1280	011011001	0000001010010	2560	000000011111	- // -