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

Методы сжатия информации

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

Сжатие с потерей информации означает, что после распаковки архива будет получен документ, несколько отличающийся от исходного. Чем больше сжатие, тем соответственно больше потери. Такие методы применяются, когда можно пожертвовать несколькими процентами информации, для фотографий, видеоданных и музыки. При потери нескольких процентов информации достигается сжатие в несколько десятков раз, 10 - 15 для музыки и
20 - 30 для фото и видеоматериалов.

К алгоритмам данного класса относятся алгоритмы JPEG и MPEG. Алгоритм JPEG используется для сжатия фотоизображений (графики). Графические файлы, сжатые этим алгоритмом, имеют расширение JPG. Алгоритм MPEG используется для сжатия видео и музыки. Сжатые файлы имеют расширение MPG для видео и MP3 для музыки.

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

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

Методы сжатия, при которых не допустима потеря информации, основаны на устранении избыточности информации.

Алгоритмы ХАФМАНА основаны на перекодировки информации. При кодировке данных по таблице ASCII для кодирования любого символа используется одинаковое число бит – 8. Но есть символы, которые встречаются часто, например А или О, и которые встречаются редко. Программы для сжатия информации имеют свою таблицу перекодировки символов, меньшим числом бит, и приписывают её сжатому файлу.

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

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

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

Программы – архиваторы позволяют (стандартный набор функций):

Создавать архивный файл, то есть помещать в один файл группу файлов;

Распаковывать архив, то есть разместить в указанной папке все файлы архива;

Извлекать из архива выбранные файлы в указанный каталог;

Просматривать оглавление архива;

Добавлять новые файлы;

Обновлять файлы в архиве;

Удалять файлы из архива;

Создавать самораспаковывающиеся архивы;

Создавать многотомные архивы;

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

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

Имя файла, возможно имена папок;

Дата и время последней модификации файла;

Размер файла на диске в архиве, степень сжатия;

Код циклического контроля, который используется для проверки целостности архива;

Состав информации зависит от программы - архиватора.

Для архивирования данных в Windows широко известны программы WinZip и WinRar.

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

Команда ДОБАВИТЬ (ADD) позволяет, как создать новый архив, так и добавить в архив.

Метод обновления:

- Добавить и заменить (Add and Replace Files) – все выбранные файлы включаются в архив, если файл существует, то он заменяется новым;

"Сжатие данных"

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

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

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

Сжатие (архивация) файлов: используется для уменьшения размеров файлов при подготовке их к передаче каналами связи или к транспортированию на внешних носителях маленькой емкости;

Сжатие (архивация) папок: используется как средство уменьшения объема папок перед долгим хранением, например, при резервном копировании;

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

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

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

JPEG - для графических данных;

MPG - для для видеоданных;

MP3 - для аудиоданных.

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

GIF, TIFF - для графических данных;

AVI - для видеоданных;

ZIP, ARJ, RAR, CAB, LH - для произвольных типов данных.

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

алгоритм RLE (Run Length Encoding);

алгоритмы группы KWE(KeyWord Encoding);

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

Алгоритм RLE

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

1 1 1 1 2 2 3 4 4 4

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

где Vx- объем памяти, необходимый для хранения выходной (результирующей) последовательности данных, Vn- входной последовательности данных.

Чем меньше значение коэффициента сжатия, тем эффективней метод сжатия. Понятно, что алгоритм RLE будет давать лучший эффект сжатия при большей длине повторяющейся последовательности данных. В случае рассмотренного выше примера, если входная последовательность будет иметь такой вид: 1 1 1 1 1 1 3 4 4 4, то коэффициент сжатия будет равен 60%. В связи с этим большая эффективность алгоритма RLE достигается при сжатии графических данных (в особенности для однотонных изображений).

Алгоритмы группы KWE

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

Существует довольно много реализаций этого алгоритма, среди которых наиболее распространенными являются алгоритм Лемпеля-Зіва (алгоритм LZ) и его модификация алгоритм Лемпеля-Зіва-Велча (алгоритм LZW). Словарем в данном алгоритме является потенциально бесконечный список фраз. Алгоритм начинает работу с почти пустым словарем, который содержит только одну закодированную строку, так называемая NULL-строка. При считывании очередного символа входной последовательности данных, он прибавляется к текущей строке. Процесс продолжается до тех пор, пока текущая строка соответствует какой-нибудь фразе из словаря. Но рано или поздно текущая строка перестает соответствовать какой-нибудь фразе словаря. В момент, когда текущая строка представляет собой последнее совпадение со словарем плюс только что прочитанный символ сообщения, кодер выдает код, который состоит из индекса совпадения и следующего за ним символа, который нарушил совпадение строк. Новая фраза, состоящая из индекса совпадения и следующего за ним символа, прибавляется в словарь. В следующий раз, если эта фраза появится в сообщении, она может быть использована для построения более длинной фразы, что повышает меру сжатия информации.

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

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

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

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

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

Пусть задан текст, в котором бурва "А" входит 10 раз, буква "В" - 8 раз, "С"- 6 раз, "D" - 5 раз, "Е" и "F" - по 4 раза. Тогда один из возможных вариантов кодирования по алгоритму Хаффмана приведен в таблицы 1.

Таблица 1.

	Частота вхождения	Битовый код

Как видно из таблицы 1, размер входного текста до сжатия равен 37 байт, тогда как после сжатия - 93 бит, то есть около 12 байт (без учета длины словаря). Коэффициент сжатия равен 32%. Алгоритм Хаффмана универсальный, его можно применять для сжатия данных любых типов, но он малоэффективен для файлов маленьких размеров (за счет необходимости сохранение словаря).

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

Таблица 2.

Формат сжатия	Операционная система MS DOS		Операционная система Windows
Формат сжатия	Программа архивации	Программа разархивации	Программа архивации	Программа разархивации

Кроме того, современные архиваторы предоставляют пользователю полный спектр услуг для работы с архивами, основными из которых являются:

создание нового архива;

добавление файлов в существующий архив;

распаковывание файлов из архива;

создание самораспаковающихся архивов (self-extractor archive);

создание распределенных архивов фиксированного размера для носителей маленькой емкости;

защита архивов паролями от несанкционированного доступа;

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

поиск файлов и данных внутри архива;

проверка на вирусы в архиве к распаковыванию;

выбор и настройка коэффициента сжатия.

Контрольные вопросы

1. Какие факторы влияют на степень избыточности данных? 2. Что такое архив? Какие программные средства называются архиваторами? 3. Почему методы сжатия, при которых происходит изменение содержимого данных, называются необратимыми? 4. Приведите примеры форматов сжатия с потерями информации. 5. В чем состоит преимущество обратимых методов сжатия над необратимыми? А недостаток? 6. Которая существует зависимость между коэффициентом сжатия и эффективностью метода сжатия? 7. В чем состоит основная идея алгоритма RLE? 8. В чем состоит основная идея алгоритмов группы KWE? 9. В чем состоит основная идея алгоритма Хаффмана? 10. Какие вы знаете програми-архиваторы? Коротко охарактеризуйте их.

Информатика. Базовый курс. / Под ред. С.В.Симоновича. - СПб., 2000 г.

А.П.Микляев, Настольная книга пользователя IBM PC 3-издание М.:, "Солон-Р", 2000, 720 с.

Симонович С.В., Евсеев Г.А., Мураховский В.И. Вы купили компьютер: Полное руководство для начинающих в вопросах и ответах. - М.: АСТ-ПРЕСС КНИГА; Инфорком-Пресс, 2001.- 544 с.: ил. (1000 советов).

Ковтанюк Ю.С., Соловьян С.В. Самоучитель работы на персональном компьютере - К.:Юниор, 2001.- 560с., ил.

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

1. Сжатие (архивация) файлов: используется для уменьшения размеров файлов при подготовке их к передаче каналами связи или к транспортированию на внешних носителях маленькой емкости;

2. Сжатие (архивация) папок: используется как средство уменьшения объема папок перед долгим хранением, например, при резервном копировании;

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

· JPEG - для графических данных;

· MPG - для для видеоданных;

· MP3 - для аудиоданных.

· GIF, TIFF - для графических данных;

· AVI - для видеоданных;

· ZIP, ARJ, RAR, CAB, LH - для произвольных типов данных.

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

Теория и стратегия представления данных

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

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

Что понимается под сжатием данных? Если говорить кратко, то сжатие устраняет из данных избыточность ; в терминах же теории информации сжатие увеличивает энтропию сжатого текста. Однако оба этих утверждения по существу по существу верны в силу определения самих понятий. Избыточность может быть выражена в самых разных формах. Одним типом является последовательности повторяющихся битов (11111111). Вторым – последовательности повторяющихся байтов (XXXXXXXX). Однако чаще избыточность проявляется в более крупном масштабе и выражается либо закономерностями в наборе данных, взятом как единое целое, либо последовательностями различной длины, имеющими общие признаки. По существу, цель сжатия данных заключается в поиске алгоритмических преобразований представлений данных, которые позволят получить более компактные представления «типовых» наборов данных. Это описание может показаться несколько туманным, но мы постараемся раскрыть его суть на практических примерах.

Сжатие без потерь и с потерями

Фактически существуют два в корне различающихся подхода к сжатию данных: сжатие с потерями и без потерь. Эта статья, в основном, посвящена методам сжатия без потерь, но для начала полезно изучить различия. Сжатие без потерь предусматривает преобразование представления набора данных таким образом, чтобы затем можно было в точности воспроизвести первоначальный набор данных путем обратного преобразования (распаковки). Сжатие с потерями – это представление, которое позволяет воспроизводить нечто «очень похожее» на первоначальный набор данных. Преимущество использования методов сжатия с потерями заключается в том, что они зачастую позволяют получать намного более компактные представления данных по сравнению с методами сжатия без потерь. Чаще всего методы сжатия с потерями применяются для обработки изображений, звуковых файлов и видео. Сжатие с потерями в этих областях может оказаться уместным благодаря тому, что человек воспринимает битовую комбинацию цифрового изображения/звука не с «побитовой» точностью, а скорее оценивает музыку или изображение в целом.

С точки зрения «обычных» данных сжатие с потерями – неудачный вариант. Нам не нужна программа, которая делает «примерно» то, а не точно то, что было запрошено в действительности. То же касается и баз данных, которые должны хранить именно те данные, которые были в них загружены. По крайней мере, это не подойдет для решения большинства задач (и мне известно очень мало практических примеров использования сжатия с потерями за пределами тех данных, которые сами по себе описывают чувственное восприятие реального мира (например, изображений и звуков)).

Пример набора данных

В данной статье будет использоваться специально подготовленное гипотетическое представление данных. Приведем простой для понимания пример. В городе Гринфилд (штат Массачусетс, США) используются префиксы телефонных номеров 772- , 773- и 774- . (К сведению читателей за пределами США: в США местные телефонные номера являются семизначными и традиционно представляются в виде ###-####; префиксы назначаются в соответствии с географическим местоположением). Также предположим, что из всех трех префиксов чаще всего используется первый. Частями суффикса могут быть любые другие цифры с приблизительно равной вероятностью. Набор интересующих нас данных находится в «списке всех телефонных номеров, которые в настоящее время находятся в активном пользовании». Можно попробовать подобрать причину, почему это могло бы быть интересным с точки зрения программирования, но в данном случае это не важно.

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

Таблица 1. Многоколоночный отчет

============================================================= 772-7628 772-8601 772-0113 773-3429 774-9833 773-4319 774-3920 772-0893 772-9934 773-8923 773-1134 772-4930 772-9390 774-9992 772-2314 [...]

Сжатие пустых мест

Сжатие пустых мест может быть охарактеризовано в более общем смысле как «удаление того, что нас не интересует». Даже несмотря на то, что этот метод с технической точки зрения представляет собой метод сжатия с потерями, он все равно полезен для многих типов представлений данных, с которыми мы сталкиваемся в реальном мире. Например, даже несмотря на то, что HTML намного удобнее читать в текстовом редакторе при добавлении отступов и междустрочных интервалов, ни одно из этих «пустых мест» никак не влияет на визуализацию HTML-документа в Web-браузере. Если вам точно известно, что конкретный документ HTML предназначается исключительно для Web-браузера (или для какого-либо робота/поискового агента), то, возможно, будет неплохо убрать все пустые места, чтобы документ передавался быстрее и занимал меньше места в хранилище. Все то, что мы удаляем при сжатии пустых мест, в действительности не несет никакой функциональной нагрузки.

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

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

Групповое кодирование

Групповое кодирование (RLE) является простейшим из широко используемых методов сжатия без потерь. Подобно сжатию пустых мест, оно не требует особых затрат, особенно для декодирования. Идея, стоящая за данным методом, заключается в том, что многие представления данных состоят большей частью из строк повторяющихся байтов. Наш образец отчета является одним из таких представлений данных. Он начинается со строки повторяющихся символов «=» и имеет разбросанные по отчету строки, состоящие только из пробелов. Вместо того чтобы представлять каждый символ с помощью его собственного байта, метод RLE предусматривает (иногда или всегда) указание количества повторений, за которым следует символ, который необходимо воспроизвести указанное число раз.

Если в обрабатываемом формате данных преобладают повторяющиеся байты, то может быть уместным и эффективным использование алгоритма, в котором один или несколько байтов указывают количество повторений, а затем следует повторяемый символ. Однако если имеются строки символов единичной длины, для их кодирования потребуются два (или более) байта. Другими словами, для одного символа ASCII «X» входного потока мог бы потребоваться выходной битовый поток 00000001 01011000 . С другой стороны, для кодирования ста следующих друг за другом символов «X» использовалось бы то же самое количество битов: 01100100 01011000 , что весьма эффективно.

В различных вариантах RLE часто применяется избирательное использование байтов для указания числа повторений, в то время как остальные байты просто представляют сами себя. Для этого должно быть зарезервировано как минимум одно однобайтовое значение, которое в случае необходимости может удаляться из выходных данных. Например, в нашем образце отчета по телефонным номерам известно, что вся информация во входном потоке состоит из простых символов ASCII. В частности, у всех таких символов первый бит ASCII-значения равен 0. Мы могли бы использовать этот первый бит ASCII для указания на то, что байт указывает число повторений, а не обычный символ. Следующие семь битов байта итератора могли бы использоваться для указания числа повторений, а в следующем байте мог бы содержаться повторяющийся символ. Так, например, мы могли бы представить строку «YXXXXXXXX» следующим образом:

"Y" Iter(8) "X" 01001111 10001000 01011000

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

Кодирование по методу Хаффмана

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

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

Таблица 2. Результаты кодирования по методу Хаффмана

Encoding Symbol 1 7 010 2 011 3 00000 4 00001 5 00010 6 00011 8 00100 9 00101 0 00111 1

Исходный набор символов (состоящий из чисел) может быть легко закодирован (без сжатия) в виде 4-х битных последовательностей (полубайтов). Приведенное кодирование по методу Хаффмана будет использовать до 5 битов для символов в наихудшем случае, что очевидно хуже кодирования с помощью полубайтов. Однако в лучшем случае потребуется всего 1 бит; при этом известно, что именно лучший случай будет использоваться чаще всего (так как именно этот символ чаще всего встречается в данных). Таким образом, мы могли бы закодировать конкретный телефонный номер следующим образом:

772 7628 --> 1 1 010 1 00010 010 00011

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

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

Сжатие по алгоритму Лемпеля-Зива

Вероятно, самым значимым методом сжатия без потерь является алгоритм Лемпеля-Зива. В этой статье речь пойдет о варианте LZ78, но LZ77 и другие варианты работают схожим образом. Идея, заложенная в алгоритме LZ78, заключается в кодировании потоковой последовательности байтов с использованием некоторой динамической таблицы. В начале сжатия битового потока таблица LZ заполняется фактическим набором символов, наряду с несколькими пустыми слотами. В алгоритме применяются таблицы разных размеров, но в данном примере с телефонными номерами (со сжатием пустых мест) используется таблица из 32 элементов (этого достаточно для данного примера, но может оказаться мало для других типов данных). Вначале мы заполняем первые десять слотов символами используемого алфавита (цифрами). По мере поступления новых байтов сначала выводится значение из таблицы, соответствующее самой длинной подходящей последовательности, а затем в следующий доступный слот записывается последовательность длиной N+1. В наихудшем случае мы используем 5 битов вместо 4 для отдельного символа, однако в большинстве случаев мы сможем обойтись 5 битами на несколько символов. Рассмотрим пример работы этого алгоритма (слот таблицы указан в квадратных скобках):

7 --> Поиск: 7 найдено --> добавлять нечего --> продолжить поиск 7 --> Поиск: 77 не найдено --> добавить "77" to --> вывести =00111 2 --> Поиск: 72 не найдено --> добавить "72" to --> вывести =00111 7 --> Поиск: 27 не найдено --> добавить "27" to --> вывести =00010 6 --> Поиск: 76 не найдено --> добавить "76" to --> вывести =00111 2 --> Поиск: 62 не найдено --> добавить "62" to --> вывести =00110 8 --> Поиск: 28 не найдено --> добавить "28" to --> вывести =00010

До сих пор мы не извлекли из этого никакой пользы, но давайте перейдем к следующему телефонному номеру:

7 --> Поиск: 87 не найдено --> добавить "87 to --> вывести =00100 7 --> Поиск: 77 найдено --> добавлять нечего --> продолжить поиск 2 --> Поиск: 772 не найдено --> добавить "772" to --> вывести =01011 8 --> Поиск: 28 найдено --> добавлять нечего --> продолжить поиск 6 --> Поиск: 286 не найдено --> добавить "286" to --> вывести =10000 ....

Приведенных операций должно быть достаточно для демонстрации работы модели. Хотя никакого заметного сжатия пока не достигнуто, уже видно, что мы повторно использовали слоты 11 и 16, закодировав по два символа одним выходным символом. Кроме того, мы уже накопили крайне полезную последовательность байтов 772 в слоте 18, которая впоследствии неоднократно будет встречаться в потоке.

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

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

Правильная постановка задачи

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

Необходимо еще раз взглянуть на проблему, которую представляют данные. Так как это не общий набор данных и для него существуют четкие предварительные требования, то проблему можно переформулировать. Известно, что существует максимум 30000 телефонных номеров (от 7720000 до 7749999), некоторые из которых являются активными, а некоторые – нет. Перед нами не стоит задача вывести полное представление всех активных номеров. Нам просто требуется указать с помощью логического значения, активен данный номер или нет. Размышляя о проблеме подобным образом, мы можем просто выделить 30000 битов в памяти и в системе хранения и использовать каждый бит для индикации активности («да» или «нет») соответствующего телефонного номера. Порядок битов в битовом массиве может соответствовать телефонным номерам, отсортированным по возрастанию (от меньшего к большему).

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

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

Посвящается памяти Клода Шеннона (Claude Shannon).

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

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

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

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

В качестве примеров алгоритмов сжатия графических данных без потерь можно привести алгоритм 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