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

Содержание

• 
  Слайд 1

  Тема урока:

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

• 
  Слайд 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

• 
  Слайд 5
  

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

• 
  Слайд 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:

• 
  Слайд 9
  

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

• 
  Слайд 10
  

  а в д , е н р о т _ 0 1 0 1 0 1 1 0 0 1 0 1 0 1 0 1 0 1 00 010 0110 Шаг 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:

• 
  Слайд 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:

• 
  Слайд 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:

• 
  Слайд 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:

• 
  Слайд 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:

• 
  Слайд 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:

• 
  Слайд 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:

• 
  Слайд 18

  Вопросы

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

• 
  Слайд 19
  

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