2.3.7. Кодирование длин повторений (rle)
Кодирование длин участков (или повторений) может быть достаточно эффективным при сжатии двоичных данных, например черно-белых факсимильных изображений, черно-белых изображений, содержащих множество прямых линий и однородных участков (BMP, GIF, TIFF), а также любых других данных, содержащих длинные цепочки повторяющихся символов. Кодирование длин повторений является одним из элементов известного алгоритма сжатия изображений JPEG.
Идея сжатия данных на основе кодирования длин повторений состоит в том, что вместо кодирования собственно данных подвергаются кодированию числа, соответствующие длинам участков, на которых данные сохраняют неизменное значение.
Существует множество разновидностей RLE-кодирования. Рассмотрим несколько примеров.
Очень часто в различных цифровых данных встречаются участки с большим количеством нулевых значений. В частности, такая ситуация имеет место при сжатии изображений с использованием алгоритма JPEG. В этом случае RLE-кодирование производится следующим образом. Всякий раз, когда в потоке данных встречается “ноль”, он кодируется двумя числами. Первое 0, являющееся флагом начала кодирования длины потока нулей, и второе – количество нулей в очередной группе. Если среднее число нулей в группе больше двух, будет иметь место сжатие. С другой стороны, большое число отдельных нулей может привести даже к увеличению размера кодируемого файла:
Другим примером RLE-сжатия может служить кодирование байтовых данных. При этом цепочки или серии повторяющихся байтов заменяются на один кодирующий байт и счетчик числа их повторений.
Пример.
44 44 44 11 11 11 11 11 01 33 FF 22 22 исходная последовательность; 03 44 04 11 00 03 01 03 FF 02 22 сжатая последовательность.
Здесь
первый байт указывает, сколько раз нужно
повторить следующий байт. Если первый
байт равен 00, то за ним следует счетчик,
показывающий сколько неповторяющихся
данных следует за ним, а также сами
неповторяющиеся данные, в этом примере
– 01 03 FFм
следуетт равен 00, то затем
этомны
Наконец, более сложный пример, в котором реализовано сразу и RLE-кодирование и кодирование по Хаффмену. Предположим, что нужно закодировать двоичное изображение размером 8 х 8 элементов, показанное на рис. 2.6.
Рис. 2.6
Просканируем это изображение по строкам (белым и черным участкам на изображении будут соответствовать 0 и 1), в результате получим двоичный вектор данных
X= (0111000011110000000100000001000000010000000100000001111111010111),
длиной 64 бита. При этом скорость исходного кода составляет 1 бит на элемент изображения.
Выделим в векторе X участки, на которых данные сохраняют неизменное значение, и определим их длины. Результирующая последовательность длин участков целых чисел, соответствующих исходному вектору данных X, будет иметь вид r = (1, 3, 4, 4, 7, 1, 7, 1, 7, 1, 7, 1, 7, 7, 1, 1, 1, 3).
Теперь эту последовательность, в которой заметна явная неравновероятность символов (единиц и семерок гораздо больше, чем других символов), можно закодировать каким-либо статистическим кодом, например кодом Хаффмена, имеющим таблицу кодирования (табл. 2.6)
Таблица 2.6
-
Кодер
Длина участка
Кодовое слово
1
0
7
10
4
110
3
111
Для того чтобы указать, что кодируемая последовательность начинается с нуля, добавим в начале кодового слова префиксный символ 0. В результате получим кодовое слово B (r) = ( 001111101101001001001001010000111) длиной в 33 бита, то есть результирующая скорость кода R составит 33/64, или немногим более 0,5 бита, на элемент изображения (при исходном – 1 бит/точку). При сжатии изображений большего размера, содержащих множество повторяющихся элементов, эффективность сжатия может оказаться гораздо более высокой.