/> Лабораторная работа№1Количественная мера информации
ЦЕЛЬ РАБОТЫ:экспериментальное изучение количественных аспектов информации.ЛАБОРАТОРНОЕЗАДАНИЕ
1. Определитьколичество информации (по Хартли), содержащееся в заданном сообщении, приусловии,что значениями являются буквы кириллицы.
«ФамилияИмя Отчество» завершил ежегодный съезд эрудированныхшкольников, мечтающих глубоко проникнуть в тайны физических явлений ихимических реакций
2. Построить таблицураспределения частот символов, характерные для заданногосообщения. Производится так называемая частотная селекция,текст сообщения анализируется как поток символов и высчитывается частотавстречаемости каждого символа. Сравнить с имеющимися данными в табл 1.
3. На основании полученных данных определитьсреднее и полное количество информации, содержащееся в заданном сообщении
/>/>4. Оценитьизбыточность сообщения.
КРАТКИЕ ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ
Количество информациипо Хартли и Шеннону
Понятиеколичество информации отождествляется с понятием информация. Эти два понятияявляются синонимами. Мера информации должна монотонно возрастать с увеличениемдлительности сообщения (сигнала), которую естественно измерять числом символовв дискретном сообщении и временем передачи в непрерывном случае. Кроме того, насодержание количества информации должны влиять и статистические характеристики,так как сигнал должен рассматриваться как случайный процесс.
При этом наложено рядограничений:
1. Рассматриваютсятолько дискретные сообщения.
2. Множество различныхсообщений конечно.
3. Символы,составляющие сообщения равновероятны и независимы.
Хартли впервыепредложил в качестве меры количества информации принять логарифм числа возможныхпоследовательностей символов.
I=logmk=log N (1)
К.Шеннон попыталсяснять те ограничения, которые наложил Хартли. На самом деле в рассмотренномвыше случае равной вероятности и независимости символов при любом kвсе возможные сообщения оказываются также равновероятными, вероятность каждогоиз таких сообщений равна P=1/N.Тогда количество информации можно выразить через вероятности появлениясообщений I=-logP.
В силу статистическойнезависимости символов, вероятность сообщения длиной в kсимволов равна
/>
Если i-йсимвол повторяется в данном сообщении kiраз,то
/>
так как при повторении iсимвола kiраз k уменьшается до m.Из теории вероятностей известно, что, при достаточно длинных сообщениях(большое число символов k)ki≈k·piитогда вероятность сообщений будет равняться
/>
Тогда окончательнополучим
/> (2)
Данное выражениеназывается формулой Шеннона для определения количества информации.
Формула Шеннона дляколичества информации на отдельный символ сообщения совпадает с энтропией.Тогда количество информации сообщения состоящего из kсимволов будет равняться I=k·H
Количество информации,как мера снятой неопределенности
При передаче сообщений,о какой либо системе происходит уменьшение неопределенности. Если о системе всеизвестно, то нет смысла посылать сообщение. Количество информации измеряютуменьшением энтропии.
Количествоинформации, приобретаемое при полном выяснении состояния некоторой физическойсистемы, равно энтропии этой системы:
/>
Количествоинформации I-есть осредненное значение логарифма вероятности состояния. Тогда каждоеотдельное слагаемое -logpiнеобходиморассматривать как частную информацию, получаемую от отдельного сообщения, тоесть
/>Избыточностьинформации
Если бы сообщенияпередавались с помощью равновероятных букв алфавита и между собой статистическинезависимых, то энтропия таких сообщений была бы максимальной. На самом делереальные сообщения строятся из не равновероятных букв алфавита с наличиемстатистических связей между буквами. Поэтому энтропия реальных сообщений -Hр,оказывается много меньше оптимальных сообщений — Hо. Допустим,нужно передать сообщение, содержащее количество информации, равное I.Источнику, обладающему энтропией на букву, равной Hр,придется затратить некоторое число nр,то есть
/>
Если энтропия источникабыла бы Н0,то пришлось бы затратить меньше букв на передачу этого же количества информации
I=n0H0/>
Таким образом, частьбукв nр-nоявляются как бы лишними, избыточными. Мера удлинения реальных сообщений посравнению с оптимально закодированными и представляет собой избыточность D.
/> (3)
Но наличие избыточностинельзя рассматривать как признак несовершенства источника сообщений. Наличиеизбыточности способствует повышению помехоустойчивости сообщений. Высокаяизбыточность естественных языков обеспечивает надежное общение между людьми.
Частотныехарактеристики текстовых сообщений
Важнымихарактеристиками текста являются повторяемость букв, пар букв (биграмм) ивообще m-ок (m-грамм), сочетаемость букв друг с другом, чередование гласных исогласных и некоторые другие. Замечательно, что эти характеристики являютсядостаточно устойчивыми.
Идея состоит в подсчетечисел вхождений каждой nm возможных m-грамм в достаточно длинныхоткрытых текстах T=t1t2…tl, составленных избукв алфавита {a1, a2, ..., an}. При этомпросматриваются подряд идущие m-граммы текста
t1t2...tm,t2t3… tm+1, ..., ti-m+1tl-m+2...tl.
Если />–число появлений m-граммы ai1ai2...aim в текстеT, а L общее число подсчитанных m-грамм, то опыт показывает, что при достаточнобольших L частоты
/>
для данной m-граммымало отличаются друг от друга.
В силу этого,относительную частоту считают приближением вероятности P (ai1ai2...aim)появления данной m-граммы в случайно выбранном месте текста (такой подходпринят при статистическом определении вероятности).
Для русского языкачастоты (в порядке убывания) знаков алфавита, в котором отождествлены E c Ё, Ьс Ъ, а также имеется знак пробела (-) между словами, приведены в таблице 1.
информация текстовый сообщение количественный
Таблица 1- 0.175 О 0.090 Е, Ё 0.072 А 0.062 И 0.062 Т 0.053 Н 0.053 С 0.045 Р 0.040 В 0.038 Л 0.035 К 0.028 М 0.026 Д 0.025 П 0.023 У 0.021 Я 0.018 Ы 0.016 З 0.016 Ь, Ъ 0.014 Б 0.014 Г 0.013 Ч 0.012 Й 0.010 Х 0.009 Ж 0.007 Ю 0.006 Ш 0.006 Ц 0.004 Щ 0.003 Э 0.003 Ф 0.002
Некоторая разницазначений частот в приводимых в различных источниках таблицах объясняется тем,что частоты существенно зависят не только от длины текста, но и от егохарактера.
Устойчивыми являютсятакже частотные характеристики биграмм, триграмм и четырехграмм осмысленныхтекстов.
ХОД РАБОТЫ
1. Построил таблицураспределения частот символов, характерныxдля заданного сообщения путём деленияколичества определённого символа в данном сообщении на общее число символов
Поформуле
/>
H= вычислилэнтропию сообщения
2. Далеепо формуле Шеннона для определения кол-ва информации
/>
вычислилкол-во информации в передаваемом сообщении
3. Вычислилизбыточность D по формуле
/>