«ВВЕДЕНИЕ В ТЕОРИЮ ИНФОРМАЦИИ Учебное пособие 2013 УДК ББК Потапов В. Н. Введение в теорию информации / ISBN Учебное пособие представляет собой систематическое изложение основ теории информации, которая является ...»

В. Н. Потапов

ВВЕДЕНИЕ В ТЕОРИЮ ИНФОРМАЦИИ

Учебное пособие

2013

УДК

ББК

Потапов В. Н. Введение в теорию информации /

ISBN

Учебное пособие представляет собой систематическое изложение основ теории

информации, которая является математическим фундаментом для развития методов

передачи и обработки текстов и сигналов.

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

Рецезенты Учебное пособие подготовлено в рамках реализации Программы развития НИУ-НГУ c Потапов В. Н., Содержание Введение Глава 1. Три подхода к понятию сложности сообщений 1.1. Алгоритмический подход 1.2. Комбинаторный подход 1.3. Вероятностный подход Глава 2. Определение и свойства энтропии разбиения Глава 3. Цепи Маркова 3.1. Эргодическая теорема для марковской цепи 3.2. Закон больших чисел для марковской цепи Глава 4. Модели источников сообщений 4.1. Конечные автоматы 4.2. Параметры модели источника сообщений 4.3. Контекстная модель 4.4. Метод трансфер-матрицы 4.5. Скрытые марковские модели Глава 5. Энтропия источника сообщений 5.1. Стационарные источники. Энтропия стационарного источника 5.2. Энтропия марковского источника 5.3. Энтропия источника Бернулли Глава 6. Кодирование 6.1. Префиксные и разделимые множества слов 6.2. Кодирование натуральных чисел 6.3. Теорема кодирования Шеннона 6.4. Побуквенное кодирование 6.5. Равноблочное на выходе кодирование 6.6. Нумерационное кодирование 6.7. Арифметическое кодирование 6.8. Адаптивное и универсальное кодирования 6.9. Интервальное кодирование 6.10. Преобразование Барроуза Уилера Глава 7. Сложность слова относительно программы 7.1. Схема Лемпела Зива 7.2. Схема конкатенации Глава 8. Недоопределённые данные 8.1. Энтропия недоопределённых данных 8.2. Энтропия разбиения, при заданной точности воспроизведения 8.3. Кодирование недоопределённых данных Глава 9. Передача сообщений по каналам связи, допускающим ошибки 9.1. Канал связи и его пропускная способность 9.2. Теорема кодирования для канала связи, допускающего ошибки 9.3. Обращение теоремы о помехоустойчивом кодировании 9.4. Избыточность универсального кодирования как пропускная способность некоторого канала Предметный указатель Именной указатель Литература Введение Теория информации представляет собой математическую дисциплину, в которой методы различных разделов математики: теории вероятностей, теории алгоритмов, комбинаторики применяются для исследования возможностей поиска, предсказания, сжатия, передачи и защиты информации. Теория информации исследует феномен информации с количественной стороны. Отвечая на вопросы о том сколько информации имеется или лучше сказать может содержаться в данном сообщении, как сообщение лучше передать или насколько его можно сжать, теория информации не выдвигает суждений о важности заключённой в сообщении информации. В настоящее время теория информации является динамично развивающейся областью математики, что обусловлено как математической красотой результатов, так и множеством приложений в информатике, физике и генетике. Понятие информации, в частности квантовой и генетической, стало в последние десятилетия одним из важнейших при изучении как неживой так и живой природы.

Работой, заложившей основу математической теории информации, является статья К. Шеннона Математическая теория связи, опубликованная в 1948 году. В этой статье впервые было введено понятие энтропии (количества информации) и были указаны основные задачи и направления развития теории. В настоящее время теория информации (в широком смысле) включает теорию распознавания статистических свойств источников сообщений, теорию кодирования источников сообщений (сжатия данных), теорию передачи сообщений по каналам связи, теорию помехоустойчивого кодирования, теорию поиска информации и криптографию. Теория информации рассматривает два типа сообщений дискретные (тексты) и непрерывные (сигналы). Методы обработки дискретной и непрерывной информации весьма существенно отличаются, точнее непрерывная информация как правило сначала специальными методами преобразуется в дискретную. В данном учебнике рассматриваются только методы обработки дискретных данных. В нём подробно рассмотрены модели источников сообщений, методы кодирования сообщений, модели каналов связи, допускающих ошибки. Значительное внимание уделено обоснованию соответствия между вводимыми математическими понятиями и их естественными прототипами.

Теория помехоустойчивого кодирования, проблемы поиска и защиты информации остались за рамками данного учебного пособия. Учебник был написан на основе лекций, которые автор в разные годы читал на факультете естественных наук, механикоматематическом и техническом факультетах НГУ. Автор благодарит Л. А. Шоломова за замечания, способствовавшие улучшению текста книги.

Глава 1.

Три подхода к понятию сложности сообщений Пусть A = {a1,..., ak } некоторый конечный алфавит. Упорядоченный набор, состоящий из букв алфавита, называется словом. Сложность слова естественно определить как количество информации, т. е. число двоичных символов, необходимое для однозначного задания слова. Существуют три основных подхода к понятию сложности слова: алгоритмический, комбинаторный и вероятностный, связанные с различными способами задания слов.

1.1. Алгоритмический подход Рассмотрим некоторую вычислимую функцию (программу) : {0, 1} A, где A = Ai. Общепринято считать вычислимыми те и только те функции, которые могут быть реализованы некоторой машиной Тьюринга (см., например, [7], [9], [25], [32]). Некоторые программы, реализованные на машине Тьюринга, могут иметь аргументы, на которых работа программы никогда не заканчивается, поэтому считается, что функция может быть определена не на всём множестве {0, 1}, а только на некотором его подмножестве, т. е. может быть частично вычислимой функцией.

Двоичное слово v {0, 1} будем называть кодом слова w A относительно программы, если (v) = w. Определим сложность слова w относительно программы Здесь и далее |v| быть получено применением программы, то K(w|) =. Естественно рассмотреть вопрос о возможности введения некоторого универсального понятия сложности, независимого от конкретной программы.

Т е о р е м а 1. (Колмогоров) Существует универсальная программа 0 такая, что для любой программы и слова w A выполнено неравенство K(w|0 ) K(w|) + C, где константа C зависит от программы, но не от слова w.

Д о к а з а т е л ь с т в о. Произвольная программа является набором команд, т. е. задаётся некоторым словом u. Рассмотрим программу 0, которая вначале по слову u записывает программу, а потом запускает программу на слове v.

Тогда кодом слова w относительно 0 будет пара слов: код программы и код слова w относительно программы. Преобразуем слово u в двоичное слово (u ) так, чтобы его можно было отделить от кода слова w относительно программы, методы разделимого кодирования слов будут описаны ниже (см. главу 6). По построению получаем K(w|0 ) |(u )| + K(w|).

Очевидно, если мы рассмотрим две универсальные программы 0 и 0, то сложности K(w|0 ) и K(w|0 ) отличаются на константу C0,0. Существование универсальной программы позволяет определить понятие сложности, асимптотически не зависящее от выбора конкретной универсальной программы. Если мы рассмотрим бесконечное слово и будем вычислять сложность K(wn |0 ), где wn начало слова w длины n, то величина K(wn |0 ) либо будет ограниченной, либо будет стремиться к бесконечности и тогда влияние константы, зависящей от выбора конкретной универсальной программы 0, станет ничтожным.

Сложность слова w относительно некоторой универсальной программы 0 называется колмогоровской сложностью. Предположим, что A = {0, 1} или что слова в алфавите A закодированы словами в алфавите {0, 1}. Длине слова как и любому натуральному числу можно поставить в соответствие его двоичную запись. Следовательно, функцию K(·|) можно рассматривать как функцию действующую из {0, 1} в {0, 1}. Тогда можно поставить вопрос о вычислимости, т. е. о реализации на машине Тьюринга функции K(·|).

У т в е р ж д е н и е 1. Если программа определена на всём множестве {0, 1}, то функция K(·|) является частично вычислимой.

Д о к а з а т е л ь с т в о. Определим линейный порядок на множестве {0, 1}, упорядочив двоичные слова вначале по возрастанию длины, а слова одинаковой длины лексикографически. Чтобы вычислить число K(w|), будем перебирать элементы v множества {0, 1} в этом порядке и вычислять (v). Когда слово w будет первый раз вычислено на некотором аргументе v, перебор следует остановить, так как K(w|) = |v|. Если слово w не вычисляется программой ни на каком аргументе, то перебор продлится бесконечно и, соответственно, K(w|) =.

Т е о р е м а 2. (Колмогоров) Колмогоровская сложность K(·|0 ) является невычислимой функцией.

Д о к а з а т е л ь с т в о. Предположим противное. Пусть найдётся такая программа 1, которая вычисляет колмогоровскую сложность двоичных слов, т. е. ставит в соответствие двоичному слову w двоичную запись числа K(w|0 ). Заметим, что программа 1 должна быть всюду определена, поскольку для любого слова w A найдётся вычисляющая его программа w и K(w|0 ) K(w|w ) + Cw <. Пусть на множестве {0, 1} задан линейный порядок, определённый в предыдущем утверждении. Построим программу 2, которая ставит в соответствие двоичной записи числа1 m N наименьшее из слов, удовлетворяющих неравенству K(w|0 ) m.

Программа 2 перебирает двоичные слова в порядке возрастания и посредством программы 1 вычисляет их сложность, пока не встретится первое слово удовлетворяющее неравенству K(w|0 ) m. Обозначим его wm. Из вычислимости (на любом аргументе) программы 1 следует, что и программа 2 вычислима на любом аргументе, так как множество слов сложности менее m конечно. Тогда2 K(wm |2 ) = log m + 1, поскольку кодом wm относительно программы 2 является двоичная запись числа Здесь и всюду далее буквой N обозначается множество натуральных чисел.

Здесь и всюду далее через log обозначается логарифм по основанию 2.

m. Из теоремы 1 получаем неравенство Переходя к пределу при m, получаем противоречие с известным равенством lim log m = 0.

Таким образом, вычисление колмогоровской сложности не может быть реализовано в виде программы. И сама универсальная программа, как следует из утверждения 1 и теоремы 2, не может быть определена на всех всех двоичных словах. Невозможность вычисления сложности относительно универсальной программы оправдывает изучение сложности слов относительно некоторых неуниверсальных программ, которые выбираются для нужд конкретных исследований. Подробнее об алгоритмической сложности и её связи с разными разделами математики можно прочесть в [25].

З а д а ч а 1. Пусть w слово в двоичном алфавите. Докажите, что K(w|0 ) |w| + c, где c некоторая константа.

З а д а ч а 2. Докажите, что существует менее 2n двоичных слов w, для которых K(w|0 ) < n.

З а д а ч а 3. Пусть задана некоторая программа P. Какова максимальная доля тех двоичных слов длины N, код которых относительно программы P имеет длину не больше, чем N n?

З а д а ч а 4. Докажите невычислимость функции (возможно частичной), ставящей в соответствие двоичной записи числа m наиболее длинное слово w такое, что K(w|0 ) = m.

З а д а ч а 5. Можно ли указать наименьшее натуральное число, которое нельзя однозначно задать меньше чем двенадцатью словами? (парадокс Берри) 1.2. Комбинаторный подход Пусть M A некоторое множество слов и w M. Для однозначного задания слова из множества M достаточно указать его номер во множестве M относительно некоторого, например, лексикографического порядка. Поскольку словам из M присваиваются номера3 от 0 до |M | 1, то для записи номера достаточно log |M | битов. Соответственно определим комбинаторную сложность слова w относительно множества M равенством Определим множество M (r) как множество слов с частотным составом r = (r1,..., rk ), т. е. если w M (r), то в слове w имеется ровно ri букв ai для любого i = 1,..., k.

Д о к а з а т е л ь с т в о. Обозначим n = r1 +· · ·+rk. Сначала рассмотрим случай k = 2. Докажем формулу Здесь и всюду далее если M множество, то через |M | обозначается его мощность.

методом индукции по n. Очевидно, что |M (n, 0)| = |M (0, n)| = 1.

Поскольку любое слово из M (r1, n + 1 r1 ) получается приписыванием буквы a2 к слову из M (r1, n r1 ) или буквы a1 к слову из M (r1 1, n (r1 1)), то из предположения индукции (1.1) имеем Таким образом формула (1.1) доказана.

При k > 2 будем доказывать утверждение методом индукции по k. Любое слово w M (r1,..., rk, rk+1 ) можно получить из слова u M (r1,..., rk + rk+1 ) заменив rk+1 букв ak в слове u на буквы ak+1. По доказанному выше это можно сделать |M (rk, rk+1 )| = (rrkk+rk+1 !)! способами. Тогда b(, n) 2nh( /n).

В дальнейшем нам понадобится следующее асимптотическое равенство У т в е р ж д е н и е 4. (формула Стирлинга) n! = nn en 2n(1 + o(1)) при n.

Д о к а з а т е л ь с т в о. Вначале докажем формулу Валлиса sinn x dx. Применяя формулу интегрирования по частям, получаем Пусть xn = Отсюда получаем рекуррентную формулу По индукции получаем формулы Из монотонности последовательности (xn ) и равенства (1.2) имеем Рассмотрим последовательность an = nn+1/2. Из формулы Тейлора для логарифма имеем ln(1 + n ) = n 2n2 + O( n3 ) при n. Тогда дел. Тогда последовательность (an ), где an = a1 a2... an1 = a1 esn, имеет конечный предел. Обозначим его через A. Из арифметических свойств предела, определения последовательности an и формулы Валлиса получаем Таким образом, имеем равенство A = 2. Формула Стирлинга эквивалентна равенству lim an = 2.

всех i = 1,..., k.

Д о к а з а т е л ь с т в о. Используя неравенство Бернулли (1 + x)n 1 + nx, справедливое для любого x 1 и n N, можно показать, что (1+ n )n (1+ n+1 )n+1.

Из последнего неравенства методом индукции по n нетрудно вывести неравенство Кроме того, из утверждения 2 и формулы Стирлинга имеем Из последнего неравенства и определения величины L(w|M ) получаем требуемое.

З а д а ч а 6. Выведите формулу для числа двоичных слов длины n с k единицами, никакие две из которых не встречаются в слове подряд.

З а д а ч а 7. Дана 81 монетка, из них ровно одна фальшивая, которая легче всех настоящих (настоящие монетки имеют одинаковый вес). Какое минимальное число взвешиваний нужно проделать на чашечных весах, чтобы найти фальшивую монетку?

1.3. Вероятностный подход Рассмотрим некоторый опыт со случайными исходами. Естественно предположить, что количество информации, возникающее в результате получения сведений о некотором случайном исходе, зависит от вероятности исхода. Во всяком случае, если мы многократно записываем результаты однотипных опытов, то, выбирая для наиболее вероятного исхода более короткое обозначение, можно получить более короткую запись результатов эксперимента. Например, если опыт имеет два равновероятных исхода, то для записи каждого из них достаточно одного бита. А если опыт имеет исходы a1, a2, a3 с вероятностями 1/2, 1/4, 1/4, то его итог можно записывать в виде пары результатов последовательного выполнения двух опытов: первого с равновероятными исходами a1 и a2 a3, и второго (в случае второго исхода в первом опыте) c равновероятными исходами a2 и a3.

Найдём функцию h(p1,..., pk ), которая определяет количество информации, содержащееся в результатах опыта, имеющего k случайных исходов с вероятностями (p1,..., pk ). Сначала предположим, что все исходы опыта равновероятны, тогда h(1/k, 1/k,..., 1/k) = (k). Естественно предположить, что опыт, имеющий большее число равновероятных исходов, имеет большую неопределенность, поэтому (k) возрастающая функция. Пусть опыт B состоит в последовательном выполнении двух независимых экспериментов A и A, имеющих по k равновероятных исходов.

Опыт B имеет k 2 равновероятных исходов, и для записи его результата нужно записать результаты опытов A и A. Следовательно должно быть справедливо равенство (k 2 ) = 2(k). Аналогичным образом заключаем, что (k i ) = i(k) для любых натуральных чисел i > 0. Покажем, что единственной с точностью до умножения на константу функцией, удовлетворяющей этим условиям, является log k, т. е.

(k) = C log k, где C > 0 постоянная величина.

Пусть n > 1 и a > 2 целые числа. Найдется такое натуральное m, что справедливы неравенства Тогда из монотонности функции имеем неравенство m(2) n(a) < (m + 1)(2).

Кроме того, имеем m n log a < m + 1. Из двух последних неравенств получаем, что Увеличивая n, число m можно сделать сколь угодно большим. Тогда из предыдущего неравенства следует, что (a) = (2) log a. Поскольку для записи результата опыта с двумя равновероятными исходами достаточно одного бита, неопределенность такого опыта естественно считать равной 1, т. е. (2) = 1.

Пусть опыт A имеет k исходов, вероятности которых равны некоторым рациональным числам pi. Тогда количество информации, необходимое для записи исхода pi. Рассмотрим опыт B, имеющий n равновероятных исходов. Сгруппируем исходы опыта B в k групп так, чтобы i-я группа имела вероятность mi. Тогда исход опыта B можно указать, определив сначала группу, в которую попал данный исход, а затем найдя место нужного исхода в этой группе. Проделаем n раз опыт B. Поскольку исходы опытов, содержащихся в каждой группе, равновероятны и опыт по определению места нужного исхода в i-й группе необходимо проводить в среднем в mi из n случаях, то функция h должна удовлетворять неравенству Тогда В дальнейшем будет показано (теорема Шеннона, глава 6), что при достаточно большом n для записи n исходов опыта с вероятностями m1, m2,..., mk достаточn n n но k mi log mi битов. Таким образом, на каждый опыт в среднем приходится по i=1 n log mi битов. Тогда Также естественно предположить, что функция h непрерывна по всем своим аргументам. Из непрерывности функции h следует, что равенство h m1, m2,..., mk = log mi верно и для опытов с иррациональными вероятностями исходов. Нетрудi=1 n но видеть, что полученная нами формула утверждает, что количество информации, содержащееся в исходе некоторого опыта, равняется логарифму от его вероятности взятому со знаком минус.

В дальнейшем мы будем считать, что возможные исходы опыта закодированы буквами некоторого алфавита A, а наборы исходов опыта будем отождествлять со словами в этом алфавите.

Говорят, что задан источник сообщений A, P с алфавитом A и распределением вероятностей P, когда на множестве слов A определена вероятность P : A [0, 1], удовлетворяющая условиям Определим сложность слова w A относительно вероятности P равенством Пусть w M (r), где r = (r1,..., rk ) и r1 + · · · + rk = n. Определим эмпирическую вероятность каждой буквы как частоту её встречаемости в слове w, а эмпирическую вероятность слова как произведение вероятностей букв, составляющих слово. Имеем равенства:

Нетрудно видеть, что эмпирические вероятности всех слов w M (r) равны и для любого слова w M (r) имеется равенство Тогда из утверждения 5 имеем |I(wn |Pr ) L(wn |M (r))| = o(n) = o(I(wn |Prn )), когда длина n слова wn стремится к бесконечности.

Занумеруем слова из M (r) в лексикографическом порядке. Каждое слово из M (r) получит номер из целочисленного промежутка [1, |M (r)|], который можно записать в виде двоичного слова длины log |M (r)|. Определим программу r, которая ставит в соответствие этому номеру слово из M (r). Тогда |K(w|r ) L(w|M (r))| 1. Величина I(w|Pr ) асимптотически (при росте длины слова w) совпадает со сложностью слова w относительно некоторой программы, поэтому является простейшей верхней оценкой колмогоровской сложности слова w.

Таким образом, различные способы определения условной сложности слова приводят к приблизительно одинаковому результату при должном выборе условий. Однако, следует обратить внимание и на некоторую разницу между рассмотренными подходами. При алгоритмическом подходе имеется абсолютное определение сложности, которое хорошо согласованно с интуитивными представлениями. Действительно, слово из чередующихся нулей и единиц является простым и с интуитивной и с алгоритмической точки зрения: имеется простая программа порождения, а значит колмогоровская сложность слова мала. В то время как с точки зрения эмпирической вероятности оно ничем не выделяется среди слов, в которых по половине нулей и единиц. Можно выбрать распределение вероятностей, относительно которого это чередующееся слово окажется простым. Но тогда окажутся маловероятными, т. е.

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

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

З а д а ч а 8. Докажите, что если непрерывная функция f : (0, ) (, ) такова, что f (a) = 1 и при любых x, y (0, ) удовлетворяет равенству f (xy) = f (x) + f (y), то f (x) = loga x при любом x (0, ).

Глава 2.

Определение и свойства энтропии разбиения Вероятностным пространством называется тройка, F, P, где множество элементарных событий, F = {a } -алгебра событий, a и P : F [0, 1] вероятностная мера. Вероятностной мерой (вероятностью) называется функция, которая удовлетворяет условиям P () = 1 и P ( i ai ) = i ai, где {ai }i произвольное конечное или счётное семейство попарно непересекающихся событий ai F. Для обозначения вероятности будем также пользоваться символом Pr, когда помимо основного вероятностного пространства приходится рассматривать ещё одно, возможно заданное неявно.

Случайной величиной называется измеримая функция : R, т. е. такая функция, что 1 (, c) F для любого c R. Случайная величина, принимающая конечное число значений, называется дискретной1. Набор дискретных случайных величин 1, 2,..., n называется независимым, если события 1 (c1 ), 2 (c2 ),..., n (cn ) независимы для любых c1, c2... cn R, т. е. справедливо равенство Математическим ожиданием (средним значением) дискретной случайной веci P ( 1 (ci )), где суммирование ведётся по вселичины называется число E = возможным значениям случайной величины. Дисперсией случайной величины называется число D = E( E)2.

В дальнейшем нам понадобятся следующие известные (см., например, [1]) свойства случайных величин.

A1. E(1 + 2 ) = E1 + E2 для любых случайных величин 1 и 2.

A2. E(1 2... n ) = E1 E2... En для любого набора независимых случайных величин 1, 2,..., n.

A3. D(1 + 2 + · · · + n ) = D1 + D2 + · · · + Dn для любого набора независимых случайных величин 1, 2,..., n.

A4. P {|E| > } D для любой случайной величины и числа > 0 (неравенство Чебышёва).

Разбиением множества элементарных событий называется конечное множество Дискретную случайную величину можно определить как функцию с произвольной (не обязательно числовой) конечной областью значений. В этом случае для измеримости функции достаточно, чтобы прообразы 1 (c) принадлежали -алгебре событий.

Пересечение событий a1 и a2 принято обозначать через a1 a2.

понятие разбиения эквивалентно понятию дискретной случайной величины, заданной равенствами (ai ) = i при i = 1,..., k. Однако, мы не будем использовать термин "случайная величина" если нет необходимости применять свойства A1–A4.

Энтропией разбиения A относительно вероятности P называется величина Когда вероятностная мера фиксирована, энтропию будем обозначать просто H(A).

Основными примерами пространств событий в дальнейшем будут служить источники сообщений. В этом случае событиями являются слова в некотором фиксированном алфавите A = {a1,..., ak }, причём считается, что когда слово w A выступает в качестве события, оно является объединением всех своих продолжений wai, i = 1,..., k. Это вполне естественно, если рассматривать слово как запись результатов некоторого повторяющегося опыта с исходами, закодированными буквами алфавита A. В частности, алфавит A будет порождать разбиение на множества, каждому из которых будут принадлежать слова начинающиеся с некоторой фиксированной буквы. Нетрудно видеть, что условия (1.3) обеспечивают свойство аддитивности вероятности на объединении непересекающихся событий.

Пусть задано слово w с частотным составом r. Определим вероятность Pr слова w в соответствии с формулой (1.4). Из формулы (1.5) вытекает равенство H(A, Pr ) = I(w|Pr ) для любого слова w M (r). Величина H(A, Pr ) = H(w) называется эмпиw| рической энтропией слова w.

П р и м е р 1. Рассмотрим слово w = abbaccbbbabbaaab. Слово w имеет частотный состав (6, 8, 2). Вычислим эмпирическую энтропию слова H(w) = 16 log 16 1 log Пусть имеется две вероятностные меры P и Q, определённые на разбиении A.

Информационной дивергенцией называется величина У т в е р ж д е н и е 6. Пусть A разбиение, |A| = k, P и Q вероятностные меры. Тогда 2) DA (P Q) = 0 тогда и только тогда, когда P (a) = Q(a) для любых a A.

Д о к а з а т е л ь с т в о. Рассмотрим функцию f (x) = log x. Поскольку f (x) < 0 при x > 0, функция f (x) выпукла вверх и для неё справедливо неравенство Йенсена формуле (2.1) возможно только если xj = xi когда j, i > 0.

P (ai ) log P (ai ) = 0.

Если P (ai ) = Q(ai ) для любых событий ai A, то равенство DA (P Q) = 0 очевидно.

Предположим, что DA (P Q) = 0. Тогда из неравенства Йенсена следует, что У т в е р ж д е н и е 7. Пусть |A| = k, тогда для любой вероятности P справедливо неравенство 0 H(A, P ) log k.

Д о к а з а т е л ь с т в о. Рассмотрим равномерное распределение вероятностей Q(ai ) = 1/k для всех i = 1,..., k. Из утверждения 6 получаем Неравенство 0 H(A, P ) непосредственно вытекает из определения энтропии.

Вероятность события a при условии b определяется равенством P (a|b) = P (ab). P (b) Здесь и далее пересечение событий a и b обозначается через ab.

Для произвольных событий b и c и любого разбиения A = {a1,..., ak } справедливы формулы полной вероятности:

Пусть H(A|b) = P (ai |b) log P (ai |b). Для пары разбиений A и B определим условную энтропию П р и м е р 2. Рассмотрим слова w1 = abbaccbbbabbaaab w2 = cabbbacabbbcaccc.

Эмпирическую вероятность P (x|y) буквы x при условии y можно определить как частоту встречаемости буквы x над буквой y, когда одно слово записано под другим.

Например, P (a|b) = 1/3. Вычислим условную эмпирическую энтропию H(w1 |w2 ) = = 4 H(w1 |a) + 3 H(w1 |b) + 3 H(w1 |c) = 1 3 + 3 ( 3 + 1 log 3) + 3.

П р и м е р 3. Рассмотрим циклическое слово w1 = abbaccbbbabbaaab(a), т. е. считаем, что за последней буквой слова следует первая и далее по циклу. Определим P (xy) как частоту пары букв xy в слове w1. Например, P (ab) = 3/16. Соответственно определим условные вероятности. Нетрудно видеть, что условные вероятности получились такие же как если бы мы в предыдущем примере взяли вместо слова w сдвинутое слово w1, т. е. bbaccbbbabbaaaba.

Пусть A и B разбиения. Разбиение AB = {ai bj }ij определяется, как разбиение, состоящее из всевозможных пересечений событий ai и bj.

H(AB) = H(B) + H(A|B).

Доказательство.

Разбиения A и B называются независимыми, если события ai и bj попарно независимы, т. е. P (ai bj ) = P (ai )P (bj ) для всевозможных i, j.

У т в е р ж д е н и е 9. Пусть A, B разбиения, тогда H(A) H(A|B). Разбиения A и B независимы тогда и только тогда, когда H(A|B) = H(A).

Доказательство.

Из утверждения 6 следует, что для любого события bj B справедливо неравенство причём равенство возможно только в случае, когда P (ai |bj ) = P (ai ) для любых Используя формулу полной вероятности, получаем равенство По определению условной вероятности имеем Тогда справедливо неравенство H(A) H(A|B), причём равенство H(A) = H(A|B) возможно только в случае, когда P (ai |bj ) = P (ai ) для любых i = 1,..., k и Если разбиения A и B независимы, то равенство H(A|B) = H(A) очевидно.

Д о к а з а т е л ь с т в о. Из утверждения 6 и формулы (2.2) имеем Тогда Взаимной информацией разбиений A и B называется величина a) I(A, B) = H(A) + H(B) H(AB);

b) I(B, A) = I(A, B);

c) I(A, A) = H(A);

e) I(A, BC) I(A, B).

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

П р и м е р 4. Пусть w1, w2 An. Рассмотрим эмпирическую информацию I(w1, w2 ) = H(w1 ) H(w1 |w2 ). Нетрудно видеть, что эмпирическая информация слов обладает свойствами a) e) и может использоваться как мера подобия слов. Пусть w1 = abbaccbbbabbaaab, w2 = cabbbacabbbcaccc. Тогда I(w1, w2 ) = 2 8 log 3 1 3 3 ( 3 + Введённые в данном разделе понятия имеют свои комбинаторные и алгоритмические аналоги. Пусть задано произвольное конечное множество X и его разбиение A = {a1,..., ak }, где X = ai, причём множества ai попарно не пересекаются. Тогда комбинаторным аналогом энтропии разбиения A будет величина Исходя из того, что log |X| есть число битов, необходимое для указания некоторого бятся для указания элемента множества X если уже известно, какому из множеств ai принадлежит этот элемент, можно заключить, что энтропия разбиения есть разность между сложностью задания элемента при отсутствии информации и сложностью задания элемента, когда он известен приблизительно, с точностью до элемента разбиения.

При алгоритмическом подходе можно определить условную сложность как сложность преобразования одного слова из другого. Тогда алгоритмическим аналогом энтропии разбиения будет разность между колмогоровской сложностью слова и средней сложностью получения слова из некоторого набора образцов.

ных разбиений A, B и вероятностных распределений P и Q справедливо неравенство DAB (P Q) DA (P Q).

З а д а ч а 10. Докажите, что следующие условия эквивалентны:

1) Разбиения A и B независимы;

З а д а ч а 11. Для произвольных разбиений A, B и распределения вероятностей P определим распределение вероятностей Q на AB равенствами Q(ai bj ) = P (ai )P (bj ).

Докажите равенство I(A, B) = DAB (P Q).

З а д а ч а 12. Для произвольных разбиений A, B, C докажите равенство H(AB|C) = H(B|C) + H(A|CB).

З а д а ч а 13. Для произвольных разбиений A, B, C докажите неравенства a) H(AB|AC) H(B|C) + H(A|CB);

b) H(A) + H(B) + H(C) + 3H(ABC) 2(H(AB) + H(BC) + H(CA));

З а д а ч а 14. Пусть задан набор разбиений A1,..., An. Для произвольных наборов I = (i1,..., ik ), 1 i1 < i2 < · · · < ik n, определим AI = Ai1... Aik и hk = C k1 H(AI ). Докажите неравенства h1 h2 · · · hn.

З а д а ч а 15. Для произвольного разбиения A и независимых разбиений B1, B докажите неравенство I(B1 B2, A) I(B1, A) + I(B2 |A).

З а д а ч а 16. Для пары разбиений A и B определим величину Докажите, что величина (A, B) обладает всеми свойствами метрики4 :

c) (A, B) = (B, A);

d) (A, B) + (B, C) (A, C).

З а д а ч а 17. Для трёх разбиений A, B и C определим условную взаимную информацию равенством I(A, B|C) = H(A|C) H(A|BC). Докажите равенство Разбиения A и B, для которых условная вероятность P (Ai |Bj ) принимает только два значения 0 и 1, считаются одинаковыми. Если, используя эмпирические вероятности, аналогично определить расстояние между словами, то два слова, совпадающие после переименования букв, будут находится на расстоянии 0.

I(A, B|C) = I(AC, B) I(C, B).

З а д а ч а 18. Пусть разбиения A, B, C таковы, что H(C|AB) = H(C|B). Докажите, что a) H(A|BC) = H(A|B);

b) I(A, B) I(A, C) (неравенство обработки информации).

Неравенство обработки информации означает, что в процессе обработки первоначальная информация может только теряться. Действительно, пусть A, B и C дискретные величины соответствующие разбиениям A, B и C. Предположим, что B = f1 (A ) и C = f2 (B ), где f1, f2 некоторые операции обработки информации.

Тогда выполнено условие H(C|AB) = H(C|B), поскольку P (c|ab) = P (c|b), для любых событий a A, b B, c C. Неравенство обработки информации утверждает, что в разбиении B, полученном посредством первого преобразования f1, не меньше информации о разбиении A, чем в разбиении C, полученном посредством преобразования f2 f1.

З а д а ч а 19. Пусть имеются две вероятностные меры P и Q, определённые на разбиении A. Определим величину dA (P, Q) = |P (ai ) Q(ai )|. Докажите, что dA (P, Q) обладает всеми свойствами метрики и справедливо неравенство dA (P, Q) P (ai )P (bj )|. Докажите, что sup AB = 2 P (ai )(1 P (ai )).

З а д а ч а 21. Докажите неравенства Пинскера Глава 3.

Цепи Маркова Рассмотрим последовательность одинаковых случайных испытаний, в которой вероятность исхода следующего испытания зависит только от исхода испытания, непосредственно предшествующего ему. Такая случайная последовательность называется цепью Маркова.

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

3.1. Эргодическая теорема для марковской цепи Пусть задано множество текстов в некотором алфавите. Предположим, что вероятность появления буквы на некоторой позиции в тексте зависит только от непосредственно ей предшествующей буквы и не зависит ни от позиции, ни от предыдущего текста. Такие тексты в алфавите E можно рассматривать как реализации некоторой цепи Маркова.

Дадим формальное определение. Пусть, F, P вероятностное пространство.

При изложении теории марковских цепей принято рассматривать дискретные случайные величины, областью значений которых является некоторое конечное множество E = {s1,..., sk }. Последовательность случайных величин 1,2,...,n,... образует однородную цепь Маркова (марковскую цепь), если для любых номеров n, а также произвольных i, j, i1,..., in2 справедливо равенство Исходы испытаний si, i = 1,..., k называются состояниями марковской цепи.

Матрица P составленная из чисел pij называется матрицей переходных вероятностей. Из определения и формулы полной вероятности (2.2) видно, что pij 0 и pij = 1 для всех j = 1,..., k. Матрицы, обладающие такими свойствами, называi= ются стохастическими.

В соответствии с определением марковской цепи и формулой полной вероятности (2.2), вероятность pij (n) = P (n+m = si |m = sj ) перехода за n шагов из состояния sj в состояние si вычисляется по рекуррентной формуле где pij (1) = pij.

У т в е р ж д е н и е 12. Пусть P (n) матрица, составленная из чисел pij (n).

Тогда P (n) = P, P (n) стохастическая матрица и для всех натуральных n, m и i, j = 1,..., k, справедливы равенства Следовательно, справедливо равенство P n+m = P n P m, эквивалентное равенству (3.2).

Из определения видно, что pij (n) 0. Методом индукции по n докажем, что Пусть (3.3) верно. Тогда из (3.1) имеем Марковская цепь называется неразложимой, если для любых i, j = 1,..., k найдётся такое n, что pij (n) > 0.

Число d > 1 называется периодом состояния si, если d есть наибольший общий делитель таких чисел n, что pii (n) > 0, т. е. число d период состояния si, если в состояние si можно вернуться только за кратное d число шагов.

У т в е р ж д е н и е 13. Все состояния неразложимой марковской цепи имеют одинаковый период.

Д о к а з а т е л ь с т в о. Поскольку марковская цепь неразложима, найдутся такие n1, n2 N, что pij (n1 ) > 0 и pji (n2 ) > 0. Пусть di период состояния si, тогда di делит число n1 + n2. Рассмотрим произвольное n3 N такое, что pjj (n3 ) > 0.

Тогда di делит число n1 + n2 + n3 и, следовательно, делит число n3. Тогда di делит dj, где dj период состояния sj. Поскольку это верно для произвольных i, j, то di = dj для любых i, j = 1,..., k.

Если все состояния марковской цепи имеют период d > 1, то марковская цепь называется периодической. В противном случае марковская цепь называется непериодической.

Нам понадобится следующее N, что любое натуральное число n n0 представляется в виде n = 1 m1 + 2 m2 + · · · + t mt, где 1,..., t целые неотрицательные числа.

Д о к а з а т е л ь с т в о. Пусть НОД(m1, m2 ) = d, тогда из алгоритма Евклида нахождения наибольшего общего делителя следует, что найдутся такие целые числа 1, 2, что 1 m1 + 2 m2 = d. Пусть НОД(m1, m2,..., mr ) = dr, методом индукции по r покажем, что для r, 2 r t, найдутся такие целые числа 1, 2,..., r, что верно равенство Имеем НОД(dr, mr+1 ) = dr+1. Тогда найдутся целые числа 1, 2 такие, что 1 dr + 2 mr+1 = dr+1. По предположению индукции (3.4) имеем равенство что и требовалось. Рассмотрим целые числа 1, 2,..., t, для которых выполняется равенство Пусть m0 = min(m1,..., mt ) и C = max{|i m0 |}. Если n C(m1 + m2 + · · · + mt ) = n0, x2 (n) < m0, чтобы выполнялось равенство Поскольку i C + x2 (n)i 0 для любого i = 1,..., t, требуемое представление числа n получено.

У т в е р ж д е н и е 15. Если марковская цепь неразложимая и непериодическая, то найдётся такое n0 N, что pij (n) > 0 для всех n n0 и i, j = 1,..., k.

Д о к а з а т е л ь с т в о. Поскольку марковская цепь непериодическая, то найдутся такие числа m1,..., mti, что НОД(m1, m2,..., mti ) = 1 и pii (mr ) > 0 для всех r = 1,..., ti. Из утверждения 14 следует, что найдётся такое число ni, что при всех n ni число n представимо в виде n = 1 m1 + 2 m2 + · · · + ti mti, где j целые. Тогда из формулы (3.2) имеем Из неразложимости марковской цепи для всех i, j = 1,..., k найдутся такие числа mij N, что pij (mij ) > 0. Рассмотрим n max mij + max ni. Тогда из формулы (3.2) имеем pij (n) pij (mij )pjj (n mij ) > 0.

Следующая теорема занимает центральное место в теории марковских цепей.

Т е о р е м а 3. (эргодическая) Марковская цепь является неразложимой и непериодической тогда и только тогда, когда для каждого i = 1,..., k существует предел lim pij (n) = i > 0, не зависящий от j.

Д о к а з а т е л ь с т в о. Необходимость (). Введём обозначения ai (n) = min pij (n) и b (n) = max pij (n). Поскольку из (3.2) имеем то bi (n + 1) bi (n). Аналогично получаем неравенство ai (n + 1) ai (n) для всех n N и i = 1,..., k. Таким образом, монотонные ограниченные последовательности ai (n) и bi (n) имеют конечные пределы. Докажем, что bi (n) ai (n) 0 при n.

Из утверждения 15 следует существование такого числа n0 N, что pij (n0 ) > для всех i, j = 1... k. Рассмотрим произвольную пару столбцов с номерами j1, j2 в матрице P (n0 ) и определим множествo L1 следующим образом: l L1, если plj1 (n0 ) plj2 (n0 ) 0, L2 = {1,..., k} \ L1.

Введём обозначение h = max hij < 1. Тогда для некоторых номеров j1, j2 из равенства (3.2) имеем Следовательно, bi (n + mn0 ) ai (n + mn0 ) (bi (n) ai (n))hm 0 при m.

Таким образом, некоторая подпоследовательность сходящейся последовательности (bi (n) ai (n)) сходится к нулю, тогда и (bi (n) ai (n)) 0 при n.

По определению имеем ai (n) pij (n) bi (n) для всех j = 1,..., k. По лемме о зажатой последовательности справедливы неравенства Обозначим этот предел через i. Из утверждения 15 имеем pij (n) > 0 и ai (n) > 0 для достаточно больших n. Поскольку последовательности (ai (n)) не убывают для всех i = 1,..., k, их пределы положительны, т. е. i > 0.

Достаточность (). Начиная с некоторого номера n0 N, для всех n n0 и i, j = 1...., k выполнено неравенство pij (n) > 0, так как lim pij (n) > 0. Тогда марn ковская цепь является неразложимой и непериодической.

Величины i называются стационарными или финальными вероятностями состояний цепи Маркова.

П р и м е р 5. Пусть P = 1/4 1/3 1/2 матрица переходных вероятностей марковской цепи. Нетрудно видеть, что соответствующая цепь Маркова является неразложимой и непериодической. Вычислим вектор стационарных вероятностей.

Из утверждения 16 видно, что является собственным вектором матрицы P, соответствующим собственному числу 1. Решим систему линейных уравнений (P E)x = 0.

Одним из решений системы будет вектор x = (2, 3/2, 1). Поскольку сумма координат вектора стационарных вероятностей равна 1, то = x/(9/2) = (4/9, 1/3, 2/9).

З а д а ч а 22. Пусть P матрица переходных вероятностей неразложимой непериодической марковской цепи и вектор v удовлетворяет равенствами v = P v и vi = 1. Докажите, что v является вектором стационарных вероятностей.

З а д а ч а 23. Пусть P матрица переходных вероятностей неразложимой непериодической марковской цепи и транспонированная матрица P является стохастической. Докажите, что все компоненты вектора стационарных вероятностей равны между собой.

З а д а ч а 24. Пусть P матрица переходных вероятностей неразложимой периодической марковской цепи с периодом m. Докажите, что стохастическая матрица P m является матрицей переходных вероятностей некоторой разложимой непериодической марковской цепи.

З а д а ч а 25. Докажите, что любая стохастическая матрица имеет собственное число равное 1.

З а д а ч а 26. Докажите, что модуль любого собственного числа стохастической матрицы не превосходит единицы.

З а д а ч а 27. Докажите, что если последовательность случайных величин 1..., n,... является цепью Маркова, то последовательность блоков (1,..., k ), (2,..., k+1 ),... также является цепью Маркова. Докажите, что последовательность блоков непериодична и неразложима, если первоначальная последовательность обладает этими свойствами.

З а д а ч а 28. Пусть P некоторая стохастическая матрица, а p и q наборы вероятностей элементов разбиения A. Докажите неравенствo DA (P p P q) DA (p q).

3.2. Закон больших чисел для марковской цепи Говорят, что последовательность случайных величин (n ) сходится к случайной величине (или числу) по вероятности (n ), если Pr{|n | > } 0 при n для любого > 0. Последовательность случайных величин (n ) сходится к числу a R в среднем, если En a при n.

У т в е р ж д е н и е 17. Пусть (n ) ограниченная последовательность случайных величин, сходящаяся по вероятности к числу a R. Тогда последовательность (n ) сходится к числу a в среднем.

Д о к а з а т е л ь с т в о. Пусть |n | C. Рассмотрим произвольные, > 0.

Найдётся номер n, начиная с которого Pr{|n a| > } <. Тогда Поскольку числа, > 0 могут быть взяты произвольно малыми, получаем, что Т е о р е м а 4. (закон больших чисел) Пусть (n ) последовательность независимых одинаково распределённых случайных величин, причём E1 = a R и Доказательство.

Из свойств математического ожидания и дисперсии суммы случайных величин Чебышёва (A4, с.13) получаем для произвольных > 0 и натуральных n.

Пусть задана некоторая марковская цепь. Будем рассматривать в качестве пространства событий последовательности = 1, 2,..., n... её состояний, i {s1,..., sk }. Определим случайные величины ij (s), где i = 1,..., k, j натуральное, равенством Тогда ri (n) количество состояний si в слове 1 2... n удовлетворяет равенству ri (n) = Пусть марковская цепь неразложима и непериодична, тогда из эргодической теоремы следует существование стационарных вероятностей = (1,..., k ). Будем считать, что начальное состояние марковской цепи равно si с вероятностью i. Нетрудно видеть, что в этом случае вероятность любого слова в последовательности состояний не зависят от места слова в последовательности. В частности, из утверждений для любого натурального числа j. Тогда из (A1, с.13) получаем равенство Определим случайную величину i () = min{k | k = si }. Имеем где случайная величина ij определяется как разность номеров (j + 1)-го и j-го вхождения состояния состояния si в последовательность (i1 = i ). Как было замечено выше, вероятности не зависят от того, начиная с какой позиции мы будем искать первое вхождение состояния si. Поэтому для любого j случайные величины ij одинаково распределены cо случайной величиной i и являются независимыми в отличие от случайных величин ij.

дится к числу i по вероятности при n.

Д о к а з а т е л ь с т в о. Из определения случайной величины i видно, что вероятности Pr{i = n} убывают экспоненциально при росте n. Тогда случайная величина i имеет конечные математическое ожидание и дисперсию. Пусть Ei = a, > 0, m(n, ) = ( + a)n. Из равенства (3.6) имеем где C > 0 некоторая константа. Аналогичное неравенство получается и для вероятности Pr rin a. Тогда, применяя закон больших чисел к последовательn) ности (in ), получаем, что a. Из утверждения 17 и равенства (3.5) следует, что a = i.

Таким образом, частота вхождений состояния si в неразложимую непериодическую марковскую цепь стремиться к стационарной вероятности i не только в среднем, но и по вероятности.

Глава 4.

Модели источников сообщений В этом разделе мы рассмотрим различные модели источников сообщений. Будут рассмотрены способы задания вероятности на множестве слов, порождённых той или иной моделью. Однако, наибольший интерес представляет обратная задача: выбор модели наилучшим образом соответствующей данному тексту. Выбор подходящей модели текста позволяет успешно сжимать текст, прогнозировать продолжение текста, а также устанавливать степень похожести одного текста на другой.

4.1. Конечные автоматы Наиболее известной моделью источника сообщений является конечный автомат. Конечный автомат задаётся с помощью мультиграфа1 G = V, E, E = {ei }, V = {vj }. Вершины графа G называются состояниями автомата, среди них выделяется множество входных состояний Vb V и множество выходных состояний Ve V.

Дуги графа G помечены буквами некоторого алфавита A, т. е. определена функция F : E A. Пути в графе G, начинающиеся в состояниях из множества Vb и заканчивающиеся в состояниях из множества Ve, будем называть допустимыми. Каждый допустимый путь считаем помеченным словом, которое состоит из букв, которыми помечены дуги этого пути, т. е. определим Таким образом, множество допустимых путей автомата порождает множество слов.

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

Мультиграфом называется ориентированный граф с кратными дугами. В дальнейшим будем называть мультиграфы просто графами.

Из сказанного выше видно, что конечный автомат определяется как G, Vb, Ve, A, F, где G мультиграф, Vb, Ve множества входных и выходных состояний, A алфавит, F функция, помечающая дуги графа G буквами алфавита A. Автомат называется детерминированным, если из каждой вершины графа не выходит двух дуг, помеченных одинаковой буквой алфавита A. В противном случае автомат называют недетерминированным. Нетрудно видеть, что детерминированный автомат определяется множеством состояний V и функцией µ : V A V.

Автоматы называют эквивалентными, если они порождают одинаковый язык.

Т е о р е м а 5. (Рабин и Скотт) Для любого конечного автомата найдётся эквивалентный ему детерминированный автомат.

Д о к а з а т е л ь с т в о. Рассмотрим конечный автомат, задаваемый графом G = V, E. Пусть P(V ) множество всех подмножеств состояний автомата. На множестве вершин P(V ) построим мультиграф. Для любых множества P(V ) и буквы a A определим f (, a) P(V ) как множество состояний, которые являются концами путей, начинающихся в состояниях из множества, и помеченных буквой a A. В мультиграфе соединим вершины и f (, a) дугой, помеченной буквой a A. В качестве входных состояний выберем такие одноэлементные множества {v} P(V ), что v Vb. В качестве выходных состояний выберем такие множества P(V ), что Ve =. Полученный автомат является детерминированным по построению. Покажем, что он эквивалентен исходному конечному автомату. Достаточно показать, что в графе имеется путь из состояния {v0 } в состояние = {vi1,..., vim }, помеченный словом w тогда и только тогда, когда в графе G имеются пути из вершины v0 в каждую из вершин vij помеченные словом w.

Докажем последнее высказывание методом индукции по длине слова w. Для слов длины 1 утверждение верно по построению. Пусть утверждение справедливо для слова w. Рассмотрим слово wa. Принадлежность v f (, a) эквивалентна тому, что для некоторой вершины vij найдётся путь в графе G из vij в v помеченный буквой a. Так как автомат задаваемый графом детерминированный, то только один путь {v},...,, f (, a) помечен словом wa. По предположению индукции и определению множества f (, a), все вершины v f (, a) и только они являются концами путей в графе G с началом в вершине v0, помеченных словом wa.

ком. Известно (см., например, [7]), что множество регулярных языков замкнуто относительно естественных операций над языками: пересечения, объединения и конкатенации.

4.2. Параметры модели источника сообщений Конечный автомат служит моделью источника сообщений (случайных слов).

Для определения вероятностей слов необходимо задать параметры модели вероятности дуг графа. Пусть дана модель с графом G = V, E. Вероятности дуг p(e), e E должны удовлетворять условиям где сумма берётся по всем дугам с началом в любом фиксированном состоянии v V.

Кроме того, нужно определить вероятности входных состояний p(v) 0, где v Vb, удовлетворяющие равенству p(v) = 1, где сумма берётся по всем v Vb. Если входное v состояние единственное, то p(v) = 1. Вероятность pij перехода за один шаг из состояния vj в состояние vi определяется как p(e), где сумма берётся по всем дугам с началом в vj и концом в vi. Из (4.1) видно, что pij = 1. Таким обраi зом, последовательность состояний модели можно рассматривать как цепь Маркова, поэтому такие модели источников сообщений нередко называют марковскими.

Определим вероятность P (a|v) = p(e), где сумма берётся по всем дугам e E с началом в состоянии v V, помеченным буквой a A. Вероятность пути ei1... ein в графе G с началом в состоянии v Vb определяется как p(v)p(ei1 )... p(ein ). Вероятность P (w) слова w A в модели с графом G = V, E и параметрами p(e), e E и p(v), v Vb определяется как сумма вероятностей всех допустимых путей, помеченных словом w.

У т в е р ж д е н и е 19. Пусть все состояния марковской модели являются выходными. Тогда марковская модель с фиксированным набором параметров определяет источник сообщений, т. е. для любого слова w A справедливо равенство Д о к а з а т е л ь с т в о. Пусть u E допустимый путь. Тогда из (4.1) имеем P (ue) = P (u), где сумма берётся по всем дугам e, выходяшим из концевой вершины пути u. Из этого равенства и определения вероятности слова вытекает равенство P (wa) = P (w). Справедливость равенства P (w) = 1 нетрудно установить из предыдущего равенства методом индукции по длине слова.

Модель порождения слов будем называть автоматной, если она определяется детерминированным автоматом, все состояния которого являются выходными и только одно входным. Как было отмечено выше, детерминированный автомат определяется функцией µ : V A V, которая по состоянию v V и порождённой в этом состоянии букве a A определяет следующее состояние µ(v, a). Тогда имеется равенство pij = P (a|vj ), где µ(vj, a) = vi.

Простейшая автоматная модель, имеющая только одно состояние, называется моделью Бернулли. Источники сообщений с такой моделью называются источниками Бернулли.

У т в е р ж д е н и е 20. Пусть задан детерминированный автомат, тогда существует взаимно однозначное соответствие между допустимыми путями u V и порождаемыми автоматом словами w A. При этом справедливо равенство где vi1 = v0 входное состояние и vim = µ(vim1, aim1 ).

Д о к а з а т е л ь с т в о. Соответствующий слову ai1... ain допустимый путь vi1,..., vin получаем по правилу vi1 = v0 входное состояние и vim = µ(vim1, aim1 ).

Из определения детерминированного автомата видно, что найденный допустимый путь является единственным путём помеченным словом ai1... ain.

Таким образом, автоматная модель M и набор параметров P определяют некоторый источник сообщений. Отметим, что равенства (4.2) остаются справедливым и при более слабых требованиях на модель, для этого достаточно уже того, чтобы все состояния модели были выходными и все дуги были помечены буквами.

Предположим, что задана некоторая модель M и слово w A, которое может быть порождено источником сообщений с моделью M. Возникает вопрос: какими следует выбрать параметры модели, чтобы вероятность произвести слово w была максимальной? Если модель M является автоматной, то на этот вопрос нетрудно ответить.

Пусть w An и u V n соответствующий слову w набор состояний детерминированного автомата. Определим эмпирические вероятности порождения букв в различных состояниях v V равенствами Pw (a|v) = rrw (v), где rw (v) число вхожw (a|v) дений состояния v в набор состояний u V n и rw (a|v) число раз, когда буква a A встречается в состоянии v V при порождении слова w. Если rw (v) = 0, то вероятности Pw (a|v) можно назначать произвольно, например, равными для всех букв. Нетрудно видеть, что в модели Бернулли n log Pw (w) = H(w) для любого слова w An, где H(w) эмпирическая энтропия слова w. Индекс w у величин rw и Pw будем опускать, если из контекста ясно, какое слово w A подразумевается.

В частности, будем всегда предполагать, что P (w) = Pw (w).

У т в е р ж д е н и е 21. Пусть w A. Справедливо равенство P (w) = max P (w), где максимум берётся по всевозможным наборам параметров автоматной модели M.

Д о к а з а т е л ь с т в о. Пусть w = ai1... ain. Рассмотрим модель M с произвольным набором параметров. По формуле (4.3) имеем Тогда Из утверждения 6 имеем Тогда log P (w) log P (w) и P (w) P (w).

Из утверждения 21 можно сделать вывод: если задана модель M и слово w, порождённое источником сообщений с этой моделью, то наиболее вероятными параметрами модели являются Pw. Действительно, пусть {} множество параметров автоматной модели M. Предположим, что на {} задано некоторое распределение вероятностей Pr. Из формулы полной вероятности (2.2) нетрудно получить формулу Байеса где Pr(w|P ) = P (w). Если считать вероятности Pr() наборов параметров одинаковыми, то наибольшая условная вероятность Pr(|w) того, что параметры модели равны, при уcловии порождения источником слова w, достигается на параметрах P = Pw. Величину log P (w) естественно считать сложностью слова w относительно модели M.

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

Действительно, если одно слово порождается двумя путями, то соответствующие этим путям наборы состояний различаются, а значит некоторый префикс слова приводит в разные состояния, что противоречит определению контекстной модели. Очевидно верно и обратное: если каждому слову соответствует единственный путь, то модель контекстная. Как показано в утверждении 20, автоматная модель является контекстной. Если для определения следующего состояния необходимо и достаточно знать контекст некоторой фиксированной длины m, то такая модель называется марковской порядка m. Марковская модель порядка m является автоматной. Действительно, определим множество состояний как V = Am. Произвольную вершину вида aw, где w Am1 соединим дугой с вершиной wb и пометим дугу буквой b A.

Полученный граф называется графом де Брёйна порядка m. Нетрудно видеть, что марковская модель порядка m есть автоматная модель с графом де Брёйна порядка m. При m = 1 множество букв и множество состояний совпадают и марковской модели соответствует цепь Маркова с множеством состояний A. Частным случаем марковской модели при m = 0 является модель Бернулли с единственным состоянием.

Пусть w A произвольное слово. Чтобы не было неопределённости в определении контекста первых букв слова, будем считать слово циклическим. Обозначим через Pm эмпирическую вероятность слова w в марковской модели порядка m.

У т в е р ж д е н и е 22. Для любого слова w A и натурального числа m верно неравенство Pm1 (w) Pm (w).

Д о к а з а т е л ь с т в о. Пусть w A. Определим пространство элементарных событий = Am+1 и P (x) = r(x), где r(x) число вхождений слова x Am+1 в слово w, учитывая и перекрывающиеся вхождения. Пусть разбиение B k состоит из множеств By = {zya | z Amk, a A}, где y Ak, k = 0,..., m, а разбиение A из множеств Aa = {za | z Am }. Тогда Поскольку B m1 B m = B m, из утверждения 10 следует, что log Pm (w) = nH(A|B m ) = nH(A|B m1 B m ) nH(A|B m1 ) = log Pm1 (w).

Откуда имеем Pm1 (w) Pm (w).

Таким образом, эмпирическая вероятность любого слова больше в марковской модели с большей длиной контекста. Будет ли из этого следовать, что модель с более длинным контекстом точнее моделирует механизм порождения текста? Если взять контекст длины равной длине слова без единицы, то эмпирическая вероятность слова будет равна 1. Однако, вряд ли такая модель осмысленна, поскольку она не выполняет своей роли служить кратким описанием слова. Для выбора модели, наилучшим образом соответствующей слову, мало минимизировать сложность слова относительно модели, нужно учитывать ещё и сложность самой модели. С этой целью Й. Риссанен ввёл понятие стохастической сложности St(w, M ) слова w относительно модели M. В § 6.8 будет дано формальное определение величины St(w, M ), а также величины n (M ), отвечающей за сложность модели, и доказано равенство Для автоматных моделей известно, что n (M ) = d log |w| + O(1), где d число независимых параметров модели. Не строго можно сказать, что сложность модели равняется количеству битов, необходимых для записи эмпирических параметров модели с точностью, которую обеспечивает длина слова.

Выбор такой модели текста, в которой текст имеет минимальную стохастическую сложность, соответствует принципу кратчайшего описания: лучшим способом описания объекта будет тот, который имеет минимальную длину. Более того, нередко наиболее короткое описание объекта является и наиболее осмысленным описанием, поскольку не содержит ничего лишнего. Использование кратчайшего описания соответствует известному в естественных науках методологическому принципу Оккама:

не следует изобретать сущностей сверх необходимого.

Описанный выше подход применяется к марковским моделям конечного порядка следующим образом. Из-за того, что количество контекстов состояний марковской модели порядка m растёт экспоненциально относительно m, принято рассматривать контекстные модели, получающиеся из марковских объединением состояний с близкими параметрами, т. е. в графе де Брёйна вершины vi и vj отождествляются, если P (a|vi ) P (a|vj ) для всех a A. Полученная модель уже может оказаться не автоматной, но сохраняет свойства однозначного соответствия между словами и допустимыми путями, т. е. является контекстной.

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

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

4.4. Метод трансфер-матрицы В этом разделе рассмотрен вопрос о количестве слов фиксированной длины в регулярном языке. Пусть G = V, E некоторый мультиграф. Занумеруем произвольным образом его вершины V = {v1,..., vm }. Матрицей смежности мультиграфа G (трансфер-матрицей) называется квадратная матрица M размера nn, в которой компонента M [i, j] равняется количеству дуг, идущих из вершины vi в вершину vj.

У т в е р ж д е н и е 23. Количество путей длины n ведущих из вершины vi в вершину vj равно M n [i, j].

Д о к а з а т е л ь с т в о. Докажем это утверждение методом математической индукции по длине пути. База индукции обеспечивается определением матрицы M.

Пусть утверждение доказано для количества путей длины n. Тогда число путей длиГлава 4. Модели источников сообщений ны n + 1, соединяющих вершину vi с вершиной vj равно соответствии с определением операции умножения матриц совпадает с компонентой M n+1 [i, j] матрицы M n+1 = M n M.

Пусть v1 входное состояние некоторой контекстной модели. Тогда количество слов длины, порождаемых в этой модели равняется сумме элементов первой строки матрицы M n, где M матрица смежности мультиграфа модели. Числа M n [i, j] можно вычислять описанным ниже способом.

собственные числа матрицы M справедливо равенство где E единичная матрица, а через Bij обозначено алгебраическое дополнение элемента B[i, j] в матрице B.

= (E M )1. Приравнивая компоненты двух матриц в левой и правой части равенства, получаем требуемое.

Рассмотрим задачу вычисления количества слов алфавита A, не содержащих подслов из некоторого множества Z A. Пусть максимальная длина слова из множества запретов Z равняется n0 + 1. Рассмотрим граф де Брёйна порядка n0 для этого алфавита и удалим из него все дуги и вершины, соответстующие запрещённым словам. Полученный граф обозначим GZ. Ясно, что множество слов длины n > n0 в алфавите A, не содержащих запрещённых подслов, вычисляется как число различных путей длины2 n n0 в графе GZ.

П р и м е р 6. Вычислим f (n) количество слов длины n в алфавите {a1, a2, a3 }, не содержащих подслов из множества Z = {a1 a1, a2 a3 }. Матрица смежности графа GZ с вершинами a1 2, a3 имеет вид Тогда Таким образом, f (1) = 3, f (2) = 7, f (3) = 16, f (4) = 36.

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

З а д а ч а 29. Пусть M матрица смежности некоторого мультиграфа G. Докажите, что количество контуров длины n в мультиграфе G равно n + · · · + n, где 1,..., m набор собственных чисел матрицы M с учётом их кратности.

З а д а ч а 30. Пусть NZ (n) множество циклических слов длины n в алфавите, не содержащих подслова из множества Z. Пусть максимальное по модулю собственное число3 матрицы смежности графа GZ. Докажите, что log |NZ (n)| = = n log ||(1 + o(1)) при n.

4.5. Скрытые марковские модели Рассмотрим марковскую модель с некоторым фиксированным набором параметров. В случае произвольной марковской модели последовательность состояний модели не восстанавливается однозначно по последовательности букв, порождённых в этих состояниях. Обычно предполагается, что слова это наблюдаемые данные, а состояния модели неизвестны. Отсюда происходит название скрытые марковские модели.

Для простоты будем считать, что марковская модель имеет единственное входное состояние vb, все её состояния являются выходными и все дуги графа G помечены буквами алфавита A. Пусть ei1... ein путь в графе G с началом в состоянии vb, которому соответствует слово x A и последовательность состояний vb s, s V n.

Введём обозначения: P (x, s) = P (ei1... ein ) и P (s|x) = P (x, s)/P (x).

Рассмотрим следующую задачу: пусть задано слово x A, нужно найти наиболее вероятный путь его порождения, т. е. такую последовательность состояний s(x), что где максимум берётся по всевозможным последовательностям состояний4.

Приведённый ниже алгоритм вычисления последовательности состояний s(x) был предложен А. Д. Витерби. Введём обозначение xn для префикса длины n слова x, n |x|. Из определений имеем где P (xn+1, sn+1 |sn ) = p(ein+1 ) вероятность дуги из состояния sn в состояние sn+1, помеченной буквой xn+1. Для более удобных вычислений следует перейти от умножений к сложениям, т. е. к логарифмам обратных вероятностей. Из (4.5) имеем где l(·) = log P (·). Задача (4.4) на поиск максимума превращается в задачу на поиск минимума где N = |x|.

По теореме Перрона Фробениуса (см. [28]) максимальное по модулю собственное число (перронов корень) неотрицательной матрицы является вещественным неотрицательным числом.

Заметим, что максимум вероятности P (s|x) может достигаться на нескольких последовательностях состояний s(x).

Для всех v V, n 0 определим величину L(v|xn+1 ) = minn l(xn+1, sn v). Тогда из формулы (4.6) имеем Поскольку l(xn, s(xn )) = minvV L(v|xn ), формула (4.7) обеспечивает рекуррентную процедуру вычисления величины l(x, s(x)). Последовательность состояний s(xN ) можно получить двигаясь в обратном направлении и определяя состояния sn, на которых достигается равенство начиная с L(sN |xN ) = l(xN, s(xN )).

Используя алгоритм Витерби, можно решать задачу о нахождении параметров марковской модели, при которых некоторое слово имеет максимальную вероятность порождения. А именно, сначала зададим параметры модели вероятности p(e) дуг графа, задающего модель, как произвольный набор положительных чисел, удовлетворяющих условию (4.1). Для определённости положим p(e) = 1/d(v), где d(v) степень исхода вершины v. Для заданного слова x A вычислим последовательr(e) ность состояний s(x). Определим эмпирические параметры p(e) = r(v), где r(e) количество прохождений дуги e, а r(v) количество прохождений вершины v, являющейся началом дуги e, при порождении слова x A на пути s(x). Повторим вычисление последовательности состояний s(x) для модели с новым набором параметров, вычислим новые эмпирические вероятности и т. д.

У т в е р ж д е н и е 25. Определённый выше процесс сходится, т. е. последовательность наборов эмпирических параметров, начиная с некоторой итерации, становится постоянной.

Д о к а з а т е л ь с т в о. Аналогично доказательству утверждения 21 можно показать, что величина P (x|s(x)) не возрастает после каждой итерации. Нетрудно видеть, что эмпирические параметры модели и, следовательно, величина P (x|s(x)) могут принимать только конечное число значений (при фиксированных начальных данных). Очевидно, что монотонная последовательность, принимающая конечное число значений, стабилизируется. Если стабилизируется величина P (x|s(x)), то стабилизируется и последовательность состояний s(x), а значит и набор эмпирических параметров.

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

На практике выбирают эмпирические параметры с поправкой p(e) = r(v)+d(v)/2, чтобы вероятности непройденных дуг не превращались в 0 и эти дуги не терялись на последующих итерациях. Кроме того, обнуление параметров эквивалентно удалению из графа соответствующих дуг, что может привести к уменьшению множества слов, порождаемых данной марковской моделью. Причины выбора величины сдвига, равной 2, обсуждается в § 6.8.

П р и м е р 7. Рассмотрим пример скрытой марковской модели. Имеются две монеты: правильная и погнутая, которые представляют два состояния модели.

Наблюдаемыми данными будут орлы и решки, которые выпадают при подбрасывании монеты, причём вероятности выпадения орла и решки при подбрасывании правильной монеты одинаковы, а при подбрасывании погнутой монеты различны.

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

Рис. 3. Граф скрытой марковской модели с правильной и погнутой монетами Определим модель формально. Пусть {v, v} множество состояний модели, имеющей следующие параметры P (0|v) = P (1|v) = 1, P (0|v) = 7, P (1|v) = 1, P (v|v) = P (v|v) = 16 и P (a, v1 |v2 ) = P (a|v2 )P (v1 |v2 ) при a {0, 1}, v1, v2 {v, v}. Пусть состояние v является входным. Рассмотрим последовательность 101000000. Построим таблицу где c = log 15. Имеет место неравенство 45 9c < 58 8c 6 log 7. Из таблицы получаем следующую последовательность состояний s(101000000) = vvvvvvvvv.

Глава 5.

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

Будем писать Hn (P ) вместо Hn ( A, P ) и H(P ) вместо H( A, P ) в тех случаях, когда алфавит фиксирован.

Энтропия является важнейшей характеристикой источника сообщений, отражающей среднее количество информации в сообщениях. Как будет показано в § 6.3 энтропия источника сообщений является точной нижней гранью количества двоичных символов, которые необходимо в среднем затратить на кодирование одного символа сообщения. В данном разделе будет доказано существование энтропии для широкого класса источников сообщений и предложены способы её вычисления.

5.1. Стационарные источники. Энтропия стационарного источника Пусть A = {a1, a2,..., ak } конечный алфавит. Рассмотрим в качестве пространства событий множество бесконечных в обе стороны последовательностей букв алфавита A, т. е. = A. Пусть множество Bij A состоит из последовательностей, имеющих на j-ом месте букву ai. Ясно, что набор множеств B j = {Bij }i=1...k является разбиением A.

Известная теорема Каратеодори (см., например, [1]) утверждает, что вероятностная мера, определённая на некотором полукольце множеств (дробящейся системе множеств) однозначно продолжается на порождённую этими множествами -алгебру.

i1,..., ik {1,..., k} является полукольцом. Действительно, в соответствии с определением полукольца она замкнута по отношению к взятию пересечений и если некоторое множество из этой системы содержится в другом, то последнее можно представить в виде объединения набора (включающего первое множество) попарно непересекающихся множеств из этой системы.

Пусть на -алгебре F, порождённой всевозможными событиями Bij, где i = 1,..., k, j целое, определена вероятностная мера P. Меру P будем называть стационарной, если она инвариантна относительно сдвигов бесконечных слов из A на произвольное число позиций, в частности, для любых наборов i1,..., in {1,..., k} и целых чисел j0, j1,..., jn должны быть справедливы равенства стационарная мера, то события Bi11 Bi22... Bin можно отождествить со словами ai1 ai2... ain и определить P (ai1... ain ) = P (Bi11... Bin ). Таким образом, люn бая стационарная мера определяет источник сообщений, который также называется стационарным.

Из (5.2) следует, что для стационарного источника A, P верно равенство У т в е р ж д е н и е 26. Пусть A, P стационарный источник, тогда последоn 12 n вательность n = H(B |B B... B ) монотонно убывает.

равенства Тогда и из утверждения 10 следует, что Из (5.4) и последнего неравенства утверждение доказано.

Д о к а з а т е л ь с т в о. Пусть n = H(B n |B 1 B 2... B n1 ). Из определения энтропии следует, что n 0. Из утверждения 26 следует, что последовательность n монотонно убывает. Тогда существует предел lim n 0.

Покажем методом индукции, что 8 имеем Известно, что предел среднего арифметического последовательности равен пределу последовательности, поэтому Из доказательства утверждения 27 видно, что последовательность (hn ), hn = Hn (P ) монотонно убывает (возможно нестрого) для любого стационарного источника.

З а д а ч а 31. Пусть A, P стационарный источник сообщений, побуквенное отображение : A B переводит слова в алфавите A в слова в алфавите B.

ционарным источником сообщений и справедливо неравенство H B, Q H A, P.

5.2. Энтропия марковского источника Как было доказано в § 4.2 марковская модель M с алфавитом A и множеством состояний V при фиксированным наборе параметров P определяет некоторый источник сообщений A, P. Кроме того, последовательность состояний автоматной модели можно рассматривать как некоторую марковскую цепь s(M, P ). Определённый указанным выше способом источник сообщений называют марковским1.

Определим энтропию в состоянии v V равенством Для значительного класса марковских источников имеется простая формула вычисления энтропии.

У т в е р ж д е н и е 28. Пусть A, P марковский источник, определённый контекстной моделью M c набором параметров P, причём марковская цепь s(M, P ) является неразложимой и непериодической. Тогда энтропия источника A, P существует и удовлетворяет равенству где v стационарные вероятности марковской цепи s(M, P ).

Д о к а з а т е л ь с т в о. Марковский источник определяет распределения вероятностей на множествах An при всех натуральных n. Пусть события Bij определены Нередко марковскими называют только источники сообщений с контекстной или автоматной моделью.

также как и ранее, т. е. Bij множество слов, имеющих на j-м месте букву ai. Из свойств энтропии разбиения имеем равенства где Nj состоит из таких наборов (i1, i2,..., in1 ), что марковская модель M переходит из входного состояния v1 в состояние vj, когда порождает слово ai1 ai2... ain1.

Тогда из определения марковского источника для переходных вероятностей марковской цепи имеем равенство Кроме того, поскольку вероятность следующей буквы зависит только от текущего состояния, то H(B n |Bi11 Bi22... Bin1 ) = Hvj при (i1, i2,..., in1 ) Nj. Таким образом Тогда из равенства (5.5) имеем Из эргодической теоремы следует, что lim pj1 (n) = vj. Известно, что предел среднеn го арифметического последовательности равен пределу последовательности, поэтому lim pj1 (m) = vj. Из эргодической теоремы следует, что этот предел не зависит n n m= от выбора начального состояния. Тогда Определение энтропии источника можно записать следующим образом:

где функция n (x) = log P (x) рассматривается как случайная величина, определённая на множестве бесконечных последовательностей в алфавите A, которая принимает значение log P (w) на последовательностях, начинающихся со слова w An. Докажем, что для стационарного марковского источника последовательность (n ) сходится к энтропии источника не только в среднем, но и по вероятности.

У т в е р ж д е н и е 29. Пусть A, P марковский источник, определённый контекстной моделью M c набором параметров P, причём марковская цепь s(M, P ) является неразложимой и непериодической. Тогда log P (x) H(P ), Д о к а з а т е л ь с т в о. Докажем это утверждение вначале для источников Бернулли. Пусть ri (x) количество букв ai в слове x An. Рассмотрим набор случайных величин j (x):

Тогда математическое ожидание случайной величины j (x) удовлетворяет равенству Поскольку = j (x), дисперсия случайной величины j (x) удовлетворяет равенству Кроме того, ri (x) = j (x). По определению источника Бернулли случайные велиj= чины 1, 2,..., n независимы. Как следствие закона больших чисел получаем, что ri (x) Пусть V множество состояний марковского источника A, P. Если задано входное состояние, то для любого слова x An однозначно определяется последовательность состояний V n, где буква xi порождается источником в состоянии i V, произведения, соответствующую буквам, порождённым в состоянии v V, тогда P (x) = Pv (x). Через rv (x) обозначим количество вхождений состояния v в послеvV довательность состояний, соответствующую слову x. Справедливы равенства Подслова слова x, состоящие из букв порождённых в состоянии v V можно рассматривать как слова, порождённые источником Бернулли с вероятностями P (ai |v).

Тогда по доказанному выше имеем rv1 log Pv1 Hv 0 при n, чего как видно из равенства (5.8) и утверждения 28 достаточно для завершения доказательства.

Из-за того, что в контекстной модели имеется выделенное начальное состояние, порождённый контекстной моделью источник оказывается нестационарным (конечно если модель имеет не менее двух состояний). Марковский источник с неразложимой и непериодической цепью состояний может быть преобразован в стационарный с теми же статистическими свойствами, если все состояния считать начальными и определить исходные вероятности состояний равными стационарным вероятностям. Такие источники сообщений будем называть стационарными марковскими источниками.

З а д а ч а 32. Пусть задан некоторый стационарный марковский источник A, P.

Упорядочим слова w An по убыванию вероятностей и будем отбирать наиболее вероятные до тех пор, пока впервые суммарная вероятность отобранных цепочек не превзойдёт некоторый заранее заданный уровень, 0 < < 1. Число отобранных цепочек обозначим через M (n). Докажите, что для любого, 0 < < 1 существует один и тот же lim log M (n) = H( A, P ).

З а д а ч а 33. Пусть A, P марковский источник первого порядка, т. е. вероятность следующей буквы зависит только от предыдущей буквы сообщения. Определим матрицу M размера |A| |A|, в которой M [i, j] = 1 при P (ai |aj ) > 0 и M [i, j] = при P (ai |aj ) = 0. Докажите, что энтропия H( A, P ) не превосходит логарифма перронова корня матрицы M.

5.3. Энтропия источника Бернулли Источником Бернулли называется марковский источник с единственным состоянием. Последовательности букв, порождаемые этим источником, соответствуют последовательностям испытаний Бернулли, когда вероятности всех испытаний одинаково распределены и независимы. Ясно, что любой источник Бернулли является стационарным. Для энтропии H(P ) источника Бернулли и эмпирической энтропии H(x) слова x A справедливы следующие утверждения.

У т в е р ж д е н и е 30. Пусть A, P источник Бернулли. Тогда энтропия источника A, P существует и удовлетворяет равенству для любых натуральных n.

Утверждение 30 непосредственно вытекает из утверждения 9 и определения энтропии источника сообщений.

У т в е р ж д е н и е 31. Для источника Бернулли A, P справедливо неравенство ri количество букв ai в слове x, i = 1,..., k. Тогда из утверждения 6 следует неравенство Следовательно, из утверждения 30 имеем Чтобы доказать неравенство в другую сторону pассмотрим набор случайных веi личин j (x):

Имеем ri (x) = j (x). По определению источника Бернулли A, P случайные веj= личины 1, 2,..., n независимы. Тогда из равенств (5.6), (5.7) и свойств (A1, A3, с.13) получаем Откуда имеем Из равенств (5.9) и утверждения 30 получаем Тогда Докажем неравенство Из равенств (5.9) следует, что Функция log t выпукла вверх, тогда из неравенства Йенсена, (5.10) и (5.11) имеем Применив неравенство ln(1 + t) t, получаем искомое неравенство.

В утверждении 31 доказано, что эмпирическая энтропия H(x) сходится к энтропии источника Бернулли в среднем. Теперь докажем, что сходимость имеет место и по вероятности.

при n.

Dri (x) = n(P (ai ) (P (ai ))2 ). Из неравенства Чебышёва (A4, с.13) имеем для любого натурального n и > 0.

Без ограничения общности можно считать, что min P (ai ) > 0, поскольку слоi ва, которые содержат буквы с нулевой вероятностью, сами имеют нулевую вероятность. Пусть x An таково, что для любого i = 1,..., k справедливо неравенство | rin P (ai )| <. Из теоремы Лагранжа о приращениях вытекает неравенство | log rin log P (ai )| < C ln 2, где C = min(P (ai ) ). Тогда емое следует из неравенства (5.12).

Утверждения 31 и 32 можно обобщить на произвольные стационарные марковские источники, определив эмпирическую энтропию слова относительно марковской модели как log P (x), где P (x) эмпирическая энтропия слова в этой модели.

Глава 6.

Кодирование Пусть A некоторый конечный алфавит. Кодированием называется инъективное отображение f : A {0, 1}. Подразумевается, что обратная функция f декодирование должна быть частично вычислимой, т. е. является программой.

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

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

6.1. Префиксные и разделимые множества слов Префиксом слова w называется произвольное начало u слова w, т. е. если w = uv, то u префикс слова w. Кодирование f называется префиксным, если из того, что кодовое слово f (u) является префиксом кодового слова f (w) следует, что и слово u является префиксом слова w. Свойство префиксности обеспечивает возможность декодирования кодового слова по частям: если мы декодировали некий префикс слова f (w) как слово u, то мы можем быть уверены, что слово u является началом закодированного слова w. Свойства отображения f быть префиксным достаточно для того, чтобы отображение являлось инъективным, так как из равенства f (u) = f (v) следует, что слова u и v являются префиксами друг друга и, следовательно, совпадают.

Множество D A называется префиксным, если для любой пары слов u, v D ни одно из них не является префиксом другого. Нетрудно видеть, что если f префиксное кодирование, то множества f (An ) являются префиксными для каждого натурального n. Кодирование f будем называть префиксным в сильном смысле если множество кодовых слов f (A ) префиксное.

Множество D A называется разделимым (однозначно декодируемым), если любая последовательность записанных подряд слов из D разделяется на слова из D единственным образом. Т. е. из равенства w1 w2... wm = w1 w2... wn при wi, wi D следует, что n = m и wi = wi при i = 1,..., n. Нетрудно видеть, что префиксное множество является разделимым.

Пусть : A {0, 1} некоторое отображение. Определим отображение f : A {0, 1} равенством Непосредственно из определений имеем У т в е р ж д е н и е 33. Отображение f, определённое формулой (6.1), является кодированием тогда и только тогда, когда (A) разделимое множество.

У т в е р ж д е н и е 34. Отображение f, определённое формулой (6.1), является префиксным кодированием тогда и только тогда, когда (A) префиксное множество.

Д о к а з а т е л ь с т в о. Необходимость (). Пусть (A) не префиксное множество. Тогда найдутся такие буквы ai1, ai2 A, что кодовое слово (ai1 ) = f (ai1 ) является префиксом кодового слова (ai2 ) = f (ai2 ). Противоречие.

Достаточность (). Пусть отображение f не обладает свойством префиксности, т. е. некоторое кодовое слово f (x1... xm ) является префиксом слова f (y1... yn ) или наоборот. Пусть xk первая из букв слова x1... xm, не совпадающая с соответствующей буквой yk слова y1... yn. Тогда (xk ) префикс слова (yk ) или наоборот, но (xk ) = (yk ). Противоречие с префиксностью множества (A).

Кодирование f, определяемое формулой (6.1), называется побуквенным. Побуквенным кодированием будем называть также и отображение. Как видно из утверждения 34, построение побуквенного префиксного кодирования сводится к построению префиксного множества.

Рассмотрим некоторое двоичное дерево T. Вершины двоичного дерева T пометим двоичными словами (т. е. построим функцию : T {0, 1} ) по следующему правилу (см. рис. 4): корень дерева пометим пустым словом, если вершина t T уже помечена словом u, то её левого сына пометим словом u0, а правого u1. Вершины k-ичного дерева можно аналогичным образом пометить словами k-буквенного алфавита.

Обозначим через L(T ) множество листьев (висячих вершин) дерева T.

У т в е р ж д е н и е 35. Множество D {0, 1} является префиксным тогда и только тогда, когда D (L(T )) для некоторого двоичного дерева T.

Д о к а з а т е л ь с т в о. Необходимость (). Рассмотрим такое дерево T, что D (T ). Из определения отображения видно, что если вершина t помечена словом (t), то префиксами слова (t) помечены предки вершины t и только они.

Значит вершины дерева T, помеченные словами из множества D, не являются предками друг друга. Удалив из дерева T всех потомков вершин, помеченных словами из D, получим искомое дерево T.

Достаточность (). Поскольку листья дерева T не являются предками друг друга, то и соответствующие им слова не являются префиксами друг друга. Таким образом, (L(T )) является префиксным множеством.

Исследуем свойство разделимости множества D {0, 1}. Для каждого слова w D рассмотрим его всевозможные представления вида где слова wij D не совпадают со словом w при j = 1... k, слово не содержит слова из D в качестве суффикса, а слово не содержит слова из D в качестве префикса. В этом представлении число k может быть равным нулю, а слова и могут быть пустыми. Определим ориентированный граф GD, вершинами которого являются слова, из всевозможных представлений вида (6.2) слов w D, причём слова, соединены дугой, если они содержатся в одном из представлений вида (6.2).

Т е о р е м а 6. (Марков) Множество D {0, 1} является разделимым тогда и только тогда, когда граф GD не содержит контур, проходящий через вершину, соответствующую пустому слову.

Доказательство.

Пометим каждую дугу (1, 2 ) в графе GD словом W12 D, если имеется представление w = 1 W12 2 вида (6.2) для некоторого слова w D. В ориентированном графе GD имеется контур тогда и только тогда, когда существует слово W {0, 1}, допускающее представление Нетрудно видеть, что слово W может быть представлено в виде двух различных конкатенаций слов из множества D. Первая конкатенация составлена из слов W01, 1 W12 2, W23 и т. д., вторая из слов W01 1, W12, 2 W23 3 и т. д.

Предположим множество D является неразделимым. Рассмотрим кратчайшее слово, для которого имеются два представления w = wi1... wik = wj1... wjk, где слова wit, wjs D. Пусть |wi1 | < |wj1 |, тогда wi1 u = wj1 и в графе GD имеется цикл Из предыдущего утверждения немедленно следует, что для проверки разделимости конечного множества слов достаточно проделать конечное число вычислений.

З а д а ч а 34. Пусть li длина i-го слова в неразделимом множестве D {0, 1}, |D| = n. Пусть K = max k по всевозможным представлениям вида (6.2) слов из D. Тогда найдётся конкатенация, состоящая не более чем из (K + 1)(l1 +...

+ln n + 2)/2 слов из D, которая имеет представление в виде другой конкатенации слов из D.

Т е о р е м а 7. (неравенство Крафта Макмиллана) D. Тогда справедливо неравенство 2) Если выполнено неравенство (6.3), то найдётся префиксное множество D {0, 1} с длинами кодовых слов l1, l2,..., lk.

Доказательство.

1) Пусть S(n, t) количество различных упорядоченных наборов по n слов из множества D, суммарная длина которых равняется t. Из определения разделимости множества видно, что различным упорядоченным наборам (w1,..., wn ) Dn соответствуют различные слова W = w1... wn, |W | = t. Поэтому S(n, t) 2t. Кроме того, S(n, t) = 0 при t > N = n max li.

Следовательно xn = O(n) при n. Поскольку это асимптотическое равенство возможно только при |x| 1, получаем требуемое неравенство (6.3).

2) Будем считать, что l1 l2 · · · lk. Достаточно рассмотреть случай, когда в ется целым и, добавив к набору длин l1, l2,..., lk ещё m чисел lk, получим равенство 2li + m2lk = 1 для расширенного набора.

i= Проведём доказательство методом индукции по k. При k = 2 имеем l1 = l2 = и D = {0, 1}. Пусть неравенство (6.3) доказано для k слагаемых. Поскольку мы рассматриваем случай, когда последние два слагаемых равны: lk = lk+1. В противном случае (lk < lk+1 ) после умножения на 2lk получим в равенстве (6.4) целое число справа и дробное слева.

Рассмотрим набор длин l1, l2,..., lk1, lk 1. Поскольку для этого набора справедливо равенство (6.4), по предположению индукции найдётся префиксное множество D с соответствующими длинами слов. Пусть u D и |u| = lk 1. Тогда определим D = (D \ {u}) {u0, u1}. Очевидно, что D префиксное множество и состоит из слов требуемой длины.

D. Докажите неравенство 6.2. Кодирование натуральных чисел Каждому натуральному числу можно поставить в соответствие его двоичную запись Bin(n) = k k1... 1, где n = Нетрудно видеть, что k = log n + 1. Стандартная двоичная запись не является префиксной, поэтому из слитно записанной последовательности двоичных записей чисел нельзя восстановить последовательность чисел.

Ниже будет построено префиксное кодирование натурального ряда N. Поскольку двоичная запись любого натурального числа начинается с 1, первый символ слова Bin(n) не несёт информации. Определим Bin (n) как Bin(n) без первого символа, т. е.

Bin(n) = 1Bin (n) для любого n N. Пусть k = |Bin(n)|. Определим кодирование PBin натурального ряда формулой П р и м е р 8. PBin(1) = 1, PBin(2) = 0 10 0, PBin(3) = 0 10 1, PBin(10) = 00 100 010.

Если нужно кодировать также и число 0, то определяют PBin(0) = 10, PBin(1) = 11, а остальные числа в соответствии с формулой (6.5). Кодирование PBin было предложено П. Элайесом.

1) Кодирование PBin является префиксным.

2) |PBin(n)| log n + 2 log log(n + 1) + 2.

Доказательство.

1) Пусть слово PBin(n1 ) есть префикс слова PBin(n2 ) и ki = |Bin(ni )|, i = 1, 2.

Поскольку двоичные слова Bin(k1 ) и Bin(k2 ) начинаются с символа 1, число нулей в начале слова PBin(n1 ) должно совпадать с числом нулей в начале слова PBin(n2 ), т. е. |Bin(k1 )| = |Bin(k2 )|. Так как слово Bin(k1 ) префикс слова Bin(k2 ), Bin(k1 ) = = Bin(k2 ). Тогда k1 = k2 и |Bin(n1 )| = |Bin(n2 )|. А так как слово Bin(n1 ) есть префикс слова Bin(n2 ), то Bin(n1 ) = Bin(n2 ).

2) По определению (6.5) имеем Из равенств k = log n + 1 = |Bin(n)| и |Bin (k)| = log k и неравенства log(1 + log n) 1 + log log(n + 1) при натуральных n получаем требуемое.

Следующее кодирование множества N{0} было предложено В. И. Левенштейном.

Введем обозначение (n) = |Bin (n)| и k (n) = (k1 (n)), где 1 (n) = (n). Если k (n) = 0 и k1 (n) > 0, то определим П р и м е р 9. Lev(0) = 0, Lev(1) = 10, Lev(5) = 1110 0 01, Lev(62) = 11110 0 01 11110.

Преобразование двоичной записи числа n в код Lev(n) осуществляется достаточно просто, поскольку (n) = |Bin (n)|, 2 (n) = |Bin ((n))| и так далее. Декодирование кода Lev(n) производится в обратном порядке, причем число итераций k равняется числу единиц в кодовом слове до первого нуля.

1) Кодирование Lev является префиксным.

2) Для любого натурального k справедливо асимптотическое равенство при n.

Доказательство утверждения 37 аналогично доказательству утверждения 36.

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

при n. Тогда множество B(N) не разделимое.

Д о к а з а т е л ь с т в о. Пусть B(N) разделимое множество. Без ограничения общности будем считать |B(n)| |B(n + 1)| для любого натурального n. Из рального n, т. е. ряд довательность n монотонна. Применяя этот признак k раз к ряду (1/(n log n · · · (log log... log n)(log log... log n)+o(1) ), получаем, что ряд 2n(1+o(1)) необходимому признаку сходимости ряда.

6.3. Теорема кодирования Шеннона Пусть заданы некоторый источник сообщений A, P и кодирование f : A {0, 1}. Стоимостью кодирования f источника A, P будем называть Стоимость кодирования Cn (f, P ) равна средней длине кодового слова, вычисленной по всем исходным словам длины n.

Разность Rn (f, P ) = Cn (f, P ) Hn (P ) называется избыточностью. Величину r(f, P ) = lim n Rn (f, P ) будем называть предельной избыточностью кодирования f.

1) Для любого источника сообщений A, P и любого префиксного кодирования f избыточность неотрицательна, т. е. Rn (f, P ) 0.

2) Для любого источника сообщений A, P найдётся такое префиксное в сильном смысле кодирование f, что r(f, P ) = 0.

Доказательство.