Теоретические основы информатики - Аветисян Р.Д.
Скачать (прямая ссылка):
Pd) = PU) = - ('-J = 1,2.....я). (2.4)
и
При соблюдении условия (2.4) /Z1 монотонно возрастает с увеличе-
42 ниєм п. И наконец, для функции #, справедливо
#, = -I MO log2 P(I)-Xk Iog2 \к-Xk ? ^lOg2 (2.5)
1=1 /=It +1 ^k
где
п
к<п, Xk= X р(і).
і^к+і
Это говорит о том, что исходную неопределенность можно представить как аддитивную сумму двух неопределенностей, а именно:
неопределенность угадывания того, является ли наугад взятая буква первой, второй,..., к-й или произвольной другой буквой из оставшихся п - к букв алфавита;
при условии, что угадываемая буква является одной из к + 1, к + + 2,..., п, букв алфавита, неопределенность, связанная с угадыванием того, какой же она окажется конкретно.
В приложениях важное место занимают случаи, когда алфавит рассматриваемого языка содержит две буквы. Примем, что ими являются двоичные символы "О" и "1". Для этого случая формула (2.3) примет вид
#, =-P(O)Iog2 P(O)-P(I)Iog2P(I). (2.6)
или, так как р(0) + р(1) = 1,
#, = — р Iog2 р — (1 — р) Iog2 (1 — р), (2.7)
где через р обозначено какое-либо одно из значений р(0) или р(1). что, как легко заметить из формул (2.6) и (2.7), все равно. Функция (2.7) графически представлена на рис. 2.3. Наибольшее возможное значение #1 = 1, которое достигается при р = 0,5. и принято за единицу измерения количества информации. Эту единицу по предложению Тьюки назвали бит (английское bit (binary "двоичный" + digit "знак, цифра")). Это название представляется не очень удачным, поскольку является источником весьма распространенного заблуждения, заключающегося в убеждении, что информационная нагрузка одного двоичного символа всегда равна одному биту.
Один бит - это количество неопределенности, которое имеет место при необходимости угадывания того, какое из двух равновероятных (и независимых от результатов предыдущих экспериментов) событий будет иметь место при очередном испытании. Иными словами, это количество информации, содержащееся в сообщении о том, какое именно из двух равновероятных событий имело место. Если же эти сбытия не являются рав-
Рис. 2.3. Примерный характер функции К. Шеннона Н(р) в области 0<р< I
43
ГЛАВА 1 невероятными, то информационная нагрузка одного двоичного символа становится меньше одного бита и может уменьшаться до нуля.
В реальных текстах вероятности появления тех или иных букв алфавита в значительной степени зависят от того, какие именно буквы им предшествовали. Например, значение вероятности того, что очередная буква в произвольном русском тексте окажется мягким знаком, близка к нулю, если ей предшествовал набор букв "рассмагрив?"; и близка к единице, если предшествовал набор букв "рассматриват?". Интуитивно ясно, что знание предшествующих букв в общем случае облегчает угадывание очередной буквы. Ясно также, что чем больше число известных предшествующих букв, тем, при прочих равных условиях, в большей степени облегчается угадывание очередной буквы. Такая зависимость присутствует в любом связном тексте (будь это обычные тексты, цифровые представления изображений, музыки, фильмов или связный текст произвольного иного характера) и обусловлена синтаксисом рассматриваемого языка и (что важнее, хотя и менее очевидно) смысловой нагрузкой (семантикой) текста.
Чтобы осуществить количественную оценку указанного обстоятельства, наряду с (2.3) К. Шеннон рассматривал следующую формулу:
р(Вш)\0ёгр(В„„), (2.8)
т s
где p(Bms) - вероятность того, что наугад взятая из текста последовательность букв длины т окажется последовательностью Bms. Суммирование в (2.8) ведется по всем пт возможным последовательностям длины т. В качестве энтропии угадывания очередной буквы связного текста К. Шеннон предлагает пользоваться значением
H = Iim Hnr (2.9)
Естественно, что Hm - монотонно убывающая функция от т. Лишь в том частном случае, когда вероятности появления в тексте тех или иных букв не зависят от того, какие именно буквы им предшествовали, значение Hm не зависит от т и равно Hm = W1 (см. формулу (2.3)).
К. Шенноном была доказана теорема о том, что путем кодирования достаточно длинных последовательностей букв можно добиться того, чтобы среднее число двоичных символов (/), приходящееся на одну букву, было бы сколь угодно близким к значению H. Он же доказал, что величина H является нижним пределом значения /. Это и естественно, если энтропия угадывания одной буквы исходного текста равна H битам, то для того, чтобы ликвидировать это количество неопределенности, необходимо заполучить как минимум H бит информации. С другой стороны, известно (ем. рис. 2.3), что каждый двоичный символ может содержать не более одного бита информации и поэтому необходимо "взглянуть" как минимум (в лучшем случае) на I = H двоичных
44 символов, чтобы заиолучить достаточное (т.е. равное Н) количество информации. Несмотря на теоретическую достижимость условия / = Н, на практике оно может оказаться труднореализуемым. Ведь, как это следует из рис. 2.3 и из формулы (2.7), для доведения информационной нагрузки одного двоичного символа до одного бита необходимо, чтобы соблюдались следующие два условия:
