Оцените презентацию от 1 до 5 баллов!
Тип файла:
ppt / pptx (powerpoint)
Всего слайдов:
24 слайда
Для класса:
1,2,3,4,5,6,7,8,9,10,11
Размер файла:
94.33 kB
Просмотров:
77
Скачиваний:
0
Автор:
неизвестен
Слайды и текст к этой презентации:
№1 слайд![Статистические методы сжатия](/documents_6/f158c6cc98959999c5953dd9ffa354ac/img0.jpg)
Содержание слайда: Статистические методы сжатия
Лекция 2
№2 слайд![План Коды переменной длины](/documents_6/f158c6cc98959999c5953dd9ffa354ac/img1.jpg)
Содержание слайда: План
Коды переменной длины
Декодирование
Кодирование Хаффмана
Арифметическое сжатие
№3 слайд![Коды переменной длины или](/documents_6/f158c6cc98959999c5953dd9ffa354ac/img2.jpg)
Содержание слайда: Коды переменной длины
или выражайтесь ясно
Дано
Минимальное число бит по теории информации 1,57
По Code1 среднее число бит 1х0.49+2х0.25+3х0.25+3х0.01=1.77
№4 слайд![Коды переменной длины или](/documents_6/f158c6cc98959999c5953dd9ffa354ac/img3.jpg)
Содержание слайда: Коды переменной длины
или выражайтесь ясно
Закодируем строку
a1a3a2a1a3a3a4a2a1a1a2a2a1a1a3a1a1a2a3a1
Код строки
1|010|01|1|010|010|001|01|1|1|01|01|1|1|010|1|1|01|010|1
37 битов на 20 символов = 1,85 бит/символ
Декодируем
a1/a2?a3 – код двусмысленный
№5 слайд![Свойство префикса Если](/documents_6/f158c6cc98959999c5953dd9ffa354ac/img4.jpg)
Содержание слайда: Свойство префикса
Если некоторая последовательность битов выбрана в качестве кода какого-то символа, то ни один код другого символа не должен иметь в начале эту последовательность
№6 слайд![Правила назначения кодов](/documents_6/f158c6cc98959999c5953dd9ffa354ac/img5.jpg)
Содержание слайда: Правила назначения кодов переменной длины
Следует назначать более короткие коды чаще встречающимся символам
Коды должны удовлетворять свойству префикса
№7 слайд![Декодирование Проблема](/documents_6/f158c6cc98959999c5953dd9ffa354ac/img6.jpg)
Содержание слайда: Декодирование
Проблема – декодер должен знать префиксный код каждого символа
Решения
Использовать набор стандартных префиксных кодов (факсимильная связь)
Кодер сканирует файл и передает информацию о статистических свойствах файла декодеру. Декодер подбирает префиксы
Кодер по мере работы над исходными данными улучшает исходный префиксный код. Декодер повторяет каждый шаг кодера
№8 слайд![Кодирование Хаффмана](/documents_6/f158c6cc98959999c5953dd9ffa354ac/img7.jpg)
Содержание слайда: Кодирование Хаффмана
№9 слайд![Кодирование Хаффмана](/documents_6/f158c6cc98959999c5953dd9ffa354ac/img8.jpg)
Содержание слайда: Кодирование Хаффмана
№10 слайд![Выбор кода Хаффмана Наилучший](/documents_6/f158c6cc98959999c5953dd9ffa354ac/img9.jpg)
Содержание слайда: Выбор кода Хаффмана
Наилучший код – с минимальной дисперсией
Дисперсия кода 1
Дисперсия кода 2
№11 слайд![признаки оптимального дерева](/documents_6/f158c6cc98959999c5953dd9ffa354ac/img10.jpg)
Содержание слайда: «признаки» оптимального дерева
Объединение символов с минимальной вероятностью с символами с максимальной вероятностью
№12 слайд![Когда не применим код](/documents_6/f158c6cc98959999c5953dd9ffa354ac/img11.jpg)
Содержание слайда: Когда не применим код Хаффмана
Символы равновероятны
Если размер алфавита n является степенью 2, то получаются просто коды фиксированной длины. В других случаях коды весьма близки к кодам с фиксированной длиной
Двухсимвольный алфавит
Идет потеря информации о корреляции соседних битов исходного изображения
№13 слайд![Декодирование Хаффмана](/documents_6/f158c6cc98959999c5953dd9ffa354ac/img12.jpg)
Содержание слайда: Декодирование Хаффмана
№14 слайд![Адаптивное кодирование](/documents_6/f158c6cc98959999c5953dd9ffa354ac/img13.jpg)
Содержание слайда: Адаптивное кодирование Хаффмана
До начала работы в дереве есть корень, в нем символ esc
Новый символ просто добавляем в дерево без кодирования
При повторе символа модифицируем дерево по принципу – частоты символов растут снизу вверх и слева направо
№15 слайд![Добавляем новый символ](/documents_6/f158c6cc98959999c5953dd9ffa354ac/img14.jpg)
Содержание слайда: Добавляем новый символ
Закодируем строку ABC
№16 слайд![Модификация дерева](/documents_6/f158c6cc98959999c5953dd9ffa354ac/img15.jpg)
Содержание слайда: Модификация дерева
№17 слайд![Модификация дерева](/documents_6/f158c6cc98959999c5953dd9ffa354ac/img16.jpg)
Содержание слайда: Модификация дерева
№18 слайд![Арифметическое сжатие Всему](/documents_6/f158c6cc98959999c5953dd9ffa354ac/img17.jpg)
Содержание слайда: Арифметическое сжатие
Всему кодируемому объекту назначается интервал [0;1)
Вычисляются частоты появления символов входного алфавита в файле
Начальный интервал делится пропорционально частотам символов
По мере считывания символов из входного файла интервал переопределяется (сокращается)
№19 слайд![пример Закодируем строку](/documents_6/f158c6cc98959999c5953dd9ffa354ac/img18.jpg)
Содержание слайда: пример
Закодируем строку SWISS_MISS. Длина строки – 10 символов.
Введем 2 переменные Low = 0, High = 1
Частоты и интервалы символов
№20 слайд![Процесс кодирования](/documents_6/f158c6cc98959999c5953dd9ffa354ac/img19.jpg)
Содержание слайда: Процесс кодирования
№21 слайд![Декодирование Декодер узнает](/documents_6/f158c6cc98959999c5953dd9ffa354ac/img20.jpg)
Содержание слайда: Декодирование
Декодер узнает символы алфавита
Получает информацию о частотах и интервалах символов
Читает по 1 цифре из конечного кода
№22 слайд![Процесс декодирования](/documents_6/f158c6cc98959999c5953dd9ffa354ac/img21.jpg)
Содержание слайда: Процесс декодирования
№23 слайд![Несимметричное кодирование](/documents_6/f158c6cc98959999c5953dd9ffa354ac/img22.jpg)
Содержание слайда: Несимметричное кодирование
Если вероятности появления символов в строке очень разные, то есть опасность наступления 0 до конца строки при декодировании
Для избежания этого добавляют специальный символ eof с очень низкой вероятностью
№24 слайд![Особенности реализации](/documents_6/f158c6cc98959999c5953dd9ffa354ac/img23.jpg)
Содержание слайда: Особенности реализации
Переменные Low и High делать целыми и хранить в них только часть после запятой
При вычислении символа округлять до диапазона частот
По мере накопления в левой части числа неменяющихся чисел, убирать их