Пример распаковки данных с помощью алгоритма lz78

Пусть длина словаря составляет 16 фраз. Коды сжатого сообщения -

Кодирование длин повторений

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

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

Предположим, что нужно закодировать двоичное (двухцветное) изображение размером 8 х 8 элементов, приведенное на рис. 1.

Рис. 1

Просканируем это изображение по строкам (двум цветам на изображении будут соответствовать 0 и 1), и получим двоичный вектор данных

X= (0111000011110000000100000001000000010000000111100011110111101111)

длиной 64 бита.

Выделим в векторе X участки, на которых данные сохраняют неизменное значение, и определим их длины. Результирующая последовательность длин участков - положительных целых чисел, соответствующих исходному вектору данных X, - будет иметь вид r = (1, 3, 4, 4, 7, 1, 7, 1, 7, 1, 7, 4, 3, 4, 1, 4, 1, 4).

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

Таблица 1

Кодер
Длина участка	Кодовое слово
4	0
1	10
7	110
3	111

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

B (r) = (0101110011010110101101011001110100100)

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

Дифференциальное кодирование

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

Покажем, какое преимущество может дать дифференциальное кодирование (кодирование разности между соседними отсчетами) в сравнении с простым кодированием (кодированием отсчетов независимо друг от друга).

Просканируем 8-битовое (256-уровневое) цифровое изображение, при этом десять последовательных пикселов имеют уровни:

144, 147, 150, 146, 141, 142, 138, 143, 145, 142.

Если закодировать эти уровни пиксел за пикселом каким-либо кодом без памяти, использующим 8 бит на пиксел изображения, получим кодовое слово, содержащее 80 бит.

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

144, 147, 150, 146, 141, 142, 138, 143, 145, 142.

         

144, 3, 3, - 4, - 5, 1, - 4, 5, 2, -3.

Исходная последовательность может быть легко восстановлена из разностной простым суммированием:

144, 144+3, 147+3, 150–4, 146–5, 141+1, 142–4, 138+5, 143+2, 145-3

         

144, 147, 150, 146, 141, 142, 138, 143, 145, 142.

Для кодирования первого числа из полученной последовательности разностей отсчетов, как и ранее, понадобится 8 бит, все остальные числа можно закодировать 4-битовыми словами (один знаковый бит и 3 бита на кодирование модуля числа ).

Таким образом, в результате кодирования получим кодовое слово длиной 8 + 9*4 = 44 бита или почти вдвое более короткое, чем при индивидуальном кодировании отсчетов.

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

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