Материал предоставлен https://it.rfei.ru

Информация и алфавит

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

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

В устной речи это достигается использованием различных фонем (основных звуков разного звучания), по которым и отличаются знаки речи. В письменности это достигается различным начертанием букв и дальнейшим нашим анализом написанного. Как данная задача может решаться техническим устройством, рассмотрим позднее. Сейчас для важно, что можно реализовать некоторую процедуру (механизм), посредством которой выделить из сообщения тот или иной знак. Но появление конкретного знака (буквы) в конкретном месте сообщения - событие случайное. Следовательно, узнавание (отождествление) знака требует получения некоторой порции информации. Можно связать эту информацию с самим знаком и считать, что знак несет в себе (содержит) некоторое количество информации. Попробуем оценить это количество.

Начнем с самого грубого приближения (будем называть его нулевым, что отражается индексом у получаемых величин) - предположим, что появление всех знаков (букв) алфавита в сообщении равновероятно. Тогда для английского алфавита %%n_e = 27%% (с учетом пробела как самостоятельного знака); для русского алфавита %%n_r = 34%%. Из формулы Хартли (2.15) находим:

%%I_0^e=log_227=4.755\; бит%%

%%I_0^r=log_234=5.087\; бит%%

Получается, что в нулевом приближении со знаком русского алфавита в среднем связано больше информации, чем со знаком английского. Например, в русской букве «а» информации больше, чем в «а» английской! Это, безусловно, не означает, что английский язык - язык Шекспира и Диккенса - беднее, чем язык Пушкина и Достоевского. Лингвистическое богатство языка определяется количеством слов и их сочетаний, и никак не связано с числом букв в алфавите. С точки зрения техники это означает, что сообщения из равного количества символов будет иметь разную длину (и соответственно, время передачи) и большими они окажутся у сообщений на русском языке.

В качестве следующего (первого) приближения, уточняющего исходное, попробуем учесть то обстоятельство, что относительная частота, т.е. вероятность появления различных букв в тексте (или сообщении) различна. Рассмотрим таблицу средних частот букв для русского алфавита, в который включен также знак «пробел» для разделения слов с учетом неразличимости букв «е» и «ё», а также «ь» и «ъ» (так принято в телеграфном кодировании), получим алфавит из 32 знаков со следующими вероятностями их появления в русских текстах:

Таблица 2.1

Букваo e,ё а и т нс
Относительная частота 0.1750.0900.0720.0620.0620.0530.053
Буквар в л к м д п
Относительная частота0.0400.0380.0350.0280.0260.0250.023
Буквая ы з ь,ъ б г ч
Относительная частота0.0180.0160.0160.0140.0140.0130.012
Буквач ж ю ш ц щ э
Относительная частота0.0090.0070.0060.0060.0040.0030.003

Для оценки информации, связанной с выбором одного знака алфавита с учетом неравной вероятности их появления в сообщении (текстах) можно воспользоваться формулой (2.14). Из нее, в частности, следует, что если %%р_i%% - вероятность (относительная частота) знака номер %%i%% данного алфавита из %%N%% знаков, то среднее количество информации, приходящейся на один знак, равно:

$$I= -\sum^{n}_{i=1}{p_i\cdot log_2 p_i}~~~(2.17)$$

Это и есть знаменитая формула К.Шеннона, с работы которого «Математическая теория связи» (1948) принято начинать отсчет возраста информатики, как самостоятельной науки. Объективности ради следует заметить, что и в нашей стране практически одновременно с Шенноном велись подобные исследования, например, в том же 1948 г. вышла работа А. Н. Колмогорова «Математическая теория передачи информации».

В общем случае информация, которая содержится в сообщении, может зависеть от того, в какой момент времени оно достигает приемника. Например, несвоевременное сообщение о погоде, очевидно, не несет той же информации, что и своевременное. Предельным случаем оказывается ситуация, когда вся переносимая сообщением информация определяется временем его поступления; например, бой часов или звонок с урока. Однако возможно существование сообщений, в которых содержащаяся в них информация не зависит от времени поступления. В частности, такая ситуация реализуется в том случае, если вероятность встретить в сообщении какой-либо знак %%i%% не зависит от времени, точнее, она одинакова во все моменты времени и равна относительной частоте этого знака %%р_i%% во всей последовательности знаков. Поэтому вероятности знаков (относительные частоты) определяются для сообщений (текстов), содержащих большое число символов с тем, чтобы проявились статистические закономерности, и далее считаются неизменными во всех сообщениях данного источника.

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

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

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

Применение формулы (2.17) к алфавиту русского языка дает значение средней информации на знак %%I_1^{(r)} = 4,36 бит%%, а для английского языка %%I_1^{(e)} = = 4,04 бит%%, для французского %%I_1^{(f)} = = 3,96 бит%%, для немецкого %%I_1^{(d)} = - 4,10 бит%%, для испанского %%I_1^{(s)} = = 3,98 бит%%. Как видим, и для русского, и для английского языков учет вероятностей появления букв в сообщениях приводит к уменьшению среднего информационного содержания буквы, что, кстати, подтверждает справедливость формулы (2.7).

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

Следующими приближениями при оценке значения информации, приходящейся на знак алфавита, должен быть учет корреляций, т.е. связей между буквами в словах. Дело в том, что в словах буквы появляются не в любых сочетаниях; это понижает неопределенность угадывания следующей буквы после нескольких, например, в русском языке нет слов, в которых встречается сочетание ”щц” или ”фъ”. И напротив, после некоторых сочетаний можно с большей определенностью, чем чистый случай, судить о появлении следующей буквы, например, после распространенного сочетания ”пр-” всегда следует гласная буква, а их в русском языке 10 и, следовательно, вероятность угадывания следующей буквы %%\frac{1}{10}%%, а не %%\frac{1}{33}%%. Учет в английских словах двухбуквенных сочетаний понижает среднюю информацию на знак до значения %%I_2(e) = 3,32 бит%%, учет трехбуквенных - до %%I_3(e) = 3,10 бит%%.

Шеннон сумел приблизительно оценить

$$I_5(e) ≈ 2,1 бит%% и %%I_8(e) = 1,9 \;бит$$

Аналогичные исследования для русского языка дают:

$$I_2(r) = 3,52 бит%%; %%I_3(r) = 3,01\; бит$$

Последовательность %%I_0, I_1, I_2...%% является убывающей в любом языке. Экстраполируя ее на учет бесконечного числа корреляций, можно оценить предельную информацию на знак в данном языке %%I_∞%%, которая будет отражать минимальную неопределенность, связанную с выбором знака алфавита без учета семантических особенностей языка, в то время как %%I_0%% является другим предельным случаем, поскольку характеризует наибольшую информацию, которая может содержаться в знаке данного алфавита. Шеннон ввел величину, которую назвал относительной избыточностью языка:

$$R=1-\frac{I_∞}{I_0}~~~(2.18)$$

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

Исследования Шеннона для английского языка дали значение %%I_∞ ≈ 1,4÷1,5%% бит, что по отношению к %%I_0 = 4,755\; бит%% создает избыточность около 0,68. Подобные оценки показывают, что и для других европейских языков, в том числе русского, избыточность составляет 60 - 70%. Это означает, что в принципе возможно почти трехкратное сокращение текстов без ущерба для их содержательной стороны и выразительности.

Например, телеграфные тексты делаются короче за счет отбрасывания союзов и предлогов без ущерба для смысла; в них же используются однозначно интерпретируемые сокращения «ЗПТ» и «ТЧК» вместо полных слов (эти сокращения приходится использовать, поскольку знаки «.» и «,» не входят в телеграфный алфавит). Однако такое «экономичное» представление слов снижает разборчивость языка, уменьшает возможность понимания речи при наличии шума (а это одна из проблем передачи информации по реальным линиям связи), а также исключает возможность локализации и исправления ошибки (написания или передачи) при ее возникновении. Именно избыточность языка позволяет легко восстановить текст, даже если он содержит большое число ошибок или неполон (например, при отгадывании кроссвордов или при игре в «Поле чудес»). В этом смысле избыточность есть определенная страховка и гарантия разборчивости.

Энтропия и информацияПроверка знаний: Понятие информации в теории Шеннона