- •Лабораторная работа №1
- •«Исследование методов неразрушающего сжатия информации. Простейшие методы неразрушающего сжатия »
- •Цель работы
- •Цель работы – уточнить постановку задачи и классификацию методов неразрушающего сжатия информации, изучить простейшие методы неразрушающего сжатия.
- •1. Введение и классификация
- •2. Понятие кодовой таблицы.
- •3. Минимальное равномерное кодирование.
- •3.1 Принцип работы.
- •3.2 Алгоритм кодирования.
- •3.3 Алгоритм декодирования.
- •3.4 Адаптивные и вариантные кодовые таблицы
- •4. Коэффициент сжатия
- •5. Неразрушающее групповое кодирование
- •Задания
- •Лабораторная работа №2 «иСследование методов неразрушающего сжатия информации. Минимальное неРавномерное кодирование» Цель работы
- •1. Принцип работы.
- •2. Дешифрация минимальных неравномерных кодов.
- •Метод последовательного разбора.
- •Алгоритмы генерации кодовой таблицы.
- •Алгоритм Шэннона-Фано.
- •Коэффициент сжатия.
- •2.2. Разрушающее групповое кодирование.
- •Сжатие палитры.
- •2.4. Психофизиологические методы.
- •3. Популярные форматы разрушающего сжатия
- •3.1 Сжатие статичной графики.
- •3.2 Сжатие динамической графики
- •3.3 Сжатие аудио
- •3.4 Совместное сжатие аудио и видео
- •3.5 Универсальные методы сжатия
Задания
Определить минимальную кодовую длину для сообщения "мама мыла раму"
Закодировать в минимальный равномерный код сообщение "мама мыла раму"
Определить коэффициент сжатия при минимальном равномерном кодировании, для сообщения "мама мыла раму"
Декодировать из минимального равномерного кода сообщение "000001000001010000011100001010101001000110" если известна кодовая таблица:
-
символ
код
м
000
а
001
_
010
ы
011
л
100
р
101
у
110
Лабораторная работа №2 «иСследование методов неразрушающего сжатия информации. Минимальное неРавномерное кодирование» Цель работы
Цель работы – изучить алгоритм "минимального неравномерного кодирования", одного из самых применяемых методов неразрушающего сжатия, освоить генерацию кодовых таблиц минимального неравномерного кодирования с использованием алгоритма Шеннона-Фано, а также изучить вопрос определения коэффициента сжатия для методов минимального неравномерного кодирования.
Теоретическое обоснование
1. Принцип работы.
Различие с методом минимального равномерного кодирования, проявляется при составлении кодовой таблицы. Для часто встречающихся символов используются очень короткие коды, длиной меньше nmin = . Тогда для редких символов, придется использовать длинные коды, длиной даже больше чем nmin.
Кроме этого, в силу того что задача дешифрации при использовании этого метода оказывается не так тривиальна, различия имеются также в алгоритме дешифрации.
2. Дешифрация минимальных неравномерных кодов.
Проблема: как определить границы между отдельными кодами?
Решение проблемы: возможно т. н. методом «последовательного разбора», но только если наложить на используемые коды дополнительное ограничение - никакие первые биты длинных кодов, не должны совпадать с короткими кодами.
Если, при составлении таблицы, означенное условие выполнено, возможна дешифрация с использованием "метода последовательного разбора".
Метод последовательного разбора.
Считываем из файла первый бит.
Интерпретируя этот бит - как возможный код, просматриваем кодовую таблицу и ищем - нет ли в таблице такого кода.
Если нет, считывается второй бит и т. д. пока не получим совпадение считанного кода с одним из кодов кодовой таблицы. Считаем - символ найден.
4. С того места, где закончен поиск предыдущего символа, аналогично начинаем поиск нового символа. Повторяем алгоритм поиска нового символа до тех пор, пока не будут определены все символы.
Алгоритмы генерации кодовой таблицы.
Задача: составить такую кодовую таблицу, чтобы часто встречающиеся символы в ней были закодированы короткими кодами и при этом короткие коды не совпадали с первыми битами длинных кодов.
Два наиболее популярных метода:
Алгоритм Шеннона-Фано - более простой и быстрый.
Алгоритм Лэмпэла-Зива - усовершенствованный алгоритм Шэннона-Фано, обеспечивает большее сжатее, но сложнее и требует больших вычислений при составлении кодовой таблицы.