Частотные характеристики текстовых сообщений

Важными характеристиками текста являются повторяемость букв, пар букв (биграмм) и вообще m-ок (m-грамм), сочетаемость букв друг с другом, чередование гласных и согласных и некоторые другие. Замечательно, что эти характеристики являются достаточно устойчивыми.

Идея состоит в подсчете чисел вхождений каждой n^m возможных m-грамм в достаточно длинных открытых текстах T=t₁t₂…t_l, составленных из букв алфавита {a₁, a₂, ..., a_n}. При этом просматриваются подряд идущие m-граммы текста

t₁t₂...t_m, t₂t₃... t_m+1, ..., t_i-m+1t_l-m+2...t_l.

Если – число появлений m-граммы a_i1a_i2...a_im в тексте T, а L общее число подсчитанных m-грамм, то опыт показывает, что при достаточно больших L частоты

для данной m-граммы мало отличаются друг от друга.

В силу этого, относительную частоту считают приближением вероятности P (a_i1a_i2...a_im) появления данной m-граммы в случайно выбранном месте текста (такой подход принят при статистическом определении вероятности).

Для русского языка частоты (в порядке убывания) знаков алфавита, в котором отождествлены E c Ё, Ь с Ъ, а также имеется знак пробела (-) между словами, приведены в таблице 1.

Таблица 1

Некоторая разница значений частот в приводимых в различных источниках таблицах объясняется тем, что частоты существенно зависят не только от длины текста, но и от его характера.

Устойчивыми являются также частотные характеристики биграмм, триграмм и четырехграмм осмысленных текстов.

Задания к лабораторной работе:

1. Определить количество информации (по Хартли), содержащееся в заданном сообщении, при условии, что значениями являются буквы кириллицы.

«Фамилия Имя Отчество» завершил ежегодный съезд эрудированных школьников, мечтающих глубоко проникнуть в тайны физических явлений и химических реакций»

2. Построить таблицу распределения частот символов, характерные для заданного сообщения. Производится так называемая частотная селекция, текст сообщения анализируется как поток символов и высчитывается частота встречаемости каждого символа. Сравнить с имеющимися данными в табл 1.

3. На основании полученных данных определить среднее и полное количество информации, содержащееся в заданном сообщении

4. Оценить избыточность сообщения.

Методические рекомендации:

1. Построить таблицу распределения частот символов, характерныx для заданного сообщения путём деления количества определённого символа в данном сообщении на общее число символов

По формуле

H= вычислить энтропию сообщения

2. Далее по формуле Шеннона для определения кол-ва информации

вычислить кол-во информации в передаваемом сообщении

3. Вычислить избыточность D по формуле

ВАЖНО ЗНАТЬ!!!

 Закрепление изучаемого материала.

Пример: Задача №1

В корзине лежат 32 клубка красной и черной шерсти. Среди них 4 клубка красной шерсти.

Сколько информации несет сообщение, что достали клубок красной шерсти? Сколько информации несет сообщение, что достали клубок шерсти любой окраски?

Дано: К_к=4;N=32

Найти: I_к, I

Решение:

1. Найдем количество клубков черной шерсти: К_ч=N- К_к; К_ч=32-4=28
2. Найдем вероятность доставания клубка каждого вида: p_к= К_к/N=4/32=1/8; p_ч= К_ч/N=28/32=7/8;
3. Найдем количество информации, которое несет сообщение, что достали клубок красной шерсти: I_к= log₂(1/(1/ p_к))= log₂(1/1/8)= log₂8=3 бит
4. Найдем количество информации, которое несет сообщение, что достали клубок шерсти любой окраски:

Ответ: I_к=3 бит; I=0,547 бит

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

• Объясните на конкретных примерах отличие равновероятного события от неравновероятного?
• С помощью какой формулы вычисляется вероятность события.
• Объясните качественную связь между вероятностью события и количеством информации в сообщении об этом событии.
• В каких случаях применяется формула Шеннона для измерения количества информации.
• В каком случае количество информации о событии достигает максимального значения.

Пример Задача №2

В озере обитает 12500 окуней, 25000 пескарей, а карасей и щук по 6250. Какое количество информации несет сообщение о ловле рыбы каждого вида. Сколько информации мы получим, когда поймаем какую-нибудь рыбу?

Дано: К_о=12500; К_п=25000; К_к= К_щ=6250

Найти: I_о, I_п, I_к,I_щ, I

Решение:

1. Найдем общее количество рыбы: N= К_о+К_п+К_к+К_щ.
2. Найдем вероятность ловли каждого вида рыбы: p_о= К_о/N;p_п= К_п/N;p_к=p_щ= К_к/N.
3. Найдем количество информации о ловле рыбы каждого вида: I_о=log₂( 1/p_о);I_п=log₂(1/p_п);I_к=I_щ=log₂(1/p_к)
4. Найдем количество информации о ловле рыбы любого вида: I=p_о∙log₂p_о+p_п∙log₂p_п+p_к∙log₂p_к+p_щ∙log₂p_щ