2. Определения, аббревиатуры и классификации методов сжатия

Базовые определения

Бит- это "атом" цифровой информации: переменная, которая может принимать ровно два различных значения:

• "1" (единица, да, истина, существует);

• "0" (нуль, нет, ложь, не существует).

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

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

Данные - информация в цифровом виде.

Объем данных измеряется в битах, но может быть и рациональным числом, а не только целым.

R-битовый элемент - совокупность R битов - имеет 2R возможных значений-состояний. Большинство источников цифровой информации порождает элементы одного размера R. А в большинстве остальных случаев - элементы нескольких размеров: R], R2, R3— (например, 8, 16 и 32).

Байт - это 8-битовый элемент: совокупность 8 битов.

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

Блок - конечная последовательность цифровой информации.

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

Блок - последовательность с произвольным доступом, а поток - с последовательным.

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

Используют и такие пары терминов: компрессия/декомпрессия, кодирование/декодирование, упаковка/распаковка.

Под просто сжатием будем далее понимать сжатие без потерь (lossless compression).

Сжатие с потерями (lossy compression) - это два разных процесса:

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

2. собственно сжатие, без потерь.

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

Конечную последовательность битов назовем кодом¹, а количество битов в коде - длиной кода.

Конечную последовательность элементов назовем словом, а количество элементов в слове - длиной слова. Иногда используются синонимы строка и фраза. В общем случае слово построено из R-битовых элементов, а не 8-битовых. Таким образом, код - это слово из 1-битовых элементов.

Например, в блоке из 14 элементов "кинчотсихыннад" одно слово длиной14 элементов, два слова длиной 13 элементов, и т. д., 13 слов длиной 2 и 14 слов длиной 1. Аналогично в блоке из семи битов "0100110" один код длиной 7 бит, два кода длиной 6 бит, и т. д., семь кодов длиной 1 бит.

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

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

ASCII (American Standard Code for Information Interchange - Американский стандартный код для обмена информацией) каждому значению байта ставит в соответствие символ. Но чтобы построить однозначное соответствие для всех необходимых символов из множества национальных алфавитов народов мира, требуется больше: по крайней мере 16 бит на символ (что и обеспечивает стандарт Unicode).

Множество всех различных символов, порождаемых некоторым источником, называется алфавитом, а количество символов в этом множестве - размером алфавита. Источники данных порождают только элементы, но физические источники информации - символы или элементы.

Размер алфавита таблицы ASCII равен 28=256, a Unicode- 216=65 536. Это две самые распространенные таблицы символов.

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

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

• учет значений соседних элементов (контекста) улучшает сжатие, т. е. имеет смысл трактовать данные как слова;

• поток данных выглядит как поток слов.

В первом же случае имеем дело с перестановкой элементов и рассматривать данные как слова нет смысла.

Кавычки показывают, что это условные названия способов интерпретации входных данных: "слова", "элементы", "биты".

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

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

• данные считаются количественными;

• источник данных считается источником Маркова 1-го порядка.

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

Еще две важные характеристики алгоритма сжатия - объемы памяти, необходимые для сжатия и для разжатия (для хранения данных, создаваемых и/или используемых алгоритмом).

Названия методов

CM (Context Modeling) - контекстное моделирование.

DMC (Dynamic Markov Compression) - динамическое марковское сжатие (является частным случаем СМ).

PPM (Prediction by Partial Match) - предсказание по частичному совпадению (является частным случаем СМ).

LZ-методы - методы Зива - Лемпела, в том числе LZ77, LZ78, LZH и LZW.

PBS (Parallel Blocks Sorting) - сортировка параллельных блоков.

ST (Sort Transformation) - частичное сортирующее преобразование (является частным случаем PBS).

BWT (Burrows-Wheeler Transform) - преобразование Барроуза - Уилера (является частным случаем ST).

RLE (Run Length Encoding) - кодирование длин повторов.

HUFF (Huffman Coding) - кодирование по методу Хаффмана.

SEM (Separate Exponents and Mantissas) - разделение экспонент и мантисс (представление целых чисел).

UNIC (Universal Coding) - универсальное кодирование (является частным случаем SEM).

ARIC (Arithmetic Coding) - арифметическое кодирование.

RC (Range Coding) - интервальное кодирование (вариант арифметического).

DC (Distance Coding) - кодирование расстояний.

IF (Inversion Frequences) - "обратные частоты" (вариант DC).

MTF (Move To Front) - "сдвиг к вершине", "перемещение стопки книг".

ENUC (Enumerative Coding) - нумерующее кодирование.

FT (Fourier Transform) - преобразование Фурье.

DCT (Discrete Cosine Transform) - дискретное Косинусное Преобразование, ДКП (является частным случаем FT).

DWT (Discrete Wavelet Transform) - дискретное вэйвлетное преобразование, ДВП.

LPC (Linear Prediction Coding) - линейно-предсказывающее кодирование, ЛПК (к нему относятся дельта-кодирование, ADPCM, CELP и MELP).

SC (Subband Coding) - субполосное кодирование.

VQ (Vector Quantization) - векторное квантование.

Каждая группа (ветвь, семейство) содержит множество методов. Исключением является блочно-ориентированный СМ - это относительно мало исследованная область. Авторам не известны другие практические реализации, кроме компрессоров СМ Булата Зиганшина и "pre-conditioned PPMZ" Чарльза Блума.

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

Все поточные методы применимы и к блокам, но обратное неверно.

Блочные методы не применимы к потокам, поскольку не могут начать выполнение, пока не задана длина блока, заполненного данными, подлежащими сжатию.

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

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

Не все методы для потоков R-битовых "элементов" применимы к "битам" (только те, которые в третьей строке "карты").

Очевидно, что невыгодно применять методы для "элементов" - к "словам" или "битам". Менее очевидно, что невыгодно и обратное: применять методы для потоков "слов" к данным без значимых вероятностных взаимосвязей, к "элементам" ИЛИ "битам".

Базовые стратегии сжатия

Базовых стратегий сжатия три:

1. Преобразование потока ("Скользящее окно-словарь"). Описание поступающих данных через уже обработанные. Сюда входят LZ-методы для потоков "слов", т. е. когда комбинации поступающих элементов предсказуемы по уже обработанным комбинациям. Преобразование по таблице, RLE, LPC, DC, MTF, VQ, SEM, Subband Coding, Discrete Wavelet Transform - для потоков "элементов", т. е. когда не имеет смысла рассматривать комбинации длиной два и более элемента или запоминать эти комбинации, как в случае Linear Prediction Coding.

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

2. Статистическая стратегия.

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

б) Блочная. Отдельно кодируется и добавляется к сжатому блоку его статистика. Статические варианты методов Хаффмана, Шеннона – Фано и арифметического кодирования - для потоков "элементов". Статическое СМ - для "слов".

3. Преобразование блока. Входящие данные разбиваются на блоки, которые затем трансформируются целиком, а в случае блока однородных данных лучше брать весь блок, который требуется сжать. Это методы сортировки блоков ("BlockSorting''-методы: ST, BWT, PBS), а также Fourier Transform, Discrete Cosine Transform, фрактальные преобразования, Enumerative Coding.

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

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

• чем больше и однороднее данные и память, тем эффективнее блочные методы;

• чем меньше и неоднороднее данные и память, тем эффективнее поточные методы;

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

• чем проще источник, тем эффективнее прямолинейное статистическое решение (математические модели "источник Бернулли" и "источник Маркова").