Кодирование стохастических контекстно-свободных языков Жильцова Лариса Павловна

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

В этой главе исследуются вопросы, связанные с двоичным кодированием стохастических языков. В качестве стоимости кодирования рассматривается математическое ожидание длины закодированного слова стохастического языка. Целью оптимального кодирования является минимизация стоимости кодирования. Понятие стоимости кодирования здесь существенно отличается от понятия, рассматриваемого К.Шенноном в [36]. Основное отличие состоит в том, что мы определяем стоимость кодирования на множестве всех слов языка. Поэтому на величину стоимости кодирования влияют как короткие, так и длинные сообщения. Напомним, что в [36] стоимость кодирования определялась на множестве слов "большой"длины t при t — со. Результаты главы можно разбить на две части. К первой части относятся результаты для произвольных стохастических языков, то есть языков, на множестве слов которых задано распределение вероятностей. Здесь исследуется зависимость стоимости оптимального кодирования произвольного стохастического языка от его энтропии. Для произвольного языка с конечным значением энтропии установлены верхняя и нижняя неулучшаемые оценки стоимости оптимального кодирования, зависящие только от энтропии. Показано, что стоимость оптимального кодирования произвольного стохастического языка имеет конечное значение тогда и только тогда, когда конечное значение имеет энтропия языка. Ко второй части относятся результаты для стохастических КС-языков с однозначным выводом. Для произвольного стохастического КС-языка с однозначным выводом найдено необходимое и достаточное условие существования конечных значений стоимости оптимального кодирования и энтропии. Показано, что стоимость оптимального кодирования может принимать любое значение между нижней и верхней границами, включая нижнюю границу. По произвольной стохастической КС-грамматике с однозначным выводом построена система линейных уравнений, решение которой дает значение энтропии языка, порождаемого грамматикой. Тем самым указан эффективный метод вычисления энтропии, если ее значение конечно. Пусть = (L,P) - стохастический язык. Кодированием языка будем называть инъективное отображение / : L — {0,1}+. Для а L последовательность f(a) будем называть кодом слова а. Через F(L) обозначим класс всех инъективных отображений из L в {0,1}+. Пусть / Є F{L). Величину назовем стоимостью кодирования f (здесь x \ - длина слова x). Если существует конечное значение С(,/). будем сокращенно записывать Величину будем называть стоимостью оптимального кодирования, а кодирование /о, для которого будем называть оптимальным. Оптимальное кодирование для любого стохастического языка существует и состоит в упорядочении слов в соответствии с невозрастанием их вероятностей и кодировании их в алфавите {0; 1} сначала словами длины 1, потом словами длины 2, и т.д.

Под энтропией стохастического языка = (L. Р) мы будем понимать величину (логарифм здесь и везде далее берется но основанию 2). Если существует конечное значение Н(С), будем писать Отметим, что если Н(С) конечна, то, так как ряд положительный, он абсолютно сходится, поэтому в нем можно переставлять слагаемые [33]. Следовательно, неважно, как упорядочены слова языка L при вычислении Н(С). 2.2. Соотношение между стоимостью оптимального кодирования и энтропией для произвольного стохастического языка Теорема 2.2.1. а) Пуст,ь С = (L, Р) - произвольный бесконечный стохастический язык, для которого существует конечное значение Н{). Тогда сто имость оптимального кодирования Со(С) имеет конечное значение и удовлетворяет неравенствам б) Пусть L = {с !, е 2,...}— произвольный бесконечный язык. Существует распределение вероятностей Р — {р\,р }? такое, что для стохастического языка С = {(с ,р ) : г = 1,2,...} энтропия Н(С) имеет конечное значение и выполняется равенство в) Пусть L = {ai,Qi2, }— произвольный бесконечный язык. Для любого є О существует распределение вероятностей Р = {рі{є),Р2{є), }? такое, что для стохастического языка С = {(аг,Рі(є)) : і = 1, 2,...} выполняется неравенство Доказательство этой теоремы было получено совместно с А.А.Марковым. Доказательство. а) Пусть L — {di,a2, ..}, Р = {pi,P2, } и, для определенности, Р\ Р2 , где pj - вероятность слова аг. Рассмотрим последовательность чисел D = (d\, d , , d{, ), в которой di = [—logpi] для любого г (здесь \х] - ближайшее целое сверху).

Последовательность D удовлетворяет неравенству Мак-Миллана [39]: Нетрудно показать, что существует бесконечный префиксный код /і с заданным набором длин D кодов слов из L. Для этого достаточно применить без каких-либо изменений метод построения префиксного кода по заданному конечному набору длин, описанный в [36]. Оценим стоимость кодирования для f\ : (здесь г = [— log(pi)] + log(pj) и, следовательно, є% 1 для любого г). Так как CQ(JC) С (С, fi), то CQ{C) также конечна и CQ(C) Н(С) + 1. Докажем неравенство \Н() CQ{C). Длина оптимального кода для слова сц, равна [log(z + 1)J. Рассмотрим разность: Используя неравенство log a: (x — 1) loge. получим: Оценим сумму: Окончательно получаем, что Н(С) - 2 С0{) 0, откуда следует \Н(С) С0{). б) Рассмотрим произвольный бесконечный язык L = {ai, о ,...} и распределение ВерОЯТНОСТеЙ Р = (р$,р 2, -Р , - - ) , Ще р = ю +В] для г = 1, 2,.... Нетрудно показать, что и Р действительно является распределением вероятностей. Для стохастического языка Вычислим стоимость оптимального кодирования: следовательно, с) Рассмотрим произвольный бесконечный язык L = {сні, С 2, } и распределение вероятностей Р , построенное по Р из пункта (б), для которого для г 1, где 0 5 1. Для стохастического языка С& — {(а р-) : г = 1,2,...} нетрудно показать, что энтропия Н($) конечна, и, следовательно, Со() также конечна. Действительно, (здесь - язык из (б) и Н(6) = —8 log 8 -(1-(5)- log(l — 8)). Оценим стоимость оптимального кодирования: при 8 —- 0, и, следовательно, существует (5 , удовлетворяющее условию: 1 — 3 5 — Н(8 ) 1 — є. В качестве возьмем - Для -е выполняется неравенство Теорема доказана. Теорема 2.2.2. Пусть С = (L, Р) - произвольный бесконечный стохастический язык, для которого CQ(C) имеет конечное значение. Тогда Н(С) также имеет конечное значение. Доказательство. Пусть слова из L упорядочены в порядке невозрастания их вероятностей, т.е. L = {&!, а2,...,ап...} и р(сц) p(ai+i) для любого г. Рассмотрим частичные суммы Покажем, что существует константа С, для которой Sn С для любого п. Рассмотрим разность Вторая сумма не превосходит 2. Для оценки первой суммы применим неравенство logx loge При п — оо сумма X Li сходится к конечному пределу, обозначим его через S1. Окончательно получаем, что для любого п. Отсюда следует, что имеет конечное значение. Теорема доказана. Следствие 2.2.1. Пусть - произвольный стохастический язык. Тогда стоимость оптимального кодирования CQ{) имеет конечное значение тогда и только тогда, когда конечное значение имеет энтропия Н{). В доказательстве теоремы 2.2.1 мы в действительности использовали свойства различных вероятностных распределений. Мы не накладывали ограничений на распределение вероятностей, которое может зависеть от синтаксиса языка. Рассмотрим класс КС-языков с однозначным выводом. В этом случае вероятность слова определяется как произведение вероятностей правил грамматики, образующих левый вывод слова. Поэтому значение вероятности слова определяется словом.

Моменты

Пусть Н = (i,... ,&)— случайный вектор, а = (а ,..., а ) — фиксированный вектор с целочисленными неотрицательными компонентами и а = а\ + ... + cxk- Обозначим где х — х(х — 1)... (х — а -\- 1). Математическое ожидание MHfQ l называется [31] факториальным, моментом Н порядка а или, более подробно, а -моментом Н. Пусть х ;(/:) - число нетерминалов Л? в дереве вывода из Di на ярусе t. Через Mla,(t) обозначим Примем специальные обозначения для моментов первых четырех порядков. Факториальные моменты первого порядка будем обозначать через oJj{t). Для факториальных моментов второго порядка введем обозначения bljk(i). Таким образом, b J3(t) = Mxl {t){x%j{t) — 1) и Ат( ) = Мх)(ї)х1(ї) ПРИ 3 7 к- Для факториальных моментов Третьего И ЧеТВерТОГО ПОРЯДКОВ Введем Обозначения Cljkm(t) И fjkml(t) соответственно. Нетрудно заметить, что агА1) - элементы матрицы первых моментов, для которых мы ввели ранее обозначения а1„. Будем также применять далее обозначения Ьг-к для Ъг-к{1). Нас интересуют оценки для первых четырех моментов в случае, когда перронов корень г меньше единицы. Рассмотрим матрицу A(t) = \\aUt)\\. Известно [31], что A(t) = At. Для А1 имеет место представление [3]: где Л; — корни минимального многочлена (Л) матрицы А (I = 1,... , s), s к, ті — кратность корня А/ для минимального многочлена, (Xj) — n-я производная по Л; от Xj, матрицы Zij вполне определяются заданием матрицы Л и не зависят от t. Используем представление (3.2.1) для вычисления вторых моментов. Так как матрица А неразложима и неотрицательна, по теореме Фробениуса [3] ее перронов корень г — простой. Следовательно, элемент CLlj{t) можно также представить в виде Представление ЩУ3ГЬ для определяющего слагаемого в (3.2.2) доказано, например, в [31]. В качестве г\ может быть выбрано любое число, удовлетворяющее условиям: Г\ г и Гі Го, где Го — модуль максимального по модулю среди собственных корней, отличных от г. Вынесем за скобку множитель г1 в (3.2.2). Тогда Для вторых моментов известна следующая формула из [31]: Подставим в (3.2.4) представление (3.2.3) для первых моментов: Проведем несложные преобразования в полученном равенстве: Введем обозначения Оценим сначала S? )- Так как ( — г) — 0{rf T), то где Го = max{r. г2} и, следовательно, Го 1. Очевидно, ЧТО (wmVj + Cmj(r - 1)) = 0(1) и (wsvn + Сзп(т - 1)) = 0(1).

Поэтому сходится, так как мажорируется геометрической прогрессией со знаменателем г. Обозначим его сумму через hjn(t). Поэтому и bjn(t) можно представить в следующем виде: Используя результаты из [31], мы можем записать формулу для третьего момента: В этой формуле zl- {т — 1) состоит из конечного числа слагаемых двух типов. Слагаемые первого типа имеют вид: Са (т — 1)а(т — 1)а -(т — 1) для некоторых w, т, /, где С — некоторая константа, зависящая от слагаемого; слагаемые второго типа имеют вид: Са1Лт — 1)6 (г — 1) для некоторых l,m и константы С. Поэтому вычисление Cj (t) сводится к вычислению конечного числа сумм вида или вида для некоторых значений /. т, и;. Оценим Si(t) и 2 ), используя оценки dj(t) — 0{гь). 6г7() = 0(rl). Получим, что S\{t) = 0{rf) и Аналогичный результат может быть получен и для четвертого момента. Для него известна формула [31]: для некоторых значений іі,І2ііз,Ч- Используя оценки для первых трех моментов и проведя элементарные преобразования в (3.2.7), получаем оценку по порядку для четвертого момента: 3.3. Закономерности применения правил грамматики в докритическом случае Пусть С — язык, порожденный стохастической КС-грамматикой G. Будем полагать, как и ранее, что аксиомой исходной грамматики G является нетерминал А\. Пусть D\ — множество деревьев вывода для слов языка L. Рассмотрим D\ — множество деревьев из D\ высоты t. Через Mi(t,r) обозначим условное математическое ожидание числа вершин на ярусе т, помеченных нетерминалом Аг: в деревьях вывода высоты t. Теорема 3.3.1. Пусть G -- стохастическая КС-грамматика с неразложимой непериодической матрицей первых моментов, для которой перронов корень меньше единицы, и D\ мноэюество деревьев вывода высоты t. Тогда для любого і Є {1,..., к} при т— oow —т— оо выполняется асимптотическое равенство Mi(t,r) игиг + ВІ, в котором щ и Vi — і—е компоненты правого и левого собственных векторов для перронова корня г соответственно, ВІ = Хл=ім№ и 9и — константы, определяемые формулой (3.2.6). Доказательство. Мы можем записать следующую формулу для Mt(t, т) : где Zi(d, т) - число вершин на ярусе г дерева d, помеченных Д, и p(d) -вероятность дерева d в исходной грамматике. Рассмотрим неотрицательный целочисленный вектор X — (xi,..., Xk), который будем называть далее вектором нетерминалов. Используя вектор X, мы можем записать, что где Ах - вклад в математическое ожидание тех деревьев вывода из D\, которые на ярусе т содержат х} вершин, помеченных нетерминалом Aj (j = 1,..., к). Множество таких деревьев обозначим через DX(T). Пусть d Є DX(T). Выделим в d поддерево do и последовательность поддеревьев (di, d-2,... dm), где m = Yli=i xi- Поддерево d0 получено из d удалением всех вершин на ярусах т+1,т + 2, ...Ли инцидентных им дуг. Последовательность (d\, G?2; dm) образуют все поддеревья, корни которых расположены на ярусе г дерева d. При этом корни поддеревьев di, с?2, - - - dm расположены в дереве d последовательно в порядке обхода вершин яруса г слева направо, и каждое дерево di (I = 1,...,m) содержит все дуги и вершины дерева d, лежащие на путях от корня di к листьям дерева d. Выделим в DX{T) множество деревьев, имеющих в качестве поддерева do одно и то же дерево. Обозначим это множество через DQ. Нетрудно понять, что где функция Qi{n) определена в разделе 3.1 и ее значение равно суммарной вероятности деревьев из множества D/, высота которых больше п, и, следовательно, (1 — Qi{n)) - это суммарная вероятность деревьев из Di, высота которых не превосходит п. Обозначим через 5\{Х) выражение П/=і(1 Qi(t r))Xl и через (Х) — выражение ГЬ=і(1 Qi{t — т — 1))Х;- В (3.3.1) величина p(do) 5\{Х) есть суммарная вероятность деревьев, определяемых поддеревом do, высота которых не превосходит t, так как каждое поддерево с корнем на ярусе т имеет высоту, не превосходящую (t-r).

Вторая величина p(do) (52(X) есть суммарная вероятность деревьев, определяемых поддеревом do, высота которых не превосходит (t — T — 1). Разность этих величин равна, очевидно, суммарной вероятности деревьев высоты t, определяемых деревом do, и значение ді(Х) — 62(Х) не зависит от порядка следования вершин на ярусе т, помеченных нетерминалами. Таким образом, где суммирование ведется по всем возможным поддеревьям do деревьев вывода из D -(r). Для каждой вершины, помеченной некоторым нетерминалом Ai, суммарная вероятность возможных деревьев с корнем в этой вершине и листьями, помеченными только терминалами, равна P(D{). Легко показать, что -Р(Д) = 1 для любого I ввиду согласованности исходной грамматики G. Поэтому величина Yld Р( о) равна вероятности деревьев вывода из D\. имеющих xi вершин на ярусе г, помеченных нетерминалом Ai (/ = 1,..., к): где DX{T) — множество деревьев из D\, имеющих Xj вершин на ярусе т, помеченных Aj (j = Будем обозначать J2deDx(T)P(d) чеРез рх(т). Таким образом, В разделе 3.1 величина (6і(Х) — 52(Х)) обозначена через Rx(t — т). Применим лемму 3.1.4 для представления Rx(t — т). Получим, что Отдельно вычислим 5i = Ylx opx{T) x&i и S2 = J2x o Рх{т) хг xi -Фх -г). Используя первые и вторые моменты, мы можем записать, что Si = Учитывая оценку из леммы 3.1.4 для ipx{n) и используя первые три момента, получим нижнюю и верхнюю оценки для S2 Применяя оценки для первых трех моментов, получим, что S2 —с-г2т, где с — некоторая положительная константа. С другой стороны, Так как Si = tfi(T) при і I vi Si = Ь (т) + а}(т), то, с учетом оценок для моментов, получаем, что Раскрывая моменты и используя лемму 3.1.2, после несложных преобразований получим, что Отсюда следует, что мг(г,т) год + д, где Д = J2i=iui9u-Теорема доказана. Выражение для Вг можно несколько упростить, если учесть, что U = (щ,..., щ) - правый собственный вектор. Применяя представление (3.2.6) для дц. получаем, что Пусть Tij — произвольное правило грамматики G. Через s\ обозначим число нетерминалов Ai в правой части правила Т{3. Условное математическое ожидание числа применений правила Гц в деревьях вывода высоты t на ярусе г будем обозначать через Mij(t,r). Пусть D\ - множество деревьев вывода высоты t для слов языка, порождаемого стохастической КС-грамматикой с неразложимой и непериодической матрицей первых моментов, для которой перронов корень меньше единицы.

Нижняя оценка стоимости кодирования

В настоящей главе рассматриваются вопросы экономного кодирования слов языка, порождаемого стохастической КС-грамматикой с однозначным выводом (в КС-грамматике с однозначным выводом любое слово порождаемого языка имеет единственное дерево вывода). При этом рассматривается случай, когда матрица первых моментов неразложима, непериодична, и ее перронов корень строго меньше единицы (докритический случай). Постановка задачи кодирования здесь аналогична той, которую исследовал К.Шеннон для конечного эргодического источника [36]. Задача кодирования рассматривается на множестве слов большой длины. В качестве такого множества берется множество слов стохастического КС-языка, каждому из которых соответствует дерево вывода высоты t при t — оо. Мерой эффективности кодирования является его стоимость, или число двоичных разрядов, используемых для кодирования одной буквы слова. На основе установленных в главе 3 закономерностей в деревьях вывода получена точная нижняя оценка стоимости двоичного кодирования. Построен также алгоритм асимптотически оптимального кодирования, сравнимый по сложности с алгоритмом кодирования Шеннона из [36]. В основе построенного алгоритма лежит "блочное"кодирование деревьев вывода, и блоком является поддерево дерева вывода, имеющее фиксированную высоту. Полученные в настоящей главе результаты можно рассматривать как обобщение результатов К.Шеннона на класс рассматриваемых КС-языков. 4.1. Определение стоимости кодирования Пусть С = (L.P) - стохастический КС-язык с однозначным выводом. Кодированием языка С будем называть инъективное отображение Через 1} обозначим множество таких слов из L, что дерево вывода каждого слова имеет высоту t. Для а Є V через pt(ot) обозначим условную вероятность появления слова а, т.е. Pt(oc) = рг[}\ В силу однозначности вывода Стоимостью кодирования f назовем величину (здесь \х\ -длина последовательности х). Корректность определения С(, /) нуждается в обосновании, так как предел может не существовать. Величина С(, /) характеризует число двоичных разрядов, приходящихся на кодирование одного символа слова языка. Через F{C) обозначим класс всех инъективных отображений из L в {0,1}+, для которых существует С(,/).

Стоимостью оптимального кодирования языка С назовем величину 4.2. Нижняя оценка стоимости кодирования Пусть С — стохастический КС-язык, порождаемый грамматикой G с однозначным выводом, для которой матрица первых моментов неразложима, непериодична и ее перронов корень строго меньше единицы. Для є 0 выделим множество тех слов из 1}. на которых для любого правила г грамматики G выполняется неравенство Обозначим множество таких слов через М1{е). Произведение назовем типичной вероятностью слова и обозначим через р0) произведение рп ...piU[ .. .pki.. -Ркпк обозначим через р\. Для а Є М (е) вероятность р(а) удовлетворяет следующему соотношению: Ро-Рг Р{) РІ-РҐ-При доказательстве теоремы 3.3.4 установлено, что дисперсия случайной величины SLj(t)/t стремится к нулю при t — со. Поэтому, используя неравенство Чебышева [37], для суммарной вероятности Р{М1(є)) можно записать формулу По лемме 3.1.2 где / - некоторая константа и «і - первая компонента правого собственного вектора для перронова корня г. Ясно, что число слов N в множестве Мі{є) удовлетворяет неравенствам Рассмотрим способ кодирования на множестве Ьг, состоящий в упорядочении слов в порядке невозрастания их вероятностей и кодировании их по порядку сначала двоичными словами длины 1, затем двоичными словами длины 2, и т.д. Обозначим такое кодирование через / . Очевидно, / дает наименьшее значение суммы YlaeL1 Pt(a) l/ (a)l среди всех возможных кодирований множества слов ZA Поэтому для любого кодирования / на множестве всех слов языка L, включающем множество Z/, выполняется неравенство В [28] доказана нижняя оценка для стоимости кодирования / на конечном множестве элементов с заданным на нем распределением вероятностей. Применяя эту оценку к множеству Mf(e), можно записать следующее неравенство: где рє(о ) - условная вероятность слова а в множестве Мг(є). т.е. Н (М1(є)) = — Yla&M4e)P a) &Рє(а)і N число слов в множестве Mt(e) и С - некоторая константа. Используя неравенство (4.2.2), из (4.2.1) получаем Подсчитаем величину XlaeL (1) М- Пусть правило Гц содержит 1Ъ] терминальных символов. Тогда где Wij(a) - число применений правила тц в выводе слова а (і — І,..., к: j = 1,..., ПІ). Поэтому, используя теорему 3-3.3, мы можем записать, что Через h обозначим сумму Yli j jwij- Величина h характеризует среднее число терминальных символов на одном ярусе дерева вывода. Тогда мы можем записать: Суммируя полученные оценки, получаем Так как полученное неравенство справедливо при любом є 0, то Вычислим logpo : Подставив полученное выражение в (4.2.3) и используя обозначение получаем Таким образом, мы установили нижнюю оценку для стоимости произвольного кодирования / Є F(C). Сформулируем полученный результат в виде следующей теоремы: Теорема 4.2.1. Пусть С - язык, порожденный стохастической КС-грамматикой с однозначным выводом,, для которой матрица первых моментов неразложима, непериодична и перронов корень строго меньше 1. Тогда для любого кодирования f Є F(C) стоимость кодирования С (С, f) удовлетворяет следующему неравенству: где pij - вероятность правила r , U = (ui,.... щ) и V = (v\,..., Vk) - соответственно правый и левый положительные собственные векторы для перронова корня г при Нормировке Y2i=lUiVi = 1; s\, число нетерминалов А\ в правой части правила г : В{ - константа, определяемая теоремой (3.3.1), h - предел математического ожидания среднего числа терминальных символов на одном ярусе дерева вывода при t —» со.

Обозначим полученную нижнюю оценку стоимости кодирования через С (С). Величину С (С) будем в дальнейшем представлять также в следующем виде: Неулучшаемость нижней оценки стоимости кодирования и асимптотически оптимальное кодирование Докажем, что установленная в теореме 4.2.1 нижняя оценка стоимости кодирования является неулучшаемой, то есть имеет место равенство Определим частоту р ц применения правила г среди правил грамматики с одинаковой левой частью А{ : Для каждого множества правил R; с одинаковой левой частью АІ построим схему двоичного префиксного кодирования по алгоритму Шеннона [36]. Правилу г будет при этом соответствовать элементарный код Vij длины \-logp i:j]. Пусть а Є Z/ имеет левый вывод w(a) = Tilj1rl2j2 .. . nmJm. Тогда в качестве кода слова а мы будем рассматривать двоичную последовательность vi1j1vi2j2 vimjm- полученную конкатенацией элементарных кодов правил, образующих левый вывод. Предложенный алгоритм кодирования строит локально-префиксный код [29] на множестве левых выводов слов из L, когда в качестве алфавита рассматривается множество правил R исходной грамматики G. Обозначим построенное кодирование через / / . Определим стоимость кодирования для /s. : Оценим выражение в числителе дроби: Разобьем множество правил Ri с одинаковой левой частью Аг на два подмножества: множество Rf незаключительных правил (то есть содержащих в правой части нетерминальные символы) и множество Rf заключительных правил (не содержащих в правой части нетерминальных символов). Тогда Раскроем Wij, используя теорему (3.3.2). Предварительно заметим, что для любого заключительного правила г значение sf равно нулю для любого /, ПОЭТОМУ Y2l=l ulsl — О И Wjj = Pij В{. Будем применять обозначение ц для Yli=\uisi Раскрывая гу , получим: Перейдем от исходной грамматики G к грамматике G(n) с укрупненными правилами, описанной в главе 1. Для множества правил Ri(n) суммарная вероятность незаключительных правил при п — со имеет следующий вид: где &о - некоторая константа и Ui - координата правого собственного вектора для перронова корня г. Этот результат легко может быть получен интерпретацией результатов теории ветвящихся процессов [31] применительно к процессу порождения слов языка. Вероятности множества правил Rt(n)H соответствует вероятность продолжения соответствующего ветвящегося процесса в момент времени п. Таким образом, P(Ri(n)H) = 0(гп) и, следовательно, Р (Ri(n)3) = 1 + О (rn).

Закономерности в деревьях вывода в критическом случае

Пусть G - стохастическая КС-грамматика, для которой матрица первых моментов неразложима, непериодична и ее перронов корень равен 1. Через Mi(t,r) обозначим условное математическое ожидание числа вершин, помеченных нетерминалом Л , в деревьях вывода высоты t на ярусе т Теорема 5.2.1. Пусть D\ - множество деревьев вывода высоты t для слов языка, порождаемого стохастической К С-грамматикой с неразложимой и непериодической матрицей первых моментов, для которой перронов корень равен единице. Тогда для любого є из интервала (О,1) при t — оо и t \[е т t (1 — у/є) выполняется следующее равенство: где \xi{t,T,e)\ CQ є и со - некоторая константа, не зависящая от t и Т. В формулировке теоремы Vi - г -я компонента левого собственного вектора для перронова корня и В - константа, определяемая формулой (5.1.1). Доказательство. Будем полагать, что аксиомой исходной грамматики является нетерминал Лі. Мы можем записать следующую формулу для МІ{І.Т) : где Zi(d, т) - число верши [і на ярусе г дерева cf, помеченных Лг, и p(d) -вероятность дерева d в исходной грамматике. Рассмотрим неотрицательный целочисленный вектор X = (xi,... ,Xk)- Используя вектор X, мы можем записать, что где Ах - вклад в математическое ожидание тех деревьев вывода из D\, которые на ярусе т содержат Xj вершин, помеченных нетерминалом А, (j = 1,..., к). Множество таких деревьев обозначим через Dx(r). Пусть d Є J9x(r). Выделим в d поддерево do и последовательность поддеревьев (di, с?2, dm), где m = Yli=i xi- Поддерево do получено из d удалением всех вершин на ярусах т+1,т + 2,...,и инцидентных им дуг. Последовательность (d\, d2, -dm) образуют все поддеревья, корни которых расположены на ярусе т дерева d. При этом корни поддеревьев d\, d2,.. .dm расположены в дереве d последовательно в порядке обхода вершин яруса т слева направо, и каждое дерево d\ (I — 1,-.., m) содержит все дуги и вершины дерева d, лежащие на путях от корня di к листьям дерева d. Выделим в D1X{T) множество деревьев, имеющих в качестве поддерева do одно и то же дерево. Обозначим это множество через DQ. Нетрудно понять, что где функция Qi(n) определена в разделе 2 и ее значение равно вероятности деревьев из множества Di, высота которых больше п, и, следовательно, (1 — Qi(n)) это вероятность деревьев из D\, высота которых не превосходит п. Обозначим через 5\(Х) выражение Пг=і(1 — Qi{t r))Xt и через 52(Х) выражение ГЬ=і(1 — Qitt т )У1- В (5.2.1) величина p(do) $i(X) есть вероятность появления деревьев, определяемых поддеревом do, высота которых не превосходит . так как каждое поддерево с корнем на ярусе т имеет высоту, не превосходящую (t — т).

Вторая величина p(do) -52(Х) есть вероятность появления деревьев, определяемых поддеревом do. высота которых не превосходит (t — т — 1). Разность p(do) $i(X) — p(do) 52(Х) равна, очевидно, вероятности деревьев высоты , определяемых деревом do, и значение 5\(Х) — 52(Х) не зависит от порядка следования вершин на ярусе т, помеченных нетерминалами. Поэтому где суммирование ведется по всем возможным поддеревьям GJQ деревьев вывода из Dx{r). Для каждой вершины, помеченной некоторым нетерминалом А\, вероятность появления деревьев с корнем в этой вершине и листьями, помеченными только терминалами, равна P{D\). Легко показать, что P(Di) = 1 для любого I ввиду согласованности исходной грамматики G. Поэтому величина Yld Р( о) Равна вероятности деревьев вывода из D\, имеющих xi вершин на ярусе т, помеченных нетерминалом Ai (I = 1,...,/с): где DX{T) — множество деревьев из Di, имеющих Xj вершин на ярусе г, помеченных Aj (j= Будем обозначать $ єГ х(т)Р(0 чеРез Рх{т). Таким образом, Пусть М - множество целочисленных неотрицательных векторов, определенное в разделе 5.1. (Напомним, что любой вектор X в М близок к вектору вида bV, где V - левый собственный вектор для перронова корня и Ъ 0.) Мы можем записать, что где М - дополнение множества М до множества всех целочисленных неотрицательных векторов. В обозначениях раздела 5.1 разность 8і{Х) - 62{Х) есть Rx(t - т). Обозначим через S\ сумму Y2X&M - (Г) Rx(t — т) х7 и через 52 сумму Е Рх{т) Rx{t - т) хг. ХеМ Отдельно вычислим эти суммы. Пусть X Є М . На множестве М представим х\ в виде следующей суммы: (здесь vi - 1-я компонента левого собственного вектора для перронова корня г, а В - величина, определенная формулой (5.1.1)). Из определения множества М следует, что 0 Л(х/) еВ1. Применим к Рх{т) следствие 5.1.3 при m = 1. Так как (в предположении, что аксиомой грамматики является А\), мы можем записать, что Применяя лемму 5.1.4 к Rx{t — т), найдем для Si верхнюю оценку Sf: Отметим, что слагаемое Su учитывает погрешность в значениях Х{ и Xj, а 5із учитывает погрешность в представлении вероятности Рх(т). Отдельно оценим каждое из слагаемых 5ц, Si 2 и Sis-Для оценки Su воспользуемся следующим равенством, справедливым при любом х, 0 х Выполнение соотношений (5.2.3) означает, что ярус т находится на достаточно большом удалении от корня дерева вывода и от последнего яруса t. При t — оо значения т и і — г также стремятся к оо. Аппроксимируем е с помощью разложения в ряд Тейлора: Здесь и далее запись 0(f(e)) применяется для обозначения величины, не превосходящей но модулю с f(s), где с 0 - некоторая константа. Для оценки выражения Yli=i (1 — Qi(t т) (1 + Ф?( r))) 2 используем следующее равенство, доказанное в [31]: Применяя это равенство и учитывая нормировку YLi=iuivi = 1, а также соотношения мы можем записать, что где 7г(і — г) = о{\) для / = 1,... ,к, rj(t — т) — о(1) и 0 R2 с u_TT\2 Для некоторой константы с. С учетом соотношений (5.2.3) для R2 справедлива оценка R2 сє? и поэтому Будем использовать также более грубую оценку: Применяя найденные оценки, после несложных преобразований с учетом соотношений (5.2.3) получим, что Так как для любого є 0 выполняется неравенство ту(і — т) є, начиная с некоторого t — т, можно записать, что при некоторой константе с2 0. При оценке Si з мы воспользовались леммой 5.1.5. Разобьем множество М на два подмножества М + и М : множество М отнесем к М +, если Тогда S13 можно оценить следующим образом: Обозначим через + сумму Х л/ + и чеРез сумму Х м - п-Так как имеет место сходимость по распределению, то 5+ — 0 и — 0 при г — оо. Положим 5 = J+ + \5 \.

Тогда Вычислим сумму Sn -f- Si 2 + Si з : Поскольку либо j 1/2, либо - 1/2 и выполняются соотношения (5.2.3), мы можем записать, что Так как 5- 0 при г — сю, найдется такое Q: Для которого при t to и выполнении условий (5.2.3) выполняется неравенство 5 е. Тогда Вернемся к вычислению Sf. .7==1 Воспользуемся леммами 5.1.1 и 5.1.2 для представления QI(T) И Р (Z) -7") , а также оценкой для jf(t т), следующей из леммы 5.1.4. Получим, что Аналогично вычислению верхней оценки Sf вычислим нижнюю оценку Sf. Для этого достаточно провести те же самые преобразования, что и для Sf, заменив lf{t т) на lj{t т) 0, 4 f(t — г) на f(t — т) и положив А = 0. При этом для множителя достаточно применить оценку (1+0( 2)). справедливую при выполнении (5.2.3). Поэтому для Sf так же выполняется равенство и. следовательно, Наконец, оценим величину $2, равную ХеМ Применим лемму 5.1.4 к Rx(t — т). Получим, что Применим несколько раз лемму 5.1.5: для j = і к выражению и для каждого j ф г к выражениям Учитывая оценку P{Dl T) = О ( ,t}T\2 ) , следующую из леммы 5.1.2, оценку Qj(t — т) = О (jz ) из леммы 5.1.1, получим, что (здесь с - некоторая константа). Так как то, учитывая (5.2.2), мы можем записать, что При 5 є получаем, что хем Таким образом, При выполнении (5.2.3) очевидно, что Поэтому при любом є из интервала (0.1) и t —- со, л ё т і (1 — \/і). Возьмем в качестве нового значения є значение є2. Тогда можно записать, что и формула для Mt(t. т) примет следующий вид: Заметим, что в доказательстве теоремы при получении оценки О (є) для Хг(і-Т-Є) мы использовали конечное число раз бесконечно малые величины из конечного множества, зависящие от t, т и t — т. Поэтому существует константа CQ 0, не зависящая от t и т. такая, Теорема доказана. Обозначим через Mij(t,r) условное математическое ожидание числа применений правила г на ярусе т в деревьях вывода из D\. Теорема 5.2.2. Пусть D\ - множество деревьев вывода высоты t для слов языка, порождаемого стохастической КС-грамматикой с неразложимой и непериодической матрицей первых моментов, для которой перронов корень равен единице. Тогда для любого є из интервала (О,1) при t —» оо и t у/є г t (1 — л/є) выполняется следующее равенство: В формулировке теоремы pjj - вероятность правила r2J, заданная в исходной грамматике, иг - г-я компонента левого собственного вектора для перронова корня и В - константа, определяемая формулой (5.1.1).

Похожие диссертации на Кодирование стохастических контекстно-свободных языков

Закономерности в словах стохастических КС-языков с двумя классами нетерминальных символов. Вопросы экономного кодированияБорисов Александр Евгеньевич