НА САМОСТОЯТЕЛЬНУЮ РАБОТУ

Вступ

Література.

Час – 2 год.

Навчальні питання

Лекція 6. Дискретне джерело повідомлень

1.... Дискретна послідовність символів. 1

2.... Послідовні наближення до англійської мови.. 4

3.... Марковські процеси.. 6

4.... Ергодичні і змішані джерела. 8

1. Reprinted with corrections from The Bell System Technical Journal, Vol. 27, pp. 379–423, 623–656, July, October, 1948.

2. Дж. Пирс. Символы, сигналы, шумы. Закономерности и процессы передачи информации. Издательство «МИР», Москва, 1967.

3. К.Шеннон. Работы по теории информации и кибернетике. Издательство иностранной литературы, Москва, 1963.

Для исследования свойств информации источника сообщений необходимо создание удовлетворительной математической модели. Клод Шеннон предложил несколько решений, позволяющих математически описывать источник сообщений, и соответственно имитировать реальный поток текстовых сообщений. Рассмотрим его рассуждения на этот счет. В лекции в основном приводится прямой перевод [3], который был представлен в [1].

1. Дискретна послідовність символів

Как следует математически описывать источник сообщений и какое количество информации, измеряемое числом битов в секунду, создается данным источником?

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

Буква встречается чаще, чем ; последовательность чаще, чем , и т. д. Наличие такой структуры позволяет получить некоторую экономию времени (или пропускной способности канала) с помощью подходящего кодирования последовательностей сообщений в последовательности сигналов.

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

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

1. Печатные тексты на таких языках, как английский, немецкий, китайский.

2. Непрерывные источники сообщений, которые превращены в дискретные с помощью некоторого процесса квантования.

3. Математические случаи, когда просто определяется абстрактно некоторый вероятностный процесс, который порождает последовательность символов.

Приведем следующие примеры источников последнего типа:

A) пусть имеются пять букв , каждая из которых выбирается с вероятностью 0,2 независимо от результатов предыдущих выборов. Это привело бы к последовательностям, типичным примером которых является следующая последовательность:

Этот пример был построен при помощи таблицы случайных чисел.

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

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

Другой эквивалентный способ задания этой структуры заключается в том, чтобы задать вероятности «диграмм» (двухбуквенных сочетаний) , т.е. относительные частоты диграмм . Частоты букв (вероятности буквы ), условные вероятности и вероятности диаграмм связаны следующими соотношениями:

В качестве примера предположим, что имеются три буквы с таблицами вероятностей

Типичное сообщение от такого источника имеет вид

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

В общем случае -грамм (сочетаний из букв) для задания статистической структуры требуется множество n-граммных вероятностей или же множество условных вероятностей .

Г) Можно также определять вероятностные процессы, которые создают текст, состоящий из последовательности «слов». Предположим, что в языке имеются пять букв и 16 «слов» с вероятностями появления:

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

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

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

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

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

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

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

Для приближения третьего порядка вводится структура триграмм. Каждая буква выбирается с вероятностями, которые зависят от двух предыдущих букв.

Следует заметить, что использование вероятностных характеристик букв, например, английского языка, может иметь некоторые ограничения. В 1939 году Эрнест Винсент Райт опубликовал роман. На 267 страницах этой книги ни разу не была использована буква . Один абзац из этой книги:

Upon this basis I am going to show you how a bunch of bright young folks did find a champion; a man with boys and girls of his own; a man of so dominating and happy individuality that Youth is drawn to him as is a fly to a sugar bowl. It is a story about a small town. It is not a gossipy yarn; nor is it a dry, monotonous account, full of such customary "fill-ins" as "romantic moonlight casting murky shadows down a long, winding country road". Nor will it say anything about tinklings lulling distant folds; robins carolling at twilight, nor any "warm glow of lamplight" from a cabin window. No. It is an account of up-and-doing activity; a vivid portrayal of Youth as it is today; and a practical discarding of that wornout notion that "a child don't know anything".

1. Послідовні наближення до англійської мови

Чтобы дать наглядную картину того, как эти последовательные приближения аппроксимируют естественный язык, ниже приводятся типичные последовательности букв для таких приближений к английскому языку. Во всех случаях использовался 27-буквенный «алфавит»(26 букв и пробел между буквами).

1. Приближение нулевого порядка (символы независимы и равновероятны):

.

Здесь слишком много букв и и явно недостаточно буквы и пробелов. Лучшее приближение к английскому тексту можно получить, выбирая буквы независимо одна от другой, но выбирая букву намного чаще, чем буквы или . Это можно было бы сделать, положив в шляпу много карточек с буквой и мало карточек с буквами . Поскольку вероятность того, что вытащенной буквой окажется , должна быть равна 0,13, то из каждой сотни карточек, положенных в шляпу, на тринадцати должна стоять буква . Вероятность того, что вытащенной буквой окажется , должна быть равна 0,02, поэтому из каждой сотни карточек, положенных в шляпу, на двух должна стоять буква , и т. д.

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

2. Приближение первого порядка (символы независимы, но с частотами, свойственными английскому тексту):

В английском языке нет ни одной пары букв, начинающейся с , кроме сочетания . Вероятность того, что встретится или , равна нулю. Хотя вероятность появления не равна нулю, она так мала, что ее нет в известных таблицах. С другой стороны, вероятность появления сочетания равна 0,037, вероятность появления — 0,010, а вероятность появления — 0,006. Эти вероятности имеют следующий смысл. Пусть в тексте содержится 10 001 буква. Тогда первая и вторая буквы, вторая и третья и т. д. дадут 10 000 последовательных буквенных пар. Определенное количество раз встретится сочетание . Предположим, что оно встретилось 370 раз. Если разделить это число на общее число пар, которое по предположению равно 10 000, то получим вероятность того, что при случайном выборе в тексте появится сочетание , т. е. эта вероятность равна 370/10 000, или 0,037.

Усердные шифровальщики составили таблицы вероятностей появления в английском тексте групп из двух букв, так называемых диграмм. Покажем, как можно было бы построить буквенную последовательность, используя те же вероятности появления диграмм, что и в английском тексте. Для этого возьмем 27 шляп: из них 26 для диграмм, начинающихся с каждой из букв алфавита, и одну для диграмм, начинающихся с пробела. Затем положим в шляпы карточки с написанными на них диграммами в соответствии с вероятностью их появления, т. е. каждая 1000 карточек должна содержать 37 диграмм , 6 диграмм и т. д.

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

Предположим, что мы хотим найти все буквы в тексте и для этого просматриваем его букву за буквой. Будем выписывать на карточки и класть в одну шляпу все диграммы, начинающиеся с буквы . При этом окажется, что таких диграмм ровно столько, сколько букв попалось в тексте. А доля, которую эти диграммы составляют от общего количества диграмм, есть вероятность появления буквы в тексте, т. е. 0,10. Обозначим эту вероятность ; тогда можно записать .

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

Далее, если общее число букв в тексте 1001 и, следовательно, количество последовательных диграмм 1000, то диграмма ТН встретится 37 раз, и поэтому вероятность ее появления мы обозначим р (Т, Н), и она равна р (Т, Н) = 0,037.

Теперь ясно, что 100 диграмм, или 0,10 часть всего их количества, будут начинаться с буквы Т и они попадут, следовательно, в шляпу Т, а 37 из них будут диграммы ТН. Таким образом, доля диграмм ТН от всего количества диграмм, начинающихся с буквы Т, будет равна 37/100, или 0,37. Соответственно мы говорим о вероятности Р_т(Н) того, что диграмма, начинающаяся с буквы Т, будет ТН, т. е. P_т(Н) = 0,37; P_т(Н) — это условная вероятность появления буквы Н после буквы Т.

Вероятности появления диграмм можно использовать, чтобы построить текст, в котором и буквы, и диграммы появляются с той же частотой, что и в английском языке. Для этого вытащим наудачу карточку из любой шляпы и выпишем проставленные на ней буквы. Затем по второй букве первой диграммы определим шляпу, из которой нужно вытащить вторую карточку, и выпишем вторую букву второй диграммы. Затем по второй букве второй диграммы определим шляпу, из которой нужно вытащить третью, и т. д. Пробел можно считать буквой, так как имеется вполне определенная вероятность того, что после данной буквы будет пробел (окончание «слова»), а также имеется вполне определенная вероятность того, что после пробела будет стоять определенная буква (начало «слова»).

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

3. Приближение второго порядка (структура диграмм такая же, как в английском языке):

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

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

5. Приближение первого порядка на уровне слов. Вместо того чтобы продолжать процесс приближения с помощью структур тетраграмм n-грамм, легче и лучше сразу перейти к словарным единицам. Здесь слова выбираются независимо, но с соответствующими им частотами:

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

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

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

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

В примере 6 последовательности из четырех или более слов могут быть довольно легко вставлены в предложения без необычных или натянутых конструкций. Последовательность из десяти слов «attack on an English writer that the character of this» не является совершенно неприемлемой. Таким образом, оказывается, что достаточно сложный вероятностный процесс дает удовлетворительное представление дискретного источника.

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

Точно так же можно было бы построить и примеры 3, 4 и 5 , так как частоты диграмм, триграмм и отдельных слов известны, но мы использовали более простой эквивалентный метод. Например, чтобы построить пример 3, можно открыть книгу случайным образом и выбрать также случайно букву на странице. Эта буква записывается. Затем книга открывается на другой странице и читается до тех пор, пока не встречается записанная буква. Следующая за ней буква записывается. Затем на другой странице ищется эта последняя буква и записывается следующая за ней и так далее. Аналогичный процесс был использован для составления примеров 4, 5 и 6.

1. Марковські процеси

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

Нестрогое определение. Цепь Маркова — последовательность случайных событий с конечным или счётным числом исходов, характеризующаяся тем свойством, что, говоря нестрого, при фиксированном настоящем будущее независимо от прошлого. Названа в честь А. А. Маркова (старшего).

Строгое определение. Цепь Маркова с дискретным временем

Последовательность дискретных случайных величин называется простой цепью Маркова (с дискретным временем), если

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

Область значений случайных величин называется пространством состояний цепи, а номер — номером шага.