2.9.2. Специальные методы эффективного кодирования

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

2.9.2.1. Методы эффективного кодирования числовых последовательностей

Различают два метода – разностное кодирование и кодирование повторений.

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

2 14 18 27 34

первый способ даст после­довательность:

2 12 4 9 7.

Этот метод эффективен для медленно меняющихся после­довательностей. Его недостаток состоит в том, что для получения значения n-го члена последовательности надо декодировать все предыдущие (n-1) членов последовательности.

Второй способ порождает последо­вательность:

-17 -5 -1 8 15 ,

поскольку среднее значение для исходной последовательности - 19.

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

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

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

Кодирование повторений заключается в замене цепочки оди­наковых цифровых символов самим символом и числом повторений (возможно включение разделителей). Напри­мер, для последовательности:

55556666888888

применение этого способа даст последовательность:

5(4)6(4)8(6),

где круглые скобки играют роль разделителей.

Данный метод может быть использован для эффективного кодирования растровых форматов изображений. Растровыми называются форматы изображений, которые получаются во время ввода изображения путем кодирования каждой точки – пиксела (pixel–PIсtureELement) – двумерного пространства, на котором расположено исходное изображение, даже если эта точка не содержит самого изображения. Очевидно, в общем случае, изображение занимает не все пространство. Тем не менее, кодированию подлежат и «пустоты», при этом те точки, которые содержат изображение, в простейшем случае (для монохромных изображений) кодируются двоичной 1, точки без изображения кодируются двоичным 0. В результате получаются числовые последовательности, подобные следующей:

00000000000000000000000000000000000000000000000010000000000000000000.

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

00000000000080000.

Очевидно, к таким последовательностям можно применить метод кодирования повторений. В результате для нашего случая получим (круглые скобки используем как разделители):

0(С)8000,

что означает: 0 повторяется 12 раз (С₁₆= 12), для остальных символов число повторений не вводится.

Поскольку результирующая последовательность должна также быть шестнадцатеричной, полученное выражение преобразуем следующим образом: заменим круглые скобки соответствующими ASCII-кодами. Тогда открывающей скобке соответствует код 28₁₆, закрывающей – 29₁₆. Получим:

028С2980000.

Длина результата меньше исходной последовательности (11 символов против 17), поэтому получен эффект в 6 символов.