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

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

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

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

4 a00 b01 c10 d011 e100 f101 g1001 h1010 i a b c d e g h i Данный код не является префиксным f

5 a00 b10 c010 d110 e0110 f0111 g1110 h f b d e g h a c Данный код п пп префиксный, т.к. к кк кодируемые символы располагаются в вершинах, из которых не выходят новые дуги.

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

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

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

9 а в д, ен р от _

10 а в д, ен р от _

11 а в д, ен р от _

12 а в д, ен р от _

13 а в д, ен р от _

14 а в д, ен р от _

15 а в д, ен р от _

16 а в д, ен р от _

17 а в д, ен р от _

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

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