Что такое findslide.org?

FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.


Для правообладателей

Обратная связь

Email: Нажмите что бы посмотреть 

Яндекс.Метрика

Презентация на тему Алгоритмы сжатия информации

Содержание

Сжатие - кодирование информации с целью уменьшения ее объема.Коэффициент сжатия - отношение исходного объема информации к полученному объему в результате сжатия:− исходный объем информации− объем сжатой информации
Тема урока:«Алгоритмы сжатия текстовой информации»Учитель информатики МОУ школа №8Зайцев А. И.г. о. Жуковский, 2013 Сжатие - кодирование информации с целью уменьшения ее объема.Коэффициент сжатия - отношение Условие Шеннона-ФаноНикакое кодовое слово не является началом другого кодового слова.Код, удовлетворяющий условию 010110110abcdegh0111iДанный код не является префикснымf 010101fbdegh01011001acДанный код − префиксный, т.к. кодируемые символы располагаются в вершинах, из которых не выходят новые дуги. Алгоритм Хаффмана построения префиксного кодаВсе символы кодируемой информации образуют вершины-листья. Каждой вершине Пример. Построить код Хаффмана для фразы: на дворе трава, на траве дроваШаг авд,енрот_01010110010101010100Шаг 4: авд,енрот_01010110010101010100010Шаг 4: авд,енрот_010101100101010101000100110Шаг 4: авд,енрот_0101011001010101010001001100111Шаг 4: авд,енрот_01010110010101010100010011001111000Шаг 4: авд,енрот_010101100101010101000100110011110001001Шаг 4: авд,енрот_010101100101010101000100110011110001001101Шаг 4: авд,енрот_0101011001010101010001001100111100010011011100Шаг 4: авд,енрот_01010110010101010100010011001111000100110111001101Шаг 4: авд,енрот_01010110010101010100010011001111000100110111001101111Шаг 4: ВопросыЗа счет чего достигается эффект сжатия данных при их упаковке?Какой код называется префиксным? ЗаданиеПостройте код Хаффмана для фразы: КАРЛ У КЛАРЫ УКРАЛ КОРАЛЛЫ, А КЛАРА
Слайды презентации

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

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

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

объему в результате сжатия:


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

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


Слайд 3 Условие Шеннона-Фано
Никакое кодовое слово не является началом другого

Условие Шеннона-ФаноНикакое кодовое слово не является началом другого кодового слова.Код, удовлетворяющий

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

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

Слайд 4 0
1
0
1
1
0
1
1
0
a
b
c
d
e
g
h
0
1
1
1
i
Данный код не является префиксным
f

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

Слайд 5 0
1
0
1
0
1
f
b
d
e
g
h
0
1
0
1
1
0
0
1
a
c
Данный код − префиксный, т.к. кодируемые символы располагаются

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

в вершинах, из которых не выходят новые дуги.


Слайд 6 Алгоритм Хаффмана построения префиксного кода
Все символы кодируемой информации

Алгоритм Хаффмана построения префиксного кодаВсе символы кодируемой информации образуют вершины-листья. Каждой

образуют вершины-листья. Каждой вершине приписывается вес, равный количеству вхождений

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


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

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

трава, на траве дрова
Шаг 1:
Шаги 2-3:
а
в
д
,
е
н
р
о
т
_
6
4
2
1
2
2
4
2
2

3
4
4
7
0
1
0


1

0

1

1

0

8


0

1

9

0

1

13

0

1

17

0

1

30

0

1

5

а

6

в

4

д

2

,

1

е

2

н

2

р

4

о

2

т

2

_

5


Слайд 8



а
в
д
,
е
н
р
о
т
_

0
1
0
1
0
1
1
0

0
1
0
1
0
1
0
1
0
1




00

Шаг 4:

авд,енрот_01010110010101010100Шаг 4:

Слайд 9



а
в
д
,
е
н
р
о
т
_

0
1
0
1
0
1
1
0

0
1
0
1
0
1
0
1
0
1




00
010

Шаг 4:

авд,енрот_01010110010101010100010Шаг 4:

Слайд 10



а
в
д
,
е
н
р
о
т
_

0
1
0
1
0
1
1
0

0
1
0
1
0
1
0
1
0
1




00
010
0110

Шаг 4:

авд,енрот_010101100101010101000100110Шаг 4:

Слайд 11



а
в
д
,
е
н
р
о
т
_

0
1
0
1
0
1
1
0

0
1
0
1
0
1
0
1
0
1




00
010
0110
0111

Шаг 4:

авд,енрот_0101011001010101010001001100111Шаг 4:

Слайд 12



а
в
д
,
е
н
р
о
т
_

0
1
0
1
0
1
1
0

0
1
0
1
0
1
0
1
0
1




00
010
0110
0111
1000

Шаг 4:

авд,енрот_01010110010101010100010011001111000Шаг 4:

Слайд 13



а
в
д
,
е
н
р
о
т
_

0
1
0
1
0
1
1
0

0
1
0
1
0
1
0
1
0
1




00
010
0110
0111
1000
1001

Шаг 4:

авд,енрот_010101100101010101000100110011110001001Шаг 4:

Слайд 14



а
в
д
,
е
н
р
о
т
_

0
1
0
1
0
1
1
0

0
1
0
1
0
1
0
1
0
1




00
010
0110
0111
1000
1001
101

Шаг 4:

авд,енрот_010101100101010101000100110011110001001101Шаг 4:

Слайд 15



а
в
д
,
е
н
р
о
т
_

0
1
0
1
0
1
1
0

0
1
0
1
0
1
0
1
0
1




00
010
0110
0111
1000
1001
101
1100

Шаг 4:

авд,енрот_0101011001010101010001001100111100010011011100Шаг 4:

Слайд 16



а
в
д
,
е
н
р
о
т
_

0
1
0
1
0
1
1
0

0
1
0
1
0
1
0
1
0
1




00
010
0110
0111
1000
1001
101
1100
1101

Шаг 4:

авд,енрот_01010110010101010100010011001111000100110111001101Шаг 4:

Слайд 17



а
в
д
,
е
н
р
о
т
_

0
1
0
1
0
1
1
0

0
1
0
1
0
1
0
1
0
1




00
010
0110
0111
1000
1001
101
1100
1101
111

Шаг 4:

авд,енрот_01010110010101010100010011001111000100110111001101111Шаг 4:

Слайд 18 Вопросы
За счет чего достигается эффект сжатия данных при

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

их упаковке?
Какой код называется префиксным?


  • Имя файла: algoritmy-szhatiya-informatsii.pptx
  • Количество просмотров: 143
  • Количество скачиваний: 2