Тема 5: Теоретические основы сжатия данных

Вид материала

Содержание

Подобный материал:

Тема 5: Теоретические основы сжатия данных

Характерной особенностью большинства «классических» типов данных, с которыми традиционно работают люди, является определенная избыточность. Степень избыточности зависит от типа данных. Например, у видеоданных степень избыточности обычно в несколько раз больше, чем у графических данных, а степень избыточности графических данных в несколько раз больше, чем текстовых. Кроме того, степень избыточности данных зависит от принятой системы кодирования. Так, например, можно сказать, что кодирование текстовой информации средствами русского языка (с использованием русской азбуки) дает в среднем избыточность на 20-30% больше, чем кодирование адекватной информации средствами английского языка.

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

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

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

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

Если методы сжатия информации применяют к готовым документам, то нередко термин сжатие данных подменяют термином архивация данных, а программные средства, выполняющие эти операции, называют архиваторами,

Объекты сжатия

В зависимости от того, в каком объекте размещены данные, подвергаемые сжатию, различают:

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

Обратимость сжатия

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

Если при сжатии данных происходит изменение их содержания, метод сжатия необратим и при восстановлении данных из сжатого файла не происходит полного восстановления исходной последовательности. Такие методы называют также методами сжатия с регулируемой потерей информации (losing compression). Они применимы только для тех типов данных, для которых формальная утрата части содержания не приводит к значительному снижению потребительских свойств. В первую очередь, это относится к мультимедийным данным: видеорядам, музыкальным записям, звукозаписям и рисункам. Методы сжатия с потерей информации обычно обеспечивают гораздо более высокую степень сжатия, чем обратимые методы, но их нельзя применять к текстовым документам, базам данных и, тем более, к программному коду.

Характерными форматами сжатия с потерей информации являются:

.JPG для графических данных;
.MPG для видеоданных;
MP3 для звуковых данных..

Если при сжатии данных происходит только изменение их структуры, то метод сжатия обратим. Из результирующего кода можно восстановить исходный массив путем применения обратного метода. Обратимые методы применяют для сжатия любых типов данных. Характерными форматами сжатия без потери информации (losless compression) являются:

.GIF, .ТIF, .РСХ и многие другие для графических данных;
.AVI для видеоданных;
.ZIP, .ARG, .RAR, .LZH, .LH, .CAB и многие другие для любых типов данных.

При исследовании методов сжатия данных следует иметь в виду существование следующих доказанных теорем,

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

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

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

Алгоритмы сжатия данных без потери информации

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

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

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

Алгоритм RLE

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

Например, для последовательности: 0; 0; 0; 127; 127; 0; 255; 255; 255; 255 (всего 10 байтов) образуется следующий вектор:

Значение	Коэффициент повтора
0	3
127	2
0	1
255	4

При записи в строку он имеет вид:

0; 3; 127; 2; 0; 1; 255; 4 (всего 8 байтов).

В данном примере коэффициент сжатия равен 8/10 (80 %).

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

Алгоритм KWE

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

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

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

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

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

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

Алгоритм Лемпеля-Зива (LZ77, LZW, LZH)

Используется идея адаптивного сжатия. Алгоритмы Лемпеля-Зива сводятся к поиску в потоке повторяющихся последовательностей и замене этих последовательностей на их номер в динамическом словаре. Различие состоит в способах кодирования номера и формировании словаря. За один проход по тексту одновременно динамически строится словарь и кодируется текст. При этом словарь не хранится – за счёт того, что при декодированинии используется тот же самый алгоритм построения словаря, словарь динамически восстанавливается. В сжатое представление записывается найденный код слова и расширенная буква, а словарь пополняется расширенной комбинацией. Поскольку номер последовательности в словаре содержит больше битов, чем символы исходного потока, алгоритмы Лемпеля-Зива предполагают дальнейшее перекодирование преобразованного потока кодом Хаффмена. Большинство современных архиваторов, такие, как PkZip, GNU Zip, RAR, основаны на вариациях и аналогах алгоритмов Лемпеля-Зива.

Таблица: Свойства алгоритмов сжатия

Алгоритм	Выходная структура	Сфера применения	Примечание
RLE (Run-Length Encoding)	Список (вектор данных)	Графические данные	Эффективность алгоритма не зависит от объема данных
KWE (Keyword Encoding)	Таблица данных (словарь)	Текстовые данные	Эффективен для массивов большого объема
Алгоритм Хафмана	Иерархическая структура (дерево кодировки)	Любые данные	Эффективен для массивов большого объема
Алгоритм Лемпела-Зива	Таблица данных (словарь)	Любые данные	Эффективен для массивов большого объема

Синтетические алгоритмы

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

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

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

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

Алгоритмы .JFIF (лежащий в основе распространенного формата хранения растровых изображений JPG), МРЕG, МРЗ начинаются с выполнения над входным потоком преобразования Фурье. JFIF удаляет из полученного спектра фиксированное количество частот - обычно самые слабые. Количество частот, которые надо выкинуть, определяется параметром настройки упаковщика. У JFIF этот параметр так и называется - коэффициентом упаковки, у МРЗ - битрейтом.

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

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

Сжатие изображений

Растровый формат, используемый в современных цифровых преобразователях изображений, предусматривает кодирование изображений в формате по три байта на пиксель, что приводит к созданию громоздких, неудобных в работе растровых файлов. Специально для этого формата было разработано множество схем сжатия, предназначенных для уменьшения места, занимаемого подобными файлами на диске. Одной из таких схем является формат GIF (Graphic Interchange Format), разработанный компанией CompuServe. Используемый в ней метод заключается в уменьшении количества цветовых оттенков пикселя до 256, в результате чего цвет каждого пикселя может быть представлен одним байтом вместо трех. С помощью таблицы, называемой цветовой палитрой, каждый из допустимых цветовых оттенков пикселя ассоциируется с некоторой комбинацией цветов "красный-зеленый-синий". Изменяя используемую палитру, можно изменять цвета, появляющиеся в изображении.

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

Другим примером системы сжатия изображений является формат JPEG. Это стандарт, разработанный ассоциацией Joint Photographic Experts Group в рамках организации ISO. Формат JPEG показал себя как эффективный метод представления цветных фотографий. Именно по этой причине данный стандарт используется производителями современных цифровых фотокамер. Следует ожидать, что он окажет немалое влияние на область цифрового представления изображений и в будущем.

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

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

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

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

В заключение следует отметить, что сейчас в области сжатия данных проводятся интенсивные и обширные исследования. Мы обсудили лишь два из множества существующих методов сжатия изображений. А ведь, помимо них, имеются еще многочисленные методы сжатия аудио- и видеоинформации. Например, метод, подобный режиму "базовых строк" формата JPEG, был разработан входящей в состав ISO ассоциацией Motion Picture Experts Group (MPEG) и принят в качестве стандарта кодирования (или сжатия) аудио- и видеоинформации. Суть этого стандарта состоит в записи начальной картинки последовательности изображений с помощью метода, подобного режиму "базовых строк" формата JPEG, после чего для кодирования оставшейся части изображений в их последовательности применяются методы относительного кодирования.

Сжатие звука

Наиболее широко распространенным способом кодирования аудиоинформации (в целях ее сохранения, обработки и передачи} является измерение значения амплитуды звуковой волны через регулярные интервалы времени и запись последовательности полученных значений. Чтобы получить необходимое качество звучания, на современных компакт-дисках музыка записывается с частотой выборки 44 100 значений в секунду. Каждое из значений записывается в 16-разрядном формате {для стереозаписей используется 32-разрядный формат). Следовательно, для хранения звуковых данных с продолжительностью звучания в одну секунду потребуется более миллиона битов памяти.

Подобные затраты памяти приемлемы для записи музыки на компакт-дисках, однако в сочетании с видеозаписью {для получения движущихся озвученных изображений} эти требования превышают возможности современной технологии. Поэтому ассоциация Motion Picture Experts Group (MPEG), входящая в состав ISO, разработала методы сжатия аудиоинформации, позволяющие существенно снизить требования к использованию памяти. Одним из таких форматов является МРЗ (MPEG-1, Audio Layer-3), позволяющий сжимать аудиоинформацию в соотношении 12:1.

Рекомендуемая литература:

Информатика. Базовый курс / Сименович С.В. и др. – СПб: Питер, 2001. – 640 с.
Вычислительные системы, сети и телекоммуникации / В.Л. Бройдо – СПб.: Питер, 2002. - 688 с.
Введение в компьютерные науки. Общий обзор, 6-е издание / Брукшир, Дж., Гленн.: Пер. С англ. – М.: Издательский дом «Вильямс», 2001. – 688 с.

Blog

Тема 5: Теоретические основы сжатия данных

Содержание