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

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

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

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

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

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

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

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

R-битовый элемент - совокупность R битов - имеет 2^R возможных зна­чений-состояний. Большинство источников цифровой информации порож­дает элементы одного размера R. А в большинстве остальных случаев -элементы нескольких размеров: R], R₂, 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 равен 2⁸=256, a Unicode- 2¹⁶⁼65 536. Это две самые распространенные таблицы символов.

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

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

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

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

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

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

По традиции бинарный источник без памяти называют обычно источ­ником Бернулли, а важнейшим частным случаем источника данных с па­мятью является источник Маркова (N-ro порядка): состояние на i-м шаге зависит от состояний на N предыдущих шагах: /-1, i-2,..., i-N.

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

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

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

Если использовать модель "аналоговый сигнал" с N > 1, то при малых N эффективность сжатия неизменна или незначительно лучше, но метод су­щественно сложнее, а при дальнейшем увеличении N эффективность резко уменьшается.

Эффективность сжатия учитывает не только степень сжатия (отноше­ние длины несжатых данных к длине соответствующих им сжатых данных),

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

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