Содержание к диссертации
Введение
2 Оценка средней длины кода для стохастического языка 17
3 Закономерности в деревьях вывода слов и оптимальное кодирование. Докритический случай 21
3.1 Основные определения и обозначения 21
3.2 Вероятности продолжения 23
3.3 Закономерности в деревьях вывода слов. Случай простого перронова корня 33
3.4 Закономерности в деревьях вывода слов. Случай кратного перронова корня 35
3.5 Оценки моментов второго и более высоких порядков для кратного перронова корня 37
3.6 Дисперсия числа применений правил в деревьях вывода 47
3.7 Пример грамматики с двумя классами нетерминалов . 53
3.8 Оценка стоимости оптимального кодирования 54
3.9 Алгоритм асимптотически оптимального кодирования . 57
4 Закономерности в деревьях вывода слов и оптимальное кодирование. Критический случай 61
4.1 Случай кратного перронова корня 62
4.1.1 Вероятности продолжения 62
4.1.2 Математические ожидания числа применений правил в деревьях вывода 71
4.1.3 Энтропия и стоимость оптимального кодирования 82
4.1.4 Алгоритм оптимального кодирования 84
4.2 Случай простого перронова корня 86
4.2.1 Вероятности продолжения и вероятности деревьев вывода фиксированной высоты 86
4.2.2 Распределение нетерминалов на фиксированном ярусе дерева вывода 88
4.2.3 Математические ожидания числа применений правил в деревьях вывода 91
4.2.4 Алгоритм оптимального кодирования 95
5 Заключение 96
- Закономерности в деревьях вывода слов. Случай кратного перронова корня
- Дисперсия числа применений правил в деревьях вывода
- Математические ожидания числа применений правил в деревьях вывода
- Распределение нетерминалов на фиксированном ярусе дерева вывода
Введение к работе
Вопросы оптимального кодирования сообщений (слов), порождаемых некоторым вероятностным источником, возникают в задачах, связанных с передачей и хранением информации. Под оптимальным кодированием, как правило, понимают кодирование, которое дает максимальную степень сжатия информации (отношение длины исходного слова к длине его кода). Возможная степень сжатия информации определяется вероятностными и структурными свойствами источника информации. Вероятностные свойства учитывают частоты символов или фрагментов в исходном слове, а структурные (синтаксические) - правила построения слов (например, в словах русского языка не встречается сочетаний типа БББ, ЩЩ, слова не начинаются с мягкого знака).
Хорошо известны и широко используются на практике алгоритмы побуквениого кодирования, которые учитывают только частоты букв. Наиболее известными являются алгоритмы Хаффмаиа [32], Фапо [23], Шеннона [22], алгоритм арифметического кодирования [30], [31], которые применяются при отсутствии априорных знаний о структуре кодируемых слов (сообщений). Существуют также динамические версии этих алгоритмов, которые в процессе работы обновляют таблицу частот символов. Такие алгоритмы строят вероятностную модель языка в процессе получения на вход новых символов.
Хорошо известны также словарные методы сжатия, основанные на учете часто повторяемых фрагментов в кодируемом тексте. Здесь следует выделить алгоритмы Лемпеля-Зива LZ77 и LZ78 [28],[29], и их многочисленные модификации.
Задача кодирования, учитывающего синтаксические свойства сообщений, была впервые рассмотрена К.Шенноном в [22]. Им был рассмотрен вероятностный источник сообщений с конечным числом состояний. Шеннон доказал, что в случае эргодичности источника все сообщения большой длины N разбиваются на два класса: множество сообщений, вероятность которых стремится к 0 при N — со, и множество оставшихся сообщений с приблизительно одинаковыми вероятностями и буквенным составом. Такой источник фактически соответствует неразложимому марковскому процессу с конечным числом состояний. При построении алгоритмов кодирования Шенноном рассматривались в основном вероятностные свойства слов, хотя введенное им блочное кодирование косвенно учитывает и структурные свойства.
Вопросы кодирования слов с учетом структурных свойств (синтаксиса) рассматривались А.А.Марковым в [14], [15], [16]. Он поставил задачу кодирования не па всем множестве слов алфавита, а на некотором подмножестве слов, описываемом синтаксическими правилами. Для описания синтаксиса рассматривались в основном регулярные источники. Марков показал, что учет синтаксиса регулярных языков позволяет увеличить степень сжатия и уменьшить вычислительную сложность алгоритмов кодирования [16].
Ближайшим обобщением класса языков, порожденных регулярными источниками, являются языки, порожденные стохастическими контекстно-свободными (КС-) грамматиками. Неразложимые стохастические КС-грамматики рассматривались Л.П.Жильцовой в работах [10], [11], [12]. В этих работах были получены следующие результаты. В докритическом случае (перронов корень матрицы первых моментов меньше единицы) для слов большой длины стохастического КС-языка, порождаемого такой грамматикой, установлены свойства, аналогичные свойствам слов, генерируемых эргодическим конечным источником [22].
Кроме того, для множества деревьев вывода высоты t для слов языка при t — со были найдены математические ожидания числа применений каждого правила грамматики на фиксированном ярусе дерева вывода и во всем дереве вывода для критического (перронов корень матрицы первых моментов равен единице) и докритического случаев. В обоих случаях была найдена асимптотическая формула для энтропии множества слов, имеющих деревья вывода фиксированной высоты. Также была вычислена стоимость оптимального кодирования и построен алгоритм асимптотически оптимального кодирования для обоих случаев, имеющий полиномиальную временную сложность.
В данной работе аналогичные исследования проводятся для грамматики с разложимой матрицей первых моментов и двумя классами нетерминальных символов. Рассматривается докритический и критический случаи. Для такой грамматики установлены закономерности в деревьях вывода фиксированной высоты t для слов языка при t — со, то есть найдены математические ожидания числа применений правил грамматики на каждом ярусе дерева вывода и во всем дереве, а также найдена суммарная вероятность таких слов. Особое внимание уделяется случаю кратного перроиова корня, поскольку именно тогда появляются существенные отличия от неразложимого случая. С использованием этих закономерностей найдена асимптотическая формула для энтропии множества слов, имеющих деревья вывода фиксированной высоты.
Полученные результаты использованы для получения нижней оценки стоимости двоичного кодирования слов языка, порожденного рассматриваемой грамматикой. Задача оптимального кодирования рассматривалась в том же виде, что и в [12]. Под оптимальным кодированием понималось взаимпо-одиозиачнос кодирование множества всех слов языка, которое позволяет хорошо сжимать длинные слова (имеющие деревья вывода большой высоты). Была найдена стоимость оптимального кодирования для рассматриваемого языка. Доказано, что алгоритм блочного кодирования, использованный Жильцовой в [12] для неразложимого случая, является асимптотически оптимальным и для рассматриваемой в данной работе грамматики. Применяемый алгоритм кодирования использует состав правил в выводе слова, таким образом учитывая синтаксические свойства.
Также были изучены общие вопросы кодирования стохастических языков, получена нижняя оценка для средней длины кода в зависимости от энтропии, которая является более точной, чем полученная в [12], при больших значениях энтропии. Эта оценка была использована для получения нижней оценки стоимости кодирования стохастического КС-языка.
Закономерности в деревьях вывода слов. Случай кратного перронова корня
Будем говорить, что нетерминал Aj следует за нетерминалом А{, или что А{ предшествует Aj (и обозначать А{ — Aj), если из Л; выводимо хотя бы одно слово, содержащее нетерминал Aj. Грамматика называется неразлооїсимой, если для любых двух различных нетерминалов А{ и Aj верно А\ — Aj. В противном случае она называется разложимой. Классом нетерминалов назовем максимальное по включению подмножество К Є V/v, такое, что А[ — Aj для любых А{, Aj є К. Будем говорить, что класс К\ предшествует классу Кч (и обозначать К\ - К і), если для любых А\ Є К\, А і Є К і верно А\ — А . Очевидно, что множество нетерминалов V/v является объединением конечного числа непересекающихся классов.
Понятие неразложимости можно пояснить на языке графов. Построим ориентированный граф, в котором вершины соответствуют нетерминалам грамматики, и от г -й вершины к j-й проводится ребро, если существует правило вида Ai Pj% aiAjCV2, ai,a.i Є (Vr U V/V) . Тогда неразложимой грамматике соответствует сильно связный граф, то есть такой, в котором существует ориентированный путь из любой вершины в любую.
Любой стохастической КС-грамматике можно очевидным образом поставить в соответствие дискретный ветвящийся процесс [17], причем нетерминалу грамматики будет соответствовать тип частицы в ветвящемся процессе. Классу нетерминалов грамматики будет соответствовать класс типов частиц в ветвящемся процессе. Матрица или вектор X называется неотрицательной (обозначается X 0), если все ее элементы неотрицательны, и положительной (обозначается X 0), если все се элементы больше нуля. Квадратная неотрицательная матрица X размера к х к называется разложимой, если множество S — (1,2,..., к) можно разбить на два подмножества Si, S2 так, чтобы Х = 0 для любых і Є Si,j Є % В противном случае матрица X называется неразложимой. В [17] показано, что неразложимость ветвящегося процесса (грамматики) эквивалентна неразложимости матрицы первых моментов. Известно, что если неотрицательная матрица X неразложима и непериодична [9], то существует такое п, что Xа 0. Очевидно, матрица первых моментов грамматики всегда неотрицательна.
По теореме Фробеииуса [9] для матрицы первых моментов А существует максимальный по модулю действительный неотрицательный собственный корень {перронов корень), причем в случае А 0 он простой, т.е. его кратность равна 1. Будем его обозначать в дальнейшем через г.
Пусть G - стохастическая КС-грамматика. Через Li обозначим язык, порожденный грамматикой, которая получена заменой аксиомы исходной грамматики па нетерминал ЛІ. Через Д обозначим множество деревьев вывода слов из Li, через Dfl - множество .деревьев вывода высоты не более t для слов из Li, а множество деревьев из Dfl высоты ровно t обозначим через D\. Для d Є D\ обозначим через Pt(d) условную вероятность дерева d. Она равна p{d)/P{Dti), где P(Dj) -общая вероятность деревьев вывода из D\. Обозначим через Qi(t) вероятность множества деревьев из Д, имеющих высоту больше чем t. Эту величину назовем вероятностью продолжения по аналогии с теорией ветвящихся процессов. Очевидно, ЧТО -Р(Д ) = Qi{t — 1) — Qi(t). Будем далее иногда для краткости обозначать Pi(t) = -Р(Д-). Для исходной грамматики G будем полагать, что аксиомой является нетерминал А\. В дальнейшем в обозначениях Lj, D\ индекс г будем опускать при і — 1. Будем использовать также векторные обозначения Q(t) = (Qi(t),...,Qk(t)), P(t) = (Pi(t),..., Pk(t)).
В работе рассматривается разложимая согласованная грамматика с двумя классами нетерминалов Ki,K2, причем один из них предшествует другому. Для определенности положим Ki - К2- Согласованность для грамматики означает, что соответствующий ей ветвящийся процесс вырождается, что, как показано в [IT], имеет место либо при г 1, либо если г = 1 и отсутствуют бесполезные (не участвующие в порождении слов языка) нетерминалы. Выполнение одного из этих двух условий мы и будем предполагать в дальнейшем. Считаем, что аксиома 5 принадлежит К\. Обозначим k\ = \K\\, / = -К2І h + 2 = k. Будем считать, что нетерминалы из К\ имеют номера 1,..., ki, из Къ - соответственно ki + l,...,k. Для такой грамматики матрица первых моментов А имеет блочный вид: где А - матрица размером k\ х к\, А - матрица размером ki х / а А - матрица размером к\ х /. Дополнительно предположим, что матрицы AM, Л(2), А& положительны. Тогда по теореме Перрона [9] для каждой из матриц А \ А существует простой максимальный по модулю действительный положительный собственный корень (перронов корень).
Обозначим за v , v" левые, за и , и" правые собственные вектора матриц А и А$\ соответствующие их перроиовым корням г и г" при нормировке v и = v"u" = 1, Ei j = Hiv l = 1 (левый собственный вектор матрицы всегда считаем вектором-строкой). Левый и правый собственные вектора для перронова корня г матрицы А при условии нормировки vu = 1, Ei Vj = 1 будем обозначать через v,u.
КС-грамматика называется КС-грамматикой с однозначным выводом, если каждому слову в терминальном алфавите, выводимому из аксиомы, соответствует единственное дерево вывода. При рассмотрении вопросов кодирования слов языка всегда будем рассматривать грамматику с однозначным выводом.
Опишем процедуру укрупнения грамматики с однозначным выводом, введенную в [12]. Пусть а - слово из (Vy U Viv) , выводимое из нетерминала А{, и d(a) - его дерево вывода. Обозначим через М-1 множество слов в алфавите Vjv U Vp, выводимых из А{ и имеющих деревья вывода высоты не более п, в которых нетерминалами могут быть помечены листья только последнего (п-го) яруса. Укрупнение грамматики состоит в замене множества правил R на R(n) = Uf=1/?j(n), где и n - число слов в Mf. Вероятность правила - = р(/3 ), т.е. равна вероятности соответствующего слова / из М-1 в исходной грамматике. Обозначим новую грамматику с полученными таким образом правилами через G(n).
Очевидно, что LQ — Ьо(п), и, если G - согласованная грамматика с однозначным выводом, то G(n) - также согласованная грамматика с однозначным выводом. Данная процедура может применяться и к грамматике с неоднозначным выводом; в этом случае вероятность правила в грамматике G(n) равна сумме вероятностей деревьев вывода для его правой части. В [17] показано, что матрица первых моментов для грамматики G(n) равна Ап, где А - матрица первых моментов грамматики G.
Дисперсия числа применений правил в деревьях вывода
Поскольку асимптотика для величин M(Sij(t)) и Р(Ог) для случая г ф г" такая же, как и в неразложимом случае, то выражения для энтропии Н(С1) множества слов С1 и нижней оценки стоимости оптимального кодирования С (С) имеют такой же вид, как и в неразложимом критическом случае, причем схема кодирования, предложенная для случая кратного перропова корня в предыдущем разделе, является оптимальной и здесь, так как H(Cl) = 0(t2),P(t) = 0(t2). Эффективный алгоритм асимптотически оптимального при укрупнении правил грамматики кодирования, описанный в главе 3, будет асимптотически оптимальным и в этом случае.
Можно заметить, что в случае г г" оценки для Н{С1) и С {С) имеют тот же вид, что и для грамматики, порожденной только нетерминалами из Hi (это следует из того, что в этом случае г (1 : к\) — 0) - как и для случая кратного перронова корня.
Диссертационная работа посвящена исследованию вопросов экономного кодирования сообщений, структурные и вероятностные свойства которых описываются с помощью разложимых стохастических КС-грамматик с двумя классами нетерминальных символов. Работа является продолжением исследованийщроведенных Л.П.Жильцовой для неразложимых грамматик.
В работе рассматривается традиционная постановка задачи экономного кодирования на множестве "длинных"сообщепий, которую рассматривал К.Шешюн [22]. Мерой эффективности кодирования является его стоимость, определяемая как число двоичных разрядов, требуемых для кодирования одной буквы сообщения. В качестве множества длинных слов рассматривалось множество слов КС-языка, деревья вывода которых имеют высоту t при t — со. В диссертационной работе получены следующие основные результаты. 1) Найдены нижние оценки средней длины кода для произвольного стохастического языка в зависимости от энтропии, которые являются более точными при больших значениях энтропии, чем полученные в [33]. 2) Для стохастического КС-языка, порожденного разложимой грамматикой с двумя классами нетерминальных символов, выделены два случая, определяемых значением перронова корня г матрицы первых моментов, а именно: а) Докритичсский случай, при г 1, б) Критический случай, при г = 1. В обоих случаях найдены асимптотические формулы для математических ожиданий числа применений произвольного правила грамматики в деревьях вывода высоты t при t —- со, а также исследовано поведение математических ожиданий числа применений правил на отдельных ярусах дерева вывода. На основе этих результатов найдена энтропия вероятностного распределения на множестве деревьев вывода высоты t, а также точная нижняя оценка стоимости двоичного кодирования. 3) Описан алгоритм блочного кодирования деревьев вывода, который был ранее применен в [12] для неразложимого случая, и доказана его оптимальность па множестве слов стохастического КС-языка, порожденного рассматриваемой разложимой грамматикой.
Установлено, что на характер полученных результатов существенно влияет кратность перронова корня матрицы первых моментов. Показано, что в случае простого перронова корня поведение всех изученных в работе характеристик совпадает с их поведением для неразложимой грамматики. Существенные отличия от неразложимой грамматики появляются для случая кратного перронова корня.
Оказывается, что при г 1 математические ожидания числа применений правил на фиксированном ярусе не стремятся к константе для разных ярусов, и дисперсия среднего числа применений каждого правила на один ярус дерева вывода высоты t не стремится к нулю при t — со в отличие от неразложимого случая. Для случая кратного перронова корня г = 1 свойства грамматики определяются свойствами правил, применяемых к нетерминалам второго класса.
Открытым остался вопрос о свойствах деревьев вывода на отдельных ярусах для случая кратного перронова корня г = 1.
Математические ожидания числа применений правил в деревьях вывода
Будем говорить, что нетерминал Aj следует за нетерминалом А{, или что А{ предшествует Aj (и обозначать А{ — Aj), если из Л; выводимо хотя бы одно слово, содержащее нетерминал Aj. Грамматика называется неразлооїсимой, если для любых двух различных нетерминалов А{ и Aj верно А\ — Aj. В противном случае она называется разложимой. Классом нетерминалов назовем максимальное по включению подмножество К Є V/v, такое, что А[ — Aj для любых А{, Aj є К. Будем говорить, что класс К\ предшествует классу Кч (и обозначать К\ - К і), если для любых А\ Є К\, А і Є К і верно А\ — А . Очевидно, что множество нетерминалов V/v является объединением конечного числа непересекающихся классов.
Понятие неразложимости можно пояснить на языке графов. Построим ориентированный граф, в котором вершины соответствуют нетерминалам грамматики, и от г -й вершины к j-й проводится ребро, если существует правило вида Ai Pj% aiAjCV2, ai,a.i Є (Vr U V/V) . Тогда неразложимой грамматике соответствует сильно связный граф, то есть такой, в котором существует ориентированный путь из любой вершины в любую.
Любой стохастической КС-грамматике можно очевидным образом поставить в соответствие дискретный ветвящийся процесс [17], причем нетерминалу грамматики будет соответствовать тип частицы в ветвящемся процессе. Классу нетерминалов грамматики будет соответствовать класс типов частиц в ветвящемся процессе. Матрица или вектор X называется неотрицательной (обозначается X 0), если все ее элементы неотрицательны, и положительной (обозначается X 0), если все се элементы больше нуля. Квадратная неотрицательная матрица X размера к х к называется разложимой, если множество S — (1,2,..., к) можно разбить на два подмножества Si, S2 так, чтобы Х = 0 для любых і Є Si,j Є % В противном случае матрица X называется неразложимой. В [17] показано, что неразложимость ветвящегося процесса (грамматики) эквивалентна неразложимости матрицы первых моментов. Известно, что если неотрицательная матрица X неразложима и непериодична [9], то существует такое п, что Xа 0. Очевидно, матрица первых моментов грамматики всегда неотрицательна.
По теореме Фробеииуса [9] для матрицы первых моментов А существует максимальный по модулю действительный неотрицательный собственный корень {перронов корень), причем в случае А 0 он простой, т.е. его кратность равна 1. Будем его обозначать в дальнейшем через г.
Пусть G - стохастическая КС-грамматика. Через Li обозначим язык, порожденный грамматикой, которая получена заменой аксиомы исходной грамматики па нетерминал ЛІ. Через Д обозначим множество деревьев вывода слов из Li, через Dfl - множество .деревьев вывода высоты не более t для слов из Li, а множество деревьев из Dfl высоты ровно t обозначим через D\. Для d Є D\ обозначим через Pt(d) условную вероятность дерева d. Она равна p{d)/P{Dti), где P(Dj) -общая вероятность деревьев вывода из D\. Обозначим через Qi(t) вероятность множества деревьев из Д, имеющих высоту больше чем t. Эту величину назовем вероятностью продолжения по аналогии с теорией ветвящихся процессов. Очевидно, ЧТО -Р(Д ) = Qi{t — 1) — Qi(t). Будем далее иногда для краткости обозначать Pi(t) = -Р(Д-). Для исходной грамматики G будем полагать, что аксиомой является нетерминал А\. В дальнейшем в обозначениях Lj, D\ индекс г будем опускать при і — 1. Будем использовать также векторные обозначения Q(t) = (Qi(t),...,Qk(t)), P(t) = (Pi(t),..., Pk(t)).
В работе рассматривается разложимая согласованная грамматика с двумя классами нетерминалов Ki,K2, причем один из них предшествует другому. Для определенности положим Ki - К2- Согласованность для грамматики означает, что соответствующий ей ветвящийся процесс вырождается, что, как показано в [IT], имеет место либо при г 1, либо если г = 1 и отсутствуют бесполезные (не участвующие в порождении слов языка) нетерминалы. Выполнение одного из этих двух условий мы и будем предполагать в дальнейшем. Считаем, что аксиома 5 принадлежит К\. Обозначим k\ = \K\\, / = -К2І h + 2 = k. Будем считать, что нетерминалы из К\ имеют номера 1,..., ki, из Къ - соответственно ki + l,...,k. Для такой грамматики матрица первых моментов А имеет блочный вид: где А - матрица размером k\ х к\, А - матрица размером ki х / а А - матрица размером к\ х /. Дополнительно предположим, что матрицы AM, Л(2), А& положительны. Тогда по теореме Перрона [9] для каждой из матриц А \ А существует простой максимальный по модулю действительный положительный собственный корень (перронов корень).
Обозначим за v , v" левые, за и , и" правые собственные вектора матриц А и А$\ соответствующие их перроиовым корням г и г" при нормировке v и = v"u" = 1, Ei j = Hiv l = 1 (левый собственный вектор матрицы всегда считаем вектором-строкой). Левый и правый собственные вектора для перронова корня г матрицы А при условии нормировки vu = 1, Ei Vj = 1 будем обозначать через v,u.
КС-грамматика называется КС-грамматикой с однозначным выводом, если каждому слову в терминальном алфавите, выводимому из аксиомы, соответствует единственное дерево вывода. При рассмотрении вопросов кодирования слов языка всегда будем рассматривать грамматику с однозначным выводом.
Опишем процедуру укрупнения грамматики с однозначным выводом, введенную в [12]. Пусть а - слово из (Vy U Viv) , выводимое из нетерминала А{, и d(a) - его дерево вывода. Обозначим через М-1 множество слов в алфавите Vjv U Vp, выводимых из А{ и имеющих деревья вывода высоты не более п, в которых нетерминалами могут быть помечены листья только последнего (п-го) яруса. Укрупнение грамматики состоит в замене множества правил R на R(n) = и n - число слов в Mf. Вероятность правила - = р(/3 ), т.е. равна вероятности соответствующего слова / из М-1 в исходной грамматике. Обозначим новую грамматику с полученными таким образом правилами через G(n).
Распределение нетерминалов на фиксированном ярусе дерева вывода
И. В третьей главе рассматривается разложимая грамматика с двумя классами нетерминалов в докритическом случае (перронов корень г 1). Поскольку результаты теории ветвящихся процессов, относящиеся к разложимым процессам (см. например [24], [25], [26]) относятся в основном к случаю непрерывного времени и не позволяют вычислить вероятности продолжения для стохастических КС-грамматик, то сначала для соответствующего грамматике ветвящегося процесса устанавливается асимптотика вероятностей продолжения, которая для неразложимого случая получена в [17]. Установлено, что для случая перронова корня кратности один асимптотика вероятности продолжения имеет такой же вид, как и в неразложимом случае, а для перронова корня кратности два их асимптотика имеет другой вид, а именно:где r-псрронов корень, и , и" - правые собственные вектора матриц А 1\ А соответственно, Со 0 - некоторая константа, и Ь определено формулой (3.2.3) (теорема 3.2.1). В доказательствах использовалась техника из теории ветвящихся процессов, аналогичная примененной в [17] для неразложимых процессов.
С использованием этих результатов показано, что в случае простого перронова корня вероятности продолжения, вероятность деревьев вывода высоты t при t — бо, и математические ожидания числа применений правил на фиксированном ярусе дерева вывода и во всем дереве имеют такую же асимптотику, как и в неразложимом случае. Это позволило доказать, что в этом случае энтропия Н(С1) множества слов, имеющих деревья вывода высоты t, и стоимость оптимального кодирования имеют тот же вид, что и в неразложимом случае.
Будем обозначать через М(), D() соответственно математическое ожидание и дисперсию случайной величины . В случае кратного перройова корня математическое ожидание M(qij(t, г)) числа применений правила Гц в дереве высоты t на ярусе т линейно зависит от т/t при t, т — со, и при этом ограничено сверху константой:
Здесь 5 -, 5 - - константы, определяемые по грамматике и учитывающие число нетерминалов в правых частях правил, G[, G" - константы, определяемые вторыми моментами грамматики (теорема 3.5.1).
Доказано, что для правил, применяемых к нетерминалам из К\, эта величина убывает, а для правил, применяемых к нетерминалам из / , может и убывать, и возрастать (см. пример параграфа 3.7). При этом, как и в неразложимом случае, имеет место перераспределение частот правил, т.е. при t — со правила, порождающие больше нетерминальных символов, используются в выводе слов чаще, что, по-видимому, нужно для достижения большей высоты дерева вывода. Величины M(qij(t,r)) не меняются при замене аксиомы на любой нетерминал из класса К\.
Пусть случайная величина Sij (t) - число правил Гц в дереве вывода высоты t. Доказано, что математическое ожидание величины Sij(t)/t - среднего числа правил, приходящихся на один ярус.дерева вывода, стремится к константе при t —» со: где величины Uij определены формулами (3.5.6) (теорема 3.5.2). Дисперсия величины Sij(t)/t для случая кратного перроиова корня г 1 не стремится к 0 при t — со в отличие от неразложимого случая [10], а именно, справедливы соотношения где величины u\- определены формулами (3.5.5) (теорема 3.G.1). Поэтому пропорциональный состав деревьев вывода по правилам грамматики и пропорциональный побуквеииый состав слов соответствующего языка не имеет места. Для нахождения математических ожиданий числа применений правил грамматики на ярусе дерева вывода, среднего числа правил, приходящихся па один ярус дерева вывода, и его дисперсии был использован метод, примененный Л.П.Жильцовой для неразложимого случая [10]. III. С помощью найденных асимптотик во всем дереве вывода в до-критическом случае установлено, что энтропия Н(С1) множества слов, имеющих деревья вывода высоты t, асимптотически линейно зависит от t, как и в неразложимом случае: Здесь величины cjij определены формулами (3.5.6), &рц - вероятность применения правила Гц (теорема 3.8.1). Из результатов главы 2 следует, что для оптимального кодирования такого множества слов отношение математического ожидания длины закодированного слова к Н(С1) стремится к 1 при t — со. Это позволило получить нижнюю оценку С (С) для стоимости двоичного кодирования слов языка, порождаемого рассматриваемой грамматикой: где ujij определены формулами (3.5.6), рц - вероятность применения правила Гц, а 1ц - число терминальных символов в правой части правила Гц (теорема (3.8.2)).
Кроме того, показано, что эта оценка является точной, то есть существует кодирование, стоимость которого сколь угодно близка к полученной оценке С (С). Для этого использовалась схема кодирования, предложенная в [12], которая состоит в кодировании множества правил в составе левого вывода слова. При этом для множества правил R{ с одинаковой левой частью Д- применяется схема префиксного кодирования Шеннона [22] с учетом найденных математических ожиданий числа применений правил в деревьях вывода. Код слова получается конкатенацией кодов правил, примененных при его выводе. По аналогии с [12] доказывается, что стоимость такого кодирования стремится к С (С) при описанном в этой работе укрупнении правил грамматики. Такое кодирование существенно использует и вероятностные, и структурные свойства языка. Сначала рассматривается случай кратного перроиова корня. Для вероятностей продолжения соответствующего грамматике ветвящегося процесса аналогично неразложимому случаю [17] получены рекуррентные соотношения. В результате их решения установлено, что асимптотика вероятностей продолжения для нетерминалов первого класса и вероятность деревьев вывода высоты t в случае кратного перроиова корня имеет другой вид по сравнению с неразложимым случаем. Доказан следующий результат.
Похожие диссертации на Закономерности в словах стохастических КС-языков с двумя классами нетерминальных символов. Вопросы экономного кодирования
