Учебно-лабораторный практикум л абораторная работа 1: Исследование информативности источников дискретных сообщений.
Задание – сравнить текстовые сообщения, написанные на двух языках (выбираются в зависимости от варианта) по количеству информации, приходящейся на одну букву, используя меру Шеннона без учета статистической связи между буквами и с учетом этой связи между двумя соседними буквами.
Цель работы – приобретение навыков измерения количества информации, заключенной в дискретных сообщениях, с использованием меры Шеннона.
Теоретическое введение
К. Шеннон предложил измерять количество информации I в сообщении по формуле:
I = Н априорная – Н апостериорная ,
где
Н априорная – неопределенность знания истинного состояния объекта до получения сообщения, в котором это состояние описывается;
Н апостериорная– неопределенность знания истинного состояния объекта после получения сообщения, в котором это состояние описывается.
Численно неопределенность состояния объекта, называемая также энтропией, рассчитывается по формуле Н = -log2P , где Р – вероятность нахождения объекта в этом состоянии.
Если считать объектом полученный текст (что в реальности мало интересно, однако кардинально упрощает задачу), то неопределенность после его получения полностью снимается, т.е. апостериорная энтропия после получения текста = 0.
Следовательно, в этом случае количество информации (мера Шеннона) в полученном тексте I = Н априорная
Если в качестве дискретных сообщения принять, как это определено в задании, тексты, написанные на разных языках, то степень информативности таких сообщений целесообразно измерять и сравнивать, измеряя среднее количество информации, приходящейся на одинаковый по длине отрезок текста, например на 1 букву текста.
Средняя энтропия, как известно из теории информации, рассчитывается по формуле:
, (1)
где Рk – вероятность реализации k-го события в полной группе независимых событий, в которую всего входят m событий.
Эту формулу можно использовать для расчета средней энтропии, приходящейся на 1 букву текста, если считать их независимыми. Здесь m - объем (количество букв) используемого при написании текста алфавита. Конечно, предположение о независимости букв в тексте достаточной искусственно, поскольку интуитивно ясно, что на самом деле буквы в тексте взаимозависимы (мы ведь, как правило, можем восстановить утерянную или искаженную или утерянную букву в тексте, что свидетельствует об их взаимозависимости).
Более точно рассчитать среднюю неопределенность одной буквы сообщения можно, учитывая связи (зависимость) между двумя соседними буквами. Формула средней энтропии двухбуквенной комбинации в этом случае принимает следующий вид:
, (2)
где P(i,j) – вероятность появления в тексте комбинации из i-ой и j-ой букв алфавита.
Заметим, что количество слагаемых в формуле (2) возросло в квадрате (m2) по сравнению с количеством слагаемых в формуле (1) (m).
Конечно, и в этом случае расчет дает неточный, приблизительный результат, поскольку связи между буквы распространяются далее, чем на одну соседнюю букву. Однако дальнейшее увеличение точности, основанное на учете более дальних связей между буквами, резко увеличивает сложность расчетов из-за резкого (по экспоненциальному закону) роста количество слагаемых.
Поэтому в данной работе ограничимся только двумя вариантами – без учета связей между буквами и учетом связей только между соседними буквами. Для сравнения полученных результатов среднюю энтропию двухбуквенной комбинации для приведения к неопределенности, приходящейся на 1 букву, следует поделить на 2.
Оба расчета опираются на знание вероятностей: в первом случае – отдельных букв алфавита, во втором случае – всевозможных сочетаний из двух букв алфавита.
Согласно положениям теории вероятностей, эти вероятности можно найти только приближенно – путем подсчета частот появления букв и двухбуквенных комбинаций в реальных текстах и деления найденных частот на общее число букв и двухбуквенных комбинаций в исходном тексте. Результаты таких вычислений согласно закону больших чисел будут тем точнее, чем большие по объему тексты были взяты в качестве исходных.
Учитывая все описанное выше, остается лишь найти подходящие тексты и соответствующим образом их обработать.
Наиболее удобным источником разноязычных текстов в настоящее время является Интернет. Обработку текстов можно вести разными средствами. Это может быть какой-либо язык программирования или табличный процессор.
При подсчете частот появления отдельных букв текста или двухбуквенных комбинаций надо иметь в виду способы их кодирования. Во всех современных вариантах ОС Windows для кодирования символов используется кодовая таблица Unicode. В отличие от ранее доминировавшей кодовой таблицы ASCII , символы в которой кодировались 1-байтовым числом, сейчас символы в ОС Windows кодируются 2-байтовыми числами. Такая 2-байтовая кодировка позволяет различать 216=65536 символов в отличие от 28=256, различаемых в таблице ASCII. Таким образом, появилась возможность обрабатывать тексты, написанные на большинстве языков народов мира. Со временем проявились недостатки кодовой таблицы Unicode (Уникод). Предпринимаются усилия, направленные на их устранение. Это отражается в разработке новых усовершенствованных версий кодовой таблицы Unicode.
Сайт консорциума по разработке кодовой таблицы Unicode находится по адресу www.unicode.org. Согласно информации, опубликованной на этом сайте к осени 2008 года уже разработано 5 версий этой кодовой таблицы. На сайте в виде PDF-документов представлены участки кодовой таблицы, закрепленные за различными алфавитами с подробным описанием входящих в них символов.
Описание стандарта Unicode на русском языке можно найти по адресу http://allo.usaaa.ru/wdh/unicode.htm. С критикой Unicode можно ознакомиться по адресу http://cie.ase.md/~sereda/kod.htm#top
Ряд алфавитов отображаются также и при помощи модификаций однобайтовой кодовой таблицы ASCII. Различные программные средства, в том числе языки Visual Basic, тестовый процессор Excel могут работать с текстами так, как будто они закодированы при помощи этой однобайтовой кодовой таблицы. Надо думать, что этот искусственный прием предусмотрен как временная мера на период полного перехода от ASCII к Unicode. Поэтому с точки зрения перспективы рекомендуется обработку текстов выполнять средствами, работающими с кодовой таблицей Unicode.
Приводим примерный план выполнения данной лабораторной работы для случая применения для обработки текстов табличного процессора Excel. Это не значит, что выполнять работу нужно только так, как описано в этом плане. Наоборот, приветствуются и поощряются другие оригинальные способы исследования информативности заданных вариантом языков основанные на использовании статистической меры К. Шеннона.
Возможный план выполнения работы с использованием табличного процессора Excel
Шаг 1. Поиск в Интернете текстов с суммарным объемом от около 10 тысяч символов на каждом из двух языках согласно варианту задания.
Вообще, источник текстов может быть любым – газеты, книги, радио, телевидение и т.д. В настоящее время удобнее всего использовать Интернет, т.к. в этой сети можно найти тексты на практически любом языке и ввиду удобства его представления в электронной форме, готовой для компьютерной обработки.
Объем текста должен быть достаточным для расчета с достаточной точностью вероятностей появления в нем букв или других символов, составляющих письмо (например, иероглифов). Почему вероятностей? Потому, что именно на основе вероятностей на основе меры Шеннона находится количество информации в сообщении (см. формула 1 и 2). Из теории вероятностей (раздел математики) следует, что приближенно вероятность (оценку вероятности) какого-либо события можно вычислить, проведя множество экспериментов. Затем подсчитывается и количество случаев возникновения нужного события. Это количество делится на число проведенных экспериментов. В результате получается оценка вероятности возникновения нужного события. Эта оценка будет тем точнее, чем больше экспериментов будет проведено. Если пользоваться терминами нашей задачи, событиями являются факты появления нужной буквы в тексте, а экспериментами – появления букв текста. Число экспериментов – количество букв в тексте. Поэтому для увеличения точности расчета вероятностей появления отдельных букв (формула 1) и комбинаций из двух букв (формула 2) следует максимально увеличить длину текста. Однако возможности компьютеров небезграничны. Поэтому опытным путем была установлена верхняя граница количества букв – около 10000 букв.
Найденные в сети Интернет тексты через буфер промежуточного хранения передаются в текстовый процессор Word. По мере передачи текстов просматривается информация об объеме накопленного текста. Для этого выбирается меню Сервис ->Статистика (рис. 1).
Рис.1. Окно Статистика
После накопления нужного объема (около 10 тыс. символов без пробелов) для удобства дальнейшей обработки абзацы на экране целесообразно сузить приблизительно на 0,5 ширины страницы. Для этого можно, например, значительно увеличить правое поле страницы (рис. 2).
Рис. 2. Изменение размера правого поля.
Затем информация сохраняется в файле типа Обычный текст (*.txt). В процессе сохранения на экран выводится диалоговое окно Преобразование файла (рис. 3).
Рис. 3. Окно Преобразование файла
В этом окне нужно выбрать опции Другая, Уникод, Вставлять разрывы строк. Надо проверить также, что весь текст (прокрутить его сверху вниз) в нижней части окна не содержит символов, помеченных красным цветом. В противном случае следует подобрать другую кодировку. Окончательно текст сохраняется после нажатий кнопки ОК.