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

Михаил Сваричевский

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

Все алгоритмы сжатия делятся на два типа: с потерями и без.

Сжатие с потерями позволяет достичь гораздо бóльшей степени сжатия (до 1/30 и менее от исходного объема).
Например, видеофильм, занимающий в неупакованном виде гигабайт 30, удается записать на 1 CD.
Однако, алгоритмы сжатия с потерями приводят к некоторым изменениям самих данных; поэтому применять такие алгоритмы можно только к тем данным, для которых небольшие искажения несущественны: видео, фото-изображения (алгоритмы JPEG), звук (алгоритм MP3).

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

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

Словарные методы

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

Словарь содержит некоторое количество слов (обычно 2x; например, 4096).
Сжатие достигается за счет того, что номер слова в словаре обычно гораздо короче самого слова.
Алгоритмы словарного сжатия делятся на две группы:
1) использующие словарь в явной форме(алгоритмы LZ78, LZW, LZC, LZT, LZMV, LZJ, LZFG)
Например, по словарю
1. "Большинство"
2. "сжатия"
3. "без"
4. "потерь"
5. "алгоритмов"
текст "Большинство алгоритмов сжатия без потерь" сжимается в "15234".

2) указывающие вместо номера слова - позицию относительно текущей позиции и длину повторяющегося участка (алгоритмы LZ77, LZR, LZSS, LZB, LZH)
Например, текст "абаббабаббабвгббабв"
сжимается в "05абабб5504абвг65", где:
"05абабб" – позиция 0 означает, что далее 5 символов идут без сжатия.
"55" – 5 букв с позиции, отстоящей от текущей на 5 символов назад.
"04абвг" – еще 4 символа не сжимается.
"65" –5 букв с позиции, отстоящей от текущей на 6 символов назад.

Модификации LZ-алгоритмов отличаются только способами представления словаря, поиска и добавления слов. Одни сжимают быстрее, но хуже; другие требуют больше памяти.

Рассмотрим подробнее модифицированный алгоритм LZ77.
Архив будет состоять из записей следующего вида:
(n,m) – означает, что с позиции n начинается такая же строка длиной m, что и с текущей позиции.
(0,m,"m символов") – означает, что далее следует m символов, которые не удалось сжать.

Алгоритм сжатия будет заключаться в следующем: ищем в файле место, начиная с которого идет самая длинная последовательность, совпадающая с последовательностью, начинающейся на текущем байте. Если ее длина больше 3, то в архив записываем начало и длину последовательности; иначе - записываем 0, длину последовательности и сами несжатые символы. Распаковка еще проще: пока файл архива не кончился, читаем по 2 числа(n,m). Если n=0, то m символов из архива сразу помещаем в буфер (эти символы нам еще понадобятся) и записываем в выходной файл. Если n<>0 то из буфера с позиции n копируем m элементов в буфер и выходной файл.

Однако есть две проблемы:
1) Ограниченный размер буфера: если нам нужно будет сжать файл размеров в 100МБ, мы его в буфер никак не поместим. Поэтому, когда он будет заполнен (скажем, на 75%), придется сдвинуть данные в нем к началу (напр., на 25%;конечно, самые старые символы при этом потеряются). Это ухудшит сжатие, но сделает алгоритм нетребовательным к памяти.
2) Скорость работы программы сжатия очень мала. В самом деле, если нужно будет сжать файл размеров 10КБ, то это потребует от нас проведения как минимум около 10000*10000/2 операций (10000 раз нам нужно будет искать совпадающую подпоследовательность, а каждый такой поиск займет в среднем 10000/2 операций). Для того, чтобы ускорить операцию поиска, можно хранить в отдельном массиве номера позиций последовательностей, начинающихся на символ chr(0), chr(2) … chr(255). Тогда при поиске нам нужно будет проверить только те комбинации, первая буква которых совпадает с первой буквой искомой последовательности.

Статистические методы

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

1) Коды Хаффмана: все символы кодируются целым количеством бит; причем так, что раскодирование всегда однозначно (например, если букве "а" соответствует последовательность бит "1001", а "b" – "10010", то раскодирование неоднозначно). Достоинство - высокая скорость сжатия. Недостатки - неоптимальное сжатие, сложности при реализации адаптивного варианта. Так как в последнее время скорость собственно алгоритма кодирования играет все меньшую роль (алгоритмы накопления статистической информации работают все медленнее и медленнее, и даже 2-х кратное увеличение времени работы кодировщика практически не влияет на скорость), этот алгоритм не имеет существенных преимуществ перед арифметическим кодированием.

2) Арифметическое кодирование: для каждого символа определяется промежуток на отрезке и в зависимости от ширины этого отрезка может выделяться разное количество бит, условно говоря, даже дробное (например: пусть строке "a" соответствует0 , а строке "ab" - 1, тогда строка "aba" закодируется в 2 бита, т.е в среднем 2/3 бита на символ). Этот метод точнее использует статистическую информацию, и всегда сжимает не хуже алгоритма Хаффмана, но медленнее. Достоинства - максимальная теоретически достижимая степень сжатия, простая реализация адаптивного варианта. Недостатки - несколько меньшая скорость.

Принцип работы арифметического кодирования:

Например, мы присвоили символу "a" промежуток , "b" – и "c" – . Тогда, если у нас будет число 0.4, то мы можем сказать, что закодирована буква "b"(0.3<=0.4<=0.6), а если 0.9 – то c(0.6<=0.9<=1). Итак, у нас получилось закодировать 1 букву в число. Как же закодировать 2 буквы? Очень просто: например, если первая буква – "b", то интервал равен . Разделим этот интервал на части, в отношении наших первоначальных отрезков. Тогда 2-м буквам "ba" будет соответствовать интервал , "bb" – и "bc" – . Для раскодирования нам достаточно знать любое число из этого интервала.

Попробуем раскодировать: пусть дано число 0.15. Это число попадает в интервал буквы "a", значит первая закодированная буква – "a". Для того, чтобы узнать вторую букву, нужно преобразовать число, чтобы оно указывало букву в интервале не , а . Для этого от числа отнимем нижнюю границу исходного интервала (0) и разделим на ширину интервала (0.3-0=0.3). Получим новое число(0.15-0)/0.3 = 0.5. Повторив те же действия, мы узнаем, что вторая буква – "b". Если бы было закодировано 3 и более букв, то, многократно повторяя этот процесс, мы нашли бы все буквы.

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

Алгоритм сжатия:
Для каждого символа мы должны присвоить соответствующий промежуток в соответствии с частотой (вероятностью встречи) в данных: пусть символ "а"имеет вероятность 0.4, "b" – 0,3 и "c" – тоже 0.3; тогда символу "а" будет соответствовать промежуток , "b" – , "c" – . Т.е мы делим имеющийся у нас промежуток между всеми необходимыми буквами в соответствии с вероятностью их встречи (более вероятному символу соответствует больший промежуток).

В процессе сжатия у нас есть 2 границы: верхняя и нижняя, назовем их соответственно hiи lo. Пусть нам нужно закодировать символ, которому мы отвели промежуток . Тогда в наш промежуток "вставляется" промежуток символа, и lo будет равен нижней границе вставляемого промежутка, hi – верхней. В итоге по мере кодирования промежуток между loи hi становится все уже и уже. Наконец, когда мы закодировали все данные, выбираем любое число из получившегося промежутка и выводим. Оно и будет сжатыми данными.

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

Проблемы:
Если бы все было так просто… На самом деле, для хранения числа-архива нужна будет очень большая точность (десятки и сотни тысяч знаков), поэтому на практике приходится пользоваться обычными типами данных. Чтобы этого добиться, будем смотреть на старшие биты/цифры числа-архива. Как только у hi и lo они совпадут, мы можем сразу записать их в архив и "отсечь". При распаковке наоборот, когда увидим, что мы довольно много раз расширяли промежуток до , считаем из файла-архива несколько цифр и допишем их в конец нашего числа-архива.
Часто используется модификация арифметического кодирования - range coder. Основное отличие - начальный интервал - . Это позволяет выводить данные сразу по байту, а не наскребать по биту, что отражается на скорости работы. В конце статьи приведена реализация именно этого варианта.

Определение вероятностей символов

Основной процесс, влияющий на скорость и степень сжатия – определение вероятностей символов. В простейшем случае будем считать вероятностью символа - количество его встреч в уже закодированной части данных, делённое на общее количество символов в данных. Для текстов это дает приблизительно 2-кратное сжатие. Чтобы его увеличить, можно учитывать такие факты, как, например, то, что вероятность встречи символа "я" после "ю" практически равна 0, а "o" после "с" – около 0.25. Поэтому для каждого предыдущего символа будем отдельно считать вероятности.

Предположения, которые мы делаем относительно сжимаемых данных (например, зависимость вероятности от предыдущих символов) называются вероятностной моделью. Модель, вероятности в которой не зависят от предыдущих символов, называется моделью 0-го порядка. Если вероятности зависят от 1 предыдущего символа, то это модель 1-го порядка, если от 2-х последних – то 2-го и т.д. Для эффективного вычисления вероятностей символов в моделях высокого порядка существуют специальная группа алгоритмов – PPM и его модификации.
Модели могут быть неадаптивными, полуадаптивными и адаптивными. В неадаптивных методах вероятности всех символов жестко зашиты в программу. В полуадаптивных по входным данным делается 2 прохода: 1-й - для определения вероятностей, 2-й – собственно для сжатия. Адаптивный – вероятности символов изменяются в процессе сжатия. Адаптивные модели самые медленные, но они обычно сжимают данные сильнее неадаптивных и полуадаптивных моделей. В общем, среди всех моделей лучше сжимают использующие наибольшее кол-во информации о сжимаемых данных - зависимость от предыдущих символов, некоторые факты, например: в текстах после точки обычно следует большая буква и т.д.

Алгоритмы, используемые в популярных архиваторах:

ZIP,ARJ,RAR - LZ+Хаффман
HA - PPM+Арифметическое кодирование
BOA - BWT+Арифметическое кодирование
UHARC - LZ+PPM+Арифметическое кодирование
(Здесь "+" означает, что результат работы алгоритма, написанного слева от знака, далее сжимается алгоритмом, записанным справа).
Как видно, в архиваторах ZIP,ARJ,RAR ,разрабатывавшихся в конце 80-х - начале 90-х, используются уже довольно устаревшие алгоритмы; поэтому они по тестам проигрывают более современным.

Пример программы адаптивного сжатия/распаковки 0-го порядка:

Данные: compr – тут хранятся сжатые данные
Data- тут хранятся исходные данные
Freq – частоты символов

Procedure compress_range; {Процедура сжатия}
Var
cum_freq: Extended;
Begin
{- Инициализация модели и кодера -}
For q:= 0 To 255 Do
freq [q] := 1; {Все символы в начале имеют одинаковую вероятность}
freq := freq - 0.20000;
total:= 256; {Сумма частот всех символов.}
{ В freq - небольшой остступ от 0 и макс.значения}
PC:= 0;{Кол-во уже закодированых байт }
Lo:= 0; range:= 256;
{- Кодирование -}
For q:= 1 To Size Do
Begin
{Нахождение интервала, соответствующего кодируемому символу}
cum_freq:= 0.1; {Начинаем накапливать вероятность}
For w:= 0 To data [q] - 1 Do
cum_freq:= cum_freq + freq [w];
{Изменяем range&lo}
range:= range / total;
Lo:= Lo + range * (cum_freq);
range:= range * freq ];
{Нормализация т.е вывод байтов, одинаковых у Lo и Hi(Hi=Lo+Range)}

Begin
Inc (PC);
compr := Trunc (Lo);
Lo:= Frac (Lo) * 256;
range:= range * 256;
End;
{Обновления модели}
freq ] := freq ] + 1;
{Присваеваем кодируемому символу на 1 большую вероятность}
total:= total + 1;
End;
{Сжатие закончено, выводим остаток}
Lo:= Lo + range / 2;
Inc (PC);
compr := Trunc (Lo);
Lo:= Frac (Lo) * 256;
range:= range * 256;
End;

Procedure decompress_range;{Процедура распаковки}
Var
temp: Extended;
ee: Extended;
Begin
{Инициализация модели и кодера}
For q:= 0 To 255 Do
freq [q] := 1;
freq := freq - 0.20000; { В freq - небольшой остступ от 0 и макс.значения}
total:= 256;
PC:= 4; {PC - номер байта, которые мы считываем}
code:= 0;
Lo:= 0; range:= 256;
{Считываем начальное, приближенное значение code.}
For q:= 1 To 4 Do
Begin
code:= code * 256 + compr [q] / 65536 / 256;
End;
w:= 0; {W- кол-во верно распакованных байт}
{Собственно расжатие}
While True Do
Begin
{Нахождения вероятности следующего символа}
temp:= (code- Lo) * total / range;
{Поиск символа, в интервал которого попадает temp}
sum:= 0.1; ssum:= 0.1;
For e:= 0 To 255 Do
Begin
sum:= sum + freq [e];
If sum > temp Then Break;
ssum:= sum;
End;
Inc (w);
{Проверка правильности распаковки}
{Сейчас в e – распакованный байт, и его можно выводить в файл}
If data [w] <> e Then Break; {Если неправильно распаковали - выходим}
If w = Size Then Begin Inc (w); Break End; {Если все распаковали выходим,}
{и модель не обновляем:-)}
{Обновления Lo&Hi(Растягивание)}
range:= range / total;
Lo:= Lo + range * (ssum);
range:= range * (freq [e]);
{Обновление модели(Делаем символ e более вероятным)}
freq [e] := freq [e] + 1;
total:= total + 1;
{Нормализация, уточнение числа}
While Trunc (Lo) = Trunc (Lo + range) Do
Begin
Inc (PC);
temp:=compr;
code:= (code - trunc(code)) * 256 + temp / 16777216;
Lo:= Frac (Lo) * 256;
range:= range * 256;
End;
End;
Dec (w);
{DONE_DECOMPRESS}
End;

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

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

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

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

Введение.

Сжатие сокращает объем пространства, тpебуемого для хранения файлов в ЭВМ, и

количество времени, необходимого для передачи информации по каналу установленной

ширины пропускания. Это есть форма кодирования. Другими целями кодирования

являются поиск и исправление ошибок, а также шифрование. Процесс поиска и

исправления ошибок противоположен сжатию - он увеличивает избыточность данных,

когда их не нужно представлять в удобной для восприятия человеком форме. Удаляя

из текста избыточность, сжатие способствует шифpованию, что затpудняет поиск

шифpа доступным для взломщика статистическим методом.

Рассмотpим обратимое сжатие или сжатие без наличия помех, где первоначальный

текст может быть в точности восстановлен из сжатого состояния. Необратимое или

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

человеческая речь или рисунки. Обратимое сжатие особенно важно для текстов,

записанных на естественных и на искусственных языках, поскольку в этом случае

ошибки обычно недопустимы. Хотя первоочередной областью применения

рассматриваемых методов есть сжатие текстов, что отpажает и наша терминология,

однако, эта техника может найти применение и в других случаях, включая обратимое

кодирование последовательностей дискретных данных.

Существует много веских причин выделять ресурсы ЭВМ в pасчете на сжатое

представление, т.к. более быстрая передача данных и сокpащение пpостpанства для

их хpанения позволяют сберечь значительные средства и зачастую улучшить

показатели ЭВМ. Сжатие вероятно будет оставаться в сфере внимания из-за все

возрастающих объемов хранимых и передаваемых в ЭВМ данных, кроме того его можно

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

напpимеp, сравнительно низкая шиpину пpопускания телефонных каналов.

ПРИМЕНЕНИЕ РАСШИРЯЮЩИХСЯ ДЕРЕВЬЕВ ДЛЯ СЖАТИЯ ДАННЫХ.

Алгоритмы сжатия могут повышать эффективность хранения и передачи данных

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

качестве входа текст источника и производит соответствующий ему сжатый текст,

когда как разворачивающий алгоритм имеет на входе сжатый текст и получает из

него на выходе первоначальный текст источника. Большинство алгоритмов сжатия

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

исходного текста.

Избыточность в представлении строки S есть L(S) - H(S), где L(S) есть длина

представления в битах, а H(S) - энтропия - мера содержания информации, также

выраженная в битах. Алгоритмов, которые могли бы без потери информации сжать

строку к меньшему числу бит, чем составляет ее энтропия, не существует. Если из

исходного текста извлекать по одной букве некоторого случайного набоpа,

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

H(S) = C(S) p(c) log ---- ,

где C(S) есть количество букв в строке, p(c) есть статическая вероятность

появления некоторой буквы C. Если для оценки p(c) использована частота появления

каждой буквы c в строке S, то H(C) называется самоэнтропией строки S. В этой

статье H (S) будет использоваться для обозначения самоэнтропии строки, взятой из

статичного источника.

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

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

иметь постоянной упорядоченности. Устранение упорядоченности приводит к

значительному упрощению основных операций расширения. Полученные в итоге

алгоритмы предельно быстры и компактны. В случае применения кодов Хаффмана,

pасширение приводит к локально адаптированному алгоритму сжатия, котоpый

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

Когда он применяется к арифметическим кодам, то результат сжатия близок к

оптимальному и приблизительно оптимален по времени.

КОДЫ ПРЕФИКСОВ.

Большинство широко изучаемых алгоритмов сжатия данных основаны на кодах

Хаффмана. В коде Хаффмана каждая буква исходного текста представляется в архиве

кодом переменной длины. Более частые буквы представляются короткими кодами,

менее частые - длинными. Коды, используемые в сжатом тексте должны подчиняться

свойствам префикса, а именно: код, использованный в сжатом тексте не может быть

префиксом любого другого кода.

Коды префикса могут быть найдены посредством дерева, в котором каждый лист

соответствует одной букве алфавита источника. Hа pисунке 1 показано дерево кода

префикса для алфавита из 4 букв. Код префикса для буквы может быть прочитан при

обходе деpева от корня к этой букве, где 0 соответствует выбору левой его ветви,

а 1 - правой. Дерево кода Хаффмана есть дерево с выравненным весом, где каждый

лист имеет вес, равный частоте встречаемости буквы в исходном тексте, а

внутренние узлы своего веса не имеют. Дерево в примере будет оптимальным, если

частоты букв A, B, C и D будут 0.125, 0.125, 0.25 и 0.5 соответственно.

Обычные коды Хаффмана требуют предварительной информации о частоте встречаемости

букв в исходном тексте, что ведет к необходимости его двойного просмотра - один

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

последующем, значения этих частот нужно объединять с самим сжатым текстом, чтобы

в дальнейшем сделать возможным его развертывание. Адаптивное сжатие выполняется

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

на частотах всех остальных кpоме нее букв алфавита. Основы для эффективной

реализации адаптивного кода Хаффмана были заложены Галлагером, Кнут опубликовал

практическую версию такого алгоритма, а Уиттер его pазвил.

Оптимальный адаптированный код Уиттера всегда лежит в пределах одного бита на

букву источника по отношению к оптимальному статичному коду Хаффмана, что обычно

составляет несколько процентов от H . К тому же, статичные коды Хаффмана всегда

лежат в пределах одного бита на букву исходного текста от H (они достигают этот

предел только когда для всех букв p(C) = 2). Существуют алгоритмы сжатия

которые могут преодолевать эти ограничения. Алгоритм Зива-Лемпелла, например,

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

пеpеменной длины, а арифметическое сжатие может использовать для кодирования

букв источника даже доли бита.

Применение расширения к кодам префикса.

Расширяющиеся деревья были впервые описаны в 1983 году и более подpобно

рассмотрены в 1985. Первоначально они понимались как вид самосбалансиpованных

деpевьев двоичного поиска, и было также показано, что они позволяют осуществить

самую быструю реализацию приоритетных очередей. Если узел расширяющегося дерева

доступен, то оно является расширенным. Это значит, что доступный узел становится

корнем, все узлы слева от него образуют новое левое поддерево, узлы справа -

новое правое поддерево. Расширение достигается при обходе дерева от старого

корня к целевому узлу и совершении пpи этом локальных изменений, поэтому цена

расширения пропорциональна длине пройденного пути.

Тарьян и Слейтон показали, что расширяющиеся деревья статично оптимальны.

Другими словами, если коды доступных узлов взяты согласно статичному

распределению вероятности, то скорости доступа к расширяющемуся дереву и

статично сбалансированному, оптимизированному этим распределением, будут

отличаться друг от друга на постоянный коэффициент, заметный при достаточно

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

статично сбалансированного дерева, то пpи использовании расширения для сжатия

данных, pазмер сжатого текста будет лежать в пределах некоторого коэффициента от

размера архива, полученного при использовании кода Хаффмана.

Как было первоначально описано, расширение применяется к деревьям, хранящим

данные во внутренних узлах, а не в листьях. Деревья же кодов префикса несут все

свои данные только в листьях. Существует, однако, вариант расширения, называемый

полурасширением, который применим для дерева кодов префикса. При нем целевой

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

взамен путь от корня до цели просто уменьшается вдвое. Полурасширение достигает

тех же теоретических границ в пределах постоянного коэффициента, что и

расширение.

В случае зигзагообразного обхода лексикографического дерева, проведение как

расширения, так и полурасширения усложняется, в отличие от прямого маршрута по

левому или правому краю дерева к целевому узлу. Этот простой случай показан на

рисунке 2. Воздействие полурасширения на маршруте от корня (узел w) до листа

узла A заключается в перемене местами каждой пары внутренних следующих друг за

другом узлов, в результате чего длина пути от корня до узла-листа сокращается в

2 раза. В процессе полурасширения узлы каждой пары, более далекие от корня,

включаются в новый путь (узлы x и z), а более близкие из него

исключаются (узлы w и y).

Сохранение операцией полурасширения лексикографического порядка в деревьях кода

префикса не является обязательным. Единственно важным в операциях с кодом

префикса является точное соответствие дерева, используемого процедурой сжатия

дереву, используемому процедурой развертывания. Любое его изменение, допущенное

между последовательно идущими буквами, производится только в том случае, если

обе процедуры осуществляют одинаковые изменения в одинаковом порядке.

Hенужность поддержки лексикографического порядка значительно упрощает проведение

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

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

Лекция №4. Сжатие информации

Принципы сжатия информации

Цель сжатия данных - обеспечить компактное представление данных, вырабатываемых источником, для их более экономного сохранения и передачи по каналам связи.

Пусть у нас имеется файл размером 1 (один) мегабайт. Нам необходимо получить из него файл меньшего размера. Ничего сложного - запускаем архиватор, к примеру, WinZip, и получаем в результате, допустим, файл размером 600 килобайт. Куда же делись остальные 424 килобайта?

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

Виды сжатия

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

Сжатие без потери информации.

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

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

Вот простой пример. В русском языке 33 буквы, десять цифр и еще примерно полтора десятка знаков препинания и прочих спе­циальных символов. Для текста, который записан только про­писными русскими буквами (как в телеграммах и радиограммах) вполне хватило бы шестидесяти разных значений. Тем не менее, каждый символ обычно кодируется байтом, который содержит 8 битов и может выражать 256 различных кодов. Это первое осно­вание для избыточности. Для нашего «телеграфного» текста вполне хватило бы шести битов на символ.

Вот другой пример. В международной кодировке символов ASCII для кодирования любого символа отводится одинаковое количество битов (8), в то время как всем давно и хорошо извест­но, что наиболее часто встречающиеся символы имеет смысл кодировать меньшим количеством знаков. Так, например, в «азбуке Морзе» буквы «Е» и «Т», которые встречаются часто, кодируются одним знаком (соответственно это точка и тире). А такие редкие буквы, как «Ю» ( - -) и «Ц» (- - ), кодиру­ются четырьмя знаками. Неэффективная кодировка - второе основание для избыточности. Программы, выполняющие сжа­тие информации, могут вводить свою кодировку (разную для разных файлов) и приписывать к сжатому файлу некую таблицу (словарь), из которой распаковывающая программа узнает, как в данном файле закодированы те или иные символы или их груп­пы. Алгоритмы, основанные на перекодировании информации, называют алгоритмами Хафмана.

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

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

Сжатие с потерей информации.

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

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

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

К алгоритмам сжатия с потерей информации относятся такие известные алгоритмы как JPEG и MPEG. Алгоритм JPEG исполь­зуется при сжатии фотоизображений. Графические файлы, сжа­тые этим методом, имеют расширение JPG. Алгоритмы MPEG используют при сжатии видео и музыки. Эти файлы могут иметь различные расширения, в зависимости от конкретной программы, но наиболее известными являются.MPG для видео и.МРЗ для музыки.

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

Величиной допустимой потери при сжатии обычно можно управ­лять. Это позволяет экспериментовать и добиваться оптималь­ного соотношения размер/качество. На фотографических иллюст­рациях, предназначенных для воспроизведения на экране, потеря 5% информации обычно некритична, а в некоторых случаях можно допустить и 20-25%.

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

Код Шеннона-Фэно

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

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

Давайте представим себе текст, алфавит которого состоит всего из 16 букв: А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М, Н, О, П, Р. Каждый из этих знаков можно закодировать с помощью всего 4 бит: от 0000 до 1111. Теперь представим себе, что вероятности появления этих символов распределены следующим образом:

Сумма этих вероятностей составляет, естественно, единицу. Разобьем эти символы на две группы таким образом, чтобы суммарная вероятность символов каждой группы составляла ~0.5 (рис). В нашем примере это будут группы символов А-В и Г-Р. Кружочки на рисунке, обозначающие группы символов, называются вершинами или узлами (nodes), а сама конструкция из этих узлов - двоичным деревом (B-tree). Присвоим каждому узлу свой код, обозначив один узел цифрой 0, а другой - цифрой 1.

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

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

Коды символов (крайние правые узлы дерева) имеют коды неодинаковой длины. Так, буква А, имеющая для нашего воображаемого текста вероятность p=0.2, кодируется всего двумя битами, а буква Р (на рисунке не показана), имеющая вероятность p=0.013, кодируется аж шестибитовой комбинацией.

Итак, принцип очевиден - часто встречающиеся символы кодируются меньшим числом бит, редко встречающиеся - большим. В результате среднестатистическое количество бит на символ будет равно

где ni - количество бит, кодирующих i-й символ, pi - вероятность появления i-го символа.

Код Хаффмана.

Алгоритм Хаффмана изящно реализует общую идею статистического кодирования с использованием префиксных множеств и работает следующим образом:

1. Выписываем в ряд все символы алфавита в порядке возрастания или убывания вероятности их появления в тексте.

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

3. Прослеживаем путь к каждому листу дерева, помечая направление к каждому узлу (например, направо - 1, налево - 0) . Полученная последовательность дает кодовое слово, соответствующее каждому символу (рис.).

Построим кодовое дерево для сообщения со следующим алфавитом:

Недостатки методов

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

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

Еще один недостаток кодов - это то, что минимальная длина кодового слова для них не может быть меньше единицы, тогда как энтропия сообщения вполне может составлять и 0,1, и 0,01 бит/букву. В этом случае код становится существенно избыточным. Проблема решается применением алгоритма к блокам символов, но тогда усложняется процедура кодирования/декодирования и значительно расширяется кодовое дерево, которое нужно в конечном итоге сохранять вместе с кодом.

Данные коды никак не учитывают взаимосвязей между символами, которые присутствуют практически в любом тексте. Например, если в тексте на английском языке нам встречается буква q, то мы с уверенностью сможем сказать, что после нее будет идти буква u.

Групповое кодирование - Run Length Encoding (RLE) - один из самых старых и самых простых алгоритмов архивации. Сжатие в RLE происходит за счет замены цепочек одинаковых байт на пары "счетчик, значение". («красный, красный, ..., красный» записывается как «N красных»).

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

При кодировании exe-файлов можно искать и упаковывать последовательности вида AxAyAzAwAt..., которые часто встречаются в ресурсах (строки в кодировке Unicode)

К положительным сторонам алгоритма, можно отнести то, что он не требует дополнительной памяти при работе, и быстро выполняется. Алгоритм применяется в форматах РСХ, TIFF, ВМР. Интересная особенность группового кодирования в PCX заключается в том, что степень архивации для некоторых изображений может быть существенно повышена всего лишь за счет изменения порядка цветов в палитре изображения.

LZW-код (Lempel-Ziv & Welch) является на сегодняшний день одним из самых распространенных кодов сжатия без потерь. Именно с помощью LZW-кода осуществляется сжатие в таких графических форматах, как TIFF и GIF, с помощью модификаций LZW осуществляют свои функции очень многие универсальные архиваторы. Работа алгоритма основана на поиске во входном файле повторяющихся последовательностей символов, которые кодируются комбинациями длиной от 8 до 12 бит. Таким образом, наибольшую эффективность данный алгоритм имеет на текстовых файлах и на графических файлах, в которых имеются большие одноцветные участки или повторяющиеся последовательности пикселов.

Отсутствие потерь информации при LZW-кодировании обусловило широкое распространение основанного на нем формата TIFF. Этот формат не накладывает каких-либо ограничений на размер и глубину цвета изображения и широко распространен, например, в полиграфии. Другой основанный на LZW формат - GIF - более примитивен - он позволяет хранить изображения с глубиной цвета не более 8 бит/пиксел. В начале GIF - файла находится палитра - таблица, устанавливающая соответствие между индексом цвета - числом в диапазоне от 0 до 255 и истинным, 24-битным значением цвета.

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

Алгоритм JPEG был разработан группой фирм под названием Joint Photographic Experts Group. Целью проекта являлось создание высокоэффективного стандарта сжатия как черно-белых, так и цветных изображений, эта цель и была достигнута разработчиками. В настоящее время JPEG находит широчайшее применение там, где требуется высокая степень сжатия - например, в Internet.

В отличие от LZW-алгоритма JPEG-кодирование является кодированием с потерями. Сам алгоритм кодирования базируется на очень сложной математике, но в общих чертах его можно описать так: изображение разбивается на квадраты 8*8 пикселов, а затем каждый квадрат преобразуется в последовательную цепочку из 64 пикселов. Далее каждая такая цепочка подвергается так называемому DCT-преобразованию, являющемуся одной из разновидностей дискретного преобразования Фурье. Оно заключается в том, что входную последовательность пикселов можно представить в виде суммы синусоидальных и косинусоидальных составляющих с кратными частотами (так называемых гармоник). В этом случае нам необходимо знать лишь амплитуды этих составляющих для того, чтобы восстановить входную последовательность с достаточной степенью точности. Чем большее количество гармонических составляющих нам известно, тем меньше будет расхождение между оригиналом и сжатым изображением. Большинство JPEG-кодеров позволяют регулировать степень сжатия. Достигается это очень простым путем: чем выше степень сжатия установлена, тем меньшим количеством гармоник будет представлен каждый 64-пиксельный блок.

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

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

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

Фрактальное сжатие

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

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

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

Основа метода фрактального кодирования - это обнаружение самоподобных участков в изображении. Впервые возможность применения теории систем итерируемых функций (IFS) к проблеме сжатия изображения была исследована Майклом Барнсли и Аланом Слоуном. Они запатентовали свою идею в 1990 и 1991 гг. Джеквин (Jacquin) представил метод фрактального кодирования, в котором используются системы доменных и ранговых блоков изображения (domain and range subimage blocks), блоков квадратной формы, покрывающих все изображение. Этот подход стал основой для большинства методов фрактального кодирования, применяемых сегодня. Он был усовершенствован Ювалом Фишером (Yuval Fisher) и рядом других исследователей.

В соответствии с данным методом изображение разбивается на множество неперекрывающихся ранговых подизображений (range subimages) и определяется множество перекрывающихся доменных подизображений (domain subimages). Для каждого рангового блока алгоритм кодирования находит наиболее подходящий доменный блок и аффинное преобразование, которое переводит этот доменный блок в данный ранговый блок. Структура изображения отображается в систему ранговых блоков, доменных блоков и преобразований.

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

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

Вкратце метод, предложенный Барнсли, можно описать следующим образом. Изображение кодируется несколькими простыми преобразованиями (в нашем случае аффинными), то есть определяется коэффициентами этих преобразований (в нашем случае A, B, C, D, E, F).

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

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

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

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

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

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

Сравнение с JPEG

Сегодня наиболее распространенным алгоритмом архивации графики является JPEG. Сравним его с фрактальной компрессией.

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

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

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

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

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