Предисловие автора

В 1829 году Луи Брайль (Louis Braille), молодой органист одного парижского собора, который потерял зрение в раннем детстве в возрасте трех лет, изобрел знаменитый шрифт для слепых. Этот шрифт, названный его именем, широко распространился по всему миру, позволяя слепым людям читать и писать. Брайль слегка усовершенствовал свои коды в 1834 году. Было еще несколько незначительных изменений, однако осталось неизменным основное начертание символов или букв, каждая из которых представлена в виде блока точек 3x2. Эти точки выдавливаются на листе плотной бумаги, причем каждая может быть поднята вверх или опущена, что означает, она присутствует или отсутствует. Таким образом, каждая точка эквивалентна одному биту информации. В результате, шрифт Брайля (см. рис.1) представляет собой шестибитовый код, с помощью которого можно представить ровно 64 символа (блок, в котором все точки опущены, обозначает пустой символ или пробел).

Рис. 1. Алфавит Брайля.

Последователи Брайля расширили возможности его шрифта несколькими путями. Прежде всего они ввели сокращения. Некоторые отдельно стоящие буквы стали обозначать целые слова. Например, отдельно стоящая буква «Ь» (или со знаком препинания) обозначает слово «but» (мы будем вести речь об английском варианте шрифта Брайля). Одиночная буква «е» означает «every», а буква «р» - «people».

Другим полезным правилом стало использование сокращенных форм некоторых часто используемых слов, то есть, комбинации двух и более символов стали обозначать целые слова. Например, «аb» означает «about», «rev» - «receive», а буквосочетание «(the)mvs» - это «themselves». (Символы «the» в круглых скобках тоже имеют свой специальный код, в котором подняты точки 2-3-4-6.) На рис. 2 показаны некоторые специальные коды и соответствующие им слова или части слов.

Рис. 2. Некоторые сокращения и короткие слова.

Немного о Луи Брайле

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

Предшественницей этой книги послужила монография «Сжатие данных: полное руководство» («Data Compression: The Complete Reference»), опубликованная в 1977 году и переизданная в конце 2000 года. Быстрые и весьма благожелательные читательские отклики на это издание побудили меня к написанию этой небольшой книги. В первой книге я стремился самым подробным образом осветить как основные принципы сжатия данных, так и все детали множества специфических методов. Поэтому она вышла такой объемной. При написании новой книги я был менее амбициозен. В ней я задался целью провести неискушенного читателя по полям сжатия, чтобы он ощутил чудесный аромат этих полей. Это будет сделано с помощью представления основных приемов сжатия информации, а также с помощью описания ключевых алгоритмов. В книге совсем немного математики, нет упражнений, но зато имеется множество примеров, которые помогут проиллюстрировать основные методы.

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

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

Популярная техника словарного сжатия является предметом главы 2. Метод словарного сжатия основан на сохранении байтов и фрагментов сжимаемого файла в виде специальной структуры, называемой словарем. Для каждого нового фрагмента данных делается поиск в словаре. Если этот фрагмент находится в словаре, то в сжатый файл записывается ссылка на этот фрагмент. В этой главе описываются следующие известные алгоритмы компрессии этого типа: LZ77, LZSS, LZ78 и LZW.

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

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

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

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

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

Northridge, California                                                                                                            
David Salomon
Математика это трудно.
- Барби
Non mi legga chi поп e matematico.
(Пусть не читает меня не математик.)
- Леонардо да Винчи