Сжатие данных (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) - метод динамического сжатия графических данных, в первую очередь изображений, основанный на уменьшении физического размера повторяющихся строк символов.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Метод кодирования длины серий

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

Пример. Используя метод кодирования длины серий последовательность: 111111111100000000000000000 - можно представить в следующем виде: 10.

Метод относительного кодирования

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

Пример. Используя метод относительного кодирования, последовательность цифр: 1476; 1473; 1480; 1477 - можно представить в следующем виде: 1476; -3; +7; -3.

Частотно-зависимое кодирование

Этот метод сжатия данных предполагает применение частотно-зависимого кодирования, при котором длина битовой комбинации, представляющей элемент данных, обратно пропорциональна частоте использования этого элемента. Такие коды входят в группу кодов переменной длины, т.е. элементы данных в этих кодах представляются битовыми комбинациями различной длины. Если взять английский текст, закодированный с помощью частотно-зависимого метода, то чаще всего встречающиеся символы [е, t, а, i] будут представлены короткими битовыми комбинациями, а те знаки, которые встречаются реже , - более длинными битовыми комбинациями. В результате мы получим более короткое представление всего текста, чем при использовании обычного кода, подобного Unicode или ASCII. Построение алгоритма, который обычно используется при разработке частотно-зависимых кодов, приписывают Девиду Хаффману , поэтому такие коды часто называются кодами Хаффмана. Большинство используемых сегодня частотно-зависимых кодов является кодами Хаффмана.

Пример. Пусть требуется закодировать частотно-зависимым методом последовательность: αγααβααγααβαλααβαβαβαβαα, которая состоит из четырех символов α, β, γ и λ. Причем в этой последовательности α встречается 15 раз, β - 6 раз, γ - 2 раза и λ - 1 раз.

Выберем в соответствии с методом Хаффмана следующий двоичный код для представления символов:

α - 1
β - 01
γ - 001
λ - 000

Метод Лемпеля-Зива

Данный метод назван в честь его создателей, Абрахама Лемпеля и Джэкоба Зива . Системы кодирования по методу Лемпеля-Зива используют технологию кодирования с применением адаптивного словаря. В данном контексте термин словарь означает набор строительных блоков, из которых создается сжатое сообщение. Если сжатию подвергается английский текст, то строительными блоками могут быть символы алфавита. Если потребуется уменьшить размер данных, которые хранятся в компьютере, то компоновочными блоками могут стать нули и единицы. В процессе адаптивного словарного кодирования содержание словаря может изменяться. Например, при сжатии английского текста может оказаться целесообразным добавить в словарь окончание ing и артикль the. В этом случае место, занимаемое будущими копиями окончания ing и артикля the, может быть уменьшено за счет записи их как одиночных ссылок вместо сочетания из трех разных ссылок. Системы кодирования по методу Лемпеля-Зива используют изощренные и весьма эффективные методы адаптации словаря в процессе кодирования или сжатия. В частности, в любой момент процесса кодирования словарь будет состоять из тех комбинаций, которые уже были закодированы [сжаты].

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

αβααβλβ

Строка αβααβλβ является уже распакованной частью сообщения. Для того чтобы разархивировать остальной текст сообщения, необходимо сначала расширить строку, присоединив к ней ту часть, которая в ней уже встречается. Первый номер в триплете указывает, сколько символов необходимо отсчитать в обратном направлении в строке, чтобы найти первый символ добавляемого сегмента. В данном случае необходимо отсчитать в обратном направлении 5 символов, и мы попадем на второй слева символ а уже распакованной строки. Второе число в триплете задает количество последовательных символов справа от начального, которые составляют добавляемый сегмент. В нашем примере это число 4, и это означает, что добавляемым сегментом будет ααβλ. Копируем его в конец строки и получаем новое значение распакованной части сообщения: αβααβλβααβλ.

Наконец, последний элемент [в нашем случае это символ α] должен быть помещен в конец расширенной строки, в результате чего получаем полностью распакованное сообщение: αβααβλβααβλα.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Характерной особенностью большинства типов данных является их избыточность. Степень избыточности данных зависит от типа данных. Например, для видеоданных степень избыточности в несколько раз больше чем для графических данных, а степень избыточности графических данных, в свою очередь, больше чем степень избыточности текстовых данных. Другим фактором, влияющим на степень избыточности является принятая система кодирования. Примером систем кодирования могут быть обычные языки общения, которые являются ни чем другим, как системами кодирования понятий и идей для высказывания мыслей. Так, установлено, что кодирование текстовых данных с помощью средств русского языка дает в среднем избыточность на 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.

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

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

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

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

создание самораспаковающихся архивов (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с., ил.