Свойства алгоритмов сжатия

Кодирование

Пример

Показывает алгоритм LZW в действии, демонстрируя состояние выходных данных и словаря на каждой стадии, как при кодировании, так и при раскодировании сообщения. Для упрощения ограничимся простым алфавитом — только заглавные буквы, без знаков препинания и пробелов. Сообщение, которое нужно сжать, выглядит следующим образом:

TOBEORNOTTOBEORTOBEORNOT#

Маркер # используется для обозначения конца сообщения. Тем самым, в нашем алфавите 27 символов (26 заглавных букв от A до Z и #). Компьютер представляет это в виде групп бит, для представления каждого символа алфавита нам достаточно группы из 5 бит на символ. По мере роста словаря, размер групп должен расти, с тем чтобы учесть новые элементы. 5-битные группы дают 25 = 32 возможных комбинации бит, поэтому, когда в словаре появится 33-е слово, алгоритм должен перейти к 6-битным группам. Заметим, что, поскольку используется группа из всех нолей 00000, то 33-я группа имеет код 32.

[62 слайд]

Начальный словарь будет содержать:

# = 00000

A = 00001

B = 00010

C = 00011

...

Z = 11010

Без использования алгоритма LZW, при передаче сообщения как оно есть — 25 символов по 5 бит на каждый — оно займёт 125 бит. Сравним это с тем, что получается при использовании LZW:

[63 слайд]

Символ: Битовый код: Новая запись словаря:

(на выходе)

T 20 = 10100

O 15 = 01111 27: TO

B 2 = 00010 28: OB

E 5 = 00101 29: BE

O 15 = 01111 30: EO

R 18 = 10010 31: OR <--- со следующего символа начинаем использовать 6-битные группы

N 14 = 001110 32: RN

O 15 = 001111 33: NO

T 20 = 010100 34: OT

TO 27 = 011011 35: TT

BE 29 = 011101 36: TOB

OR 31 = 011111 37: BEO

TOB 36 = 100100 38: ORT

EO 30 = 011110 39: TOBE

RN 32 = 100000 40: EOR

OT 34 = 100010 41: RNO

# 0 = 000000 42: OT#

Общая длина = 6*5 + 11*6 = 96 бит.

Таким образом, используя LZW мы сократили сообщение на 29 бит из 125 — это почти 22 %. Если сообщение будет длиннее, то элементы словаря будут представлять всё более и более длинные части текста, благодаря чему повторяющиеся слова будут представлены очень компактно.

[64 слайд]

Таблица 6. Свойства алгоритмов сжатия

[65 слайд]