фано. Практическая работа 11 Тема Расчет и построение кода ШеннонаФано. Цель Построение кодового дерева ивычисление коэффициента сжатия
 Скачать 22.42 Kb.
|
|
Практическая работа 11 Тема: Расчет и построение кода Шеннона-Фано. Цель : Построение кодового «дерева» и вычисление коэффициента сжатия. Теоретические сведения Сжатие данных (data compression) - это алгоритм эффективного кодирования информации, при котором она занимает меньший объем памяти, нежели ранее. Мы избавляемся от избыточности (redundancy), т.е. удаляем из физического представления данных те биты, которые в действительности не требуются, оставляя только то количество битов, которое необходимо для представления информации в соответствии со значением энтропии. Существует показатель эффективности сжатия данных: коэффициент сжатия (compression ratio). Он вычисляется путем вычитания из единицы частного от деления размера сжатых данных на размер исходных данных и обычно выражается в процентах. Например, если размер сжатых данных равен 1000 бит, а несжатых - 4000 бит, коэффициент сжатия составит 75%, т.е. мы избавились от трех четвертей исходного количества битов. Существует два основных типа сжатия данных: с потерями (lossy) и без потерь (lossless). Lossless- метод сжатия данных, когда распаковка упакованного файла приводит к созданию файла, который имеет в точности то же содержимое, что и оригинал перед его сжатием. И напротив, сжатие с потерями не позволяет при восстановлении получить те же исходные данные. Это кажется недостатком, но для определенных типов данных, таких как данные изображений и звука, различие между восстановленными и исходными данными не имеет особого значения: наши зрение и слух не в состоянии уловить образовавшиеся различия. В общем случае алгоритмы сжатия с потерями обеспечивают более эффективное сжатие, чем алгоритмы сжатия без потерь. Для примера можно сравнить предназначенный для хранения изображений формат с потерями JPEG с форматом без потерь GIF. Множество форматов потокового аудио и видео, используемых в Internet для загрузки мультимедиа-материалов, являются алгоритмами сжатия с потерями. Алгоритм сжатия Шеннона-Фано является алгоритмом сжатия без потерь и называются кодированием с минимальной избыточностью (minimum redundancy coding). Код Шеннона-Фано строится с помощью дерева. Построение этого дерева начинается от корня. Всё множество кодируемых элементов соответствует корню дерева (вершине первого уровня). Оно разбивается на два подмножества с примерно одинаковыми суммарными вероятностями. Эти подмножества соответствуют двум вершинам второго уровня, которые соединяются с корнем. Далее каждое из этих подмножеств разбивается на два подмножества с примерно одинаковыми суммарными вероятностями. Им соответствуют вершины третьего уровня. Если подмножество содержит единственный элемент, то ему соответствует концевая вершина кодового дерева; такое подмножество разбиению не подлежит. Подобным образом поступаем до тех пор, пока не получим все концевые вершины. Ветви кодового дерева размечаем символами 1 и 0, как в случае кода Хаффмана. Пусть дан текстовый файл в котором символы встречаются с числом встречаемости из таблицы1. Таблица1. Список узлов по алфавиту
Сумма чисел встречаемости символов равна 100. Делим символы на две группы с примерно одинаковой встречаемостью:АСF с вероятностью 50 и BDE с такой же вероятностью. Это две ветви выходящих из корня. Далее алгоритм повторяется. Группа ACF разбивается на две : С с встречаемостью 30 и AF с встречаемостью 20. Группа BDE – на BD и Е с соответствующими числами 25 и 25. Алгоритм прекращается для одиночных символов и продолжается для групп. AF и BD делятся на две части. Дерево построено, присваиваем левому повороту 0-й бит, а правому -1-й бит. A B C D E F (100) 0/ 1\ А С F(50) B D E(50) 0/ 1\ 0/ 1\ C(30) AF(20) E(25) BD(25) 0/ 1\ 0/ 1\ A(10) F(10) B(20) D(5) Отсчет кода ведется от корня. Таблица3. Кодовые последовательности
Каждый символ изначально представлялся 8-ю битами(1байт), и при уменьшении числа битов уменьшается и размер выходного файла. Сжатие складывается таким образом(таблица4): Таблица 4 .Расчет сжатия символов
Первоначальный размер файла : 100 байт = 800бит Размер сжатого файла: 30 байт = 245 бит Процент сжатия: 100-(245/800)х100 = 69%. Процент сжатия= 100-( Размер сжатого файла/ Первоначальный размер файла)*100 Порядок выполнения работы. Взять данные для расчета согласно варианта задания в приложении. Создать таблица списков узлов по алфавиту и встречаемости. Построить кодовое дерево. Заполнить таблицу кодовых последовательностей. Рассчитать сжатие символов. Рассчитать размер сжатого файла и процент сжатия. Контрольные вопросы По алгоритму Шеннона-Фано, чаще встречаемым символам соответствует более……… код. Для чего применяется алгоритм сжатия. Меньше сжимаются символы …….. встречаемые. 1720 |