pril

1. Тема урока:

«Алгоритмы сжатия
текстовой информации»
Учитель информатики МОУ школа №8
Зайцев А. И.
г. о. Жуковский, 2013

2.

Сжатие - кодирование информации с
целью уменьшения ее объема.
Коэффициент сжатия - отношение
исходного объема информации к
полученному объему в результате сжатия:
V0
Kc
V1
V0 исходный объем информации
V1 объем сжатой информации

3. Условие Шеннона-Фано

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

4.

a
b
c
d
e
f
g
h
i
00
01
10
011
100
101
1001
1010
1111
0
0
1
1
0
c
b
a
1
0
1
f
e
d
1
g
1
1
0
1
h
Данный код не является префиксным
i

5.

a
00
b
10
c
010
d
110
e
0110
f
0111
g
1110
h
1111
0
a
0
1
1
0
0
b
1
c
0
e
1
1
0
d
1
f
0
g
Данный код префиксный, т.к. кодируемые
символы располагаются в вершинах, из
которых не выходят новые дуги.
1
h

6. Алгоритм Хаффмана построения префиксного кода

1.
2.
3.
4.
Все символы кодируемой информации образуют
вершины-листья. Каждой вершине приписывается вес,
равный количеству вхождений данного символа в
сообщение.
Среди вершин, которым приписаны веса, выбираются
две с наименьшими весами (если таких несколько,
любые из них).
Создается следующая вершина графа, из которой
выходят две дуги к выбранным на предыдущем шаге
вершинам; одна дуга помечается символом 0, другая –
символом 1. Созданной вершине приписывается вес,
равный сумме весов выбранных вершин, а веса этих
двух вершин стираются.
К вершинам, которым приписаны веса, применяются
шаги 2 и 3 до тех пор, пока не останется одна вершина с
весом, равным сумме весов исходных символов.

7.

Пример. Построить код Хаффмана для фразы:
на дворе трава, на траве дрова
Шаг 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
1
2
н
4
р
0
1
2
о
2
т
5
_

8.

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

9.

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

10.

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

11.

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

12.

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

13.

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

14.

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

15.

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

16.

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

17.

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

18. Вопросы

1.
2.
За счет чего достигается эффект
сжатия данных при их упаковке?
Какой код называется префиксным?

19.

Задание
a)Постройте код Хаффмана для фразы:
КАРЛ У КЛАРЫ УКРАЛ КОРАЛЛЫ, А КЛАРА У КАРЛА
УКРАЛА КЛАРНЕТ
b) Определите коэффициент сжатия для
данной фразы, если каждый символ
кодируется кодом ASCII и равномерным
кодом.