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

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.