Алгоритмы сжатия информации. Сжатие данных

Сжатие данных (data compression) - технический прием сокращения объема (размеров) записи данных на их носителе (жестком магнитном диске, дискете, магнитной ленте); реализуется разными методами, преимущественно использующими кодирование (повторяющихся слов, фраз, символов). Можно выделить две группы режимов сжатия данных: статический и динамический; различают также физическое и логическое сжатие; симметричное и асимметричное сжатие; адаптивное, полуадаптивное и неадаптивное кодирование; сжатие без потерь, с потерями и минимизацией потерь. Способы (виды) сжатия данных:

Статическое сжатие данных (static data compression) - используется для длительного хранения и архивации; выполняется при помощи специальных сервисных программ-архиваторов, например ARJ, PKZIP/PKUNZIP. После восстановления (декомпрессии) исходная запись восстанавливается.
Динамическое сжатие (сжатие в реальном времени; dynamic compression, compression in real time) - предназначено для сокращения занимаемой области дисковой памяти данными, требующими оперативного доступа и вывода на внешние устройства ЭВМ (в том числе на экран монитора). Динамическое сжатие данных и их восстановление производится специальными программными средствами автоматически и «мгновенно».
Физическое сжатие (physical compression) - методология сжатия, при которой данные перестраиваются в более компактную форму «формально», то есть без учета характера содержащейся в них информации.
Логическое сжатие (logical compression) - методология, в соответствии с которой один набор алфавитных, цифровых или двоичных символов заменяется другим. При этом смысловое значение исходных данных сохраняется. Примером может служить замена словосочетания его аббревиатурой. Логическое сжатие производится на символьном или более высоком уровне и основано исключительно на содержании исходных данных. Логическое сжатие не применяется для изображений.
Симметричное сжатие (symmetric compression) - методология сжатия, в соответствии с которой принципы построения алгоритмов упаковки и распаковки данных близки или тесно взаимосвязаны. При использовании симметричного сжатия время, затрачиваемое на сжатие и распаковку данных, соизмеримо. В программах обмена данными обычно используется симметричное сжатие.
Асимметричное сжатие (asymmetric compression) - методология, в соответствии с которой при выполнении работ «в одном направлении» времени затрачивается больше, чем при выполнении работ в другом направлении. На сжатие изображений обычно затрачивается намного больше времени и системных ресурсов, чем на их распаковку. Эффективность этого подхода определяется тем, что сжатие изображений может производиться только один раз, а распаковываться с целью их отображения – многократно. Алгоритмы асимметричные «в обратном направлении» (на сжатие данных затрачивается меньше времени, чем на распаковку) используется при выполнении резервного копирования данных.
Адаптивное кодирование (adaptive encoding) - методология кодирования при сжатии данных, которая заранее не настраивается на определенный вид данных. Программы, использующие адаптивное кодирование, настраиваются на любой тип сжимаемых данных, добиваясь максимального сокращения их объема.
Неадаптивное кодирование (nonadaptive encoding) - методология кодирования, ориентированная на сжатие определенного типа или типов данных. Кодировщики, построенные по этому принципу, имеют в своем составе статические словари «предопределенных подстрок», о которых известно, что они часто появляются в кодируемых данных. Примером может служить метод сжатия Хаффмена.
Полуадаптивное кодирование (half-adaptive coding) - методология кодирования при сжатии данных, которая использует элементы адаптивного и неадаптивного кодирования. Принцип действия полуадаптивного кодирования заключается в том, что кодировщик выполняет две группы операций: вначале - просмотр массива кодируемых данных и построение для них словаря, а затем - собственно кодирование.
Сжатие без потерь (lossless compression) - методология сжатия, при которой ранее закодированная порция данных восстанавливается после их распаковки полностью без внесения изменений.
Сжатие с потерями (lossy compression) - методология, при которой для обеспечения максимальной степени сжатия исходного массива часть содержащихся в нем данных отбрасывается. Для текстовых, числовых и табличных данных использование программ, реализующих подобные методы сжатия, является неприемлемой. Однако для программ, работающих с графикой, это часто бывает целесообразно. Качество восстановленного изображения зависит от характера графического материала и корректности реализованного в программе алгоритма сжатия. Существует ряд алгоритмов сжатия, учитывающих допустимые уровни потерь исходного графического образа в конкретных вариантах использования его восстановленного изображения, например, путем просмотра его на экране монитора, распечатки принтером, в полиграфии. Эти методы имеют общее наименование «сжатия с минимизацией потерь».
Сжатие изображения (image compression) - технический прием или метод сокращения объема (размеров) записи графических изображений (рисунков, чертежей, схем) на их носителе (например, на магнитном диске, магнитной ленте). По существу «сжатие изображения» является разновидностью динамического сжатия. Для его реализации используются различные способы кодирования данных, которые ориентированы на элементы графики, составляющие изображение, включая и движущиеся объекты. Применяется также при передаче факсимильной информации по каналам связи, в системах мультимедиа, видеофонах.
Сжатие диска (disk compression) - технический прием, основанный на динамическом сжатии в процессе их записи на диск, а при считывании - их автоматическом восстановлении в исходную форму. Сжатие диска используется с целью увеличения емкости диска. В зависимости от характера записей емкость диска может быть увеличена примерно от 1, 5 до 5 раз. Сжатие диска осуществляется специальными прикладными программами, например DoubleSpace, Stacker, SuperStor.

Методы и средства сжатия данных:
Метод сжатия Хаффмена (Huffman compression method, кодирование CCITT) разработан в 1952 году Дэвидом Хаффменом (David Huffman). Международный консультативный комитет по телефонии и телеграфии (CCITT) разработал на его основе ряд коммуникативных протоколов для факсимильной передачи черно-белых изображений по телефонным каналам и сетям передачи данных (Стандарт T.4 CCIT и T.6 CCITT, они же - сжатие CCITT group 3 и сжатие CCITT group 4).
Фрактальное сжатие (fractal compression) - метод сжатия растровых изображений путем преобразования их в так называемые фракталы. Хранение изображений в виде фракталов требует в четыре раза меньше дисковой памяти, нежели в пикселях.
ART - метод для сжатия текста, графики, аудио и видео. Принцип работы алгоритма сжатия основан на анализе изображения и выявлении его ключевых признаков (цвет, помехи, края, повторяющиеся особенности).
AC3 Dolby - метод и формат сжатия, который позволяет сжимать, хранить и передавать в одном файле со скоростью от 32 до 640 кбит/с до 6 каналов аудиоданных.
DJVU (DjVu, djvu, deja vu) - технология и формат динамического сжатия отсканированных страниц изданий, содержащих текстовые и иллюстративные материалы.
DVI (Digital Video Interactive) - система динамического сжатия и восстановления аудио- и видеозаписей в цифровой форме. Ее использование позволяет записать на CD-ROM полноформатный видеофильм вместе со звуковым сопровождением.
EAD (Encoded Archival Description) - стандарт кодирования, разработанный подразделением Network Development and MARC Standards Office Библиотеки Конгресса США в сотрудничестве с Society of American Archivists в 1998 году (обновление - 2002 г.). Стандарт устанавливает принципы создания, разработки и поддержки схем кодирования для архивных и библиотечных помощников поиска (finding aids).
Image compression manager - программа управления динамическим сжатием изображений, которая обеспечивает возможность использования различных методов сжатия/восстановления изображений (MPEG, JPEG).
JBIG (Joint Bi-level Image Experts Group) - метод сжатия двухуровневых (двухцветных) изображений без потерь, создан Объединенной группой экспертов по двухуровневым изображениям ISO и CCIT в 1988 году. Метод JBIG в 1993 году утвержден как стандарт кодирования двухуровневых данных вместо менее эффективных алгоритмов сжатия MR (Modified READ) и MMR (Modified Modified READ).
LZW (Lempel-Ziv-Welch) - метод динамического сжатия, основанный на поиске во всем файле и сохранении в словаре одинаковых последовательностей данных (они называются фразы). Каждой уникальной последовательности данных присваиваются более короткие маркеры (ключи).
MP3 (Moving Pictures Experts Group, Layer 3) - метод (алгоритм) динамического сжатия и специальный формат записи файлов аудиоданных. MP3 обеспечивает высокую степень сжатия звуковых записей, используется в приложениях мультимедиа, в частности, в цифровых проигрывателях (плейерах) и Интернете.
RLE (Run Length Encoding) - метод динамического сжатия графических данных, в первую очередь изображений, основанный на уменьшении физического размера повторяющихся строк символов.

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

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

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

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

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

Для сложных изображений такой метод малоэффективен, поэтому в промышленных форматах применяют другие методы. Например, один из универсальных алгоритмов LZW (назван по фамилиям авторов Якоб Лемпель, Абрахам Зив и Терри Велч). Этот алгоритм подразумевает создание во время обработки специального словаря уже встречавшихся фрагментов. При кодировании последовательности байтов заменяются на их номера по словарю, причем номера часто встречающихся последовательностей имеют меньшее количество битов, чем редко встречающихся. Этот способ активно применяется при сжатии самых разных данных, в том числе и графических. Такой способ сжатия применяется в графическом формате TIFF, в популярном формате GIF. Аналогичные методы применяются и в современном формате PNG (P ortable N etwork G raphic ), разработанном специально для применения в сетевых приложениях.

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

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

Для решения этой проблемы группой специалистов был разработан специальный формат и способ сжатия, получивший название JPEG (J oint P hotographic E xpert G roup , объединенная группа экспертов-фотографов). Алгоритм сжатия, предложенный ими, подразумевал сжатие с потерей качества . Его достоинством было то, что “силу” сжатия можно было указывать изначально и таким образом находить компромисс между качеством и объемом изображения. Первый стандарт этого алгоритма был принят в 1991 году.

Алгоритм JPEG предусматривает перевод изображения в более пригодную для сжатия цветовую модель - YСrCb (Яркость, Хроматический красный, Хроматический синий). За счет того, что человеческий глаз более чувствителен к яркости, чем к цвету, появляется возможность сжимать цветовые компоненты сильнее. В дальнейшем операции над компонентами выполняются отдельно. Изображение разбивается на фрагменты размером 8 ґ 8 пикселей, и внутри объектов выполняется целый ряд преобразований, некоторые из которых сглаживают разницу между пикселями. В зависимости от заданного параметра степени сжатия можно сглаживать разницу сильнее или слабее.

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

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

Следующим шагом стала разработка группы методов, предназначенных для сжатия потоковых данных (видео и аудио). Существенной особенностью этих данных является их очень большой объем и постепенное изменение (из-за высокой частоты между двумя соседними кадрами, как правило, разница невелика). Сжатый видео- и/или аудиопоток характеризуется чаще всего общим показателем битрейтом (bit rate - битовая скорость) - количеством битов на одну секунду использования, которое получается после упаковки.

Первым был разработан и принят в 1992 году стандарт MPEG-1, включавший в себя способ сжатия видео в поток до 1,5 Мбит, аудио в поток 64, 128 или 192 Кбит/с на канал, а также алгоритмы синхронизации. Стандарт описывал не алгоритмы, а формат получающегося битового потока. Это позволило в дальнейшем разработать множество реализаций алгоритмов кодирования и декодирования. Стандарт применялся для создания видео и CD.

Особенную популярность завоевала реализация MPEG-1 для упаковки звука. Применяется для этого стандарт MPEG-1 Layer 3 (сокращенно названный MP3 ). При сжатии этим методом используется сжатие с потерей информации. Причем учитывается особенность слухового восприятия: если рядом расположены две частоты, то более громкая “перекрывает” более тихую. Таким образом, ее можно сгладить без ощутимой потери качества звука.

Следующим шагом была разработка и принятие в 1995 году стандарта MPEG-2, предусматривающего работу с более качественным видеопотоком, скорость которого могла изменяться от 3 до 10 Мбит/с. Эта группа методов применяется при создании DVD-дисков.

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

Несмотря на большое разнообразие, в основе всех этих алгоритмов лежит общий подход к кодированию/декодированию. Во-первых, одной из основ сжатия кадров является алгоритм JPEG. В рамках этого подхода рассматриваются три вида кадров: ключевой кадр, сохраняемый в потоке полностью (intrapictures), кадры, сжатые со ссылкой на предыдущее изображение (predicted), и кадры, ссылающиеся на два кадра (bidirection).

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

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

Технически кодеки - отдельные программы, вызываемые проигрывателями для декодирования потока, а средствами сохранения - для его сжатия . Кодек отмечается в начале файла (или сетевого потока), и его наличие - важное условие работы с мультимедиа-данными. Многие кодеки не поставляются с операционной системой, а устанавливаются дополнительно. Для удобства их часто собирают в пакеты (codec-pack).

Примеры программных средств

DivX, XviD, Lame MP3 encoder, QuickTime

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

Основоположником науки о сжатии информации принято считать Клода Шеннона. Его теорема об оптимальном кодировании показывает, к чему нужно стремиться при кодировании информации и насколько та или иная информация при этом сожмется. Кроме того, им были проведены опыты по эмпирической оценке избыточности английского текста. Шенон предлагал людям угадывать следующую букву и оценивал вероятность правильного угадывания. На основе ряда опытов он пришел к выводу, что количество информации в английском тексте колеблется в пределах 0,6 – 1,3 бита на символ. Несмотря на то, что результаты исследований Шеннона были по-настоящему востребованы лишь десятилетия спустя, трудно переоценить их значение .

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

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

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

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

Алфавит кода – множество всех символов входного потока. При сжатии англоязычных текстов обычно используют множество из 128 ASCII кодов. При сжатии изображений множество значений пиксела может содержать 2, 16, 256 или другое количество элементов.

Кодовый символ – наименьшая единица данных, подлежащая сжатию. Обычно символ – это 1 байт , но он может быть битом, тритом {0,1,2}, или чем-либо еще.

Кодовое слово – это последовательность кодовых символов из алфавита кода. Если все слова имеют одинаковую длину (число символов), то такой код называется равномерным (фиксированной длины) , а если же допускаются слова разной длины, то – неравномерным (переменной длины) .

Код – полное множество слов.

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

Фраза – фрагмент данных, помещаемый в словарь для дальнейшего использования в сжатии.

Кодирование – процесс сжатия данных.

Декодирование – обратный кодированию процесс, при котором осуществляется восстановление данных.

Отношение сжатия – одна из наиболее часто используемых величин для обозначения эффективности метода сжатия.

Значение 0,6 означает, что данные занимают 60% от первоначального объема. Значения больше 1 означают, что выходной поток больше входного (отрицательное сжатие, или расширение).

Коэффициент сжатия – величина, обратная отношению сжатия.

Значения больше 1 обозначают сжатие, а значения меньше 1 – расширение.

Средняя длина кодового слова – это величина, которая вычисляется как взвешенная вероятностями сумма длин всех кодовых слов.

L cp =p 1 L 1 +p 2 L 2 +...+p n L n ,

где – вероятности кодовых слов;

L 1 ,L 2 ,...,L n – длины кодовых слов.

Существуют два основных способа проведения сжатия.

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

Словарное сжатие – это методы сжатия, хранящие фрагменты данных в "словаре" (некоторая структура данных ). Если строка новых данных, поступающих на вход, идентична какому-либо фрагменту, уже находящемуся в словаре, в выходной поток помещается указатель на этот фрагмент. Лучшие словарные методы применяют метод Зива-Лемпела.

Рассмотрим несколько известных алгоритмов сжатия данных более подробно.

Метод Хаффмана

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

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

Префиксный код – это код, в котором никакое кодовое слово не является префиксом любого другого кодового слова. Эти коды имеют переменную длину.

Оптимальный префиксный код – это префиксный код , имеющий минимальную среднюю длину.

Алгоритм Хаффмана можно разделить на два этапа.

1. Определение вероятности появления символов в исходном тексте.

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

2. Нахождение оптимального префиксного кода.

   Далее находятся два символа a и b с наименьшими вероятностями появления и заменяются одним фиктивным символом x , который имеет вероятность появления, равную сумме вероятностей появления символов a и b . Затем, используя эту процедуру рекурсивно, находится оптимальный префиксный код для меньшего множества символов (где символы a и b заменены одним символом x ). Код для исходного множества символов получается из кодов замещающих символов путем добавления 0 или 1 перед кодом замещающего символа, и эти два новых кода принимаются как коды заменяемых символов. Например, код символа a будет соответствовать коду x с добавленным нулем перед этим кодом, а для символа b перед кодом символа x будет добавлена единица.

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

Пример 1 . Программная реализация метода Хаффмана.

#include "stdafx.h" #include using namespace std; void Expectancy(); long MinK(); void SumUp(); void BuildBits(); void OutputResult(char **Result); void Clear(); const int MaxK = 1000; long k, a, b; char bits; char sk; bool Free; char *res; long i, j, n, m, kj, kk1, kk2; char str; int _tmain(int argc, _TCHAR* argv){ char *BinaryCode; Clear(); cout << "Введите строку для кодирования: "; cin >> str; Expectancy(); SumUp(); BuildBits(); OutputResult(&BinaryCode); cout << "Закодированная строка: " << endl; cout << BinaryCode << endl; system("pause"); return 0; } //описание функции обнуления данных в массивах void Clear(){ for (i = 0; i < MaxK + 1; i++){ k[i] = a[i] = b[i] = 0; sk[i] = 0; Free[i] = true; for (j = 0; j < 40; j++) bits[i][j] = 0; } } /*описание функции вычисления вероятности вхождения каждого символа в тексте*/ void Expectancy(){ long *s = new long; for (i = 0; i < 256; i++) s[i] = 0; for (n = 0; n < strlen(str); n++) s]++; j = 0; for (i = 0; i < 256; i++) if (s[i] != 0){ j++; k[j] = s[i]; sk[j] = i; } kj = j; } /*описание функции нахождения минимальной частоты символа в исходном тексте*/ long MinK(){ long min; i = 1; while (!Free[i] && i < MaxK) i++; min = k[i]; m = i; for (i = m + 1; i <= kk2; i++) if (Free[i] && k[i] < min){ min = k[i]; m = i; } Free[m] = false; return min; } //описание функции подсчета суммарной частоты символов void SumUp(){ long s1, s2, m1, m2; for (i = 1; i <= kj; i++){ Free[i] = true; a[i] = 0; b[i] = 0; } kk1 = kk2 = kj; while (kk1 > 2){ s1 = MinK(); m1 = m; s2 = MinK(); m2 = m; kk2++; k = s1 + s2; a = m1; b = m2; Free = true; kk1--; } } //описание функции формирования префиксных кодов void BuildBits(){ strcpy(bits,"1"); Free = false; strcpy(bits],bits); strcat(bits] , "0"); strcpy(bits],bits); strcat(bits] , "1"); i = MinK(); strcpy(bits[m],"0"); Free[m] = true; strcpy(bits],bits[m]); strcat(bits] , "0"); strcpy(bits],bits[m]); strcat(bits] , "1"); for (i = kk2 - 1; i > 0; i--) if (!Free[i]) { strcpy(bits],bits[i]); strcat(bits] , "0"); strcpy(bits],bits[i]); strcat(bits] , "1"); } } //описание функции вывода данных void OutputResult(char **Result){ (*Result) = new char; for (int t = 0; i < 1000 ;i++) (*Result)[t] = 0; for (i = 1; i <= kj; i++) res] = bits[i]; for (i = 0; i < strlen(str); i++) strcat((*Result) , res]); } Листинг.

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

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

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

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

Принцип неравномерного кода для уменьшения информационного объема сообщения был реализован в азбуке Морзе. Однако, применение кода переменной длины создавало трудности разделения сообщения на отдельные кодовые слова. Эта проблема была решена Морзе путем применения символа-разделителя – паузы.

Префиксные коды

Теоретические исследования К. Шеннона и Р. Фано показали, что можно построить эффективный неравномерный код без использования разделителя. Для этого он должен удовлетворять условию Фано : ни одно кодовое слово не является началом другого кодового слова . Коды, удовлетворяющие условию Фано называются префиксными.

Префиксный код - это код, в котором ни одно кодовое слово не является началом другого кодового слова.

Шеннон и Фано предложили алгоритм построения эффективных сжимающих кодов переменной длины (алгоритм Шеннона – Фано). Однако, в некоторых случаях алгоритм давал неоптимальное решение.

Код Хаффмана

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

Построим код Хаффмана для текста «ОКОЛО КОЛОКОЛА КОЛ»

1. Строим список свободных узлов, упорядоченных по убыванию частоты появления буквы.
2. Выберем две наименее вероятные буквы и построим для них узел-предок («псевдобуква») с частотой, равной сумме частот узлов-потомков.
3. Менее вероятной букве ставим в соответствие 1, более вероятной – 0 (в следующем проходе соблюдаем порядок расстановки 0 и 1).
4. Удаляем обе буквы из списка, оставив их узел-предок.
5. Повторяем шаги, начиная с пункта 2, до тех пор, пока не останется один узел («метабуква»). Этот узел будет считаться корнем дерева.

Для получения кода каждого символа движемся от корня дерева до данного символа, выписывая по ходу нули и единицы. В нашем примере символы имеют следующие коды:

• О – 00
• К – 01
• Л – 10
• Пробел – 110
• А - 111

Современные архиваторы

Специальные программы

Лекция 6

Архиваторы – это программы для создания архивов. Архивы предназначены для хранения данных в удобном компактном виде. В качестве данных обычно выступают файлы и папки. Как правило, данные предварительно подвергаются процедуре сжатия или упаковки. Поэтому почти каждый архиватор одновременно является программой для сжатия данных. С другой стороны, любая программа для сжатия данных может рассматриваться как архиватор. Эффективность сжатия является важнейшей характеристикой архиваторов. От нее зависит размер создаваемых архивов. Чем меньше архив, тем меньше места требуется для его хранения. Для передачи нужна меньшая пропускная способность канала передачи или затрачивается меньшее время. Преимущества архивов очевидны, если учесть, что данные уменьшаются в размере и в 2 раза, и в 5 раз.

Сжатие данных используется очень широко. Можно сказать, почти везде. Например, документы PDF, как правило, содержат сжатую информацию. Довольно много исполняемых файлов EXE сжаты специальными упаковщиками. Всевозможные мультимедийные файлы (GIF, JPG, MP3, MPG) являются своеобразными архивами.

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

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

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

Кодирование длин серий (RLE - сокращение от run-length encoding - кодирование длин серий)

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

Словарный метод (LZ - сокращение от Lempel Ziv - имена авторов)

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

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

Энтропийный метод (Huffman - кодирование Хаффмена, Arithmetic coding - арифметическое кодирование)

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

Широко используется как дополнительный метод. В качестве самостоятельного метода применяется, например, в графическом формате JPG.

Метод контекстного моделирования (CM - сокращение от context modeling - контекстное моделирование)

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

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

PPM (PPM - Prediction by Partial Matching - предсказание по частичному совпадению)

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

Предварительные преобразования или фильтрация

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

Метод сортировки блока данных (BWT - сокращение от Burrows Wheeler Transform - по имени авторов)

Это особый вид или группа преобразований, в основе которых лежит сортировка. Такому преобразованию можно подвергать почти любые данные. Сортировка производится над блоками, поэтому данные предварительно разбиваются на части. Основным параметром является размер блока, который подвергается сортировке. Для распаковки данных необходимо проделать почти те же действия, что и при упаковке. Поэтому скорость и требования к оперативной памяти почти одинаковы. Архиваторы, которые используют данный метод, обычно показывают высокую скорость и степень сжатия для текстовых данных.

Непрерывные блоки или непрерывный режим (Solid mode - непрерывный режим)

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

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

Сегментирование

Во всех методах сжатия при изменении типа данных собственно сам переход кодируется очень плохо. Словарь становится не актуальным, модель настроена на другие данные. В этих случаях применяется сегментирование. Это предварительная разбивка на однородные части. Затем эти части кодируются по отдельности или группами.