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

Презентация:



Advertisements
Похожие презентации
Сжатие информации Алгоритм Хаффмана. Сжатие информации Сжатие данных – сокращение объема данных при сохранении закодированного в них содержания.
Advertisements

Алгоритм построения орграфа Хаффмана (алгоритм сжатия) Учитель информатики: Константинова Елена Ивановна Муниципальное образовательное учреждение Раменская.
Учитель информатики : Константинова Елена Ивановна Муниципальное образовательное учреждение Раменская средняя общеобразовательная школа 8.
Курсовая работа по дисциплине «Информатика» на тему: «Алгоритм Хаффмана» Автор: Пятко Наталья.
Выполнила: Медведева Анастасия, Ученица 11А класса, МОУ СОШ 3. Руководитель: Глазунова Ольга Петровна, учитель информатики. «Сжатие данных. Алгоритм Хаффмана»
Обобщение метода кодирования Хаффмана с использованием систем счисления Ковалёв Д.С. Новосибирский Государственный Университет Факультет Информационных.
Теория графов Основные определения. Задание графов Графический способ – Привести пример графического задания графа, состоящего из вершин А, В и С, связанных.
Сжатие двоичного кода. Для того чтобы сэкономить место на внешних носителях (винчестерах, флэш дисках) и ускорить передачу информации по компьютерным.
Алгоритмы на графах. Задача о максимальном потоке в сетях Требуется от источника к стоку передать максимальное количество энергии. В условиях задачи о.
Задача о максимальном потоке в сети Алгоритм Фалкерсона-Форда.
Сигнал, кодирование, декодирование, сжатие. Для передачи дискретных данных по каналам связи применяется два способа физического кодирования: - на основе.
Транспортные сети ХНУРЭ, кафедра ПО ЭВМ, Тел , Лекция 15 Н.В. Белоус Факультет компьютерных наук Кафедра ПО ЭВМ,
Алгоритмы на графах Волновой метод. Постановка задачи Постановка задачи. Пусть G – неориентированный связный граф, а и b – две его вершины. Требуется.
Алгоритм Флойда-Уоршалла Находит кратчайшие расстояния между всеми парами вершин графа Идея: Строится специальная матрица D, элементы которой – кратчайшие.
СЖАТИЕ И ЗАЩИТА ИНФОРМАЦИИ НА ОСНОВЕ ДВОИЧНЫХ БИНОМИАЛЬНЫХ КОДОВ.
Графы Волновой метод. Задание графов Пусть граф задан графически. Составить матрицу смежности и матрицу инцидентности для этого графа
Теория графов Алгоритмы на графах. Медиана графа Медиана вершина графа, у которой сумма кратчайших расстояний от неё до вершин графа минимальная возможная.
Построение остовного (покрывающего) дерева графа Преподаватель «И и ИКТ» ГБОУ лицея 1557 Куленчик Олеся Николаевна.
Комбинаторные алгоритмы Задача о покрытии. Задача о покрытии множествами Дано: Совокупность U из n элементов, и набор подмножеств U, S = {S 1,…, S k },
Транксрипт:

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

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

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

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

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

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

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

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

а в д, ен р от _

а в д, ен р от _

а в д, ен р от _

а в д, ен р от _

а в д, ен р от _

а в д, ен р от _

а в д, ен р от _

а в д, ен р от _

а в д, ен р от _

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

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