Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
ОТЦС_Ч1_2008.doc
Скачиваний:
13
Добавлен:
01.07.2025
Размер:
5 Мб
Скачать
☆
    1. Методы кодирования без потерь

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

Практически все эти методы основываются на учете статистических (вероятностных) свойств кодируемых данных и поэтому называются статистическими, или энтропийными.

Граничные возможности статистического кодирования – минимально достижимая скорость кода (среднее количество бит на один символ кодируемых данных)  определяются теоремой Шеннона: скорость кода не может быть меньше энтропии сжимаемых данных.

Учет статистических свойств данных в простейшем случае означает использование для кодирования неравномерных кодов: часто встречающиеся символы должны кодироваться короткими кодами, редко встречающиеся – длинными.

Для обеспечения однозначности декодирования неравномерных кодов они должны быть неприводимыми, или префиксными.

2.3.1. Понятие префиксного множества

Префиксным множеством S называется такое множество двоичных последовательностей, в котором ни одна последовательность не является префиксом или началом другой последовательности.

Например, множество двоичных слов S1 = {00, 01, 100, 110, 1010, 1011} является префиксным, поскольку если проверить любую совместную комбинацию (wi wj), то видно, что wi никогда не явится префиксом (началом) wj.

С другой стороны, множество S2 = { 00, 001, 1110 } не является префиксным, так как последовательность 00 является префиксом (началом) другой последовательности из этого множества  001.

Для префиксных множеств вводится понятие вектора Крафта: если S = = { w1, w2, ... , wk } – префиксное множество, то вектор v(S) = ( L1, L2, ..., Lk ), состоящий из чисел, являющихся длинами соответствующих префиксных последовательностей, называется вектором Крафта. Для него справедливо следующее условие, называемое неравенством Крафта:

. (2.7)

Если неравенство (2.7) переходит в строгое равенство, то код называется компактным и обладает наименьшей среди кодов с данным алфавитом длиной, то есть является оптимальным.

Ниже приведены примеры простейших префиксных множеств и соответствующие им векторы Крафта:

S1 = {0, 10, 11} и v(S1) = ( 1, 2, 2 );

S2 = {0, 10, 110, 111} и v(S2) = ( 1, 2, 3, 3 );

S3 = {0, 10, 110, 1110, 1111} и v(S3) = ( 1, 2, 3, 4, 4 );

S4 = {0, 10, 1100, 1101, 1110, 1111} и v(S4) = ( 1, 2, 4, 4, 4, 4 );

S5 = {0, 10, 1100, 1101, 1110, 11110, 11111} и v(S5) = (1, 2, 4, 4, 4, 5, 5);

S6 = {0, 10, 1100, 1101, 1110, 11110, 111110, 111111}

и v(S6) = (1,2,4,4,4,5,6,6).

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

2.3.2. Алгоритм кодирования Хаффмена

Алгоритм Хаффмена, названный в честь его изобретателя Дэвида Хаффмена, предлагает простой и эффективный способ кодирования, обеспечивающий получение оптимального вектора Крафта. Код, полученный с использованием этого алгоритма, называют кодом Хаффмена.

Предположим, нужно закодировать сообщение со следующим словарем символов:

A B C D E

10 5 8 13 10

Здесь под каждой буквой словаря указано, сколько раз эта буква встречалась в тексте сообщения.

Алгоритм Хаффмена работает следующим образом.

1. Выписываем в ряд все символы (буквы) алфавита в порядке возрастания или убывания вероятности их появления в тексте:

B C A E D

5 8 10 10 13

2. Последовательно объединяем два символа с наименьшими вероятностями появления в новый составной символ, вероятность появления которого полагаем равной сумме вероятностей составляющих его символов:

A E BC D

10 10 13 13

BC D AE

13 13 20

AE BCD

20 26

AEBCD

46

3. Строим кодовое дерево, каждый узел которого имеет суммарную вероятность всех узлов, находящихся ниже него (рис. 2.5).

Рис. 2.5

4. Прослеживаем путь от корня к каждому листу (вершине) дерева, помечая направление к каждому узлу: направо  1, налево  0. Полученная последовательность дает кодовое слово, соответствующее каждому символу.

Ветеран энтропийного кодирования алгоритм Хаффмена и сегодня очень широко используется в системах сжатия. Так, данный алгоритм является частью стандарта сжатия изображений JPEG и используется в компьютерных архиваторах PKZIP, LHA и др.

Алгоритм кодирования по Хаффмену обладает тем важным свойством, что кодовые слова, полученные с его использованием обладают префиксным свойством, а их длина минимальна. Недостатком этого алгоритма является необходимость предварительного вычисления вероятностей символов источника, то есть его статистический анализ. Процедура кодирования при этом становится двухпроходной. Сначала данные просматриваются и подсчитываются вероятности всех символов в кодируемом сообщении, а затем производится собственно кодирование.