- •Лабораторная работа №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 Универсальные методы сжатия
Алгоритм Шэннона-Фано.
Будем считать список из разновидности символов встречаемых в тексте "группой символов".
Подсчитаем частоту появления Fi для каждого из символов, входящего в группу символов.
Ранжируем символы по частоте: от самых частых в начале списка к самым редким в конце списка.
Подсчитаем сумму частот F символов в группе.
Подсчитаем половину суммы частот F/2 символов в группе.
Разобьем группу на 2 подгруппы:
- подгруппу нулей, куда будут включены более частые символы, их коды начинаются с 0,
- подгруппу единиц, куда будем включать коды более редких символов.
Разбивать будем так, чтобы сумма частот Fi символов в обеих подгруппах - оказалась по возможности одинаковой. Для этого:
а) начинаем включать символы в подгруппу единиц, начиная с самого редкого;
б) после включения каждого символа подсчитывается текущая сумма частот Fi в подгруппе единиц;
в) включаем символы в подгруппу нулей до тех пор, пока текущая сумма частот Fi в подгруппе единиц, не окажется равной или не привысит F/2;
г) оставшиеся символы включим в подгруппу нулей;
д) проверим, остались ли символы в подгруппе единиц, если нет, то один из символов подгруппы нулей, последний из внесённых подгруппу единиц, перенесем в подгруппу нулей.
Результат выполнения пунктов 1-6 - получили первый бита кода для каждого из символов.
Определяем второй бит. Для этого:
а) каждую из получившихся в пункте 6 подгрупп назовем группой;
б) если в группе оказывается всего один символ, других бит в коде этого символа уже не будет – код символа определён;
б) каждую группу, в которой более 1 символа, разобьем на подгруппы точно так же, как мы это делали в пунктах 1-7.
Процесс разбиения групп на подгруппы, и определения новых бит - будет продолжаться до тех пор, пока в каждой группе - не останется по одному символу.
Задача.
Составить кодовую таблицу для сжатия фразы «мама мыла раму».
Решение.
Оформим решение в виде таблицы:
-
Символ
Fi
Бит 1
Бит 2
Бит 3
Бит 4
Бит 5
м
4
0
а
4
1
0
_
2
1
1
0
0
ы
1
1
1
0
1
л
1
1
1
1
0
р
1
1
1
1
1
0
у
1
1
1
1
1
1
Ответ: получим следующие коды символов: М = 0; А = 10; _ = 1100; Ы = 1101; Л = 1110; Р = 00001; У = 11111.