Характеристики сообщений
До этого места, говоря об информации, мы ограничивались в ее определении призывами к здравому смыслу. Теперь же попробуем описать ее строже, так как использование слова информация приводит порой к недоразумениям и многозначности. Письмо, телеграмма, выступление по радио несут информацию и являются сообщениями. Однако надлежит отличать сообщения от извещений. Понять разницу между ними позволит следующий анекдот. Однажды Пьер попросил свою невесту Мари, чтобы она бросила вечером из окна монету, когда родители уйдут в кино и можно будет провести время наедине. Родители ушли, и Мари бросила монету. Через полчаса ожидания она, выглянув на улицу, увидела Пьера, обшаривающего тротуар. Таков сюжет, а теперь перейдем к размышлениям. Зачем Пьер занимался поиском? Скупость отвергнем сразу же - монета не купюра, да и драгоценное время уходит. Скорее всего, что бросок монеты Мари приняла за извещение: наступил момент времени, когда ушли родители. А Пьер, искушенный в информатике любовных посланий, отнесся к этому событию как к сообщению: если брошена монета, то родители ушли, а если обручальное кольцо, то ему предлагают утешиться аперитивом в ближайшем бистро. Извещения несут в себе информацию лишь о времени наступления известного заранее события. Ими являются сигнал точного времени, свисток футбольного судьи, выстрел стартового пистолета. А вот сообщения существуют вне времени, например, картина Рубенса, текст инъективы Цицерона против Саллюстия, опера Чайковского "Пиковая дама", лозунг Ленина "Вся власть Советам" или зажженная надпись STOP на переходе.
Сообщения, как бы сложны они не были, можно представить себе в виде последовательности знаков. Эти знаки берутся из заранее фиксированного набора, например, русского алфавита или палитры цветов (красный, желтый, зеленый). Разные знаки могут встречаются в сообщениях с разной частотой. Поэтому количество информации, передаваемой разными знаками может быть разным. В том смысле, который предложил Шеннон, количество информации определяется средним числом возможных вопросов с ответами ДА и НЕТ для того, чтобы угадать следующий символ сообщения. Если буквы в тексте следуют независимо друг от друга, то среднее количество информации в сообщении приходящееся на один знак, равно:
H= См. PiLd(Pi)
где Pi - частота появления символа i, a Ld- двоичный логарифм. Отметим три особенности такого определения информации.
1. Оно абсолютно не интересуется семантикой, смыслом сообщения, и им можно пользоваться, даже когда точный смысл неясен.
2. В нем предполагается независимость вероятности появления знаков от их предыстории.
3. Заранее известна знаковая система, в которой передается сообщение, то есть язык, способ кодирования.
В каких единицах выражается значение количества информации по Шеннону? Точнее всего ответ на этот вопрос дает теорема кодирования, утверждающая, что любое сообщение можно закодировать символами 0 и 1 так, что полученная длина сообщения будет сколь угодно близка сверху к Н. Эта теорема позволяет назвать и единицу информации - бит.
Каждый, кто использовал, работая на персональном компьютере, архиваторы, знает, как лихо они ужимают текстовые файлы, ничего при этом не теряя. Их работа лучшим образом демонстрирует теорему кодирования в действии. Так как для русского текста, переданного лишь прописными буквами, Н=4.43, то это означает, что в принципе в русском алфавите можно было бы обойтись лишь 22 буквами или на 45% сократить длину файлов в формате ASCII. Таким образом, сообщения языка занимают места больше, чем это необходимо. Это явление называют избыточностью языка. Благодаря ему искажения отдельных символов сообщения зачастую не разрушают содержания, что случилось бы при отсутствии избыточности. Заметьте, у компьютера наиболее часто встречаемые символы ETOANIRSHDLU (даны в порядке убывания частот в английском языке) вынесены в центр клавиатуры, чтобы при наборе текстов движение пальцев было бы минимальным. Это расположение клавиш было предложено изобретателем линотипа Оттомаром Мергенталером, который использовал избыточность языка для облегчения работы.
Утверждение, что вероятность появления символа в связном тексте не зависит от его предыстории, неверно и статистически, и лингвистически. Уже давно литераторы заметили, что обычно за согласной буквой следует гласная, а за гласной согласная. Поэтому в конце XIX века петербургский математик Марков предложил текст рассматривать как цепочку символов, где вероятность появления буквы зависит от предыдущей и только от нее. Таким образом, он стал рассматривать не вероятности Pj появления в сообщении знака i, а вероятности Pij появления знака j при условии, что перед ним стоит знак i. Теория марковских цепей оказалась чрезвычайно продуктивной для криптографии, и к отдельным ее применениям мы будем возвращаться позже. Пока же достаточно отметить, что первое свое опробование она имела при анализе текстов "Евгения Онегина" самим Андреем Андреевичем Марковым. Объем информации в одном символе марковской цепи определяется следующей формулой:
H= См. Pi(См. Pij*Ld(Pij))
В этом случае нет противоречия с требованием независимости знаков, так как знаком здесь считается не отдельный символ, а биграмма. В приложении приведена таблица вероятности встречи биграмм в русском техническом тексте по программированию. Вероятности их представлены десятью классами от 0 до 9 в порядке возрастания и образуют по средним значениям геометрическую прогрессию. Справа в этой таблице даны вероятности встречи отдельных символов. Так, из нее следует, что биграмма АЙ встречается довольно часто (класс 7), а биграмма ЙА почти совсем не попадается (класс 0). Среднее количество информации, приходящееся на один символ, определяемое по этой таблице равно 3.5 бит, что эквивалентно примерно II буквам в русском алфавите или возможности сжатия текстов примерно на 57% при их оптимальном кодировании.
Описанное свойство зависимости буквы в тексте от предыдущей называется марковостью первого порядка, а независимость букв друг от друга марковостью нулевого порядка. Естественно, что можно рассматривать также и марковости высших порядков, например второго, когда буква зависит от двух предыдущих. Для того, чтобы оценить порядок марковости в связном тексте, проведем случайное моделирование, используя сначала вероятности отдельных букв, потом биграмм, триграмм и так далее. Примеры марковского синтеза текстов разных порядков марковости от 0 до 4 приведены в следующей таблице:
0 ПАВЛНТ И ОАБУТ ЕИИЕТК ЖМЕ КСВИДАИВ
1 МОЙ ОГЛЬ ТАМАНУ ЧТЕТОГАНЕ СТА СЛИНА
2 КРУЖБЫ И ОТЧАЕТОНЕИСТАК ПЕХ ЭТОГО 3
3 В ДЕПАРЫ ЧТО НАСТЯМИ РАСПРОИСХОДИН
4 ПОНЯЛ О ГЛУБОКОЙ СИСТЕМ И ДЕЛЕ ВОДЫ
Из нее видно, что увеличение порядка марковости повышает схожесть отрывка случайного текста с естественным. Повышение порядка марковости позволяет доуточнить объем информации в сообщениях, но это очень скользкая тема есть масса разных точек зрения на нее. Действительно, вводя понятие шенноновской информации, мы похоронили понятие смысла, который связывает символы в слога, слога в слова, слова в предложения, а предложения в сообщение. Практически нет разницы, как сказать ребенку: "Нужно есть кашу!" или "Надо есть кашу!", а вот шенноновский подход эти сообщения считает различными. Поэтому оценка объема информации, содержащейся в сообщении и полученной по приведенным формулам, явно завышена. А ведь в жизни нередко бывает, что за целый день так и не узнаешь ничего нового!
Теперь рассмотрим одно приложение знаний свойств естественного текста сообщения для нужд криптографии. Требуется по отрезку текста решить, что он из себя представляет, осмысленное сообщение или последовательность случайных символов. Ряд шифров приходится на ЭВМ вскрывать перебором ключей, а вручную просмотреть свыше тысячи фрагментов вдень просто не под силу, да и скорость мала. Поэтому нужно эту задачу реализовать на ЭВМ. Пусть предстоит перебрать примерно миллиард ключей на машине со скоростью тысяча ключей в секунду, на что уйдет около 10 дней. В этом случае мы рискуем впасть в две крайности. Если будем чрезмерно осторожны в оценках, то часть несмысловых текстов будет воспринята как сообщения и передана человеку. Эта ошибка обычно называется "ложная тревога" или ошибка первого рода. При количестве таких ошибок свыше 1000 в день человек устанет и может начать проверять тексты невнимательно. Значит, допускается не более одной ошибки такого рода на сто тысяч проверок. Далее, если подойти к проверке поверхностно, то можно пропустить смысловой текст и по окончании полного перебора его опять придется повторить. Чтобы не рисковать необходимостью повторения всей работы, ошибки второго рода или "пропуски сообщения" допустимы лишь одном случае из ста или тысячи.
Самый простой критерий, который приходит в голову, связан с использованием алфавита сообщения. Если учитывать, что в нем могут встретиться лишь знаки препинания, цифры, заглавные и малые русские буквы, то в тексте сообщения встретится не больше половины набора кодовой таблицы ASCII. Следовательно, встретив в тексте недопустимый символ можно уверенно говорить о том, что он несмысловой - ошибки второго рода почти исключены при нормально работающем канале связи. Для того, чтобы снизить вероятность "ложных тревог" до принятой выше величины, требуется, чтобы текст состоял не менее чем из двадцати трех символов. Дело усложняется, если используемый код букв не избыточен, как представление в ASCII русского текста, а содержит ровно столько символов, сколько их в алфавите. Тогда приходится вести оценку по вероятностям встречи символов. Чтобы обеспечить принятые вероятности ошибок первого и второго рода при оценке максимального правдоподобия, необходимо анализировать уже около сотни символов, а анализ вероятностей биграмм лишь несколько снижает эту величину. Таким образом, короткие сообщения при большой длине ключа вообще невозможно расшифровать однозначно, так как появляющиеся случайные тексты могут совпадать с осмысленными фразами. Аналогичную задачу приходится решать и при контроле качества шифрования. В этом случае, правда, вероятность ложной тревоги можно повысить, приняв ее не свыше одной тысячной, при той же самой вероятности пропуска сообщения. А это позволит ограничиться для проверки лишь 20-30 символами.
