СибГУТИ Лабораторная работа 1 Теория информации скачать бесплатно
Формулировка задания
Цель работы: Экспериментальное изучение свойств энтропии Шеннона.
Среда программирования: любая с С-подобным языком программирования.
Результат: программа, тестовые примеры, отчет.
Задание:
1. Для выполнения этой практической работы необходимо иметь три файла. Объем каждого файла больше 10 Кб, формат txt.
В первом файле должна содержаться последовательность символов (количество различных символов больше 3) с равномерным распределением, т.е. символы в файле встречаются равновероятно и независимо.
Второй файл должен содержать независимую последовательность символов (количество различных символов больше 3) с неравновероятным распределением. Вероятности символов должны быть заданы заранее, до создания файла.
Эти два файла необходимо сгенерировать программно, используя генератор псевдослучайных чисел.
В третьем файле содержится фрагмент художественного текста на русском или английском языке. Для художественных текстов (русский или английский языки) предполагается, что строчные и заглавные символы не отличаются, знаки препинания объединены в один символ, к алфавиту добавлен пробел, для русских текстов буквы «е» и «ё», «ь» и «ъ» совпадают. При использовании текста программы учитываются все символы, кроме знаков табуляции.
2. Составить программу, определяющую оценки энтропии имеющихся текстовых файлов.
Для вычисления оценки энтропии необходимо программно вычислить частоты символов (пар символов) в файле, которые будут оценками реальных вероятностей символов, а затем, используя формулу Шеннона, вычислить оценки энтропии файла.
По желанию можно продолжить процесс вычисления оценок с использованием частот троек, четверок символов и т.д.
Для того чтобы правильно рассчитать частоты двойных комбинаций символов пары символов нужно рассматривать так
Пусть имеется такая последовательность
фывафпро
Под парами понимаются пары соседних символов, т.е.
фы ыв ва аф фп пр ро
Далее для получения оценки энтропии подсчитать частоту встречаемости для каждой пары и подставить в формулу Шеннона. Полученное значение оценки энтропии следует разделить на 2.
3. После тестирования программы необходимо заполнить таблицу для отчета и проанализировать полученные результаты. Сравните полученные оценки между собой. Объясните полученные результаты
Оценка энтропии
(частоты отдельных символов) Оценка энтропии
(частоты пар символов) Теоретическое значение энтропии
Файл 1
Файл 2
фрагмент художественного произведения
Краткое описание алгоритмов программы
Функция bool GenerateFile(char *fname, char s[], double p[], int total) осуществляет генерацию файлов последовательностей символов массива s. Вероятности распределения символов задаются в массиве p. Алгоритм работы функции основан на генераторе псевдослучайных чисел.
Функция double H(int m, double p[]) производит вычисление энтропии Шеннона по формуле:
В качестве входных параметров функция принимает число возможных символов m и массив их вероятностей p.
Функция int CombFrequency(char *fname, int len, char *s[], double p[]) осуществляет чтение символов из файла и составление частот их вхождений. Параметром len задается количество символов в одном состоянии. Частоты состояний заносятся в массив p.
Функция char *ArtTextPreprocessing(char *fname) осуществляет предварительную обработку файла с художественным текстом перед анализом, согласно заданию. В качестве параметра функция принимает указатель на строку с именем файла для анализа. Функция возвращает указатель на строку с именем обработанного файла.
Результаты работы программы
Анализ и сравнение полученных результатов с теоретическими оценками
Оценка энтропии
(частоты отдельных символов) Оценка энтропии
(частоты пар символов) Теоретическое значение энтропии
Файл 1 1,9838 1,98371 2
Файл 2 1,62482 1,62471 1,6838
фрагмент художественного произведения 4,18682 3,77125 4,80735
Из полученных результатов видно, что максимальное значение энтропии достигается в случае равномерных распределений символов. На значение энтропии не повлиял способ вычисления, результат получился одинаковым, как для отдельных символов, так и для пар символов. Оценки энтропии, полученные экспериментальным путем, получились немного ниже теоретических значений. Из всего вышесказанного можно сделать вывод, что неравномерность распределения символов снижает количество информации сообщения.
Файл f3.txt содержит фрагмент художественного текста на английском языке. Имеем 28 символов: 26; 1 – знаки препинания; 1 – пробел. Максимальное значение энтропии будет при равномерном распределении символов:
Оценки энтропии для фрагмента художественного произведения получились ниже максимальных значений по причине неравновероятного распределения символов в тексте.
Оценки энтропии для фрагмента художественного произведения для пар символов получились ниже энтропии отдельных символов, так как в тексте присутствуют не все возможные сочетания пар символов.
