Алгоритмы оптимального кодирования

1.

Алгоритмы
оптимального
кодирования

2.

3.

Дэвид Хаффман
David Huffman
(1925-1999)
В 18 лет Дэвид получил степень
бакалавра электротехники в университете штата Огайо. Основную
концепцию кодирования данных
Хаффман разработал во время
Второй мировой войны, когда
служил на эсминце офицеромсвязистом. Изначально алгоритм
предназначался для кодирования
радиосообщений.
За свою деятельность он получил
множество наград за исключительный
вклад в теорию информации.
3

4.

Таблица кодов Хаффмана
Буква
Код
Хаффмана
Буква
Код
Хаффмана
Буква
Код Хаффмана
E
100
D
11011
W
011101
T
001
L
01111
B
011100
A
1111
F
01001
V
1101001
O
1110
C
01000
K
110100011
N
1100
M
00011
X
110100001
R
1011
U
00010
J
110100000
I
1010
G
00001
Q
1101000101
S
0110
Y
00000
Z
1101000100
H
0101
P
110101
4

5.

Код Хаффмана обладает свойством префиксности,
то есть код никакого символа не является началом
кода какого-либо другого символа.
5

6.

Дерево Хаффмана
корень
Т
В
Q
001
011100
1101000101
МОУ СОШ №33 с углубленным изучением математики г.Ярославля
6

7.

Дерево Хаффмана
корень
00000
11011
110100011
7

8.

Дерево Хаффмана
корень
01000111011011100
С
О
D
E
8

9.

10.

11.

Алгоритм Хаффмана
Алгоритм Хаффмана двухпроходный:
на первом проходе строится частотный словарь
и
генерируются коды;
на втором проходе происходит непосредственно
кодирование.
НА ДВОРЕ ТРАВА, НА ТРАВЕ ДРОВА
1. Подсчитать частоту встречаемости (вес) каждого символа.
символ
А
В Д
,
Е
Н
Р
О
Т
_
вес
6
4
1
2
2
4
2
2
5
2
11

12.

Алгоритм построения
дерева Хаффмана
1.
Среди символов выбрать два с наименьшими
весами (если таких пар несколько, выбирается
любая из них).
2.
Свести ветки дерева от этих двух символов в
одну точку с весом, равным сумме двух весов,
при этом веса самих элементов стираются.
3.
Повторять пункты 1 и 2 до тех пор, пока не
останется одна вершина с весом, равным
сумме весов исходных символов.
4.
Пометить одну ветку нулём, а другую единицей (по собственному усмотрению).
12

13.

Пример. Построить код Хаффмана для фразы:
на дворе трава, на траве дрова
Шаг 1:
а
6
д
2
в
4
е
2
,
1
Шаги 2-3:
р
4
н
2
о
2
1
17
13
0
2
д
0
1
0
1
3
4
в
9
8
7
0
1
0
1
6
а
5
30
0
0
_
т
2
4
4
0
1
1
,
2
е
1
0
1
2
н
4
р
2
о
1
2
т
5
_

14.

Шаг 4:
0
1
1
0
0
0
а
00
в
1
0
1
д
0
1
,
е
0
1
0
1
0
н
р
о
1
1
т
_

15.

Шаг 4:
0
1
1
0
0
0
а
в
00
010
1
0
1
д
0
1
,
е
0
1
0
1
0
н
р
о
1
1
т
_

16.

Шаг 4:
0
1
1
0
0
0
а
00
в
1
0
1
д
010 0110
0
1
,
е
0
1
0
1
0
н
р
о
1
1
т
_

17.

Шаг 4:
0
1
1
0
0
0
а
00
в
1
0
1
д
0
1
,
010 0110 0111
е
0
1
0
1
0
н
р
о
1
1
т
_

18.

Шаг 4:
0
1
1
0
0
0
а
00
в
1
0
1
д
0
1
,
е
010 0110 0111 1000
0
1
0
1
0
н
р
о
1
1
т
_

19.

Шаг 4:
0
1
1
0
0
0
а
00
в
1
0
1
д
0
1
,
е
0
1
0
1
0
н
010 0110 0111 1000 1001
р
о
1
1
т
_

20.

Шаг 4:
0
1
1
0
0
0
а
00
в
1
0
1
д
0
1
,
е
0
1
0
1
0
н
010 0110 0111 1000 1001
р
101
о
1
1
т
_

21.

Шаг 4:
0
1
1
0
0
0
а
00
в
1
0
1
д
0
1
,
е
0
1
0
1
0
н
010 0110 0111 1000 1001
р
о
101 1100
1
1
т
_

22.

Шаг 4:
0
1
1
0
0
0
а
00
в
1
0
1
д
0
1
,
е
0
1
0
1
0
н
010 0110 0111 1000 1001
р
о
1
1
т
101 1100 1101
_

23.

Шаг 4:
0
1
1
0
0
0
а
00
в
1
0
1
д
0
1
,
е
0
1
0
1
0
н
010 0110 0111 1000 1001
р
о
1
1
т
101 1100 1101
_
111

24.

Кодирование текста
А
В
00
Д
,
Е
Н
Р
О
010 0110 0111 1000 1001 101
Т
_
1100 1101 111
НА ДВОРЕ ТРАВА, НА ТРАВЕ ДРОВА
1001001110110010110010110001111101
Н
А
Д
_
В
О
Р
Е
Т
_
101000100001111111001001111101101
Р
А В
А
,
_
Н
А
_
Т
Р
0001010001110110101110001000
А
В
Е
_
Д
Р
О
В
А
24

25.

Кодирование текста
А
В
00
Д
,
Е
Н
Р
010 0110 0111 1000 1001 101
О
Т
_
1100 1101 111
НА ДВОРЕ ТРАВА, НА ТРАВЕ ДРОВА
10010011101100101100101100011111
01101000100001111111001001111101
1010001010001110110101110001000
25

26.

Коэффициент сжатия
Коэффициентом сжатия называется отношение
объема исходного сообщения к объему сжатого.
символ
А
код
00
вес
6
В
Д
,
У
010 0110 0111 1000
4
2
1
2
Н
Р
О
Т
_
1001
101
1100
1101
111
2
4
2
2
5
Объем сжатого сообщения:
6*2+4*3+2*4+1*4+2*4+2*4+4*3+2*4+2*4+5*3=95 бит=12 байт.
Объем исходного сообщения в ASCII равен 30 байт.
Коэффициент сжатия составляет 30 / 12 = 2,5
26

27.

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

28.

Пример:
построить код Хаффмана для фразы
ОТ_ТОПОТА_КОПЫТ_ПЫЛЬ_ПО_ПОЛЮ_ЛЕТИТ
1. Определим частоту вхождения символов в фразу:
символ
частота
А Е И К ЛОП Т ЫЬЮ _
1 1 1 1 3 6 5 6 2 1 1 6
2. Строим таблицу частоты вхождения по
убыванию.(см.слайд 9)
3. Строим орграф Хаффмана:
-символ задает вершину- лист орграфа;
-вес вершины равен частоте вхождения символа;
-соединяются пары вершин с наименьшим весом:
-левые ветви обозначаем 0;
-правые ветви обозначаем 1;
-определяем код символа от корня к листу;

29.

Метод Хаффмана(таблица)
част
ота
По
убыван
ию
А
1
А
Е
1
Е
И
1
И
К
1
К
Л
3
Л
О
6
О
П
5
П
Т
6
Т
Ы
2
Ы
Ь
1
Ь
Ю 1
Ю
_
_
6

30.

КОРЕНЬ ДЕРЕВА

31.

Построены префиксные коды символов:
Символ
А
Е
И
К
Л О П
Т
Ы
Ь
Ю
Код
Длина
кода
Сообщение в новых кодах содержит **** бит
(сжатое),
в кодировке ASCII – 34 * 8 = 272 бита(исходное)
тогда
К сж = 272 / **** = ___
_

32.

Литература
1.
Андреева Е.В. Математические основы информатики.
Элективный курс: учебное пособие / Е.В.Андреева,
Л.Л.Босова, И.Н.Фалина – М.:БИНОМ. Лаборатория знаний,
2005.
2.
Гейн А.Г. Математические основы информатики. /
«Информатика» №17 / 2007
3.
Семакин И.Г. Информатика. Базовый курс. 7-9 классы /
И.Г.Семакин, Л.А.Залогова, С.В.Русаков, Л.В.Шестакова. – 2е изд., испр. И доп. – М.: БИНОМ. Лаборатория знаний, 2004.
4.
Семакин И.Г. Информатика и ИКТ. Базовый уровень :
практикум для 10-11 классов / И.Г.Семакин, Е.К.Хеннер,
Т.Ю.Шеина – М. : БИНОМ. Лаборатория знаний, 2007.
5.
http://www.compression.ru/ сайт «Все о сжатии»
6.
Устинов П.С. Архиватор собственными руками!
http://vio.fio.ru/vio_09/resource/Print/art_1_9.htm
32