№13 лабораторная работа. Сжатие информации методом ШеннонаФано
 Скачать 84.64 Kb.
|
|
Некоммерческое акционерное общество Институт информационных технологий Кафедра Информационных систем и кибербезопасности Лабораторная работа №13 Дисциплина: Информационные основы кибербезопасности Тема: «Сжатие информации методом Шеннона-Фано» Образовательная программа: 6B06301 – “Системы информационной безопасности” _______ ________________ «____» ________________2021г. (оценка) (подпись) (дата) Алматы 2021 Содержание Введение 3 Сжатие информации 4 Ответы на вопросы 8 Вывод 10 Литература 11 Введение Алгоритм метода Шеннона-Фано — один из первых алгоритмов сжатия, который впервые сформулировали американские учёные Шеннон и Фано, и он имеет большое сходство с алгоритмом Хаффмана. Алгоритм основан на частоте повторения. Так, часто встречающийся символ кодируется кодом меньшей длины, а редко встречающийся — кодом большей длины. В свою очередь, коды, полученные при кодировании, префиксные. Это и позволяет однозначно декодировать любую последовательность кодовых слов. Алгоритм Шеннона-Фано работает следующим образом: На вход приходят упорядоченные по невозрастанию частот данные. Находится середина, которая делит алфавит примерно на две части. Эти части (суммы частот алфавита) примерно равны. Для левой части присваивается «1», для правой «0», таким образом мы получим листья дерева Шаг 2 повторяется до тех пор, пока мы не получим единственный элемент последовательности, т.е. листок. Сжатие информации Нужно сжать следующее сообщение: «Длинношеее животное». Сначала определяю частоту символов и вероятность.
После нужно определить относительную частоту встречаемости символа. Относительная частота встречаемости символа определяется как отношение абсолютной частоты появления символа в сообщении к общей длине сообщения (числу символов в сообщении):  , где ωi – абсолютная частота встречаемости i-ого символа алфавита источника; m – число символов в сообщении.  Рисунок 1 – «Относительная частота появления символа «е»»  Рисунок 2 – «Относительная частота появления символов «о», «н»»  Рисунок 3 – «Относительная частота появления символа «и»»  Рисунок 4 – «Относительная частота появления символов «д», «л», «ш», «ж», «в», «т»» Теперь находим энтропию сообщения. Ниже представлена формула энтропии сообщения:  ,Где H – энтропия сообщения; n – длина кодовой комбинации при равномерном кодировании.  При использовании равномерного кода длина кодовой комбинации определяется так: 𝑛 = ⌈𝑙𝑜𝑔2𝑁⌉, В моём случаи N равно 11. 𝑛 = 𝑙𝑜𝑔211=3,45 бита. Нахожу значение L по этой формуле:  ,Избыточность сообщения при кодировании равномерным кодом равна:  Для получения кодовых комбинаций строится кодовое дерево. При построении кода Шеннона-Фано дерево строится от корня к листьям (в отличие от настоящего дерева здесь корень располагается вверху, а листья – внизу). В качестве корня, используется множество всех символов алфавита сообщения (рисунок 1.1), упорядоченное по частоте встречаемости символов. Число сверху таблицы равно суммарной частоте символов в исходном сообщении (суммарное число символов в сообщении).  Рисунок 5 – «Исходное сообщение» На следующей странице у меня находится кодовое дерево. Буду строить с помощью значений вероятности.     Рисунок 6 – «Кодовое дерево»
И у нас получится такое закодированное сообщение: 01010100011100100101001111111100000010001100101101000110010111 Общая длина закодированного сообщения составляет 62 бит. Средняя длина кодовой комбинации равна (напомним, что число символов в сообщении – 19):  бит/символНахожу энтропию: Избыточность сообщения после применения кода Шеннона-Фано снизилась до значения:  Ответы на вопросы 1) В чем отличие метода Шеннона-Фано от Хаффмана? В отличие от алгоритма Шеннона — Фано, алгоритм Хаффмана остаётся всегда оптимальным и для вторичных алфавитов m2 с более чем двумя символами. Этот метод кодирования состоит из двух основных этапов: Построение оптимального кодового дерева. Построение отображения код-символ на основе построенного дерева. 2) Что такое оптимальный код? Оптимальный префиксный код с длиной кодового слова не более L бит ... Оптимальный префиксный код с длиной кодового слова не более L бит — это код, обладающий следующими свойствами: длина кодового слова не превышает заданной константы, является оптимальным среди всех префиксных кодов, удовлетворяющих первому условию. 3) Поясните алгоритм оптимального кодирования Шеннона-Фано. Алгоритм использует коды переменной длины: часто встречающийся символ кодируется кодом меньшей длины, редко встречающийся — кодом большей длины. ... Коды Шеннона — Фано — префиксные, то есть никакое кодовое слово не является префиксом любого другого. 4) Поясните алгоритм оптимального кодирования метода Хаффмана. Алгоритм Хаффмана — алгоритм оптимального префиксного кодирования алфавита с минимальной избыточностью. Был разработан в 1952 году аспирантом Массачусетского технологического института Дэвидом Хаффманом при написании им курсовой работы. В настоящее время используется во многих программах сжатия данных. 5) Понятие избыточности. Как осуществляется расчет избыточности? Избыточность — термин из теории информации, означающий превышение количества информации, используемой для передачи или хранения сообщения, над его информационной энтропией. Для уменьшения избыточности применяется сжатие данных без потерь, в то же время контрольная сумма применяется для внесения дополнительной избыточности в поток, что позволяет производить исправление ошибок при передаче информации по каналам, вносящим искажения (спутниковая трансляция, беспроводная передача и т. д.). 6) Что такое энтропия? Энтропи́я (от др.-греч. ἐν «в» + τροπή «обращение; превращение») — широко используемый в естественных и точных науках термин (впервые введён в рамках термодинамики как функция состояния термодинамической системы), обозначающий меру необратимого рассеивания энергии или бесполезности энергии (потому что не всю энергию системы можно использовать для превращения в какую-нибудь полезную работу). Для понятия энтропии в данном разделе физики используют название термодинамическая энтропия; термодинамическая энтропия обычно применяется для описания равновесных (обратимых) процессов. 7) Что такое сжатие алфавита? Алгоритм Хаффмана — алгоритм оптимального префиксного кодирования алфавита с минимальной избыточностью. Был разработан в 1952 году аспирантом Массачусетского технологического института Дэвидом Хаффманом при написании им курсовой работы. В настоящее время используется во многих программах сжатия данных. 8) Что такое префиксные коды? Пре́фиксный код в теории кодирования — код со словом переменной длины, имеющий такое свойство (выполнение условия Фано): если в код входит слово a, то для любой непустой строки b слова ab в коде не существует. Хотя префиксный код состоит из слов разной длины, эти слова можно записывать без разделительного символа. 9) Сколько требуется двоичных знаков для записи кодированного сообщения? При кодировании по Фано все сообщения записываются в таблицу по степени убывания вероятности и разбиваются на две группы примерно (насколько это возможно) равной вероятности. Соответственно этой процедуре из корня кодового дерева исходят два ребра, которым в качестве весов присваиваются полученные вероятности. Двум образовавшимся вершинам приписывают кодовые символы 0 и 1. Затем каждая из групп вероятностей вновь делится на две подгруппы примерно равной вероятности. В соответствии с этим из каждой вершины 0 и 1 исходят по два ребра с весами, равными вероятностям подгрупп, а вновь образованным вершинам приписывают символы 00 и 01, 10 и 11. В результате многократного повторения процедуры разделения вероятностей и образования вершин приходим к ситуации, когда в качестве веса, приписанного ребру бинарного дерева, выступает вероятность одного из данных сообщений. В этом случае вновь образованная вершина оказывается листом дерева, т.к. процесс деления вероятностей для нее завершен. Задача кодирования считается решенной, когда на всех ветвях кодового бинарного дерева образуются листья. Вывод В этой лабораторной работе мы разобрали моменты работы сжатия информации. Разобрали следующий метод: Шеннона-Фано. Выполнили неравномерное сжатие. С методом Шеннона-Фано мы кодируем. Метод Шеннона-Фано – сверху-вниз. Кодирование Шеннона — Фано является достаточно старым методом сжатия, и на сегодняшний день оно не представляет особого практического интереса. В большинстве случаев длина последовательности, сжатой по данному методу, равна длине сжатой последовательности с использованием кодирования Хаффмана. Но на некоторых последовательностях могут сформироваться неоптимальные коды Шеннона — Фано, поэтому более эффективным считается сжатие методом Хаффмана. Литература 1. Анализ и исследование информационной безопасности телекоммуникационных сетей на основе имитационного моделирования с применением различных пакетов прикладных программ. Монография: Якубова Муборак Захидовна, Голубева Татьяна.- Министерство образования и науки Республики Казахстан Некоммерческое акционерное общество «Алматинский университет энергетики и связи 2019. 2. Попова Ольга Владимировна. Учебное пособие по информатике. 3. ↑ Sanchez, Julio & Canton, Maria P. (2007), Microcontroller programming: the microchip PIC, Boca Raton, Florida: CRC Press, с. 37, ISBN 0-8493-7189- 9 4. Experts 'decipher' Inca strings. Архивировано 18 августа 2011 года. 5. ↑ Carlos Radicati di Primeglio, Gary Urton. Estudios sobre los quipus (неопр.). — С. 49. 6. ↑ http://www.leibniz-translations.com/binary.htm Leibniz Translation.com EXPLANATION OF BINARY ARITHMETIC |