157

ИНФОРМАЦИОННЫЕ

ТЕХНОЛОГИИ

Омск 2009

5

1. Кодирование и сжатие информации

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

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

ходный, называются необратимыми, приблизительными или сжи-

мающими с потерями (losing compression). Соответственно, методы,

которые позволяют это сделать, называются обратимыми, точными,

или сжимающими без потерь (losless compression).

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

В конце сороковых годов XX века основателем современной теории информации Шенноном, и независимо от него, Фано был разработан универсальный алгоритм построения оптимальных кодов. Более известый аналог этого алгоритма был предложен несколько позже Дэвидом Хаффманом [Huffman 1952]. Принцип построения этих кодов в целом соответствует логике, которой руководствовался Морзе,

— кодировать значения, которые часто повторяются в потоке, более короткими последовательностями битов.

Коды Хаффмана и Шеннона-Фано устраняют автокорреляции,

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

6

текстов на естественных и синтетических языках. Для упаковки данных такого рода в конце 70-х Лемпелем и Зиффом было предложено семейство алгоритмов, наиболее известные из которых - LZ77 и LZW [Lempel-Ziv 1978].

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

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

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

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

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

7

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

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

Сигнал при этом, конечно, искажается, но сильнее всего при этом страдает равномерно распределенный по спектру шум, что и требуется (рис. 1).

Рис. 1. Зашумленный сигнал и его спектральный образ (результат преобразования Фурье)

Алгоритмы JFIF (лежащий в основе распространенного формата хранения растровых изображений JPG), MPEG, MP3 [www.jpeg.org] тоже начинаются с выполнения над входным потоком преобразования Фурье. Но, в отличие от шумодава, JFIF удаляет из полученного спектра не частоты, которые ниже заданного порога, а фиксированное количество частот — конечно же, стараясь отобрать самые слабые. Количество частот, которые надо выкинуть, определяется параметром настройки упаковщика. У JFIF этот параметр так и называется — коэффициентом упаковки, у МРЗ — битрейтом. Профильтрованный сигнал заведомо содержит автокорреляции — даже если исходный, незашумленный, сигнал их и не содержал, такая фильтрация их создаст — и потому легко поддается упаковке. Благодаря этому, все перечисленные алгоритмы обеспечивают гарантированный уровень

8

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

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

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

2. Передача данных и контрольные суммы

Хранение данных и их передача часто сопровождается или может сопровождаться ошибками. Приемнику и передатчику информации

9

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

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

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

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

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

10