Статистические методы сжатия. Лекция 2

План

Коды переменной длины
Декодирование
Кодирование Хаффмана
Арифметическое сжатие

Коды переменной длины или выражайтесь ясно

Дано
Минимальное число бит по теории информации 1,57
По

Коды переменной длины или выражайтесь ясно

Закодируем строку
a1a3a2a1a3a3a4a2a1a1a2a2a1a1a3a1a1a2a3a1
Код строки
1|010|01|1|010|010|001|01|1|1|01|01|1|1|010|1|1|01|010|1
37 битов на 20

Свойство префикса

Если некоторая последовательность би­тов выбрана в качестве кода какого-то символа,

Правила назначения кодов переменной длины

Следует назначать более короткие коды чаще встречающимся

Декодирование

Проблема – декодер должен знать префиксный код каждого символа
Решения
Использовать набор

Кодирование Хаффмана

1

0

0

0

0

1

1

Коды Хаффмана

Средняя длина кода 0.4 х 1 + 0.2x2+
+0.2x3+0.1x4+0.1X4 =

Кодирование Хаффмана

Средняя длина кода 0.4 х 2 + 0.2x2+
+0.2x2+0.1x3+0.1X3 = 2.2

Выбор кода Хаффмана

Наилучший код – с минимальной дисперсией
Дисперсия кода 1
Дисперсия кода

«признаки» оптимального дерева

Объединение символов с минимальной вероятностью с символами с максимальной

Когда не применим код Хаффмана

Символы равновероятны
Если размер алфавита n является степенью

Декодирование Хаффмана

1

1

1

0

0

0

0

а1

а2

а3

а4

а5

Код 1001100111

100

110

0111

а4а2а5а1

Адаптивное кодирование Хаффмана

До начала работы в дереве есть корень, в нем

Добавляем новый символ

Закодируем строку ABC

esc

esc

B

1

0

esc

C

1

0

Модификация дерева

E

A

B

C

D

1

2

2

2

9

16

3

4

7

1. A++

2

4

8

17

2. A++

A

D

3

5

9

18

Модификация дерева

A

C

D

9

E

B

5

2

2

2

4

6

11

20

Арифметическое сжатие

Всему кодируемому объекту назначается интервал [0;1)
Вычисляются частоты появления символов входного

пример

Закодируем строку SWISS_MISS. Длина строки – 10 символов.
Введем 2 переменные Low

Процесс кодирования

Декодирование

Декодер узнает символы алфавита
Получает информацию о частотах и интервалах символов
Читает

Процесс декодирования

Несимметричное кодирование

Если вероятности появления символов в строке очень разные, то есть