Контрольная и Лабораторная работа 1-3 по дисциплине: Теория информации. Вариант 11

Вычислить энтропию Шеннона для символов ФИО.
 Л О П А Т И Н Г Р Ь К Е В Ч
Ч 2 3 1 2 1 5 2 1 1 1 1 1 1 1
В 0,09 0,13 0,04 0,09 0,04 0,22 0,09 0,04 0,04 0,04 0,04 0,04 0,04 0,04


 Построить код Хаффмана для набора букв ФИО. Для оценки вероятностей символов использовать частоты вхождения букв в ФИО. Подсчитать среднюю длину кодового слова построенного кода.
 Л О П А Т И Н Г Р Ь К Е В Ч
Ч 2 3 1 2 1 5 2 1 1 1 1 1 1 1
В 0,09 0,13 0,04 0,09 0,04 0,22 0,09 0,04 0,04 0,04 0,04 0,04 0,04 0,04
 Построить код Фано для набора букв ФИО. Подсчитать среднюю длину кодового слова построенного кода.

Буква Вероятность Кодовое слово Длина
И 0,22 0 0     2
О 0,13 0 1 0    3
А 0,09 0 1 1 0   4
Н 0,09 0 1 1 1   4
Л 0,09 1 0 0    3
Ч 0,04 1 0 1 0   4
Е 0,04 1 0 1 1 0  5
В 0,04 1 0 1 1 1  5
Ь 0,04 1 1 0 0   4
К 0,04 1 1 0 1 0  5
Г 0,04 1 1 0 1 1  5
Р 0,04 1 1 1 0   4
П 0,04 1 1 1 1 0  5
Т 0,04 1 1 1 1 1  5
 Построить код Шеннона для набора букв ФИО. Подсчитать среднюю длину кодового слова построенного кода.
Буква Pi Qi-1 Li Кодовое слово
И 1/23≤0,22<1/22 0 3 000
О 1/23≤0,13<1/22 0,22 3 001
А 1/24≤0,09<1/23 0,35 4 0101
Н 1/24≤0,09<1/23 0,44 4 0111
Л 1/24≤0,09<1/23 0,53 4 1000
Ч 1/25≤0,04<1/24 0,62 5 10011
Е 1/25≤0,04<1/24 0,66 5 10101
В 1/25≤0,04<1/24 0,70 5 10110
Ь 1/25≤0,04<1/24 0,74 5 10111
К 1/25≤0,04<1/24 0,78 5 11000
Г 1/25≤0,04<1/24 0,82 5 11010
Р 1/25≤0,04<1/24 0,86 5 11011
П 1/25≤0,04<1/24 0,90 5 11100
Т 1/25≤0,04<1/24 0,94 5 11110
 Построить код Гилберта-Мура для набора букв ФИО. Подсчитать среднюю длину кодового слова построенного кода.

Буква Pi Qi Li Кодовое слово
И 1/23≤0,22<1/22 0,11 4 0001
О 1/23≤0,13<1/22 0,285 4 0100
А 1/24≤0,09<1/23 0,395 5 01100
Н 1/24≤0,09<1/23 0,485 5 01111
Л 1/24≤0,09<1/23 0,575 5 10010
Ч 1/25≤0,04<1/24 0,64 6 101000
Е 1/25≤0,04<1/24 0,68 6 101011
В 1/25≤0,04<1/24 0,72 6 101110
Ь 1/25≤0,04<1/24 0,76 6 110000
К 1/25≤0,04<1/24 0,80 6 110011
Г 1/25≤0,04<1/24 0,84 6 110101
Р 1/25≤0,04<1/24 0,88 6 111000
П 1/25≤0,04<1/24 0,92 6 111010
Т 1/25≤0,04<1/24 0,96 6 111101
 Сравнить между собой энтропию Шеннона, вычисленную в п.1, и величины средних длин кодового слова для построенных кодов.

Энтропия Шеннона равна 3,47.

Средняя длина кодового слова для кода Хаффмана равна 3,49. Это значение немного больше энтропии Шеннона, что соответствует теоретическим оценкам.




Лабораторная работа No1

Формулировка задания

Цель работы: Экспериментальное изучение свойств энтропии Шеннона.

Среда программирования: любая с С-подобным языком программирования.

Результат: программа, тестовые примеры, отчет.

Задание:
1. Для выполнения этой практической работы необходимо иметь три файла. Объем каждого файла больше 10 Кб, формат txt.
В первом файле должна содержаться последовательность символов (количество различных символов больше 3) с равномерным распределением, т.е. символы в файле встречаются равновероятно и независимо.
Второй файл должен содержать независимую последовательность символов (количество различных символов больше 3) с неравновероятным распределением. Вероятности символов должны быть заданы заранее, до создания файла.
Эти два файла необходимо сгенерировать программно, используя генератор псевдослучайных чисел.
В третьем файле содержится фрагмент художественного текста на русском или английском языке. Для художественных текстов (русский или английский языки) предполагается, что строчные и заглавные символы не отличаются, знаки препинания объединены в один символ, к алфавиту добавлен пробел, для русских текстов буквы «е» и «ё», «ь» и «ъ» совпадают. При использовании текста программы учитываются все символы, кроме знаков табуляции.

2. Составить программу, определяющую оценки энтропии имеющихся текстовых файлов.
Для вычисления оценки энтропии необходимо программно вычислить частоты символов (пар символов) в файле, которые будут оценками реальных вероятностей символов, а затем, используя формулу Шеннона, вычислить оценки энтропии файла.
По желанию можно продолжить процесс вычисления оценок с использованием частот троек, четверок символов и т.д.
Для того чтобы правильно рассчитать частоты двойных комбинаций символов пары символов нужно рассматривать так
Пусть имеется такая последовательность
фывафпро
Под парами понимаются пары соседних символов, т.е.
фы ыв ва аф фп пр ро

Далее для получения оценки энтропии подсчитать частоту встречаемости для каждой пары и подставить в формулу Шеннона. Полученное значение оценки энтропии следует разделить на 2.

3. После тестирования программы необходимо заполнить таблицу для отчета и проанализировать полученные результаты. Сравните полученные оценки между собой. Объясните полученные результаты

 Оценка энтропии
(частоты отдельных символов) Оценка энтропии
(частоты пар символов) Теоретическое значение энтропии
Файл 1     
Файл 2     
фрагмент художественного произведения   


Лабораторная работа No2
Формулировка задания

Оптимальное побуквенное кодирование
Цель работы: Изучение метода оптимального кодирования Хаффмана.
Среда программирования: любая с С-подобным языком программирования.
Результат: программа, тестовые примеры, отчет.

1. Запрограммировать процедуру двоичного кодирования текстового файла методом Хаффмана. Текстовые файлы использовать те же, что и в практической работе No1. Для художественных текстов (русский или английский языки) предполагается, что строчные и заглавные символы не отличаются, знаки препинания объединены в один символ, к алфавиту добавлен пробел, для русских текстов буквы «е» и «ё», «ь» и «ъ» совпадают.
2. Проверить, что полученный код является префиксным.
3. После кодирования текстового файла вычислить оценки энтропии выходной последовательности, используя частоты отдельных символов, пар символов и троек символов.
4. Заполнить таблицу и проанализировать полученные результаты.
Метод
кодирования Название текста Оценка
избыточности кодирования Оценка энтропии выходной посл-ти (частоты символов) Оценка энтропии выходной посл-ти (частоты пар символов) Оценка энтропии выходной посл-ти (частоты троек символов)
Метод Хаффмана Файл 1       
 Файл 2       
 фрагмент художественного произведения       

Избыточность кодирования определяется как , где H – энтропия текста, Lcp – средняя длина кодового слова.
 
Лабораторная работа No3

Формулировка задания

Методы почти оптимального кодирования
Цель работы: Изучение метода почти оптимального кодирования Фано. Изучение метода почти оптимального кодирования Шеннона
Среда программирования: любая с С-подобным языком программирования.
Результат: программа, тестовые примеры, отчет.
1. Запрограммировать процедуры двоичного кодирования текстового файла методом Фано и процедуру двоичного кодирования текстового файла методом Шеннона. Текстовые файлы использовать те же, что и в практической работе No1. Для художественных текстов (русский или английский языки) предполагается, что строчные и заглавные символы не отличаются, знаки препинания объединены в один символ, к алфавиту добавлен пробел, для русских текстов буквы «е» и «ё», «ь» и «ъ» совпадают.
2. Проверить, что полученные коды являются префиксными.
3. Для каждого метода кодирования после кодирования вычислить оценки энтропии выходной последовательности, используя частоты отдельных символов, пар символов и тройки символов.
4. После тестирования программы необходимо заполнить таблицу и проанализировать полученные результаты.
Метод
кодирования Файлы Оценка
избыточности кодирования Оценка энтропии выходной посл-ти (частоты символов) Оценка энтропии выходной посл-ти (частоты пар символов) Оценка энтропии выходной посл-ти (частоты троек символов)
Метод Хаффмана Файл 1       
 Файл 2       
 фрагмент художественного произведения       
Метод Фано Файл 1       
 Файл 2       
 фрагмент художественного произведения       
Метод Шеннона Файл 1       
 Файл 2       
 фрагмент художественного произведения       

Избыточность кодирования определяется как , где H – энтропия текста, Lcp – средняя длина кодового слова.

Оценка: Зачет
Дата оценки: 07.04.2022

Помогу с вашим онлайн тестом, другой работой или дисциплиной.
E-mail: sneroy20@gmail.com
E-mail: ego178@mail.ru