Работа №1. Исследование избыточности источника информации

Теоретические сведения Коэффициент избыточности показывает, какая часть реального сообщения является излишней и могла бы не передаваться, если бы сообщение было организовано оптимально. Коэффициент избыточности выражается формулами:

где п_р и Н_р — длина и энтропия реального сообщения; п₀ и Н₀ — длина и энтропия оптимального сообщения.

Сообщение будет оптимальным тогда, когда все символы алфавита равновероятны. Энтропия такого сообщения максимальна и равна log₂m, где т — мощность алфавита. Энтропия реального сообщения при условии независимости символов сообщения вычисляется по формуле:

где р, — вероятность появления i-ro символа.

Энтропия сообщения при условии попарной зависимости символов вычисляется по формуле:

где Ру — вероятность появления пары символов.

Справочно: для русского языка значение реальной энтропии равно 4,36 бит на символ, для английского языка — 4,04, для французского — 3,96, для немецкого — 4,10, для испанского — 3,98. С учетом попарной зависимости символов энтропия русского языка — 3,52, английского языка — 3,32 бит на символ.

Задание к работе

Задание А

А.1. Получить (найти в Интернете) текстовые файлы, содержащие текст на одном из естественных языков или языке эсперанто, в соответствии со своим вариантом. Длина текста — не менее 10 тыс. символов.

А.2. Рассчитать оптимальную энтропию для заданного языка.

А.З. Составить программу для экспериментального определения реальной энтропии сообщения при условии независимости символов. Выполнить расчет для полученного файла.

А.4. Рассчитать избыточность сообщения заданного естественного языка при условии независимости символов алфавита.

А.5. Используя текстовый файл из п. А.1, сформировать усеченный алфавит языка, т. е. оставить в текстовом файле только символы из трети исходного алфавита. Пробелы и знаки препинания не учитывать, прописные и строчные символы не различать. Мощность усеченного алфавита должна быть не более 15.

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

А.6. Построить таблицу частот символов первичного усеченного алфавита А. 7. Закодировать символы усеченного алфавита равномерным бинарным кодом.

Задание Б Б.1. Составить программу для экспериментального определения реальной энтропии сообщения при условии попарной зависимости символов. Выполнить расчет для полученного файла.

Б.2. Рассчитать избыточность сообщения заданного естественного языка с учетом попарной зависимости символов алфавита.

Б.З. Вместе с товарищами сравнить избыточность различных языков.

Б.4. Выполнить пункт Б.1 для усеченного алфавита.

Варианты заданий.

Контрольные вопросы.

• 1. Что называется энтропией?
• 2. Каковы причины появления избыточности в сообщении?
• 3. Как можно уменьшить избыточность?
• 4. Как экспериментально определить вероятность появления символа в сообщении?
• 5. Каковы положительные и отрицательные стороны наличия избыточности сообщения?
• 6. Сравните величины энтропии, полученные в п.п. А.4 и Б.2 задания. Теоретически обоснуйте полученный результат.
• 7. Сравните полученные значения энтропии естественного языка со справочными. Поясните причину отличия.