Сжатие. Групповое сжатие. Сжатие методом RLE

Размещено на http://www.allbest.ru/

Министерство образования и науки РФ

Федеральное государственное учреждение

Высшего профессионального образования

Кафедра высшей математики и информационных технологий

Реферат

По предмету

Теория кодирования

«Сжатие. Групповое сжатие. Сжатие методом RLE»

2009г.

Введение

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

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

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

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

Групповое сжатие (RLE)

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

abbbbzzzzddaaaaaffffuu

После применения группового сжатия эта последовательность будет преобразована в:

1a4b4z2d5a4f2u

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

При кодировании exe-файлов можно искать и упаковывать последовательности вида AxAyAzAwAt..., которые часто встречаются в ресурсах (строки в кодировке Unicode)

К положительным сторонам алгоритма, можно отнести то, что он не требует дополнительной памяти при работе, и быстро выполняется. Алгоритм применяется в форматах РСХ, TIFF, ВМР. Интересная особенность группового кодирования в PCX заключается в том, что степень архивации для некоторых изображений может быть существенно повышена всего лишь за счет изменения порядка цветов в палитре изображения.

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

Рассмотрим одну из популярных реализаций группового сжатия PackBits (впервые была предложена компанией Apple для сжатия bitmap данных на Apple MacIntosh). Предполагая, что значения пикселей являются 8-битными данными, PackBits кодирует регулярные величины двумя байтами. Первый байт содержит число n, находящееся в диапазоне [?127..?1], второй байт содержит значение, которое повторяется ?n + 1 раз. Неповторяющиеся величины, такие как «djlrf», предваряются 1-байтовым стартовым кодом m, соответствующим уменьшенной на 1 длине последовательности, то есть, длина последовательно неповторяющихся величин будет равна m + 1 (для «djlrf» m будет равно 4). Повторяющиеся последовательности так же, как и последовательности неповторяющихся величин, не могут быть больше 128 символов, а следовательно, при большей длине должны быть разбиты на составляющие последовательности.

NB! Обычно сжатие не переходит из одной строки развертки в другую.

Процесс декомпрессии интуитивно понятен. Последовательно просматриваем сжатую последовательность, действуя по следующему алгоритму:

Считываем текущий байт (k), длина (l) последовательности устанавливается в значение |k| + 1. Если число k отрицательно, то выполняется второй шаг, иначе происходит переход на третий шаг.

l штук текущего байта записываются на выход.

l байт из сжатой последовательности записываются на выход.

Если последовательность не закончилась, то возвращаемся к первому шагу.

Несложно показать, что время работы алгоритма (как компрессии, так и декомпрессии) пропорционально O(n).

Групповое кодирование используется во многих форматах bitmap, например, в MacPaint, TIFF, PCX.

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

Если мы запишем ее просто цветами, то она займет весьма заметное место:

ggbbbggyrrrrrbbybybg.

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

2g 3b 2g 1y 5r 2b 5(ybybg)

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

Реально это сжатие имеет смысл применять при обработке простого однотонного рисунка. Единственным его плюсом является простота реализации.

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

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

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

Initialization(...);

do {

byte = ImageFile.ReadNextByte();

if(является счетчиком(byte)) {

counter = Low6bits(byte)+1;

value = ImageFile.ReadNextByte();

for(i=1 to counter)

DecompressedFile.WriteByte(value)

}

else {

DecompressedFile.WriteByte(byte)

} while(ImageFile.EOF());

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

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

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

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

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

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:

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

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

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

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

Резюме

Алгоритм Коэфф-ты сжатия Симметричность по времени На что ориентирован Потери Размерность

Групповое кодирование 1/32 1/2 2/1 1 3,4 битные Нет 1D

LZW 1/100 1/4 7/5 1.2-3 1-8 битные Нет 1D

Хаффмана 1/8 2/3 1/1 1-1.5 1-битные Нет 1D

JBIG 1.5 раза ~1 1-битные Нет 2D

Lossless JPEG 2 раза ~1 24-битн. сер. Нет 2D

Рекурс. сжатие 2-20 раз 1.5 серые Да 2D

JPEG 2-200 раз ~1 24-битн. сер. Да 2D

Фрактальный 2-2000 раз 1000-10000 24-битн. сер. Да 2D

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

ПРИМЕНЕНИЕ RLE-КОДИРОВАНИЯ КАК ОСНОВНОГО МЕТОДА СЖАТИЯ ИНФОРМАЦИИ В СИСТЕМАХ ПЕРЕДАЧИ И ХРАНЕНИЯ

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

Количество нужной человеку информации неуклонно растет. Объемы устройств для хранения данных и пропускная способность линий связи также растут. Однако количество информации растет быстрее. У этой проблемы есть три решения. Первое - ограничение количества информации. К сожалению, оно не всегда приемлемо. Например, для изображений это означает уменьшение разрешения, что приведет к потере мелких деталей и может сделать изображения вообще бесполезными (например, для медицинских или космических изображений). Второе - увеличение объема носителей информации и пропускной способности каналов связи. Это решение связано с материальными затратами, причем иногда весьма значительными. Третье решение - использование сжатия информации. Это решение позволяет в несколько раз сократить требования к объему устройств хранения данных и пропускной способности каналов связи без дополнительных издержек (за исключением издержек на реализацию алгоритмов сжатия). Условиями его применимости является избыточность информации и возможность установки специального программного обеспечения либо аппаратуры как вблизи источника, так и вблизи приемника информации. Как правило, оба эти условия удовлетворяются [1].

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

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

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

Основоположником науки о сжатии информации принято считать Клода Шеннона. Его теорема об оптимальном кодировании показывает, к чему нужно стремиться при кодировании информации и на сколько та или иная информация при этом сожмется.

Несмотря на то, что результаты исследований Шеннона были по- настоящему востребованы лишь десятилетия спустя, трудно переоценить их значение.

Первые алгоритмы сжатия были примитивными в связи с тем, что была примитивной вычислительная техника. С развитием мощностей компьютеров стали возможными все более мощные алгоритмы. Настоящим прорывом было изобретение Лемпелем и Зивом в 1977 г. словарных алгоритмов. До этого момента сжатие сводилось к примитивному кодированию символов. Словарные алгоритмы позволяли кодировать повторяющиеся строки символов, что позволило резко повысить степень сжатия. Важную роль сыграло изобретение примерно в это же время арифметического кодирования, позволившего воплотить в жизнь идею Шеннона об оптимальном кодировании. Следующим прорывом было изобретение в 1984г. алгоритма PPM. Следует отметить, что это изобретение долго оставалось незамеченным. Дело в том, что алгоритм сложен и требует больших ресурсов, в первую очередь больших объемов памяти, что было серьезной проблемой в то время. Изобретенный в том же 1984 г. алгоритм LZW был чрезвычайно популярен благодаря своей простоте, хорошей рекламе и нетребовательности к ресурсам, несмотря на относительно низкую степень сжатия. На сегодняшний день алгоритм PPM является наилучшим алгоритмом для сжатия текстовой информации, а LZW давно уже не встраивается в новые приложения (однако широко используется в старых).

Алгоритм RLE (Run Length Encoding, упаковка, кодирование длин серий) является самым быстрым, простым и понятным алгоритмом сжатия данных и при этом иногда оказывается весьма эффективным. Это один из наиболее старых методов сжатия. Суть этого метода заключается в замене идущих подряд одинаковых символов числом, характеризующим их количество. Конечно, также мы должны и указать признак «включения» механизма кодирования длин повторов, который можем распознать при декодировании.

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

Пусть дано достаточно большое простое число - 4294966553, которое в двоичной системе счисления примет вид:

11111111111111111111110100011001

а шестнадцетиричной - FFFFFD19

Один из возможных вариантов - включать кодирование, когда число повторяющихся символов превысит некоторый порог. Например, если мы условимся, что порог равняется трем символам, то последовательность «FFFFFD19» в результате кодирования будет выглядеть как «FFF2D01090». Если мы выберем в качестве порога 4 символа, то получим «FFF1D01090».

Главное назначение кодирования длин повторов - увеличить скорость сжатия и разжатия.

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

кодирование сжатие информация

Заключение

Будущее алгоритмов сжатия тесно связано с будущим компьютерных технологий. Современные алгоритмы уже вплотную приблизились к Шенноновской оценке 1.3 бита на символ, но ученые не видят причин, по которым компьютер не может предсказывать лучше, чем человек. Для достижения высоких степеней сжатия приходится использовать более сложные алгоритмы. Однако существовавшее одно время предубеждение, что сложные алгоритмы с более высокой степенью сжатия всегда более медленны, несостоятельно. Так, существуют крайне быстрые реализации алгоритмов PPM для текстовой информации и SPIHT для графики, имеющие очень высокую степень сжатия. Таким образом, будущее за новыми алгоритмами с высокими требованиями к ресурсам и все более и более высокой степенью сжатия. Устаревают не только алгоритмы, но и типы информации, на которые они ориентированы. Так, на смену графике с малым числом цветов и неформатированному тексту пришли высококачественные изображения и электронные документы в различных форматах. Известные алгоритмы не всегда эффективны на новых типах данных. Это делает крайне актуальной проблему синтеза новых алгоритмов.

Литература

1. Рябко В. Сжатие данных. - М.: Радио и связь, 1985. - 480 с.

2. Ватолин Д., Ратушняк А., Смирнов М., Юкин В. Методы сжатия данных.

3.Устройство архиваторов, сжатие изображений и видео. - М.: ДИАЛОГ-МИФИ, 2002.

Размещено на Allbest.ru