КС109. Основы теории информации

КС109

ОП.01 Основы теории информации

Преподаватель: Класс Юлия Николаевна

E-mail: [email protected]

Дата выдачи задания

08.12.2020г.

Срок выполнения

ТЕМА ЗАНЯТИЯ :

Список литературы:

09.12.2020г.

Рекомендации по выполнению задания:

• Лекция (Код доступа: http://tech-lyceum.ru/tehnologia/informatika/lecture9.htm)

Алгоритмы сжатия текстовой информации. Решение задач

Задания можно выполнить как в тетради так и в любом текстовом редакторе.

1. В тетради запишите название лекции.

2. Изучите материалы занятия и составьте конспект (при составлении конспекта систематизируйте информацию, выпишите определения, составьте необходимые таблицы).

3. Фото конспекта и выполненные задания отправить на почту [email protected].

Сжатие - кодирование информации с целью уменьшения ее объема.

Коэффициент сжатия - отношение исходного объема информации к полученному объему в результате сжатия:

 исходный объем информации

 объем сжатой информации

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

Никакое кодовое слово не является началом другого кодового слова.

Код, удовлетворяющий условию Шеннона-Фано, называется префиксным кодом.

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

a

b

00

c

01

10

d

011

e

f

100

g

101

h

1001

1010

i

1111

1

0

1

0

1

0

c

b

a

1

0

1

1

f

e

d

0

1

1

i

g

h

Данный код не является префиксным

a

b

00

10

c

010

d

110

e

0110

f

g

0111

h

1110

1111

1

0

1

0

1

0

a

b

0

1

1

0

c

d

1

0

0

1

g

h

e

f

Данный код  префиксный, т.к. кодируемые символы располагаются в вершинах, из которых не выходят новые дуги .

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

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

Пример. Построить код Хаффмана для фразы:

на дворе трава, на траве дрова

Шаг 1:

_

,

д

р

н

т

в

а

е

о

5

2

2

4

2

2

1

4

2

6

Шаги 2-3:

30

1

0

17

13

1

0

1

9

8

7

0

1

1

0

1

0

0

4

4

3

1

0

0

1

1

0

2

2

4

2

1

2

4

6

2

5

_

,

р

о

т

н

е

д

в

а

Шаг 4:

0

1

1

0

1

0

1

1

1

0

0

0

1

1

0

0

0

1

_

о

т

д

е

н

р

в

а

,

00

Шаг 4:

0

1

1

0

1

0

1

1

1

0

0

0

1

1

0

0

0

1

_

т

о

д

е

н

р

в

а

,

010

00

Шаг 4:

0

1

1

0

1

0

1

1

1

0

0

0

1

1

0

0

0

1

_

т

о

н

е

д

р

в

а

,

0110

010

00

Шаг 4:

0

1

1

0

1

1

0

1

1

0

0

0

1

1

0

0

0

1

_

о

т

н

е

д

р

в

а

,

010

00

0110

0111

Шаг 4:

0

1

1

0

1

1

0

1

1

0

0

0

1

1

0

0

0

1

_

о

т

д

е

н

р

в

а

,

00

1000

0111

0110

010

Шаг 4:

0

1

1

0

1

1

0

1

1

0

0

0

1

1

0

0

0

1

_

о

т

д

е

н

р

в

а

,

010

1001

1000

0111

0110

00

Шаг 4:

0

1

1

0

1

1

0

1

1

0

0

0

1

0

1

0

0

1

_

о

т

д

е

н

р

в

а

,

101

0111

00

010

1000

1001

0110

Шаг 4:

0

1

1

0

1

0

1

1

1

0

0

0

1

1

0

0

0

1

_

т

о

е

д

н

р

в

а

,

1100

101

010

1001

1000

0111

0110

00

Шаг 4:

0

1

1

0

1

0

1

1

1

0

0

0

1

1

0

0

0

1

_

т

о

е

д

н

р

в

а

,

1101

1100

101

0110

1001

1000

0111

00

010

Шаг 4:

0

1

1

0

1

0

1

1

1

0

0

0

1

1

0

0

0

1

_

т

о

д

н

е

р

в

а

,

111

1101

1100

101

0111

1001

1000

0110

010

00

Задание

• Постройте код Хаффмана для фразы:

КАРЛ У КЛАРЫ УКРАЛ КОРАЛЛЫ, А КЛАРА У КАРЛА УКРАЛА КЛАРНЕТ

• Определите коэффициент сжатия для данной фразы, если каждый символ кодируется кодом ASCII и равномерным кодом.

Определите коэффициент сжатия для данной фразы, если каждый символ кодируется кодом ASCII и равномерным кодом

Рассчитаем коэффициент сжатия относительно использования кодировки ASCII (8 бит/символ). LASCII = 8 · 28 = 224 бит.

на дворе трава, на траве дрова

_

,

д

р

н

а

в

т

е

о

2

2

5

4

2

2

1

2

4

6

L Huff = 6 · 2+4 · 2 +2 · 4 +1 · 4+2 ·4+2 ·4+4 ·3+2 · 4 +2 ·4+

+5 ·3 = 12+8+8+4+8+8+12+8+8+15= 91бит.

Определите коэффициент сжатия для данной фразы, если каждый символ кодируется кодом ASCII и равномерным кодом

Следовательно, коэффициент сжатия будет равен K сж = L ASCII / L Huff =224/91≈ 2,46

Коэффициент сжатия относительно равномерного кода (5 бит/символ, т. к. у нас всего 25 символов) будет равен K сж = 5 · 28/ L Huff = 140/91≈ 1,5385

Вопросы

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