Print
Category: Теоретическая информатика
Hits: 7230

С помощью алфавитного подхода легко определить, что для кодирования символов русского алфавита потребуется пять бит (будем для простоты считать, что в алфавите 32 буквы). Количество информации в слове из N символов будем 5·N бит. А как подсчитать количество информации в слове, используя вероятностный подход? Подобную задачу я находил в задачниках по информатике для школы, жаль, правильного решения в них нет. Предложу свое решение.

Итак, известно, что буквы русского алфавита встречаются в тексте с разной вероятностью, так буква «е» встречается чаще, чем буква «ы». Это значит, что количество информации, содержащееся в слове содержащем «распространенные буквы», должно быть меньше чем слово из «редких букв». Отсюда рождается интересный ученический проект: найти часто встречи каждой буквы в русском языке, построить таблицу (написать программу) для вычисления количества информации содержащемся в слове из N букв.

1. подсчет частоты встречи букв в русском языке

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

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


замена символов текста в редакторе Notepad++

После того как получится таблица с количеством каждой буквы можно сделать несложные расчеты. Частота встречи буквы (вероятность) рассчитывается по формуле pi = Ni / Nобщ

pi – частота встречи (вероятность) конкретной буквы
Ni – количество букв в тексте
Nобщ – суммарное количество букв в тексте.

2. подсчитываем вероятность встретить конкретное слово

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

Будем считать, что из бесконечного мешка букв русского языка где буквы распределены с вычисленной нами частотой последовательно достаются N букв. Тогда вероятность получить трехбуквенное слово АБВ равна:

pАБВ = pА·pБ·pВ / 3!

3! = 1·2·3 (делить на «три факториал» необходимо так как мы подсчитываем вероятность слова АБВ, а не ВБА и т.п. иными словами последовательность букв имеет значение).

Так вероятность слова «мир», равна 0,0000164522 это 1/60782. Иными словами вытаскивая произвольные буквы именно такая вероятность последовательно вытащить «м», «и», «р».

 Из вероятности слова, используя формулу Шеннона легко получить информационный объем слова:

IАБВ = - log2(pАБВ)

Выводы

Слово «мир» содержит 15,89 бит информации. Количество близко к расчетному значению, полученному с помощью алфавитного подхода (3·5=15).

Слово состоящее из самых распространенных букв «еаи» 13, 81 бит (меньше усредненных 15 бит).

Редкое слово «йыэ» будет содержать 22,97 бит, значительно больше (15 бит).

Используя разные тексты для анализа, мы получим одинаковые частоты встреч букв, так как эти характеристики являются свойствами русского языка.

В работе получен еще одни промежуточный результат, информационный объем одной «какой-то буквы» русского алфавита равен 4,4879 бит (ячейка D34) во вложенном файле. Значение получено сложением соответствующих членов формулы Шеннона.

Attachments:
Download this file (Количество информации.xls)Количество информации.xls[Вычисление информации в слове с помощью вероятностного подхода]30 kB