Федеральное государственное образовательное бюджетное учреждение

высшего профессионального образования

Поволжский государственный университет телекоммуникаций и

информатики

кафедра ТОРС

Задание и методические указания к лабораторной работе

по дисциплинам Общая теория связи,

Теория информации и информационных систем,

для студентов 2 курса направлений 210700, 200700 дневной формы обучения Информационные характеристики дискретных источников Составители: д.т.н., проф. Николаев Б. И.

к.т.н. Борисенков А. В.

к.т.н. Чингаева А. М.

Самара, 2014 г.

УДК 621. Задание и методические указания к лабораторной работе по дисциплинам Общая теория связи, Теория информации и информационных систем для студентов 2 курса направлений 210700, 200700 дневной формы обучения Информационные характеристики дискретных источников / сост. Б. И. Николаев, А. В. Борисенков, А. М. Чингаева Самара: ПГУТИ, 2014 12 с.

Методическая разработка содержит краткую теорию и подробные указания к выполнению лабораторной работы, посвящённой анализу информационных характеристик дискретных источников.

© Б. И. Николаев © А. В. Борисенков © А. М. Чингаева © ПГУТИ 1 Краткие теоретические сведения К дискретным источникам информации относят источники с конечным алфавитом K. Примерами таких источников могут служить тексты на различных языках, телеграммы, e-mail и sms-сообщения, любые файлы данных.

С точки зрения теории информации источник характеризуется степенью неопределённости относительно выдаваемого им сообщения. Количественно эта неопределённость измеряется через информационные характеристики данного источника.

1.1 Информационные характеристики дискретного источника Основной информационной характеристикой дискретного источника является его энтропия: среднее количество информации, приходящееся на один символ источника.

K H(A) = I(ai ) = p(ai ) log2 p(ai ).

i= Здесь I(ai ) = log2 p(ai ) информация, содержащаяся в символе ai, p(ai ) вероятность его появления, A множество символов ai (алфавит источника).

Энтропия измеряется в битах на символ источника: [бит/симв].

Максимально возможное значение энтропии (максимально возможное среднее количество информации на символ) достигается при равновероятном выборе символов источником:

K 1 Hmax (A) = log2 = log2 K.

K K i= Для источника с памятью (соседние символы сообщения зависимы) вводится понятие условной энтропии:

K1 K H(A|A ) = p(ai, aj ) log2 p(ai |aj ).

i=0 j= Здесь p(ai, aj ) вероятность совместного появления символов ai и aj, вероятность появления символа ai при условии, что до него p(ai |aj ) появился символ aj (условная вероятность символа ai ), A множество символов источника на предыдущем шаге (aj ), A на текущем шаге (ai ).

Условная энтропия не превышает безусловной H(A|A ) H(A), поскольку всякая дополнительная зависимость не увеличивает (а разве только уменьшает) количество информации.

Избыточность источника H(A) n и = 1 = характеризует относительное удлинение сообщения по сравнению с источником без избыточности (с максимальной энтропией). Здесь n длина сообщения с энтропией H(A), n0 минимально возможная длина сообщения с энтропией Hmax (A).

Среднее количество информации, выдаваемое источником в единицу времени, определяется его производительностью:

где vи скорость выдачи символов.

Производительность измеряется в битах в секунду: [бит/с].

1.2 Определение энтропии языка Все естественные языки характеризуются достаточно большой избыточностью, которая обуславливается как неравновероятностью отдельных символов, так и наличием глубоких информационных связей между соседними символами (а также словами и целыми фразами).

Существует два подхода к определению энтропии языка, в предельном случае приводящие к одному и тому же результату [4].

С одной стороны, энтропию языка можно оценить как энтропию группы из n символов An, поделённую на количество символов в группе:

Группа из n символов называется n-граммой, а величина Hn С другой стороны, энтропию языка также можно оценить как условную энтропию n-го символа an при известных n 1 предыдущих символах H(A|An1 ):

В пределе, при n, обе эти величины сходятся к одному и тому же значению являющемуся энтропией данного языка [4].

В [4] также доказывается, что Hn является верхней, а Hn нижней границей H.

1.3 Опыт Шеннона Оригинальный способ определения энтропии языка был предложен в 1951 г. Шенноном [3]. Он заключается в отгадывании n-й буквы текста при известных n1 предыдущих. Мера степени неопределённости данного опыта является оценкой сверху условной энтропии.

Из осмысленного текста наугад выбираются n 1 символов и комулибо предлагается угадать n-й символ. Многократное повторение опыта даёт распределение частот правильного угадывания: частоты (вероятности) w1, w2,..., wK того, что символ будет правильно угадан с 1, 2,..., Kй попытки (K объём алфавита). Эти вероятности являются оценкой вероятностей символов алфавита, расположенных в порядке убывания частот [4]. Отсюда следует, что энтропия данного распределения будет являться оценкой (сверху) условной энтропии которая с увеличением n будет стремиться к энтропии языка.

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

1.4 Определение средней длины слова Зная вероятность (частость) появления символа пробел ( ), можно определить среднюю длину слова:

Здесь N длина текста (устремлённая к бесконечности), n число пробелов в тексте, nсл число слов в тексте, P ( ) вероятность появления пробела.

Число слов в тексте на 1 больше числа пробелов: nсл = n +1 (если считать, что текст начинается и заканчивается буквой и все слова разделены пробелами). Число пробелов связано с длиной текста через вероятность появления пробела: n = N P ( ). Вычитая число пробелов из общего числа символов, получим суммарную длину всех слов в тексте. Разделив эту величину на число слов в тексте, получим среднюю выборочную длину слова. Устремляя размер выборки (длину текста) к бесконечности, получим искомое значение nсл для произвольного текста.

Для текста на русском языке (32-символьной модели) средняя длина слова примерно равна 5 символам.

2 Домашнее задание 1. Засеките время (от 1 до нескольких минут) и наберите на компьютере произвольный текст, используя только русские буквы в нижнем регистре и пробел (без знаков препинания). Можно переписать текст из книги, учебника, лекции, набрать любой текст по памяти и т.п., главное, чтобы текст был осмысленным. Набранный текст включается в текст домашнего задания!

2. Подсчитайте количество символов в набранном тексте. Если текст набирался в обычном текстовом редакторе в кодировке WIN или DOS, то количество символов будет равняться размеру полученного файла в байтах. Если текст набирался в визуальном редакторе (Open Oce, MS Word и т.п.), то количество символов можно найти в меню статистики файла: Файл Свойства Статистика.

3. Полагая энтропию русского языка равной Hрус = 1,37 [бит/симв] (из [4]), вычислите количество информации I, содержащееся в набранном отрезке текста.

4. Зная количество информации, число символов и время, потраченное на набор текста, вычислите производительность источника H.

5. Вычислите избыточность набранного текста, полагая, что объём алфавита источника K = 32 (на самом деле 34, если вы использовали ё и ъ, но для 32-символьной модели их не учитывают, заменяя Если возможности набирать текст на компьютере нет, можно писать текст от руки.

3 Указания к выполнению работы Перед началом работы ознакомьтесь с интерфейсом пользователя:

нажмите F1 или выберите в главном меню Помощь Руководство пользователя.

3.1 Цель работы Целью работы является анализ информационных характеристик дискретных источников.

3.2 Общие замечания Для получения достоверных результатов, особенно при больших длинах n-грамм, требуется большой объём статистики. Кроме того, энтропия может существенно отличаться для текстов различных стилей: стихи, как правило, имеют меньшую энтропию, чем проза, энтропия делового текста меньше энтропии литературного и т.п.

Если расчёт идёт слишком медленно, ограничьте размер исходного текста 20–30 тысячами символов: отметьте пункт Ограничить размер и укажите размер текста в окошке Макс. длина. Однако, в этом случае достоверность получаемых результатов снизится. Степень достоверности результатов можно контролировать с помощью кнопки Статистика, отображающей таблицу распределения n-грамм. Если большая часть n-грамм встречается в тексте менее 10 раз, получаемое значение энтропии будет далеко от реального.

Объём алфавита K текста на русском языке в расчётах полагается равным 32, на английском, немецком и французском 27 (пробел и строчные буквы без акцентов).

Имена файлов для исследований задаются преподавателем!

3.3 Снятие гистограмм распределения Зарисуйте (сохраните в файл) гистограммы однобуквенного распределения для различных языков:

1. Откройте исходный текстовый файл на русском языке.

2. Нажмите кнопку Гистограмма.

3. Зарисуйте (сохраните) полученную гистограмму.

4. Запишите (скопируйте) значения числа встречаемости для всех символов алфавита.

Проделайте всё то же самое для текстов на английском, немецком и французском языках.

Проанализируйте полученные распределения. Сделайте выводы.

Рассчитайте вероятность (частость) символа пробел P ( ) как отношение числа пробелов к общему числу символов в тексте и найдите среднюю длину слова nсл для всех четырёх языков.

3.4 Исследование энтропии различных языков Снимите зависимость энтропии от длины n-граммы:

1. Откройте исходный текстовый файл на русском языке.

2. Установите параметр n равным 1.

3. Нажмите кнопку Рассчитать энтропию.

4. Занесите в табл. 1 значения длины n-граммы, рассчитанные значения энтропии n-граммы H(An ) и удельной энтропии H(An )/n.

5. Повторите п. 3–4 для значений n = 2... 5.

6. Рассчитайте условную энтропию H(A|An1 ) для n = 2... 5 как разность текущего H(An ) и предыдущего H(An1 ) значений энтропии n-граммы.

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

Отобразите полученные зависимости H(An )/n и H(A|An1 ) графически в одной системе координат. Сделайте выводы.

Примите за энтропию языка соответствующие значения удельной энтропии H(A3 ), полученные для n = 3 (при n > 3 полученные значения энтропии будут менее достоверными из-за малой длины исходных текстов). Сравните энтропии различных языков. Сделайте выводы.

Рассчитайте избыточность для каждого языка. Сделайте выводы.

3.5 Генератор случайных текстов Пронаблюдайте за работой генератора случайных текстов:

1. Откройте исходный текстовый файл на русском языке.

2. Установите параметр n (длина n-граммы) равным 1.

3. Нажмите кнопку Случайный текст. Программа сгенерирует некоторое количество символов случайного текста.

4. Увеличивая значение n до 5 с шагом 1 пронаблюдайте за изменением генерируемого текста.

5. Запишите (скопируйте) несколько слов случайного текста при различных значениях n.

6. Сделайте выводы.

3.6 Опыт Шеннона Определите энтропию русского языка методом Шеннона.

1. Откройте исходный текстовый файл на русском языке.

2. Установите параметр n (длина n-граммы) равным 6.

3. Нажмите кнопку Опыт Шеннона.

4. Попытайтесь угадать последнюю букву случайной n-граммы. Не сводите угадывание к простому перебору всех символов алфавита, используйте свои знания структуры русского языка. В трудных случаях (например, в начале слова) используйте хотя бы известное вам из п. 3.3 распределение вероятностей одиночных символов.

5. Повторите эксперимент как можно большее число раз (20–30).

6. Нажмите кнопку Энтропия.

7. Зарисуйте (сохраните) полученную гистограмму распределения и запишите соответствующее ей значение энтропии языка.

4 Содержание отчёта 1. Название и цель работы.

2. Выполненное домашнее задание.

3. Графики, таблицы, расчётные значения и выводы по всем пунктам 4. Общий вывод по результатам лабораторной работы.

Примечание: общий вывод не должен быть перефразировкой целей работы, а должен содержать обобщение (но не копию!) всех выводов, сделанных по каждому пункту в отдельности.

5 Контрольные вопросы 1. Какие источники называют дискретными? Что называется алфавитом источника?

2. Что такое информация ? Как определяется количество информации?

3. Дайте определение энтропии дискретного источника. Как рассчитывается энтропия источника без памяти?

4. Какие источники называются источниками с памятью? Как рассчитывается энтропия источника с памятью?

5. В каком случае энтропия будет максимальной? Как определить максимальное значение энтропии?

6. Дайте определение избыточности источника. Какие источники называют безызбыточными?

7. Какую величину называют производительностью источника? В каком случае производительность будет максимальной?

8. Как экспериментально можно определить энтропию языка?

9. Опишите суть опыта Шеннона для определения энтропии языка.

10. Как определить среднюю длину слова для текста на заданном языке?

Литература 1. Кловский Д. Д. Теория электрической связи. М.: Радиотехника, 2009. 648 с.

2. Теория электрической связи: учебник для вузов / А. Г. Зюко, Д. Д. Кловский, В. И. Коржик, М. В. Назаров; Под ред. Д. Д. Кловского. М.: Радио и связь, 1998. 432 с.

3. Шеннон К. Работы по теории информации и кибернетике. М,:

Издательство иностранной литературы, 1963.

4. Яглом И. М., Яглом А. М. Вероятность и информация. М.: Наука, Борисенков Алексей Владимирович Задание и методические указания к лабораторной работе по дисциплинам Общая теория связи, Теория информации и информационных систем, для студентов 2 курса направлений 210700, Информационные характеристики дискретных источников