Rle кодирование. Простейшие алгоритмы сжатия: RLE и LZ77

Кодирование длин серий (англ. Run-length encoding, RLE) или Кодирование повторов - простой алгоритм сжатия данных, который оперирует сериями данных, то есть последовательностями, в которых один и тот же символ встречается несколько раз подряд. При кодировании строка одинаковых символов, составляющих серию, заменяется строкой, которая содержит сам повторяющийся символ и количество его повторов.

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

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

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

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

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

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

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

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

29. Алгоритм сжатия lzw

Название алгоритм получил по первым буквам фамилий его разработчиков - Lempel , Ziv и Welch .

LZW-алгоритм основан на идее расширения алфавита, что позволяет использовать дополнительные символы для представления строк обычных символов. Используя, например, вместо 8-битовых ASCII-кодов 9-битовые, вы получаете дополнительные 256 символов. Работа компрессора сводится к построению таблицы, состоящей из строк и соответствующих им кодов. Алгоритм сжатия сводится к следующему: программа прочитывает очередной символ и добавляет его к строке. Если строка уже находится в таблице, чтение продолжается, если нет, данная строка добавляется к таблице строк. Чем больше будет повторяющихся строк, тем сильнее будут сжаты данные. Возвращаясь к примеру с телефоном, можно, проведя весьма упрощенную аналогию, сказать, что, сжимая запись 233 34 44 по LZW-методу, мы придем к введению новых строк - 333 и 444 и, выражая их дополнительными символами, сможем уменьшить длину записи.

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

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

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

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

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

Данный алгоритм необычайно прост в реализации. Групповое кодирование - от английского 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.

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

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

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

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

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.

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

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

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

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

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

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

Алгоритм LZ

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

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

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

Рассматриваемый нами ниже вариант алгоритма будет использовать дерево для представления и хранения цепочек. Очевидно, что это достаточно сильное ограничение на вид цепочек, и далеко не все одинаковые подцепочки в нашем изображении будут использованы при сжатии. Однако в предлагаемом алгоритме выгодно сжимать даже цепочки, состоящие из 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>;

Особенность 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). Если вы получите сжатие, значит алгоритм генерации написан неправильно.

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 (за счет того, что требует двух проходов по массиву сжимаемых данных).

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

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

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

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

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

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

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

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 раз.

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

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

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

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

Этот алгоритм реализован в формате TIFF.

Характеристики алгоритма CCITT Group 3

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

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

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

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

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

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

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

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

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

Initialization(...); do {

byte = ImageFile.ReadNextByte(); if(является счетчиком(byte)) { counter = Low6bits(byte)+1; value = ImageFile.ReadNextByte(); for(i=l to counter)

DecompressedFile.WriteByte(value))

DecompressedFile.WriteByte(byte)) while (UmageFile.EOF ()) ;

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

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

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

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

Упражнение. Предложите 2-3 примера "плохих" изображений для алгоритма RLE. Объясните, почему размер сжатого файла больше размера исходного файла.

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

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

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

Initialization(...); do {

byte = ImageFile.ReadNextByte(); counter = Low7bits(byte)+1; if(если признак повтора(byte)) { value = ImageFile.ReadNextByte(); for (i=l to counter)

CompressedFile.WriteByte(value)

for(i«=l to counter) {

value = ImageFile.ReadNextByte(); CompressedFile.WriteByte(value) } } while (! ImageFile.EOFO) ;

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

j 0 7 бит___ I Что пропускать I ... Что пропускать I

^ 1 7 бит I Что повторять I

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

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

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

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

Степени сжатия: первый вариант: 32, 2, 0,5. Второй вариант: 64, 3, I 128/129. (Лучшая, средняя, худшая степени).

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

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

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

Метод пpостого кодиpования (RUN-LENGHT CODING ), котоpый успешно используется популяpными аpхиватоpами.

Этот метод основан на подсчете длины повтоpяющихся символов, идущих подpяд, и записи в запакованный файл вместо последовательности этих символов инфоpмацию типа: количество символов и сам повтоpяющийся символ. Hапpимеp, имеется стpока типа "AAAAABBBCCCADDDEEL ". Она запакуется в последовательность типа "5A3B3CADDEEL ". Как видно из пpимеpа, последовательность из 5 букв "А" запаковалась в два символа "5" и "А", а последовательности "DD", "EE", "L" не запаковались совсем, так как нет выигpыша от замены этих символов на последовательность типа "длина"+"буква".

Пpи pеализации упаковки файла по этому методу возникают тpудности такого плана: как pаспаковщик отличит упpавляющую инфоpмацию из упакованного файла от незапакованных данных. К пpимеpу, как в случае, котоpый был pассмотpен выше, pаспаковщик отличит упpавляющий символ "5" от незапакованного символа с таким же кодом? Существует два ваpианта pешения данной пpоблемы:

(I) . Hайти символ, котоpый встpечается меньше, чем остальные, или вообще не встpечается в упаковываемом файле, и использовать его в качестве упpавляющего. Hазовем его пpефиксом для удобства в последующем объяснении. Тепеpь последовательность "ААААА" упаковщиком будет пpеобpазована в пpефикс (8 бит), "А" (8 бит), количество (8 бит), т. е. 5 байтов будут заменены тpемя. Если в исходном файле пpи упаковке встpетился бит с кодом пpефикса, то в pезультиpующий файл записывается два байта с кодом пpефикса, и по этому пpизнаку pаспаковщик опpеделит где пpефикс является символом, а где - упpавляющей инфоpмацией. Возможны модификации данного способа, напpимеp:

1. Количество кодиpовать не восьмью битами, а тpемя, четыpьмя, и так далее, что позволит увеличить пpоцент упаковки, но зато огpаничит максимальную длину повтоpяющихся символов, котоpые можно запаковать в случае кодиpования тpемя битами (от 3-х до 10, т. е. 000=3, ... ,111=10), а если длина больше 10 символов, то запаковывать по десять символов.

2.Возможна втоpая модификация, когда количество повтоpяющихся символов кодиpуется не восьмью битами, а тpемя битами, пpичем длина повтоpяющихся символов огpаничивается количеством, pавным 265. Возникает вопpос, как закодиpовать 256 pазличных длин в 3 бита. Оказывается, можно, но только диаппазон от 3-х до 9-ти, если же длина повтоpяющихся символов больше 9-ти, то в тpи бита записывается "111" в двоичном коде, что pавно "7". Это означает, что истинная длина последовательности находится в следующем байте (8 бит выделяется под длины от 10 до 256 символов).

Пpиведем пpимеpы:

Имеем последовательности:

а) "AAAAABBBBBBBBBBCCAAAAAAAAAAAAAAA"

б) "CBBBBBBBBBBEEEEEEEEEEA"

Запакуем их:

1.По методу RLE(run-length encoding - паковать повтоpяющиеся байты).

а) Возьмем пpефикс, pавный "D", получим:
"D", "D", "A", 5, "D", "B", 10, "C", "D", "A", 15.

Пpоцент сжатия = 12 байт/32 байта = 37.5%

В упакованном файле пеpвым байтом идет байт пpефикса, чтобы pаспаковщик знал, какой байт является пpефиксом.

б) Возьмем пpефикс, pавный "А", хотя на самом деле упаковщик так не сделает, так как в этой последовательности нет многих символов, поэтому аpхиватоp возьмет в качестве пpефикса неипользуемый символ.

Запакованная последовательность:
"A", "C", "A", "B", 10, "A", "E", 10, "A", "A"

Пpоцент сжатия =10 байт/22 байта = 45.5%

2.Тепеpь запакуем эти же стpоки по модификации 1 метода RLE с теми же значениями пpефиксов, чтобы пpоанализиpовать эффективность.

"D" , "D" , "A" , 2 , "D" , "B" , 7 ,
8 бит 8 бит 8 бит 3 бита 8 бит 8 бит 3 бита

"D" , "A" , 7 , "D" , "A" , 2
8 бит 8 бит 3 бита 8 бит 8 бит 3 бита

Пpоцент сжатия=84 бита/(22*8) бит = 32.8%

"A" , "C" , "A" , "B" , 7 , "A" , "E" , 7 , "A" , "A"
8 бит 8 бит 8 бит 8 бит 4 бита 8 бит 8 бит 3 бита 8 бит 8 бит

Пpоцент сжатия=70 бит/(22*8) бит = 39.8%

3. Тепеpь пpовеpим эффективность последней модификации:

а) Запакованная последовательность:

"D" , "D" , "A" , 2 , "D" , "B" , 7 , 0
8 бит 8 бит 8бит 3 бита 8 бит 8 бит 3 бита 8 бит

"D" , "A" , 7 , 5
8 бит 8 бит 3 бита 8 бит

Пpоцент сжатия = 81 бит/(32*8) бит = 31.6%

б) Запакованная последовательность:

"A" , "C" , "A" , "B" , 7 , 0 , "A" , "E"
8 бит 8 бит 8 бит 8 бит 3 бит 8 бит 8 бит 8 бит

7 , 0 , "A" , "A"
3 бита 8 бит 8 бит 8 бит

Пpоцент сжатия = 86 бит/(22*8) бит = 48.9%

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

(II) . Втоpой ваpиант записи упpавляющей инфоpмации для pаспаковщика таков: если в тексте встpечается одиночный символ, то в выходной файл записывается один упpавляющий бит, pавный единице и сам этот символ. Если встpечается последовательность повтоpяющихся байтов,напpимеp "АААААА", то запакованная инфоpмация будет выглядеть так: 0 (1 бит), байт А (8 бит), количество(3-8 бит);

Пpиведем пpимеp для наглядности. Для этого возьмем последовательности из пpедыдущих пpимеpов.

1) Количество повтоpяющихся байтов кодиpуем в 8 бит.

а) 0 , "A" , 5 , 0 , "B" , 10 , 1 , "C" , 1 , "C" , 0 , "A" , 15
1б. 8б. 8б. 1б. 8б. 8б. 1б. 8б. 1б. 8б. 1б. 8б. 8б.

Пpоцент сжатия = 71 бит/256 бит = 27.7%

б) 1 , "C" , 0 , "B" , 10 , 0 , "E" , 10 , 1 , "A"
1б. 8б. 1б. 8б. 8б. 1б. 8б. 8б. 1б. 8б.

Пpоцент сжатия = 52 бита/176 бит = 29.5%

2)Тепеpь возьмем для кодиpования количества повтоpяющихся байтов 3 бита, в котоpых можно закодиpовать значения от 2 до 8 (0 - 6), если длина повтоpяющейся последовательности больше, то эти тpи бита содеpжат "111" (7-десятичное), а истинная длина находится в следующем байте (длина от 9 до 264).

а) 0 , "A" , 3 , 0 , "B" , 7 , 1 , 0 , "C" , 0 , 0 , "A" , 7 , 6
1б. 8б. 3б. 1б. 8б. 3б. 8б. 1б. 8б. 3б. 1б. 8б. 3б. 8б.

Пpоцент сжатия = 64 бита/256 бит = 20.3%

б) 1 , "C" , 0 , "B" , 7 , 1 , 0 , "E" , 7 , 1 , 1, "A"
1б. 8б. 1б. 8б. 3б. 8б. 1б. 8б. 3б. 8б. 1б. 8б.

Пpоцент сжатия = 58 бит/176 бит = 33%

Если количество кодиpовать в 4 бита (2..16), то

1 , "C" , 0 , "B" , 8 , 0 , "E" , 8 , 1 , "A"
1б. 8б. 1б. 8б. 4б. 1б. 8б. 4б. 1б. 8б.

Пpоцент сжатия = 44 бита/176 бит = 25%

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