Главная › Телефон › В чем идея алгоритма сжатия rle. Сжатие способом кодирования серий: алгоритм RLE. Ограничение информационного алфавита

В чем идея алгоритма сжатия rle. Сжатие способом кодирования серий: алгоритм RLE. Ограничение информационного алфавита

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

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

На чем основан алгоритм сжатия RLE?

RLE работает, уменьшая физический размер повторяющейся строки символов. Эта строка, называемая run, обычно кодируется в два байта. Первый байт представляет количество символов в пробеге и называется счетчиком прогона. На практике кодированный прогон может включать от 1 до 128 и 256 символов. Счетчик обычно содержит число символов минус один (значение в диапазоне значений от 0 до 127 и 255). Второй байт — это значение символа в прогоне, которое содержится в диапазоне значений от 0 до 255 и именуется значением запуска.

Без сжатия символьный пробег в 15 символов обычно требует 15 байтов для хранения:

AAAAAAAAAAAAAAA.

В той же строке после RLE-кодирования потребуется только два байта: 15А.

Кодировка 15A, сгенерированная для обозначения символьной строки, называется RLE-пакетом. В данном коде первый байт, 15, является счетчиком прогона и содержит необходимое количество повторений. Второй байт, A, является значением run и содержит фактическое повторяющееся значение в пробеге.

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

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

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

Особенности

Длинные прогоны редки в некоторых типах данных. Например, открытый текст ASCII редко содержит длинные прогоны. В предыдущем примере последний пробег (содержащий символ t) был только одним символом в длину. 1-символьный прогон все еще работает. И счет запуска, и значение запуска должны быть записаны для каждого пробега в 2 символа. Для кодирования пробега с помощью алгоритма RLE требуется информация, состоящая не менее чем из двух символов. В связи с чем запуск одиночных символов на самом деле занимает больше места. По тем же причинам данные, состоящие полностью из 2-символьных прогонов, остаются неизменными после кодирования RLE.

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

Варианты кодирования по длине

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

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

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

Кросс-кодирование

Кросс-кодирование — это объединение строк сканирования, которое происходит, когда процесс сжатия теряет различие между исходными линиями. Если данные отдельных линий объединены алгоритмом кодирования повторов RLE, точка, где одна линия сканирования остановлена, а другая - потеряна, является уязвимой и сложной для обнаружения.

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

Как с помощью алгоритма RLE закодировать изображение?

Индивидуальное кодирование строк сканирования имеет преимущества в тех случаях, когда приложение должно использовать только некоторую часть изображения. Предположим, что фото содержит 512 строк развертки, и необходимо отображать только строки от 100 до 110. Если мы не знали, где строки сканирования начинались и заканчивались данными кодированного изображения, нашему приложению пришлось бы декодировать строки с 1 по 100, прежде чем найти десять строк, которые требуются. Если переходы между линиями сканирования были отмечены каким-то легко узнаваемым маркером разграничения, приложение могло бы просто считывать закодированные данные, подсчитывая маркеры, пока не дойдет до нужных ему строк. Но этот подход был бы довольно неэффективным.

Альтернативный вариант

Другим вариантом для определения начальной точки любой конкретной строки сканирования в блоке кодированных данных является построение таблицы строк развертки. Данная табличная структура обычно содержит один элемент для каждой строки сканирования на изображении, и каждый элемент содержит значение смещения соответствующей строки сканирования. Чтобы найти первый RLE-пакет строки 10 сканирования, все, что нужно сделать декодеру, — это найти значения позиции смещения, хранящегося в десятом элементе таблицы поиска строки сканирования. Таблица строк развертки также может содержать количество байтов, используемых для кодирования каждой строки. Используя этот метод с целью найти первый RLE-пакет строки сканирования 10, ваш декодер будет объединять значения первых 9-ти элементов таблицы строк развертки. Первый пакет для строки 10 сканирования будет начинаться с этого смещения байта от начала данных изображения с кодированием RLE.

Единицы измерения

Части алгоритмов кодирования по длине, которые различаются, — это решения, которые принимаются на основе типа данных, которые декодируются (например, длина прогона данных). Схемы RLE, используемые для сжатия растровой графики, обычно подразделяются на классы по типу атомных (то есть наиболее фундаментальных) элементов, которые они кодируют. Три класса, используемые большинством графических форматов файлов, — это бит, байты и пиксельные RLE.

Качество сжатия

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

Исключения

Схемы RLE на уровне байта кодируют прогоны одинаковых байтовых значений, игнорируя некоторые биты и границы слов в строке сканирования. Наиболее распространенная схема RLE на байтовом уровне кодирует прогоны байтов в 2-байтовые пакеты. Первый байт содержит счетчик от 0 до 255, а второй — содержит значение байтового запуска. Также распространено дополнение двухбайтовой схемы кодирования с возможностью хранения литеральных, незаписанных прогонов байтов в потоке кодированных данных.

В такой схеме семь младших значащих бит первого байта содержат счетчик прогона минус один, а самый старший бит первого байта является индикатором типа запуска, который следует за байтом подсчета прогона. Если старший бит установлен в 1, он обозначает кодированный прогон. Закодированные прогоны декодируются путем считывания значения пробега и повторения его количества раз, указанного числом циклов. Если самый старший бит установлен в 0, отображается литеральный прогон, а это означает, что байты подсчета следующего прогона считываются буквально из данных кодированного изображения. Затем байт счетчика выполнения содержит значение в диапазоне от 0 до 127 (счетчик запуска минус один). Схемы RLE на уровне байта хороши для данных изображения, которые сохраняются как один байт на пиксель.

Схемы RLE на уровне пикселей используются, когда два или более последовательных байта данных изображения используются для хранения значений одного пикселя. На уровне пикселей биты игнорируются, а байты подсчитываются только для идентификации каждого значения пикселя. Размер кодированных пакетов зависит от размера кодируемых значений пикселей. Количество бит или байтов на пиксель сохраняется в заголовке файла изображения. Запуск данных изображения, сохраненных в виде 3-байтовых значений пикселей, кодируется в 4-байтовый пакет, с одним байтом подсчета количества операций, за которым следуют три байта с байтами. Метод кодирования остается таким же, как и с байтовым RLE.

Алгоритм 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	- // -

Если в одном столбце встретятся два числа с одинаковым префиксом, то это опечатка.

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

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

Оформление документа

Скопируйте в свой каталог документ ТЕХ.doc и оформите его следующим образом:

и оформите этим стилем формулу, набранную в формате LaТ Е Х.

Оформите заголовок «Литература» стилем «Заголовок 2 ». Информацию о книге Д. Кнута оформите в виде нумерованного списка.
Найдите информацию о книге «Все про Т Е Х» на сайте издательства «Вильямс» и сделайте название книги гиперссылкой на найденную страницу. Проверьте работу гиперссылки.

Алгоритм RLE

Используя алгоритм RLE, закодируйте последовательность символов

BBBBBBACCCABBBBBB

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

Раскодируйте последовательность, упакованную с помощью алгоритма RLE (приводятся шестнадцатеричные коды): 01 4D 8E 41 01 4D 8E 41 16 . Для определения символов по их шестнадцатеричным кодом используйте таблицу ASCII. Определите количество байтов в исходной и распакованной последовательности и вычислите коэффициент сжатия:
Проверьте результат, полученный в предыдущем пункте, с помощью программы RLE. Предложите два способа проверки.
Постройте последовательности, которые сжимаются алгоритмом RLE ровно в 2 раза, в 4 раза, в 5 раз. Проверьте свои ответы с помощью программы RLE.

Несжатая последовательность

Сжатая последовательность

Коэффициент сжатия

2

4

5
Придумайте три последовательности, которые невозможно сжать с помощью алгоритма RLE:

Несжатая последовательность

«Сжатая» последовательность

Коэффициент сжатия
Используя программу RLE, примените RLE-сжатие к следующим файлам и найдите для каждого из них коэффициент сжатия:

Файл

Размер без сжатия

Размер после сжатия

Коэффициент сжатия

grad_vert.bmp

grad_horz.bmp

grad_diag.jpg
Объясните результаты, полученные в предыдущем пункте:

почему невыгодно сжимать рисунки в формате JPEG?
почему для двух рисунков в формате BMP одинакового размера коэффициенты сжатия по алгоритму RLE так сильно отличаются? Подсказка : откройте эти рисунки в любой программе просмотра.

Оцените максимально достижимый коэффициент сжатия с помощью рассмотренного в учебнике варианта RLE-алгоритма. В каком случае его удастся достичь?

Ответ :

Оцените коэффициент сжатия с помощью RLE-алгоритма в худшем случае. Опишите этот худший случай.

Ответ :

Сравнение алгоритмов сжатия

При выполнении этой работы используются программы RLE (алгоритм сжатия RLE) и Huffman (кодирование Хаффмана и Шеннона-Фано).

Запустите программу Huffman.exe и закодируйте строку «ЕНОТ НЕ ТОНЕТ», используя методы Шеннона-Фано и Хаффмана. Запишите результаты в таблицу:

	Шеннон и Фано	Хаффман
Длина основного кода

Сделайте выводы.

Ответ :

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

Ответ :

Повторите эксперимент с фразой «НОВОЕ ЕНОТОВО».

	Шеннон и Фано	Хаффман
Длина основного кода
Длина кодовой таблицы (дерева)
Коэффициент сжатия (по основным кодам)
Коэффициент сжатия (с учетом дерева кодов)

Сделайте выводы.

Ответ :

Нарисуйте в тетради кодовые деревья, которые были построены программой при использовании обоих методов.

Используя кнопку Анализ файла в программе Huffman a.txt 1 при побайтном кодировании.

Ответ :

С помощью программ RLE и Huffman выполните сжатие файла a . txt разными способами. Запишите результаты в таблицу:

Объясните результат, полученный с помощью алгоритма RLE.

Ответ :

Используя кнопку Анализ файла в программе Huffman , определите предельный теоретический коэффициент сжатия для файла a.txt.huf при побайтном кодировании. Объясните результат.

Ответ :

Примените несколько раз повторное сжатие этого файла с помощью алгоритма Хаффмана (новые файлы получат имена a.txt.huf2 , a.txt.huf3 и т.д.) и заполните таблицу, каждый раз выполняя анализ полученного файла.

	Размер файла
a.txt
a.txt.huf
a.txt.huf2
a.txt.huf3
a.txt.huf4
a.txt.huf5

Ответ :

Выполните те же действия, используя метод Шеннона-Фано.

	Размер файла	Предельный коэффициент сжатия
a.txt
a.txt.shf
a.txt.shf2
a.txt.shf3
a.txt.shf4
a.txt.shf5

Объясните, почему с некоторого момента при повторном сжатии файла его размер увеличивается.

Ответ :

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

	Размер файла	Предельный коэффициент сжатия
RLE
Хаффман
Шеннон и Фано
ZIP
RAR
7Z

Объясните результаты и сделайте выводы.

Ответ :

Использование архиватора

Изучите возможности архиватора, который установлен на вашем компьютере (Ark , 7- Zip , WinRAR или др.).
Откройте каталог, указанный учителем. Он должен содержать все файлы, которые используются далее.
Распакуйте архив secret. zip , который упакован с паролем secretLatin . В подкаталогах, получившихся после распаковки, вы должны найти 3 файла, содержащие части высказывания на латинском языке, которое означает «договоры следует выполнять».
Создайте новый текстовый файл latin.txt и запишите в него это высказывание на латыни. После этого удалите архив secret.zip .
Выполните сжатие отдельно для каждого из перечисленных в таблице файлов, используя формат архива, указанный учителем. Вычислите коэффициент сжатия (для этого удобно использовать табличный процессор):

Имя файла	Описание	Объем до сжатия, Кб	Объем после сжатия, Кб	Коэффициент сжатия
random.dat	случайные данные	391
morning.zip	сжатый файл	244
sunset.jpg	рисунок в формате JPEG	730
prog.exe	программа для Windows	163
signal.mp3	звук в формате MP3	137
forest.wav	звук в формате WAV	609
ladoga.bmp	рисунок в формате BMP	9217
tolstoy.txt	текст	5379

Запишите в тетради выводы о том, какие файлы обычно сжимаются лучше, а какие – хуже.

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

Объясните, почему размеры двух архивов получились разные. После этого удалите оба созданных архива.

Переместите рисунки в отдельный каталог Pictures , а звуковые файлы – в каталог Sounds.
Упакуйте рисунки и звуки в архив Media с паролем media123 .
Упакуйте все остальные файлы и папки в архив Data (без пароля).
Удалите все файлы, кроме архивов Media и Data , и покажите работу учителю.

Сжатие с потерями

Скопируйте в свою папку файл valaam.jpg .
Используя растровый графический редактор (GIMP , Photoshop ), сохраните несколько копий этого рисунка с разным качеством, от 0% до 100%.

Качество, %	0	10	20	30	40	50	60	70	80	90	100
Объем файла, Кбайт

С помощью табличного процессора постройте график по этим данным. Сделайте выводы.

Просмотрите файлы, полученные при разных степенях сжатия. Выберите оптимальный на ваш взгляд вариант, когда при небольшом размере файла сохраняется приемлемое качество рисунка.
Скопируйте в свою папку звуковой файл bears . mp 3 .
Используя звуковой редактор (например, Audacity ), сохраните несколько копий этого звукового файла с разным качеством. Для формата Ogg Vorbis используйте качество от 0% до 100%, для формата MP3 – битрейт от 16 до 128 Кбит/с.
В табличном процессоре заполните таблицу

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

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

ПРОФИЛЬ При сжатии с помощью алгоритма RLE сначала записывается количество повторений первого символа, затем сам первый символ, затем количество повторений второго символа и т.д. В данном случае весь закодированный файл занимает 4 байта: 011 00100 2 11 000000 2 011 00100 2 11 000001 2 100 A (код 192) 100 Б (код 193) Таким образом, мы сжали файл в 50 раз за счет того, что в нем снова была избыточность - цепочки одинаковых символов. Это сжатие без потерь, потому что, зная алгоритм упаковки, можно восстановить исходные данные из кода. Очевидно, что такой подход будет приводить к увеличению (в 2 раза) объема данных в том случае, когда в файле нет соседних одинаковых символов. Чтобы улучшить результаты RLE-кодирования даже в этом наихудшем случае, алгоритм модифицировали следующим образом. Упакованная последовательность содержит управляющие байты, за каждым управляющим байтом следует один или несколько байтов данных. Если старший бит управляющего байта равен 1, то следующий за управляющим байт данных при распаковке нужно повторить столько раз, сколько записано в оставшихся 7 битах управляющего байта. Если же старший бит управляющего байта равен 0, то надо взять несколько следующих байтов данных без изменения. Сколько именно - записано в оставшихся 7 битах управляющего байта. Например, управляющий байт 1000011 1 2 говорит о том, что следующий за ним байт надо повторить 7 раз, а управляющий байт 00000100 2 - о том, что следующие за ним 4 байта надо взять без изменений. Так последовательность 100011 11 2 11 000000 2 00000010 2 11 000001 2 11 000010 2 повтор 15 A (код 192) 2 Б (код 193) В (код 194) распаковывается в 17 символов: АААААААААААААААБВ. Алгоритм RLE успешно применялся для сжатия рисунков, в которых большие области закрашены одним цветом, и некоторых звуковых данных. Сейчас вместо него применяют более совершенные, но более сложные методы. Один из них (кодирование Хаффмана) мы рассмотрим ниже. Алгоритм RLE используется, например, на одном из этапов кодирования рисунков в формате JPEG. Возможность RLE-сжатия есть также в формате BMP (для рисунков с палитрой 16 или 256 цветов). Лучший способ понять принцип работы алгоритма - потренироваться в его использовании. С сайта автора (http://kpolyakov.narod.ru/prog/compress.htm) можно загрузить бесплатную программу-тренажер, которая предназначена для изучения алгоритма RLE: В левой части окна программы находится текстовый редактор. При нажатии на кнопку введенный текст сжимается с помощью алгоритма RLE, сжатые данные отображаются в виде шестнадцатеричных кодов в правой части окна. Окно в правой части - это тоже редактор, поэтому коды можно изменить и выполнить обратную операцию (распаковку, декомпрессию), нажав на кнопку. Кнопки в верхней части окна позволяют сжимать и восстанавливать файлы на диске. Нужно только учитывать, что программа использует свой собственный формат хранения данных. 6 декабрь 2012 / ИНФОРМАТИКА Контрольные вопросы 1) Оцените максимально достижимый коэффициент сжатия с помощью рассмотренного варианта RLEалгоритма. В каком случае его удастся достичь? 2) Оцените коэффициент сжатия с помощью RLE-алгоритма в худшем случае. Опишите этот худший случай. 3) Придумайте три последовательности, которые невозможно сжать с помощью алгоритма RLE. 4) Постройте последовательности, которые сжимаются алгоритмом RLE ровно в 2 раза, в 4 раза, в 5 раз. Практикум 1) Используя алгоритм RLE, закодируйте последовательность символов BBBBBBACCCABBBBBB Запишите результат в виде шестнадцатеричных кодов (каждый символ кодируется в виде байта, который представлен двумя шестнадцатеричными цифрами). Проверьте полученный результат с помощью программы RLE.

2) Декодируйте последовательность, упакованную с помощью алгоритма RLE (приводятся шестнадцатеричные коды): 01 4D 8E 41 01 4D 8E 41 16. Для определения символов по их шестнадцатеричным кодам используйте таблицу ASCII. Определите количество байтов в исходной и распакованной последовательности и вычислите коэффициент сжатия. Проверьте результат с помощью программы RLE. Предложите два способа проверки. 3) Используя программу RLE, примените RLEсжатие к следующим файлам 1 и найдите для каждого из них коэффициент сжатия. grad_vert.bmp grad_horz.bmp grad_diag.jpg Объясните полученные результаты: почему для двух рисунков в формате BMP одинакового размера коэффициенты сжатия по алгоритму RLE так сильно отличаются; почему не удается сжать рисунки, сохраненные в формате JPEG? Префиксные коды Вспомните азбуку Морзе, в которой для уменьшения длины сообщения используется неравномерный код - часто встречающиеся буквы (А, Е, М, Н, Т) кодируются короткими последовательностями, а редко встречающиеся - более длинными. Такой код можно представить в виде структуры, которая называется деревом: Корень Здесь показано неполное дерево кода Морзе, построенное только для символов, коды которых состоят из одного и двух знаков (точек и тире). Дерево состоит из узлов (черная точка и кружки с символами алфавита) и соединяющих их направленных ребер, стрелки указывают направление движения. Верхний узел (в который не входит ни одна стрелка) называется “корнем” дерева. Из корня и из всех промежуточных узлов (кроме конечных узлов - “листьев”) выходят две стрелки, левая помечена точкой, а правая - знаком “тире”. Чтобы найти код символа, нужно пройти по стрелкам от “корня” дерева к нужному “листу”, выписывая метки стрелок, по которым мы переходим. В дереве нет циклов (замкнутых путей), поэтому код каждого 1 Эти и другие файлы, использующиеся в заданиях практикума, находятся на диске-приложении к этому номеру журнала. символа определяется единственным образом. По этому дереву можно построить такие коды: Е И А – Т – Н – М – – Это неравномерный код, в нем символы имеют коды разной длины. При этом всегда возникает проблема разделения последовательности на отдельные кодовые слова. В коде Морзе она решена с помощью символа-разделителя - паузы. Однако можно не вводить дополнительный символ, если выполняется условие Фано: ни одно из кодовых слов не является началом другого кодового слова. Это позволяет однозначно декодировать сообщение в реальном времени, по мере получения очередных символов. Префиксный код - это код, в котором ни одно кодовое слово не является началом другого кодового слова (условие Фано). Роберт Фано (род. 1917) (nytimes.com) Клод Шеннон (1916–2001) Для использования этой идеи в компьютерной обработке данных нужно было разработать алгоритм построения префиксного кода. Впервые эту задачу решили, независимо друг от друга, американские математики и инженеры Клод Шеннон (в 1948 году) и Роберт Фано (в 1949 году) . Они использовали избыточность сообщений, состоящую в том, что символы в тексте имеют разные частоты встречаемости. В этом случае нужно читать данные исходного файла два раза: на первом проходе определяется частота встречаемости каждого символа, затем строится код с учетом этих данных, и на втором проходе символы текста заменяются на их коды. Алгоритм кодирования, предложенный Шенноном и Фано, получил название кода Шеннона - Фано. Пример 3. Пусть текст состоит только из букв О, Е, Н, Т и пробела. Известно, сколько раз они встретились в тексте: пробел - 179, О - 89, Е - 72, Н - 53 и Т - 50 раз. Следуя методу Шеннона - Фано, делим символы на две группы так, чтобы общее количество найденных в тексте символов первой группы было примерно равно общему количеству символов второй группы. В нашем случае лучший вариант - это объединить пробел и букву Т в первую группу (сумма 179+50 = 229), а остальные символы - во вторую (сумма 89+72+53 = 214). Символы первой группы будут иметь коды, начинающиеся с 0, а остальные - с 1. В первой группе всего два символа, у одного из них, например у пробела, вторая цифра кода будет 0 (и полный код 00), а у второго - 1 (код буквы Т - 01) . 7 декабрь 2012 / ИНФОРМАТИКА

Несжатая последовательность	Сжатая последовательность	Коэффициент сжатия
		2
		4
		5

Несжатая последовательность	«Сжатая» последовательность	Коэффициент сжатия

Файл	Размер без сжатия	Размер после сжатия	Коэффициент сжатия
grad_vert.bmp
grad_horz.bmp
grad_diag.jpg

В чем идея алгоритма сжатия rle. Сжатие способом кодирования серий: алгоритм RLE. Ограничение информационного алфавита

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

На чем основан алгоритм сжатия RLE?

Особенности

Варианты кодирования по длине

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

Кросс-кодирование

Как с помощью алгоритма RLE закодировать изображение?

Альтернативный вариант

Единицы измерения

Качество сжатия

Исключения

Оформление документа

Алгоритм RLE

Сравнение алгоритмов сжатия

Использование архиватора

Сжатие с потерями