Алфавитный подход к измерению инфopмации

1. Формула Хартли определения количества информации. Применение формулы Хартли .

2. Закон аддитивности информации.

3. Алфавитный подход к измерению информации .

Измерение количества информации можно объяснить на примере известной игры в угадывание. Согласно правилам этой игры, один из участников должен отгадать предмет (или одно из возможных состояний некоторого предмета), который задумал кто-то другой. При этом допускается только два вида ответа: "да" или "нет" . В данном случае ответ на один вопрос несет один бит информации , так как из двух возможных исходов выбирается один.

В начало

Предположим, что в классе находятся 32 ученика и учитель решил спросить одного из них. Спрашивается: какое минимально возможное количество вопросов нам надо задать учителю, чтобы наверняка определить, кого именно он решил спросить?

В начало

1 способ: Если в классе 4 ряда парт и они заполнены равномерно, то сначала зададим учителю вопрос: "Сидит ли задуманный ученик на парте в первом или втором ряду?" Получив ответ "да" или "нет", мы сократим количество "подозреваемых" до 16.

Вторым вопросом можно определить конкретный ряд, на котором сидит искомый школьник, сократив выбор до 8 человек.

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

В начало

Записав полученные ответы и заменив все ответы "да" единицами, а "нет — нулями, мы получим сообщение в виде последовательности из пяти двоичных цифр .

В начало

Отгадывать школьника можно было и по-другому. Присвоим каждому школьнику номер от 0 до 31 . Запишем номера в двоичной системе счисления. Самые длинные из таких номеров состоят не более чем из пяти двоичных цифр. Дополним остальные номера до пяти цифр слева нулями.

Далее вопросы учителю можно задавать так: "Верно ли, что первая слева цифра в номере задуманного ученика равна единице?", "Верно ли, что вторая цифра в номере задуманного ученика равна единице?" и т.д. Предположим, что ответы на вопросы были: "нет", "да", "нет", "нет", "да". Тогда мы сразу определим, что номер загаданного ученика — 01001 2 = 9 .

В начало

Далее вопросы учителю можно задавать так: "Верно ли, что первая слева цифра в номере задуманного ученика равна единице?", "Верно ли, что вторая цифра в номере задуманного ученика равна единице?" и т.д. Предположим, что ответы на вопросы были: "нет", "да", "нет", "нет", "да". Тогда мы сразу определим, что номер загаданного ученика — 01001 2 = 9 .

Назад

В начало

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

В противном случае может произойти «недостача» информации.

В начало

Дело в том, что при неразумном выборе вопросов может получиться так, что какие-либо два вопроса, ответ на каждый из которых несет один бит информации, в сумме содержат меньше двух бит информации. Это возможно, если ответ на первый вопрос полностью или частично содержит ответ на второй. Например, если сначала спросить, не равна ли первая цифра в номере ученика нулю, а потом — не равна ли она единице, то второй ответ не добавляет ровно никакой информации, и общее количество информации в двух ответах равно одному биту, а не двум.

В начало

• Вернемся к задаче 1 в случае, когда надо выбирать задуманного ученика уже среди 24 человек . В этом случае нам понадобится не меньше 4 и не больше 5 вопросов , если действовать методом деления пополам. После третьего вопроса у нас останется три "подозреваемых". Их можно разделить на группу из одного и группу из двух учеников. Тогда после четвертого вопроса мы либо сразу найдем нужного школьника, либо придется задавать пятый вопрос.
•  

В начало

• Попробуем действовать вторым способом. Закодируем номера 24 школьников двоичными номерами от 00000 2 до 10111 2 . Означает ли это, что закодированный номер содержит 5 бит информации? Нет, не совсем так. Длина кодовой последовательности здесь та же, что и раньше, но число различных номеров меньше. Поэтому, например, если мы узнаем, что старшая цифра номера равна 1, то вопрос о второй слева цифре задавать не придется (объясните почему), и мы сумеем определить номер искомого ученика, задав 4 вопроса, а не 5.
• Значит, количество информации, требуемой, чтобы выбрать задуманного ученика из 24 человек, больше 4 бит и меньше 5.

В начало

• Пусть N = 2 . Тогда, действуя методом деления множества предметов пополам, мы можем определить задуманный предмет с помощью к вопросов. При этом количество получаемой информации Н составляет к бит. То есть в данном случае I = к = log 2 N . Дальше будет понятно, что эта формула, носящая название формулы Хартли , справедлива для любого натурального N .
•  

В начало

• Формула Хартли: Количество информации, которое вмещает один символ N -элементного алфавита, равно log 2 N .
•  
• По-другому это же утверждение можно сформулировать так:
• Количество информации, полученной при выборе одного предмета из N равнозначных предметов, равно log 2 N . To есть именно такое количество информации необходимо для устранения неопределенности из N равнозначных вариантов.

Примеры решения задач

В начало

Задача:

• В библиотеке 16 стеллажей, в каждом стеллаже 8 полок. Какое количество информации несет сообщение о том, что нужная книга находится на четвертой полке?
•  
• В данном случае сообщение снимает неопределен­ность лишь относительно номера полки, на которой находится нужная книга. Количество информации, получаемое при этом, равно log 2 8 = 3 бита.
•  

Решение:

Назад

В начало

• Пусть нам теперь необходимо отгадать сразу два независимых предмета х 1 , и х 2 , про которые известно, что х 1 принадлежит множеству X 1 , содержащему N 1 элементов, а х 2 принадлежит множеству Х 2 , содержащему N 2 элементов.
• Вполне допустимо считать, что мы должны угадать пару ( x 1 , x 2 ) во множестве X всех возможных пар ( х 1 , х 2 ) , где х 1 ε X 1 , a x 2 ε Х 2 .
• Тогда по формуле Хартли для угадывания задуманной пары необходимо задать log 2 N 1 N 2 вопросов, то есть получить log 2 N 1 N 2 бит информации.

В начало

• С другой стороны, элементы х 1 и х 2 можно угадывать независимо. Для угадывания х 1 нам понадобится log 2 N 1 вопросов, а для угадывания х 2 — log 2 N 2 .
• Всего при этом понадобится log 2 N 1 + log 2 N 2 вопросов (бит информации).
• Мы получили два выражения для одного и того же количества информации. Согласно основному тождеству логарифма обе величины равны:
• log 2 N 1 N 2 = log 2 N 1 + log 2 N 2

В начало

• Переформулировав данное тождество в терминах количества информации, мы получаем закон аддитивности информации: количество информации H(х 1 , х 2 ), необходимое для установления пары (x 1 , x 2 ), равно сумме количеств информации H(х 1 ) и H(х 2 ), необходимых для независимого установления элементов х 1 и х 2 :
• H(x 1 x 2 )= H(x 1 ) + Н(х 2 ).

В начало

• Используя закон аддитивности информации и формулу Хартли, подсчитаем, какое количество информации несет достоверный прогноз погоды.
• Предположим, что прогноз погоды на следующий день заключается в предсказании дневной температуры (обычно выбор делается из 16 возможных для данного сезона значений) и одного из четырех значений облачности (солнечно, переменная облачность, пасмурно, дождь).
• Получаемое при этом количество информации
• равно log 2 16 + log 2 4 = 4 + 2 = 6 бит.  
• Закон аддитивности информации справедлив и
• при формальном (алфавитном) подходе к измерению информации.
•  

В начало

Назад:

• Алфавитный подход позволяет определить количество информации, заключенной в тексте.
•  
• Алфавит — множество символов, используемых при записи текста.
• Мощность (размер) алфавита — полное количество символов в алфавите.
• Будем использовать следующие обозначения:
• N — мощность алфавита,
• К — количество символов в тексте,
• i — количество информации, которое несет каждый символ алфавита,
• I — объем информации, содержащейся в тексте.
•  

В начало

• Если допустить, что все символы алфавита встречаются в тексте с одинаковой частотой ( равновероятно ), то количество информации, которое несет каждый сим­вол или содержащееся в одном символе (его информационный вес ), согласно формуле Хартли, вычисляется по формуле:
•  
• i = log 2 N , или 2 i = N

В начало

• Если весь текст состоит из К символов , то при алфавитном подходе размер со­держащейся в нем информации равен:
• I = К . i = K • log 2 N
•  

В начало

• Для представления текста в компьютере используется алфавит из 256 символов. Значит, один символ компьютерного текста несет в себе 8 бит (1 байт) информации , так как 2 8 = 256.
•  
•  
•  
• Информационный объем сообщения (информационная емкость сообщения) — количество информации в сообщении, измеренное в битах, байтах или производных единицах (килобайтах, мегабайтах и так далее).

В начало