Содержание
- 2. План Коды переменной длины Декодирование Кодирование Хаффмана Арифметическое сжатие
- 3. Коды переменной длины или выражайтесь ясно Дано Минимальное число бит по теории информации 1,57 По Code1
- 4. Коды переменной длины или выражайтесь ясно Закодируем строку a1a3a2a1a3a3a4a2a1a1a2a2a1a1a3a1a1a2a3a1 Код строки 1|010|01|1|010|010|001|01|1|1|01|01|1|1|010|1|1|01|010|1 37 битов на 20
- 5. Свойство префикса Если некоторая последовательность битов выбрана в качестве кода какого-то символа, то ни один код
- 6. Правила назначения кодов переменной длины Следует назначать более короткие коды чаще встречающимся символам Коды должны удовлетворять
- 7. Декодирование Проблема – декодер должен знать префиксный код каждого символа Решения Использовать набор стандартных префиксных кодов
- 8. Кодирование Хаффмана 1 0 0 0 0 1 1 Коды Хаффмана Средняя длина кода 0.4 х
- 9. Кодирование Хаффмана Средняя длина кода 0.4 х 2 + 0.2x2+ +0.2x2+0.1x3+0.1X3 = 2.2 бит/символ 1 0
- 10. Выбор кода Хаффмана Наилучший код – с минимальной дисперсией Дисперсия кода 1 Дисперсия кода 2
- 11. «признаки» оптимального дерева Объединение символов с минимальной вероятностью с символами с максимальной вероятностью
- 12. Когда не применим код Хаффмана Символы равновероятны Если размер алфавита n является степенью 2, то получаются
- 13. Декодирование Хаффмана 1 1 1 0 0 0 0 а1 а2 а3 а4 а5 Код 1001100111
- 14. Адаптивное кодирование Хаффмана До начала работы в дереве есть корень, в нем символ esc Новый символ
- 15. Добавляем новый символ Закодируем строку ABC esc esc B 1 0 esc C 1 0
- 16. Модификация дерева E A B C D 1 2 2 2 9 16 3 4 7
- 17. Модификация дерева A C D 9 E B 5 2 2 2 4 6 11 20
- 18. Арифметическое сжатие Всему кодируемому объекту назначается интервал [0;1) Вычисляются частоты появления символов входного алфавита в файле
- 19. пример Закодируем строку SWISS_MISS. Длина строки – 10 символов. Введем 2 переменные Low = 0, High
- 20. Процесс кодирования
- 21. Декодирование Декодер узнает символы алфавита Получает информацию о частотах и интервалах символов Читает по 1 цифре
- 22. Процесс декодирования
- 23. Несимметричное кодирование Если вероятности появления символов в строке очень разные, то есть опасность наступления 0 до
- 25. Скачать презентацию