litceysel.ru 1

Теория информации



Лабораторная работа №2


Оптимальное и почти оптимальное кодирование


Запрограммировать процедуры двоичного кодирования текстового файла методом Хаффмана, методом Фано и методом Шеннона. Текстовые файлы использовать те же, что и в лабораторной работе №1. Для художественных текстов (русский или английский языки) предполагается, что строчные и заглавные символы не отличаются, знаки препинания объединены в один символ, к алфавиту добавлен пробел, для русских текстов буквы «е» и «ё», «ь» и «ъ» совпадают.

В программе должна быть предусмотрена возможность ввода имени необходимого текстового файла.

После кодирования текстового файла вычислить энтропию выходной последовательности, используя частоты отдельных символов, пар символов и тройки символов.

После тестирования программы необходимо заполнить таблицу и проанализировать полученные результаты.


Метод

кодирования

Название текста

Избыточность кодирования

Энтропия выходной посл-ти (частоты пар символов)

Энтропия выходной посл-ти (частоты пар символов)

Энтропия выходной посл-ти (частоты троек символов)

Метод Хаффмана

Текст №1













Текст №2











Метод Шеннона

Текст №1













Текст №2













Метод Фано

Текст №1













Текст №2













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