Закономерности в словах стохастических КС-языков с двумя классами нетерминальных символов. Вопросы экономного кодирования тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

На правах рукописи

БОРИСОВ Александр Евгеньевич

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

01.01.09 - дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Нижний Новгород - 2006

Работа выполнена в Нижегородском государственном университете им. Н.И. Лобачевского.

Научный руководитель: доктор физико-математических наук,

доцент Л.П. Жильцова

Официальные оппоненты: доктор физико-математических наук,

профессор М.Ю. Мошков ' ^ кандидат физико-математических наук,

доцент В.В. Носков

Ведущая организация: Московский государственный университет им. М.В. Ломоносова (механико-математический факультет)

/I/

Защита состоится 21 сентября 2006 г. в " / ' " на заседании диссертационного совета Д 212.166.06 в Нижегородском государственном университете им. Н. И. Лобачевского по адресу: 603950, г. Нижний Новгород, пр. Гагарина, 23, конференц-зал ННГУ, корп. 2.

С диссертацией можно ознакомиться в фундаментальной библиотеке ННГУ.

Автореферат разослан п /ч? " июля 2006 г.

г " 1

Ученый секретарь диссертационного совета, кандидат физико-математических наук, доцент

В. И. Лукьянов

Общая характеристика работы.

Актуальность темы. Вопросы оптимального кодирования сообщений (слов), порождаемых некоторым вероятностным источником, возникают в задачах, связанных с передачей и хранением информации. Под оптимальным кодированием, как правило, понимают кодирование, которое дает максимальную степень сжатия информации (отношение длины исходного слова к длине его кода). Возможная степень сжатия информации определяется вероятностными и структурными свойствами источника информации. Хорошо известны и широко используются на практике алгоритмы побуквенного кодирования, которые учитывают только частоты букв. Наиболее известными являются алгоритмы Хаффмана, Фано, Шеннона, алгоритм арифметического кодирования, которые применяются при отсутствии априорных знаний о структуре кодируемых слов (сообщений).

Хорошо известны также словарные методы сжатия, основанные на учете часто повторяемых фрагментов в кодируемом тексте. Здесь следует выделить алгоритмы Лемпеля-Зива 1^77, Ь278 и их многочисленные модификации.

Задача кодирования, учитывающего синтаксические свойства сообщений, была впервые рассмотрена К.Шенноном в его работе "Математическая теория связи". Им был рассмотрен вероятностный источник сообщений с конечным числом состояний. Такой источник фактически соответствует неразложимому марковскому процессу с конечным числом состояний.

Вопросы кодирования слов с учетом структурных свойств (синтаксиса) рассматривались в работах А.А.Маркова. Он поставил задачу кодирования не на всем множестве слов алфавита, а на некотором подмножестве слов, описываемом синтаксическими правилами. Для описания синтаксиса рассматривались в основном регулярные источники. Марков показал, что учет синтаксиса регулярных языков позволяет увеличить степень сжатия и уменьшить вычислительную сложность алгоритмов кодирования.

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

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

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

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

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

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

3) нахождение стоимости оптимального кодирования длинных слов;

4) построение эффективного алгоритма асимптотически оптимального кодирования слов языка.

Научная новизна. Результаты, полученные в диссертации, являются новыми. Они имеют теоретическое и познавательное значение для теории кодирования и изучения свойств формальных языков. Данная работа является продолжением исследований, проведенных Л.П. Жильцовой для неразложимых грамматик, на разложимые. Наиболее важными, являются следующие результаты.

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

2) Изучены свойства деревьев вывода слов стохастического КС-языка, порожденного разложимой грамматикой с двумя классами нетерминальных символов, в случае, когда перронов корень матрицы первых моментов не превосходит единицы.

3) С помощью результатов 1) и 2) найдена нижняя оценка стоимости оптимального двоичного кодирования слов языка, порожденного рассмотренной грамматикой, доказано, что эта оценка является точной.

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

1 Zhilt.sova L. On Entropy and Optimal Coding Cost for Stochastic Language//Fundamenta Informaticae.-1998.-V.36.-P.285-305.

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

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

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

Апробация работы. Результаты диссертации докладывались на V и VII Международной научной конференции "Дискретные модели в теории управляющих систем" (Дубна, 2003 и Покровское, 2006), Межгосударственной шксше-семинаре "Синтез и сложность управляющих систем"(Н. Новгород, 2003), VIII Международном семинаре "Дискретная математика и ее приложения"(Москва, 2004), VI Международной конференции по математическому моделированию (Н. Новгород, 2004), а также на городском семинаре по дискретной математике в Нижегородском государственном университете им. Лобачевского.

Публикации. Основные результаты диссертации опубликованы в работах, список которых приведен в конце автореферата.

Структура диссертации. Диссертация состоит из введения (первая глава), трех глав, заключения и списка литературы. Объем диссертации составляет 103 страницы машинописного текста.. Список литературы состоит из 33 наименований.

Содержание диссертации

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

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

Языком над алфавитом В = {&!,..., Ьп} называется подмножество Ь С В\ Стохастический язык £ определяется как пара (Ь, Р), где Ь - язык, а Р - распределение вероятностей на множестве его слов, причем вероятность каждого слова языка больше нуля.

Стохастическая порождающая контекстно-свободная грамматика -это система С? = {Уг, Уи, Я, з), где Ут и Ун - множества терминальных и нетерминальных символов соответственно (в дальнейшем называемых терминалами и нетерминалами), = к,з € У^ - аксиома, Я- конечное

множество правил, Д = 0 Я*, где Л, = {г,1,..., Гш(}, и каждое правило в »=1

имеет вид

гц • Л ^ рф з = 1,...,п„ где Л( е Уи,0ц 6 {Ут и 1^)*, а ру - вероятность применения правила гу, удовлетворяющая условиям

0<ру <1, Др.; = 1-

7=1

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

Будем говорить, что слово а непосредственно выводимо из слова ¡3, если а — ах-^аг, Р — а10ча2 для некоторых слов аг^а-г £ (Уг и V//)*, и грамматика содержит правило щ : А^ ^ Рефлексивное транзитивное замыкание отношения непосредственной выводимости назовем отношением выводимости. За Ьа обозначим множество слов в терминальном алфавите, выводимых из аксиомы е. Под выводом слова будем понимать последовательность правил грамматики, с помощью которой данное слово выводится из аксиомы. Левый вывод - это вывод, в котором каждое правило применяется к самому левому по порядку нетерминалу в слове. Вероятность вывода определяется как произведение вероятностей правил, образующих вывод. Вероятность р(а) для слова а определяется как сумма вероятностей его различных левых выводов.

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

. Пусть а 6 Ьа- Каждому левому выводу слова а соответствует дерево вывода, корень которого помечен аксиомой, а вершины - терминальными и

нетерминальными символами2. При применении правила A¡ ^А Л1Л2 ... Кгп в вершине а, помеченной нетерминалом А,-, добавляются тп дуг от а к вершинам следующего яруса, которые помечаются слева направо символами /11, /¿2,. ■., Ьт, Ы € Уг и Улг. Все листья дерева помечены терминальными символами, при этом само слово а получается обходом листьев дерева слева направо. Высотой дерева вывода называется наибольшая длина пути от корня до листа. Ярусы в дереве мы будем нумеровать с едииицы, т.е. ярус, на котором располагается корень дерева, имеет номер один, следующий -два и т.д.

Проиллюстрируем понятие дерева вывода на примере. Рассмотрим грамматику с двумя нетерминалами Ах, А?, тремя терминалами у, х\,х2 и следующими правилами :

Гц : Аг Л АхуАг, П2 : Аг ^Р Л,

Г21 • М А2Х1А2Х2, л 1-г/2 Л

т-22 : Л2 А,

где Л - пустое слово, 0 < р < 1. Такая грамматика порождает слова вида уУ\... уУп, где V; - правильные скобочные выражения от х\,х2, если отождествить XI с открывающей скобкой, а х2 с закрывающей. Тогда левый вывод гитпг12г21г22г22г21г22г22 порождает слово ух\х2ух\%2 (см. рис. !)•

X X

Рис. 1: Дерево вывода.

2Ахо А., Ульман Дж. Теория синтаксического анализа, переиода и компиляции. Том 1. М.: Мир, 1978.

Стохастическая КС-грамматика называется согласованной, если fon £ р(а) = 1,

где через |а| обозначается длина слова а. Согласованная грамматика порождает распределение вероятностей Р на множестве слов и определяет стохастический КС-язык С = (L,P). В дальнейшем будем рассматривать только согласованные грамматики.

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

Пусть к - число нетерминалов в рассматриваемой грамматике. Первые моменты a*-, i,j = 1,..., к грамматики определяются как aj = pusf,

где ó" - число нетерминалов Aj в правой части правила гц. Элемент aj представляет собой математическое ожидание количества нетерминалов Aj в правых частях правил, примененных к нетерминалу A¡. Матрица А = (а]) называется матрицей первых моментов. Важной характеристикой матрицы первых моментов является ее максимальный по модулю собственный корень (перронов корень). Будем обозначать его через г. Известно, что для согласованной грамматики г < 1.

Вторые моменты определяются как

= -sp),

где 5J1 - символ Кронекера (¿J = 1, <5J- = 0 при i^j).

Будем говорить, что нетерминал Aj следует за нетерминалом или что Ai предшествует Aj (и обозначать A¡ —> Aj), если из выводимо хотя бы одно слово, содержащее нетерминал Aj. Грамматика называется неразложимой, если для любых двух различных нетерминалов A¡ и Aj верно Ai —* Aj. В противном случае она называется разложимой. Классом нетерминалов назовем максимальное по включению подмножество К € Vjv, такое, что A¡ —* Aj для любых Ai,Aj € К. Будем говорить, что класс К\ предшествует классу (и обозначать К\ -< K¡), если для любых Ai € Ki, Ai € K<¡ верно Ai —> Лг. Очевидно, что множество нетерминалов Vn является объединением конечного числа непересекающихся классов.

'Севастьянов Б.А. Ветвящиеся процессы. М.: Наука, 1971.

Пусть О - стохастическая КС-грамматика. Через обозначим язык, порожденный грамматикой, которая получена заменой аксиомы исходной грамматики на нетерминал Д-. Через А обозначим множество деревьев вывода слов из Обозначим через вероятность множества дере-

вьев из Д, имеющих высоту больше чем Эту величину назовем вероятностью продолжения по аналогии с теорией ветвящихся процессов. Пусть - вероятность множества деревьев из £><, имеющих высоту ровно Ь. Очевидно, что Р{В\) = - 1) -

В работе рассматривается разложимая согласованная грамматика с двумя классами нетерминалов , Къ, причем К\ предшествует К?, и з 6 К-1. Обозначим к\ = кч = \Кг\, к\ + к2 — к. Будем считать,

что нетерминалы из К\ имеют номера из Кг - соответственно

кх + 1,... ,к. Для такой грамматики матрица первых моментов А имеет блочный вид:

где - матрица размером кх х к^, Л'3) - матрица размером к? х к?, а А^ -матрица размером кх х Дополнительно предположим (без ограничения общности), что матрицы А« ЛИ, положительны.

Рассмотрим стохастический КС-язык С = (Ь, Р), порожденный грамматикой Ь с однозначным выводом. Под кодированием языка С. будем понимать инъективное отображение / : Ь —» {0,1}+. Образ слова при отображении / назовем его кодом. Множество всех кодирований языка С, обозначим за Р(£).

Под энтропией языка С. будем понимать величину

где через р(а) обозначается вероятность слова a, a |а| - длина слова а. Здесь и далее под log будем понимать логарифм по основанию 2. Если энтропия определена и конечна, то будем писать для краткости Н{£) — - £ р(а) ■ logp(a).

a€b

Этот подход к определению стоимости кодирования был рассмотрен Л.П. Жильцовой в неразложимом случае. В некотором смысле такая постановка задачи эквивилеитиа задаче кодирования длинных слов, порожденных эргодическим источником, которая была рассмотрена К.Шеино-ном.

(1)

tf(¿) = -lim £ р(а) • logp(a),

Л'—»oo

Для произвольного стохастического языка £ (не обязательно контекстно-свободного), предел математического ожидания длины кодового слова

M(£,/) = lim £ К*) ■!/(<*) I

oeL,|o|<N

назовем средней длиной кода для кодирования /. Значение М*(£) = ^inf М(£,/) будем называть оптимальной средней длиной кода.

II. Во второй главе исследуется связь между энтропией и средней длиной кода для произвольного стохастического языка. Л.П.Жильцовой доказано, что если энтропия Я(£) конечна, то оптимальная средняя длина кода М*(С) тоже конечна и удовлетворяет неравенствам

Я(£)/2 < М*(С) < Н(С) + 1.

Во второй главе получена более точная нижняя оценка для М*(£), которая выполняется для больших значений энтропии, а именно:

1) если энтропия стохастического языка £ = (L, Р) удовлетворяет неравенству 1 < Я(£) < оо, то выполняется неравенство:

Я(£) < (l + log (Jf^l J) • M*{C) + log{M'{C) - 1);

2) для любого H, > 1 существует такой стохастический язык £, для которого Л (С) = Н,, а неравенство пункта 1) превращается в равенство (теорема 2.2);

3) отношение Л/*(£)/Я(£) достигает' нижней оценки 1/2 только при Я(£) = Я, = 4. При Я(£) ->сюи при Я(£) —» 1 отношение М*(£)/Я(£) возрастает и стремится к верхней оценке 1 (теорема 2.3).

III. В третьей главе рассматривается разложимая грамматика с двумя классами нетерминалов в докритическом случае (перронов корень г < 1). Сначала для соответствующего грамматике ветвящегося процесса устанав-. ливается асимптотика вероятностей продолжения.

Обозначим за г?', и" левые, за и',и" правые собственные вектора матриц и t соответствующие их перроиовым корням г' и г" при нормировке v'u' = v"u" = 1, Et г>,- = Ei г/' = 1 (левый собственный вектор матрицы всегда считаем вектором-строкой).

Установлено, что для случая перронова корпя кратности один вероятности продолжения имеют такую же асимптотику, как и в неразложимом

случае, а для перронова корня кратности два их асимптотика имеет другой вид, а именно:

~ Ьсои^г', г < ки

<?,(г) ~ сои'!_ку, г > кг,

где г-перронов корень, со > 0 - некоторая константа, и Ь определено формулой

Ъ = у'А^и"/т (2)

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

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

Обозначим через М(£),.0(£) соответственно математическое ожидание и дисперсию случайной величины В случае кратного перронова корня математическое ожидание числа применений ду(<,т) правила гу в дереве вывода высоты t на ярусе т линейно зависит от т/4 при ^т —> оо, и при этом ограничено сверху константой:

для г < кг,

ЩочМГ- Ц- ■ (г • уи^/г + с>1) + (г - т) ■ с;)

для < г < к. Здесь - константы, определяемые по грамматике и

учитывающие число нетерминалов в правых частях правил, С?" - константы, определяемые вторыми моментами грамматики (теорема 3.5.1).

Доказано, что для правил, применяемых к нетерминалам из К\, величина М (%•(<, т)) убывает, а для правил, применяемых к нетерминалам из К^, может и убывать, и возрастать (см. пример параграфа 3.7). При этом, как и в неразложимом случае, имеет место перераспределение частот правил, т.е. при t —+ оо правила, порождающие больше нетерминальных символов, используются в выводе слов чаще, что, по-видимому, нужно для достижения большей высоты дерева вывода. Величины Л/(ду(4,т)) не меняются при замене аксиомы на любой нетерминал из класса Кг.

Введем константы и>}™\ т = 1,2, г, j = 1,..., к равенствами

и®-»,-4] = РцС\

= Рц ■ (с; + при г<ки

= при г > ки (3)

4? = Рц ■ (С" + С^^/г) при i>ku

ыу = с^/З при ¿<£ь

< (1) . (2)\ /о • ^ г. ^ >

= +Шу')/2 при г > «1.

Пусть 5^(4) - число правил Гу в дереве вывода высоты г. В работе доказано, что математическое ожидание величины Sij{t)/t, т.е. среднее число правил гу, приходящихся на один ярус дерева вывода высоты 4, стремится к константе при 4 —> оо:

А/(5Ь(*)/0шу, г = 1,. ..

где величины определены формулами (4) (теорема 3.5.2).

Дисперсия этой величины для случая кратного перронова корня г < 1 не стремится к 0 при 4 —* оо в отличие от неразложимого случая, а именно, справедливы соотношения

£>(5у(г)Л) - (<4})2 /12 ПРИ { ^ £>(5у(*)Л) — (42) " 4Р)2 /12 ПРИ * >

где величины а>у' определены формулами (3) (теорема 3.6.1).

IV. За Ь* обозначим множество слов языка Ь, деревья вывода которых имеют высоту 4. Черезр<(а), а € Ь1, обозначим условную вероятность слова а в множестве слов Ь*, она равна р(а)/Р(Ьг). Через С* — (.£/, Я() обозначим множество слов с определенным на нем выше распределением вероятностей Р{. Стоимостью кодирования / е -^ОС) назовем величину

если этот предел существует. Через -Р»(£) обозначим множество всех кодирований, для которых величина С(£, /) определена. Стоимостью оптимального кодирования назовем величину С*(£) = ^ т^ С[С, /).

С помощью найденных асимптотик для числа применений правил на ярусе дерева вывода и во всем дереве вывода в докритическом случае установлено, что энтропия Н(£*) множества слов, имеющих деревья вывода

высоты t, асимптотически линейно зависит от I, как и в неразложимом случае:

Здесь величины определены формулами (4), ару - вероятность применения правила гу (теорема 3.8.1).

Найденная асимптотика для Н(С1) позволила получить нижнюю оценку С* {С) для стоимости оптимального (двоичного) кодирования слов языка, порождаемого рассматриваемой грамматикой:

где и>у определены формулами (4), ру - вероятность применения правила Гу, а /у - число терминальных символов в правой части правила гу (теорема 3.8.2).

Кроме того, показано, что эта оценка является асимптотически точной, то есть существует кодирование, стоимость которого сколь угодно близка к полученной оценке С*(С). Для этого использовалась схема кодирования, предложенная Л.П. Жильцовой для неразложимого случая, которая состоит в кодировании последовательности правил грамматики, образующих левый вывод слова. При этом для множества правил Л{ с одинаковой левой частью А( применяется схема префиксного кодирования Шеннона с учетом найденных математических ожиданий числа применений правил в деревьях вывода. Код слова получается конкатенацией кодов правил, примененных при его выводе. Доказано, что стоимость такого кодирования стремится к С* {С) при укрупнении правил грамматики. Такое кодирование существенно использует и вероятностные и структурные свойства языка.

В случае простого перронова корня г < 1 энтропия //(£') множества слов, имеющих деревья вывода высоты и стоимость оптимального кодирования имеют тот же вид, что и в неразложимом случае.

V. В четвертой главе рассмотрена разложимая грамматика с двумя классами нетерминалов в критическом случае (перронов корень г = 1).

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

С* (С) =

1овг-£;,^а>у1одру

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

При условии В1В2 > 0, где ВиВ2 определяются вторыми моментами грамматики и даны формулами

при Ь —* оо верпы следующие асимптотические равенства: ~ ч'МГ1!\ Рт ~ при г < къ

2и" 2и'! ,

~ ' т ~ в^' при к1 <г" -

где ко = а ^ определено формулой (2) (теорема 4.1.1.2).

Таким образом, вероятности продолжения С}¿(¿) при i <кх больше, чем £?<(£) при i > кх.

В случае кратного перропова корня асимптотика математического ожидания М(£у(4)) числа применений правила гу, г = 1.....к, 7 = 1,..., ггг

в деревьях вывода высоты Ь при (-»оо была найдена в результате решения полученных рекуррентных уравнений. Доказано, что при г' = г" = 1 и В!В2 > 0 справедливы следующие асимптотические равенства:

М(5о-(0) ~ РцВ212/4, г > *п,

где Ь введено формулой (2), В\,В2 определяются формулами (5), а ру -вероятность применения правила гу (теорема 4.1.2.1).

Из теоремы следует, что в случае кратного перронова корня г = 1 для разложимой грамматики с двумя классами нетерминалов количество правил, примененных к нетерминалам второго класса, имеет такую же (0(£2)) асимптотику, как и в неразложимом случае, а количество правил, примененных к нетерминалам первого класса, значительно меньше (0(£)). Как и в неразложимом критическом случае, величины А/(5у(£)) пропорциональны первоначальным вероятностям применения правил ру.

VI. С помощью установленных в случае кратного перронова корня г = 1 свойств деревьев вывода найдена асимптотика величины Н{СЬ) при £ —► оо:

Я(£4) = £ г^кМ^) ■ В** ■ (1+о(1))/4, 1>к\

где Н(11{) — — ру \ogPij - энтропия множества правил Л,-, н В\Вг > О (теорема 4.1.3.1).

С использованием этой теоремы и результатов главы 2 найдена нижняя оценка стоимости кодирования С'(С) для г = г' = г" = 1, В1В2 > 0:

где Н(Н{) - энтропия множества правил Я,-, а - среднее число тер-

миналов в правой части правил из Л,- (теорема 4.1.3.2).

Таким образом, в случае кратного перронова корня нижняя оценка стоимости кодирования определяется только свойствами правил, применяемых к нетерминалам из класса К2, и совпадает со стоимостью оптимального кодирования для неразложимой грамматики, порожденной нетерминалами класса К<х. Это вызвано тем, что пропорция правил, применяемых к нетерминалам из К\ в деревьях вывода высоты стремится к нулю при Ь —* оо.

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

VII. Во второй части главы 4 рассматривается случай простого перронова корня т — 1. Оказывается, что в этом случае, как и при г < 1, асимптотики для величин а также математических ожиданий числа применений правил на фиксированном ярусе т дерева вывода из

и во всем дереве имеют такой же вид, как и в неразложимом случай.

Пусть М{х{{Ь, г)) - математическое ожидание числа нетерминалов А{ па ярусе г в деревьях вывода высоты 4, а М(5у(£, т)) - математическое ожидание числа применений правил гу на ярусе т в деревьях вывода высоты г. Доказано, что при г' ф г" величины т)), т)), А/(£у(<))

имеют тот же вид, что и в неразложимом случае.

В случае г' < г" = 1 для величин М(х^1,т)), г)), M(Sij(t))

получены следующие уточненные оценки при г < к\ и i, т —> оо:

M(9ii(i,r))<C72.(i2(rr/(i-r)). для некоторых С\, Сч, > 0, и

M(Sij(t)) -» ру • (Sy + va ■ £ GnzUj/uu

m

где 5y, Gm, г* - вычисляемые по грамматике константы (теорема 4.2.3.2).

Таким образом, в случае 0 < г' < г" = 1 в дереве вывода на каждом ярусе пропорция нетерминалов из класса К\ стремится к нулю. Оценки для Н(£*) и С* (С) в этом случае имеют тот же вид, что и для неразложимой грамматики, порожденной только нетерминалами из Кг-

Выражения для энтропии Н{С1) множества слов £' и нижней оценки стоимости кодирования С* (С) при 0 < г' ^ г" = 1 имеют такой же вид, как и в неразложимом критическом случае, причем схема кодирования, использованная для случая кратного перронова корня, является асимптотически оптимальной и в этом случае.

Список публикаций по теме диссертации

1. Борисов А.Е. О свойствах стохастического КС-языка, порожденного грамматикой с двумя классами нетерминальных символов// Дискретный анализ и исследование операций. Серия 1, т.12, N3. Новосибирск: Издательство Института математики СО РАН, 2005. С.3-31.

2. Борисов А.Е. Кодирование слов стохастического КС-языка, порожденного разложимой грамматикой с двумя нетерминалами// Вестник Нижегородского университета им. Н.И. Лобачевского. Серия Математика вып. 1(2), 2004. С. 18-28.

3. Борисов А.Е. Закономерности в деревьях вывода для стохастической разложимой КС - грамматики// Труды V Международной конференции "Дискретные модели в теории управляющих систем". М.: Изд. отдел ВМиК МГУ, 2003. С. 15-17.

4. Борисов А.Е. О свойствах стохастического КС-языка, порожденного разложимой грамматикой// Материалы XIV Международной школы-семинара "Синтез и сложность управляющих систем". Н. Новгород, 2003. С. 15-18.

5. Борисов А.Е. О свойствах слов языка, порожденного разложимой стохастической КС-грамматикой с двумя нетерминалами. Критический случай// Материалы VIII Международного семинара "Дискретная математика и ее приложения". М.: Изд. мех-мат. ф-та МГУ, 2004. С. 408-410.

6. Борисов А.Е. О числе применений правил стохастической КС-грамматики// Проблемы теоретической кибернетики. Тезисы докладов XIV Международной конференции. Изд. мех-мат. ф-та МГУ, 2005. С. 22.

7. Борисов А.Е, Жильцова Л.П. О закономерностях в словах стохастического КС - языка, порождаемого разложимой грамматикой// Труды VII Международной конференции "Дискретные модели в теории управляющих систем". М.: Изд. отдел ВМиК МГУ, 2006. С. 36-39.

8. Borisov А.Е. Optimal Coding Cost for Stochastic CF-Language Induced by Decomposable Grammar// VI International Conference on Mathematical Modeling/Book of abstracts, N.Novgorod, 2004. pp. 72.

Подписано в печать 30.06.06. Объем 1п.л. Тираж 100 экз. Заказ 240

Нижегородская государственная сельскохозяйственная академия, 603107, г. Н.Новгород,

пр.Гагарина, 97. Типография НГСХА.

1 Введение

1.1 Постановка задачи и общая характеристика работы

1.2 Основные определения и обозначения.

1.3 Формулировка основных результатов

2 Оценка средней длины кода для стохастического языка

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

3.1 Основные определения и обозначения.

3.2 Вероятности продолжения.

3.3 Закономерности в деревьях вывода слов. Случай простого перронова корня.

3.4 Закономерности в деревьях вывода слов. Случай кратного перронова корпя.

3.5 Оценки моментов второго и более высоких порядков для кратного перронова корня.

3.6 Дисперсия числа применений правил в деревьях вывода

3.7 Пример грамматики с двумя классами нетерминалов

3.8 Оценка стоимости оптимального кодирования.

3.9 Алгоритм асимптотически оптимального кодирования

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

4.1 Случай кратного перронова корня.

4.1.1 Вероятности продолжения.

4.1.2 Математические ожидания числа примсиеиий правил в деревьях вывода.

4.1.3 Энтропия и стоимость оптимального кодирования

4.1.4 Алгоритм оптимального кодирования.

4.2 Случай простого перронова корня.

4.2.1 Вероятности продолжения и вероятности деревьев вывода фиксированной высоты.

4.2.2 Распределение нетерминалов на фиксированном ярусе дерева вывода.

4.2.3 Математические ожидания числа применений правил в деревьях вывода.

4.2.4 Алгоритм оптимального кодирования.

1.1 Постановка задачи и общая характеристика работы

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

Хорошо известны и широко используются на практике алгоритмы побуквенного кодирования, которые учитывают только частоты букв. Наиболее известными являются алгоритмы Хаффмана [32], Фапо [23], Шеннона [22], алгоритм арифметического кодирования [30], [31], которые применяются при отсутствии априорных знаний о структуре кодируемых слов (сообщений). Существуют также динамические версии этих алгоритмов, которые в процессе работы обновляют таблицу частот символов. Такие алгоритмы строят вероятностную модель языка в процессе получения па вход новых символов.

Хорошо известны также словарные методы сжатия, основанные на учете часто повторяемых фрагментов в кодируемом тексте. Здесь следует выделить алгоритмы Лемпеля-Зива LZ77 и LZ78 [28],[29], и их многочисленные модификации.

Задача кодирования, учитывающего синтаксические свойства сообщений, была впервые рассмотрена К.Шенноном в [22]. Им был рассмотрен вероятностный источник сообщений с конечным числом состояний. Шеннон доказал, что в случае эргодичности источника все сообщения большой длины N разбиваются на два класса: множество сообщений, вероятность которых стремится к 0 при N —> оо, и множество оставшихся сообщений с приблизительно одинаковыми вероятностями и буквенным составом. Такой источник фактически соответствует неразложимому марковскому процессу с конечным числом состояний. При построении алгоритмов кодирования Шенноном рассматривались в основном вероятностные свойства слов, хотя введенное им блочное кодирование косвенно учитывает и структурные свойства.

Вопросы кодирования слов с учетом структурных свойств (синтаксиса) рассматривались А.А.Марковым в [14], [15], [16]. Он поставил задачу кодирования не па всем множестве слов алфавита, а па некотором подмножестве слов, описываемом синтаксическими правилами. Для описания синтаксиса рассматривались в основном регулярные источники. Марков показал, что учет синтаксиса регулярных языков позволяет увеличить степень сжатия и уменьшить вычислительную сложность алгоритмов кодирования [16].

Ближайшим обобщением класса языков, порожденных регулярными источниками, являются языки, порожденные стохастическими кон-текстпо-свободиыми (КС-) грамматиками. Неразложимые стохастические КС-грамматики рассматривались Л.П.Жильцовой в работах [10], [И], [12]. В этих работах были получены следующие результаты. В докритичсском случае (перронов корень матрицы первых моментов меньше единицы) для слов большой длины стохастического КС-языка, порождаемого такой грамматикой, установлены свойства, аналогичные свойствам слов, генерируемых эргодическим конечным источником [22].

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

В данной работе аналогичные исследования проводятся для грамматики с разложимой матрицей первых моментов и двумя классами нетерминальных символов. Рассматривается докритичсский и критический случаи. Для такой грамматики установлены закономерности в деревьях вывода фиксированной высоты £ для слов языка при Ь —»■ оо, то есть найдены математические ожидания числа применений правил грамматики на каждом ярусе дерева вывода и во всем дереве, а также найдена суммарная вероятность таких слов. Особое внимание уделяется случаю кратного перропова корня, поскольку именно тогда появляются существенные отличия от неразложимого случая. С использованием этих закономерностей найдена асимптотическая формула для энтропии множества слов, имеющих деревья вывода фиксированной высоты.

Полученные результаты использованы для получения нижней оценки стоимости двоичного кодирования слов языка, порожденного рассматриваемой грамматикой. Задача оптимального кодирования рассматривалась в том же виде, что и в [12]. Под оптимальным кодированием понималось взаимпо-одпозпачнос кодирование множества всех слов языка, которое позволяет хорошо сжимать длинные слова (имеющие деревья вывода большой высоты). Была найдена стоимость оптимального кодирования для рассматриваемого языка. Доказано, что алгоритм блочного кодирования, использованный Жильцовой в [12] для неразложимого случая, является асимптотически оптимальным и для рассматриваемой в данной работе грамматики. Применяемый алгоритм кодирования использует состав правил в выводе слова, таким образом учитывая синтаксические свойства.

Также были изучены общие вопросы кодирования стохастических языков, получена нижняя оценка для средней длины кода в зависимости от энтропии, которая является более точной, чем полученная в [12], при больших значениях энтропии. Эта оценка была использована для получения нижней оценки стоимости кодирования стохастического КС-языка.

5. Заключение

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

В работе рассматривается традиционная постановка задачи экономного кодирования на множестве "длинных"сообщепий, которую рассматривал К.Шеннон [22]. Мерой эффективности кодирования является его стоимость, определяемая как число двоичных разрядов, требуемых для кодирования одной буквы сообщения. В качестве множества длинных слов рассматривалось множество слов КС-языка, деревья вывода которых имеют высоту Ь при £ —> оо.

В диссертационной работе получены следующие основные результаты.

1) Найдены нижние оценки средней длины кода для произвольного стохастического языка в зависимости от энтропии, которые являются более точными при больших значениях энтропии, чем полученные в [33].

2) Для стохастического КС-языка, порожденного разложимой грамматикой с двумя классами нетерминальных символов, выделены два случая, определяемых значением перронова корня г матрицы первых моментов, а именно: а) Докритический случай, при г < 1, б) Критический случай, при г = 1.

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

3) Описан алгоритм блочного кодирования деревьев вывода, который был ранее применен в [12] для неразложимого случая, и доказана его оптимальность па множестве слов стохастического КС-языка, порожденного рассматриваемой разложимой грамматикой.

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

Оказывается, что при г < 1 математические ожидания числа применений правил на фиксированном ярусе не стремятся к константе для разных ярусов, и дисперсия среднего числа применений каждого правила на один ярус дерева вывода высоты I не стремится к нулю при Ь —► оо в отличие от неразложимого случая. Для случая кратного перроиова корня г = 1 свойства грамматики определяются свойствами правил, применяемых к нетерминалам второго класса.

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

1. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. Том 1. М.: Мир, 1978.

2. Борисов А.Е. О свойствах стохастического КС-языка, порожденного грамматикой с двумя классами нетерминальных символов// Дискретный анализ и исследование операций. Серия 1, т.12, N3. Новосибирск: Издательство Института математики СО РАН, 2005. С.3-31.

3. Борисов А.Е. Кодирование слов стохастического КС-языка, порожденного разложимой грамматикой с двумя нетерминалами// Вестник Нижегородского университета им. Н.И. Лобачевского. Серия Математика вып. 1(2), 2004. С. 18-28.

4. Борисов А.Е. Закономерности в деревьях вывода для стохастической разложимой КС грамматики// Труды V Международной конференции "Дискретные модели в теории управляющих систем". М.: Изд. отдел ВМиК МГУ, 2003. С. 15-17.

5. Борисов А.Е. О свойствах стохастического КС-языка, порожденного разложимой грамматикой// Материалы Международной школы-семинара "Синтез и сложность управляющих систем". Н. Новгород, 2003. С. 15-18.

6. Борисов А.Е. О числе применений правил стохастической КС-грамматики// Проблемы теоретической кибернетики. Тезисы докладов XIV Международной конференции. Изд. мех-мат.' ф-та МГУ, 2005. С. 22.

7. Борисов А.Е, Жильцова Л.П. О закономерностях в словах стохастического КС языка, порождаемого разложимой грамматикой// Труды VII Международной конференции "Дискретные модели в теории управляющих систем". М.: Изд. отдел ВМиК МГУ, 2006. С. 36-39.

8. Гантмахср Ф.Р. Теория матриц. М.: Наука, 1967.

9. Жильцова Л.П. Закономерности применения правил грамматики в выводах слов стохастического контекстно-свободного языка// Математические вопросы кибернетики. Вып.9. М.: Наука, 2000. С.101-126.

10. Кричевский P.E. Сжатие и поиск информации. М.:Радио и связь, 1989.

11. Марков A.A. Введение в теорию кодирования. М.: Наука, 1982.

12. Марков A.A., Смирнова Т.Г. Алгоритмические основания обобщеино-прсфиксиого кодирования// Доклады АН СССР,т. 274 N4, С.790-793, 1984.

13. Марков A.A. О неукоторых мерах сложности м эффективности в алфавитном кодировании. Матем. вопросы кибернетики вып. G, с.348-352, М.: Наука, Физматгиз, 1996.

14. Севастьянов Б.А. Ветвящиеся процессы. М.: Наука, 1971.

15. Фсллер В. Введение в теорию вероятностей и се приложения, том 1. М.:Мир, 1984.

16. Фихтеигольц Г.М. Основы математического анализа. Том 2. М.: Наука, 1968.

17. Фу К. Структурные методы в распознавании образов. М.: Мир, 1977.

18. Харрис Т. Теория ветвящихся случайных процессов. М.:.Мир, 1966.

19. Шеннон К. Математическая теория связи. М.: ИЛ, 1963.

20. Яблонский C.B. Введение в дискретную математику. М.:Наука, 1986.

21. Сагитов С., Ватутин В.А. Разложимый критический ветвящийся процесс с двумя типами частиц// Вероятностные проблемы дискретной математики. Труды мат.инст. Стеклов. 177 (1986), стр. 3-20.

22. Сагитов С., Ватутин В.А. Разложимый критический ветвящийся процесс Беллмана-Харриса с двумя типами частиц. 1//Теор. Вероятности. 33(1988), N3, стр. 460-472.

23. Сагитов С., Ватутин В.А. Разложимый критический ветвящийся процесс Беллмана-Харриса с двумя типами частиц.Н//Теор. Вероятности. 34(1989), N2, стр. 216-227.

24. Borisov А.Е. Optimal coding cost for stochastic CF-languagc induced by decomposable grammar// VI International Conference on Mathematical Modeling/Book of abstracts, N.Novgorod, 2004. pp. 72.

25. Ziv J.,Lempel A. Compression of individual sequences via variablerate coding// IEEE Trans.Inf.Theory IT-24,5 (Sept. 1978), p.530-536.

26. Ziv J.,Lempel A. A universal algorithm for sequential data compression. IEEE Trans. Inf. Theory IT 23,3 (1977), p.337-343.

27. Jorma Rissanen, Glen G.Langdon. Universal modeling and coding. // IEEE Transactions on Information Theory, V.21, N l,pp 12-23,1981.

28. Jorma Rissanen. Generalized Kraft inequality and arithmetic coding// IBM Journal Res.Devclop, 1976. V.20, N3, p. 198-203.

29. Haffrnan D.A. A method for construction of minimum-redundancy codes// Proc. IRE 1952, V.40, N.10, pl098-1101.

30. Zhiltsova L. On Entropy and Optimal Coding Cost for Stochastic Language// Fundamcnta Informaticae,V.36,pp.285-305,1998.