Модель расследования
Изложение материала требует предварительного ознакомления читателя с некоторыми понятиями теории информации, в связи с чем нами воспроизводится параграф 18.8 (с. 502-514). из учебника Е. С. Вентцеля «Теория вероятностей» (М.: Высш. шк., 1999), посвященный задаче кодирования сообщений методом Шеннона-Фэно.
Задачи кодирования сообщений.
Код Шеннона – Фэно
«При передаче сообщений по линиям связи всегда приходится пользоваться тем или иным кодом, т. е. представлением сообщения в виде ряда сигналов. Общеизвестным примером кода может служить принятая в телеграфии для передачи словесных сообщений азбука Морзе. С помощью этой азбуки любое сообщение представляется в виде комбинации элементарных сигналов: точка, тире, пауза (пробел между буквами), длинная пауза (пробел между словами).
Вообще кодированием называется отображение состояния одной физической системы с помощью состояния некоторой другой. Например, при телефонном разговоре звуковые сигналы кодируются в виде электромагнитных колебаний, а затем снова декодируются, превращаясь в звуковые сигналы на другом конце линии. Наиболее простым случаем кодирования является случай, когда обе системы Х и Y (отображаемая и отображающая) имеют конечное число возможных состояний. Так обстоит дело при передаче записанных буквами сообщений, например, при телеграфировании. Мы ограничимся рассмотрением этого простейшего случая кодирования.
Пусть имеется некоторая система Х (например, буква русского алфавита), которая может случайным образом принять одно из состояний х1, х2, … хn. Мы хотим отобразить ее (закодировать) с помощью другой системы Y, возможные состояния которой y1, y2, … ym. Если m<n (число состояний системы Y меньше числа состояний системы X), то нельзя каждое состояние системы X закодировать с помощью одного-единственного состояния системы Y. В таких случаях одно состояние системы X приходится отображать с помощью определенной комбинации (последовательности) состояний системы Y. Так, в азбуке Морзе буквы отображаются различными комбинациями элементарных символов (точка, тире). Выбор таких комбинаций и установление соответствия между передаваемым сообщением и этими комбинациями и называется «кодированием» в узком смысле слова.
|
|
Коды различаются по числу элементарных символов (сигналов), из которых формируются комбинации, иными словами – по числу возможных состояний системы Y. В азбуке Морзе таких элементарных символов четыре (точка, тире, короткая пауза, длинная пауза). Передача сигналов может осуществляться в различной форме: световые вспышки, посылки электрического тока различной длительности, звуковые сигналы и т.п. Код с двумя элементарными символами (0 и 1) называется двоичным. Двоичные коды широко применяются на практике, особенно при вводе информации в электронные цифровые вычислительные машины, работающие по двоичной системе счисления.
Одно и то же сообщение можно закодировать различными способами. Возникает вопрос об оптимальных (наивыгоднейших) способах кодирования. Естественно считать наивыгоднейшим такой код, при котором на передачу сообщений затрачивается минимальное время. Если на передачу каждого элементарного символа (например, 0 или 1) тратится одно и то же время, то оптимальным будет такой код, при котором на передачу сообщения заданной длины будет затрачено минимальное количество элементарных символов.
|
|
Предположим, что перед нами поставлена задача: закодировать двоичным кодом буквы русской азбуки так, чтобы каждой букве соответствовала определенная комбинация элементарных символов 0 и 1 и чтобы среднее число этих символов на букву текста было минимальным.
Рассмотрим 32 буквы русской азбуки: а, б, в, г, д, е, ж, з, и, й, к, л, м, н, о, п, р, с, т, у, ф, х, ц, ч, ш, щ, ъ, ы, ь, э, ю, я – плюс промежуток между словами, который мы будем обозначать «–». Если, как принято в телеграфии, не различать букв ъ и ь (это не приводит к разночтениям), то получится 32 буквы: а, б, в, г, д, е, ж, з, и, й, к, л, м, н, о, п, р, с, т, у, ф, х, ц, ч, ш, щ, (ъ, ь), ы, э, ю, я, «–».
Первое, что приходит в голову, – это, не меняя порядка букв, занумеровать их подряд, приписав им номера от 0 до 31, и затем перевести нумерацию в двоичную систему счисления. Двоичная система– это такая, в которой единицы разных разрядов представляют собой разные степени двух. Например, десятичное число 12 изобразится в виде
12 = 1 • 23+1•22 + 0 • 21 + 0 • 20
и в двоичной системе запишется как 1100.
Десятичное число 25 –
25 = 1 • 24 + 1 • 23+0•22 + 0 • 21 + 1 • 20
– запишется в двоичной системе как 11001.
Каждое из чисел 0, 1, 2 … 31 может быть изображено пятизначным двоичным числом. Тогда получим следующий код:
а – 00000
б – 00001
в – 00010
г – 00011
я – 11110
«–» – 11111
В этом коде на изображение каждой буквы тратится ровно 5 элементарных символов. Возникает вопрос, является ли этот простейший код оптимальным и нельзя ли составить другой код, в котором на одну букву будет в среднем приходиться меньше элементарных символов?
|
|
Действительно, в нашем коде на изображение каждой буквы – часто встречающихся «а», «е», «о» или редко встречающихся «щ», «э», «ф» – тратится одно и то же число элементарных символов. Очевидно, разумнее было бы, чтобы часто встречающиеся буквы были закодированы меньшим числом символов, а реже встречающиеся – большим.
Чтобы составить такой код, очевидно, нужно знать частоты букв в русском тексте. Эти частоты приведены в таблице 21. Буквы в таблице расположены в порядке убывания частот.
Таблица 21
| Буква | Частота | Буква | Частота | Буква | Частота | Буква | Частота |
| «–» | 0,145 | р | 0,041 | я | 0,019 | х | 0,009 |
| о | 0,095 | в | 0,039 | ы | 0,016 | ж | 0,008 |
| е | 0,074 | л | 0,036 | з | 0,015 | ю | 0,007 |
| а | 0,064 | к | 0,029 | ъ, ь | 0,015 | ш | 0,006 |
| и | 0,064 | м | 0,026 | б | 0,015 | ц | 0,004 |
| т | 0,056 | д | 0,026 | г | 0,014 | щ | 0,003 |
| н | 0,056 | п | 0,024 | ч | 0,013 | э | 0,003 |
| с | 0,047 | у | 0,021 | й | 0,010 | ф | 0,002 |
Таблица 22
Двоичные знаки
| Буквы | 1й | 2й | 3й | 4й | 5й | 6й | 7й | 8й | 9й |
| – о е а и т | |||||||||
| н с р в л к м д п у я ы з ъ, ь б г ч й х ж ю ш ц щ э ф | |||||||||
Пользуясь такой таблицей, можно составить наиболее экономичный код на основе соображений, связанных с количеством информации. Очевидно, код будет самым экономичным, когда каждый элементарный символ будет передавать максимальную информацию. Рассмотрим элементарный символ (т. е. изображающий его сигнал) как физическую систему с двумя возможными состояниями: 0 и 1.
Информация, которую дает этот символ, равна энтропии системы и максимальна в случае, когда оба состояния равновероятны; в этом случае элементарный символ передает информацию 1 (дв. ед.). Поэтому основой оптимального кодирования будет требование, чтобы элементарные символы в закодированном тексте встречались в среднем одинаково часто.
Изложим здесь способ построения кода, удовлетворяющего поставленному условию; этот способ известен под названием «код Шеннона-Фэно». Идея его состоит в том, что кодируемые символ (буквы или комбинации букв) разделяются на две приблизительно равновероятные группы: для первой группы символов на первом месте комбинации ставится 0 (первый знак двоичного числа, изображающего символ); для второй группы – 1. Далее каждая группа снова делится на две приблизительно равновероятные подгруппы; для символов первой подгруппы на втором месте ставится нуль; для второй единица.
Продемонстрируем принцип построения кода Шеннона-Фэно на материале русского алфавита (табл. 21). Отсчитаем первые шесть букв (от «–» до «т»); суммируя их вероятности (частоты), получим 0,498; на все остальные буквы (от «н» до «ф») придется приблизительно такая же вероятность; 0,502. Первые шесть букв (от «–» до «т») будут иметь на первом месте двоичный знак 0. Остальные буквы (от «н» до «ф») будут иметь на первом месте единицу. Далее снова разделим первую группу на две приблизительно равновероятные подгруппы: от «–» до «о» и от «е» до «т»; для всех букв первой подгруппы на втором месте поставим нуль, а второй подгруппы – единицу. Процесс будем продолжать до тех пор, пока в каждом подразделении не останется ровно одна буква, которая и будет закодирована определенным двоичным числом. Механизм построения кода показан на таблице 22, а сам код приведен в таблице 23.
Таблица 23
| Буква | Двоичное число | Буква | Двоичное число | Буква | Двоичное число |
| «-» | к | ч | |||
| о | м | й | |||
| е | д | х | |||
| а | п | ж | |||
| и | у | ю | |||
| т | я | ш | |||
| н | ы | ц | |||
| с | з | щ | |||
| р | ъ, ь | э | |||
| в | б | ф | |||
| л | г |
С помощью таблицы 23 можно закодировать и декодировать любое сообщение.
В виде примера запишем двоичным кодом фразу «теория информации»:
1100001011111110101100110.
Заметим, что здесь нет необходимости отделять друг от друга буквы специальным знаком, так как и без этого декодирование выполняется однозначно. В этом можно убедиться, декодируя с помощью таблицы 22 следующую фразу:
(«способ кодирования»).
Однако необходимо отметить, что любая ошибка при кодировании (случайное перепутывание знаков 0 и 1) при таком коде губительна, так как декодирование всего следующего за ошибкой текста становится невозможным. Поэтому данный принцип кодирования может быть рекомендован только в случае, когда ошибки при кодировании и передаче сообщения практически исключены.
Возникает естественный вопрос: а является ли составленный нами код при отсутствии ошибок действительно оптимальным? Для того чтобы ответить на этот вопрос, найдем среднюю информацию, приходящуюся на один элементарный символ (0 или 1), и сравним ее с максимально возможной информацией, которая равна одной двоичной единице. Для этого найдем сначала среднюю информацию, содержащуюся в одной букве передаваемого текста, т.е. энтропию на одну букву:
Н(б)= – ∑ pilog pi =∑ η(pi) ,
где pi – вероятность того, что буква примет определенное состояние («–», о, е, а, … ф).
Из табл. 18.8.1 имеем
Н(б)= η(0, 145) – η (0,095) + … η(0,003) + η (0,002) ≈ 4,42
(дв. единиц на букву текста).
По таблице 22 определяем среднее число элементарных символов на букву:
nср = 3 • 0, 145 + 3 • 0,095 +4 •0,0744 + …
… + 9 • 0,003 + 9 • 0,002 =4,45.
Деля энтропию Н (б) на nср, получаем информацию на один элементарный символ
I 1c= 4,42/4,45= 0,994 (дв. ед).
Таким образом, информация на один символ весьма близка к своему верхнему пределу 1, а выбранный нами код весьма близок к оптимальному. Оставаясь в пределах задачи кодирования по буквам, мы ничего лучшего получить не сможем.
Заметим, что в случае кодирования просто двоичных номеров букв мы имели бы изображение каждой буквы пятью двоичными знаками и информация на один символ была бы
I 1c= 4,42/5,00= 0,884 (дв. ед),
т.е. заметно меньше, чем при оптимальном буквенном кодировании.
Однако надо заметить, что кодирование «по буквам» вообще не является экономичным. Дело в том, что между соседними буквами любого осмысленного текста всегда имеется зависимость. Например, после гласной буквы в русском языке не может стоять «ъ» или «ь»; после шипящих не могут стоять «я» или «ю»; после нескольких согласных подряд увеличивается вероятность гласной и т.д.
Мы знаем, что при объединении зависимых систем суммарная энтропия меньше суммы энтропии отдельных систем; следовательно, информация, передаваемая отрезком связного текста, всегда меньше, чем информация на один символ, умноженная на число символов. С учетом этого обстоятельства более экономный код можно построить, если кодировать не каждую букву в отдельности, а целые «блоки» из букв. Например, в русском тексте имеет смысл кодировать целиком некоторые часто встречающиеся комбинации букв, как «тся», «ает», «ние» и т.п. Кодируемые блоки располагаются в порядке убывания частот, как буквы в табл. 21, а двоичное кодирование осуществляется по тому же принципу.
В ряде случаев оказывается разумным кодировать даже не блоки из букв, а целые осмысленные куски текста. Например, для разгрузки телеграфа в предпраздничные дни целесообразно кодировать условными номерами целые стандартные тексты, вроде:
«поздравляю новым годом желаю здоровья успехов работе».
Не останавливаясь специально на методах кодирования блоками, ограничимся тем, что сформулируем относящуюся сюда теорему Шеннона.
Пусть имеется источник информации X и приемник Y, связанные каналом связи К (рис. 18.8.1).
Известна производительность источника информации Н1(X), т.е. среднее количество двоичных единиц информации, поступающее от источника в единицу времени (численно оно равно средней энтропии сообщения, производимого источником в единицу времени). Пусть, кроме того, известна пропускная способность канала C1, т.е. максимальное количество информации (например, двоичных знаков 0 или 1), которое способен передать канал в ту же единицу времени. Возникает вопрос: какова должна быть пропускная способность канала, чтобы он «справлялся» со своей задачей, т.е. чтобы информация от источника X к приемнику Y поступала без задержки?
Ответ на этот вопрос дает первая теорема Шеннона. Сформулируем ее здесь без доказательства. 1-я теорема Шеннона
Если пропускная способность канала связи С1 больше энтропии источника информации в единицу времени
С1 > H1(X),
то всегда можно закодировать достаточно длинное сообщение так, чтобы оно передавалось каналом связи без задержки. Если же, напротив,
С1 < H1(X),
то передача информации без задержек невозможна».