Теория информации |
Указания по выполнению лабораторных работ |
Правила выполнения лабораторных работ
Перед выполнением заданий лабораторной работы рекомендуется изучить теоретический материал по теме лабораторной работы и описание методов кодирования на псевдокоде, используя конспекты лекционных занятий и литературу из списка.
Задания лабораторных работ выполняются только на языке программирования С/С++, среда программирования по выбору студента.
Изучаемые методы кодирования данных рекомендуется программно реализовывать в виде отдельных функций (подпрограмм), данные должны передаваться в подпрограммы в качестве параметров. Заполнение массивов данными, вывод их на экран, вычисление вспомогательных величин и пр. необходимо также оформлять в виде отдельных подпрограмм.
При выполнении заданий следует обеспечить вывод на экран данных на всех шагах алгоритма. Программа должна иметь дружественный, интуитивно понятный интерфейс (меню пользователя, вывод подсказок, комментарии при вводе/выводе данных и т.д.).
Тестирование разработанной программы необходимо
проводить для текстовых файлов с различным
частотным распределением символов. После тестирования необходимо
проанализировать полученные результаты, т.е. проверить соответствие полученных
экспериментальным путем величин теоретическим оценкам.
Для
зачета по лабораторной работе студенту необходимо представить
·
Исходные тексты
программ с подробными комментариями;
·
Исполняемые файлы
и тестовые файлы;
·
Отчет по
лабораторной работе.
Отчет
должен включать в себя следующие разделы
·
Формулировку
задания
·
Очень краткое описание
алгоритмов, используемых в лабораторной работе;
·
Результаты работы
программы (в виде файла или в виде скриншота);
·
Анализ и
сравнение полученных результатов с теоретическими оценками.
Лабораторная работа №1
Вычисление энтропии Шеннона
Цель работы: Экспериментальное
изучение свойств энтропии Шеннона.
Среда программирования: любая
с С-подобным языком программирования.
Результат: программа,
тестовые примеры, отчет.
Задание:
1.
Для выполнения данной лабораторной работы необходимо предварительно
сгенерировать два файла. Каждый файл содержит последовательность символов,
количество различных символов больше 2 (3,4 или 5). Объем файлов больше 10 Кб,
формат txt.
Первый
файл (назовем его F1) должен содержать
последовательность символов с равномерным распределением, т.е. символы
встречаются в последовательности равновероятно и независимо.
Второй
файл (F2) содержит последовательность символов с
неравновероятным распределением.
2.
Составить программу, определяющую несколько оценок энтропии созданных текстовых
файлов. Оценки энтропии необходимо вычислить по формуле Шеннона двумя
способами, т.е. используя частоты отдельных символов и используя частоты пар
символов. По желанию можно продолжить процесс вычисления оценок с
использованием частот троек, четверок символов и т.д.
3. После тестирования
программы необходимо заполнить таблицу для отчета и проанализировать полученные
результаты.
|
Оценка энтропии (частоты отдельных символов) |
Теоретическое значение энтропии (отдельные символы) |
Оценка энтропии (частоты пар символов) |
Теоретическое значение энтропии (для пар символов) |
F1 |
|
|
|
|
F2 |
|
|
|
|
Лабораторная работа №2
Вычисление энтропии Шеннона
Цель работы:
Экспериментальное изучение свойств энтропии Шеннона.
Среда программирования: любая
с С-подобным языком программирования.
Результат: программа,
тестовые примеры, отчет.
Задание:
1. Составить программу,
определяющую несколько оценок энтропии текстового файла (размер не менее 10 Кб).
Оценки энтропии необходимо вычислить по формуле Шеннона двумя способами, т.е.
используя частоты отдельных символов и используя частоты пар символов. По
желанию можно продолжить процесс вычисления оценок с использованием частот
троек, четверок символов и т.д.
Для художественных текстов
(русский или английский языки) предполагается, что строчные и заглавные символы
не отличаются, знаки препинания объединены в один символ, к алфавиту добавлен
пробел, для русских текстов буквы «е» и «ё», «ь» и «ъ» совпадают. При
использовании текста программы учитываются все символы, кроме знаков табуляции.
2. После тестирования
программы необходимо заполнить таблицу для отчета и проанализировать полученные
результаты. Сравнить полученные результаты с результатами лабораторной работы
1.
Название текста |
Максимально возможное значение энтропии |
Оценка энтропии (одиночные символы) |
Оценка энтропии (частоты пар символов) |
Текст №1 (фрагмент художественного произведения) |
|
|
|
Текст №2 (фрагмент художественного произведения) |
|
|
|
Текст написанной программы |
|
|
|
Лабораторные работы №3
Оптимальное побуквенное кодирование
Цель работы: Изучение метода
оптимального кодирования Хаффмана.
Среда программирования: любая
с С-подобным языком программирования.
Результат: программа,
тестовые примеры, отчет.
1.
Запрограммировать процедуру двоичного кодирования текстового файла методом Хаффмана. Текстовые файлы
использовать те же, что и в лабораторных работах №1,2. Для художественных
текстов (русский или английский языки) предполагается, что строчные и заглавные
символы не отличаются, знаки препинания объединены в один символ, к алфавиту
добавлен пробел, для русских текстов буквы «е» и «ё», «ь» и «ъ» совпадают.
2.
Проверить, что полученный код является префиксным.
3.
После кодирования текстового файла вычислить оценки энтропии выходной
последовательности, используя частоты отдельных символов, пар символов и троек
символов.
4.
Заполнить таблицу и проанализировать полученные результаты.
Метод кодирования |
Название текста |
Оценка избыточности кодирования |
Оценка энтропии выходной посл-ти (частоты символов) |
Оценка энтропии выходной посл-ти (частоты пар символов) |
Оценка энтропии выходной посл-ти (частоты троек символов) |
Метод Хаффмана |
Текст №1 |
|
|
|
|
Текст №2 |
|
|
|
|
Избыточность кодирования определяется как , где H – энтропия текста, Lcp – средняя длина кодового слова.
Лабораторные работы №4
Методы почти оптимального кодирования
Цель работы: Изучение метода
почти оптимального кодирования Фано.
Среда программирования: любая
с С-подобным языком программирования.
Результат: программа,
тестовые примеры, отчет.
1.
Запрограммировать процедуры двоичного кодирования текстового файла методом Фано. Текстовые файлы использовать те
же, что и в лабораторной работе №1 и 2. Для художественных текстов (русский или
английский языки) предполагается, что строчные и заглавные символы не
отличаются, знаки препинания объединены в один символ, к алфавиту добавлен
пробел, для русских текстов буквы «е» и «ё», «ь» и «ъ» совпадают.
2.
Проверить, что полученный код является префиксным.
3 После
кодирования текстового файла вычислить оценки энтропии выходной
последовательности, используя частоты отдельных символов, пар символов и тройки
символов.
4.
После тестирования программы необходимо заполнить таблицу и проанализировать
полученные результаты.
Метод кодирования |
Название текста |
Оценка избыточности кодирования |
Оценка энтропии выходной посл-ти (частоты символов) |
Оценка энтропии выходной посл-ти (частоты пар символов) |
Оценка энтропии выходной посл-ти (частоты троек символов) |
Метод Хаффмана |
Текст №1 |
|
|
|
|
Текст №2 |
|
|
|
|
|
Метод Фано |
Текст №1 |
|
|
|
|
Текст №2 |
|
|
|
|
Избыточность кодирования определяется как , где H – энтропия текста, Lcp – средняя длина кодового слова.
Лабораторные работы №5
Почти оптимальное кодирование
Цель работы: Изучение метода
почти оптимального кодирования Шеннона.
Среда программирования: любая
с С-подобным языком программирования.
Результат: программа,
тестовые примеры, отчет.
1.
Запрограммировать процедуру двоичного кодирования текстового файла методом Шеннона. Текстовые файлы использовать
те же, что и в лабораторной работе №1-4. Для художественных текстов (русский
или английский языки) предполагается, что строчные и заглавные символы не
отличаются, знаки препинания объединены в один символ, к алфавиту добавлен
пробел, для русских текстов буквы «е» и «ё», «ь» и «ъ» совпадают.
2.
Проверить, что полученный код является префиксным.
3.
После кодирования текстового файла вычислить оценки энтропии выходной
последовательности, используя частоты отдельных символов, пар символов и троек
символов.
4.
Заполнить таблицу и проанализировать полученные результаты.
Метод кодирования |
Название текста |
Оценка избыточности кодирования |
Оценка энтропии выходной посл-ти (частоты символов) |
Оценка энтропии выходной посл-ти (частоты пар символов) |
Оценка энтропии выходной посл-ти (частоты троек символов) |
Метод Хаффмана |
Текст №1 |
|
|
|
|
Текст №2 |
|
|
|
|
|
Метод Шеннона |
Текст №1 |
|
|
|
|
Текст №2 |
|
|
|
|
|
Метод Фано |
Текст №1 |
|
|
|
|
Текст №2 |
|
|
|
|
Избыточность кодирования определяется как , где H – энтропия текста, Lcp – средняя длина кодового слова.