Кодирование стохастических контекстно-свободных языков тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

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

Жильцова Лариса Павловна

КОДИРОВАНИЕ СТОХАСТИЧЕСКИХ КОНТЕКСТНО-СВОБОДНЫХ ЯЗЫКОВ

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

Автореферат

диссертации на соискание ученой степени доктора физико-математических наук

Нижний Новгород, 2004

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

Официальные оппоненты:

доктор физико-математических наук, профессор В. К. Леонтьев

доктор физико-математических наук, профессор М. А. Федоткин

доктор физико-математических наук, профессор Л. А. Шоломов

Ведущая организация:

Казанский государственный университет им. В. И. Ульянова-Ленина

Защита состоится "¿4" О в 2004 г. в /¿час. ^юи.

на заседании диссертационного совета Д 212.166.06 при Нижегородском государственном университете им. Н. И. Лобачевского по адресу:

603950 Нижний Новгород, пр. Гагарина, д. 23, корпус 2, ауд. С диссертацией можно ознакомиться в библиотеке ННГУ.

Автореферат разослан " 13" 05 2004 г.

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

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

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

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

Возможности сжатия информации определяются ее вероятностными и структурными свойствами.

Начало математическому исследованию задач экономного (в смысле сжатия информации) кодирования было положено работами К. Шеннона в 40-х годах XX века. В работе "Математическая теория связи К.Шеннон рассмотрел задачу кодирования сообщений, генерируемых эргодическим источником с конечным числом состояний.

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

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

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

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

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

1) исследование зависимости эффективности кодирования от структурных и вероятностных свойств о ~ словами

стохастического КС-языка;

2) развитие методов теории кодирования, относящихся к алгоритмам построения экономных кодов.

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

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

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

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

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

Результаты диссертационной работы включены в курс по теоретическим основам информатики, который читается на математическом факультете НГПУ.

Апробация-работы. Результаты диссертации докладывались по частям на Международных семинарах по дискретной математике и ее приложениям в МГУ в 1998, 2001 и 2004 годах, на XI, XII и ХШ Международных конференциях по проблемам, теоретической кибернетики в 1996,1999 и 2002 годах, на III, IV и V Международных конференциях "Дискретные модели в теории управляющих системпв 1998, 2000 и 2003 годах, на Межгосударственных школах-семинарах по синтезу и сложности управляющих систем в 1998, 2000, 2001 и 2002 годах, на III Международной конференции "Достижения в

теории языков"в 1997 г. (Греция, Салоники), на городском семинаре по дискретной математике в Нижегородском государственном университете и на итоговых научных конференциях Нижегородского педагогического университета.

В целом работа докладывалась на семинаре по математической кибернетике в МГУ, на городском семинаре по дискретной математике в Нижегородском государственном университете и на научных семинарах в НГПУ.

Работа поддержана грантами РФФИ 98-01-00599 и 01-01-00464.

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

Структура диссертации. Диссертация состоит из введения, шести глав и списка литературы. Объем диссертации составляет 142 страницы машинописного текста. Список литературы содержит 43 наименования.

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

I. Диссертационная работа включает введение и шесть глав.

Во введении обосновывается актуальность темы исследования и приводится краткое содержание работы.

В первой главе вводятся основные определения и понятия, относящиеся к стохастическим языкам и стохастическим КС-языкам.

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

Для краткого изложения результатов предварительно уточним некоторые понятия. Заметим, что здесь используется несколько упрощенная система понятий. Пусть Ь - множество слов (язык) в некотором алфавите В с заданным на словах языка распределением вероятностей Р. Под стохастическим языком С понимается пара (Ь, Р).

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

Стохастическая КС-грамматика — это система б = Л, л),

где Ух и Уц - конечные множества терминальных и нетерминальных

символов (терминалов и нетерминалов) соответственно; S G V^ -аксиома, R - множество правил.

Каждое правило имеет вид

nj : А{ ßtj, j = 1

где Ai G Vj/f, ßij G (Ут U VnY и Ptj ~ вероятность применения правила Гу, которая удовлетворяет следующим условиям:

0<P,j <1и =

Применение правила грамматики к слову в алфавите V^-UVjv состоит в замене вхождения нетерминала из левой части правила на слово, стоящее в его правой части. КС-язык определяется как множество всех слов в алфавите Vt, каждое из которых может быть получено из аксиомы s с помощью конечного числа применений правил грамматики.

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

Грамматика G называется согласованной, если

lim У

ЛГ-wo Vf

лб£,И£ЛГ

В работе рассматриваются согласованные КС-грамматики. Согласованная КС-грамматика G индуцирует распределение вероятностей Р на множестве слов порождаемого КС-языка L и определяет стохастический КС-язык С — (L, Р).

Процесс порождения слов стохастического КС-языка можно описать как, ветвящийся- процесс \ Важной характеристикой при описании является матрица первых моментов, которая строится по грамматике.

1Севастъхю« В. А. Вехмпцюса процессы. — \Lz Наук», 1971.

Ыа) = 1

Для матрицы А первых моментов ее элемент а} определяется как где величина равна числу нетерминальных символов А[ в правой части правила Г;у. По смыслу значение элемента о) есть математическое ожидание числа нетерминальных символов А[ в правых частях правил грамматики с одинаковым нетерминалом А{ в левой части.

Важной характеристикой матрицы первых моментов является максимальный по модулю собственный корень (перронов корень). Обозначим его через Г. Известно, что для согласованной КС-грамматики г < 1.

II. Пусть С, — стохастический язык. Под кодированием- языка С понимается инъективное отображение / : Ь —> {0,1}+, где {0,1}+ — множество всех непустых двоичных последовательностей.

В диссертационной работе рассмотрено две постановки задачи экономного кодирования.

В главе 2 в качестве стоимости кодирования рассматривается математическое ожидание длины закодированного слова языка, т.е. под стоимостью кодирования стохастического языка понимается величина

<?(£,/)= Ьп £ р(а).|/(а)|.

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

Подобное определение стоимости кодирования рассматривалось, например, для конечного множества слов в монографии Р. Е. Кричевского 2.

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

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

2 КрячвжкиЯ Р. Е. Сжатие ы поиск квфорпцщв. — М.: Ради» • епзь, 1989.

стохастического языка С понимается величина

я(£) = -ищ £ р(«)-1оеК«)

(логарифм берется по основанию 2).

В диссертационной работе доказано, что для произвольного бесконечного стохастического языка С — (Ь, Р), при условии существования конечного значения энтропии Н(С), стоимость оптимального- кодирования Сц[С) имеет конечное значение и удовлетворяет неравенствам

±Н(£)<С0(С)<Н(С) + 1

(теорема 2.2.1).

Показано также, что стоимость оптимального кодирования произвольного стохастического языка имеет конечное значение тогда и только тогда, когда конечное значение имеет энтропия языка (следствие 2.2.1).

Для класса стохастических КС-языков получены следующие результаты:

1) Для стоимости оптимального кодирования может быть реализован весь спектр значений между нижней и верхней границами (теорема 2.2.3).

2) Стоимость оптимального кодирования и энтропия стохастического КС-языка имеют конечное значение тогда и только тогда, когда перронов корень Г матрицы первых моментов строго меньше единицы (следствие 2.3.1).

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

3) Для произвольной стохастической КС-грамматики О с однозначным выводом в случае, когда получена следующая система линейных уравнений (теорема 2.3.1):

Я (£) = Я(Я,0 +£<4 (Х = 1,...Д),

в которой #(£■) - энтропия языка порождаемого грамматикой б,-, получаемой из исходной грамматики О заменой аксиомы на нетерминальный символ А{, и -Н^-й;) = — р^- log Ру (для исходной грамматики С полагается в = С?х).

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

III. В главах 3-6 исследуются вопросы, связанные с традиционной постановкой задачи экономного кодирования, которую исследовал К. Шеннон для конечного эргодического источника в классической работе "Математическая теория связи".

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

Шеннон показал, что для конечного эргодического источника:

1) Все сообщения достаточно большой длины разбиваются на две группы: маловероятные и высоковероятные (вероятность каждого сообщения приблизительно равна где Н{1) - энтропия источника

/);

2) Стоимость любого кодирования, имеющего однозначное декодирование, ограничена снизу величиной

3) Для любого е > 0 существует равномерное (блочное) кодирование -/ такое, что его стоимость Сг{1) удовлетворяет неравенству <

Н{1) + £.

В диссертационной работе аналогичное исследование проведено для стохастических КС-языков.

В главах 3-6 рассматриваются грамматики с неразложимой и непериодической матрицей первых моментов. Такое свойство матрицы первых моментов аналогично свойству эргодичности конечного источника, которое ввел К. Шеннон.

В качестве множества длинных сообщений выбрано множество слов стохастического КС-языка, каждое из которых имеет дерево вывода 3 фиксированной высоты

3 Аю> А-, Улыпа Дж. Теория синтаксического шло», пгргмда • кокпняяцяк. Том 1. — Мл Мир, 1978.

Дерево вывода строится по левому выводу слова следующим образом. Корень дерева помечается аксиомой 5. Пусть при выводе слова а на очередном шаге в процессе левого вывода применяется правило А{ ^ Ь^Ь^ ...Ь^,, где Ьц € УцНУт (I = 1,...,т). Тогда из самой левой вершины-листа дерева, помеченной символом А,- (при обходе листьев дерева слева направо), проводится т дуг в вершины следующего яруса, которые помечаются слева направо символами соответственно. После построения дуг и вершин для всех правил грамматики в выводе слова языка все листья дерева помечены терминальными символами и само слово получается при обходе листьев дерева слева направо.

Высотой дерева называется максимальная длина пути от корня к листу.

Понятие дерева вывода проиллюстрируем на следующем примере.

Рассмотрим грамматику

Со = {Л}, Я, Л),

в которой множест гх :

гг : N нГ А (А - пустое слово).

На рисунке изображено дерево вывода в грамматике Go. Ему соответствует левый вывод Высота дерева вывода равна 4.

Заметим, что сообщения, генерируемые конечным эргодическим источником, являются словами регулярного языка с некоторыми определенными свойствами. Такой регулярный язык может быть описан КС-грамматикой, так как класс регулярных языков содержится в классе КС-языков. Каждому слову длины N при этом описании соответствует дерево вывода высоты N. Поэтому наш выбор множества слов стохастического КС-языка, имеющих деревья вывода высоты I, аналогичен выбору множества слов длины N для эргрдического источника.

Под кодированием языка С, как и ранее, понимается инъективное отображение / : Ъ -> {0,1}+.

Стоимостью кодирования по Шеннону называется величина

И' М

где Ь1 - множество слов из Ь, имеющих деревья вывода высоты I, и р»(<*) - условная вероятность слова а на множестве Ь*.

Корректность определения С(£,/) нуждается в обосновании, так как предел может не существовать.

Далее стоимость кодирования по Шеннону называется просто стоимостью кодирования. Величина характеризует число

двоичных разрядов, приходящихся на кодирование одного символа слова языка.

Стоимостью оптимального кодирования языка называется величина

С0(£) = ^С(С,/).

Через Р(С) здесь обозначается класс всех инъективных отображений из С в {0,1}+, для которых существует С(С,/).

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

1) докритический случай, при

2) критический случай, при

IV. Для докритического случая в главе 3 установлены некоторые важные свойства деревьев вывода высоты аналогичные свойствам слов, генерируемых эргодическим конечным источником.

Перечислим кратко эти свойства.

1) Математическое ожидание числа применений правила

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

в котором Ру вероятность правила Гу, заданная в исходной грамматике, I/ = («1,...,«*) и V = (»!,..., ) — правый и левый положительные собственные векторы для перронова корня г при нормировке и«**» = 1»

- число нетерминальных символов Аш в правой части правила и В{- константа, определяемая формулой

(теорема 3.3.2) (здесь - вторые моменты и в™(г — 1) - элементы матрицы Лг-1).

Следовательно, стремится к константе при т —> ОО,

< - Т 00.

2) Математическое ожидание не зависит от аксиомы грамматики.

3) Величина ^^ИтЛ»»^ определяется правой частью правила Гу и имеет большее значение для тех правил, которые содержат в правой части большее количество нетерминальных символов. Таким образом, в деревьях вывода большой высоты происходит перераспределение частот применения правил: правила грамматики, содержащие в правой части большее количество нетерминальных символов, применяются чаще по сравнению с вероятностями правил, заданными в исходной грамматике. Этим, по-видимому, обеспечивается достижение большой высоты дерева вывода.

4) Рассмотрим случайную величину £¡¿(1) - число применений правила Гц, соответствующее дереву вывода высоты и величину ^^ — среднее число правил Гу, приходящееся на один ярус дерева вывода высоты и

ОО

1ШМ т—1

т—1

Пусть

При 4 —> ОО выполняется асимптотическое равенство (теорема 3.3.3).

С л с л о I! а т с л М е м и т с я к константе и М ( 5,-у(£)) линейно

зависит от Ь.

5) Для любого £ > О

->0при^ —>оо

(теорема 3.3.4).

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

Кроме того, для грамматики с однозначным выводом почти все слова, имеющие деревья вывода высоты I, имеют приблизительно одинаковые вероятности при

Заметим, что при. получении свойств 1) - 5) не- используется однозначность вывода слова в грамматике.

V. В главе 4 на основе установленных в главе 3 закономерностей применения правил грамматики получена нижняя оценка стоимости кодирования для языка, порождаемого стохастической КС-грамматикой с однозначным выводом, для которой матрица первых моментов неразложима, непериодична и ее перронов корень меньше единицы (теорема 4.2.1):

показано, что для любого кодирования / € ■?(•£) стоимость кодирования удовлетворяет неравенству

соответственно правый и левый положительные собственные векторы для перронова корня г при нормировке Х^х «,-г,- = 1,

в}'^ — число нетерминалов в правой части правила гу, — константа, определенная в формуле для Юу,

число терминальных символов в правой части

правила

Доказано, что найденная нижняя оценка является неулучшаемой (теорема 4.3.1).

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

VI. В главе 5 для критического случая устанавливаются свойства деревьев вывода высоты I при Ь —► СО. При этом предполагается, что матрица первых моментов неразложима, непериодична и ее перронов 'Корень равен единице.

При свойства деревьев вывода существенно отличаются от

свойств в докритическом случае. Перечислим кратко установленные свойства.

1) Для любого е из интервала (0,1) при 1 —> ОО и Ь • ^/ё < Т < для математического ожидания выполняется

следующее равенство:

где ру -'вероятность правила гу, заданная в исходной грамматике,

соответственно правый и левый положительные собственные векторы для перронова корня г при нормировке = 1» константа В определяется формулой

Д-^адниЧ,,, (5.1.1)

в которой Ь"т — вторые моменты, |Ху(*>т»е)1 ^ Со • е и Со - некоторая константа, не зависящая от I И Т (теорема 5.2.2).

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

2) Математическое ожидание не зависит от аксиомы грамматики.

3) При Ь —»• ОО справедливо следующее асимптотическое равенство:

где - число применений правила Гу, соответствующее всему дереву вывода высоты

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

VII. В главе 6 на основе установленных в главе 5 закономерностей применения правил грамматики в критическом случае получена нижняя оценка стоимости кодирования для языка, порождаемого стохастической КС-грамматикой с однозначным выводом, для которой матрица первых моментов неразложима и непериодична (теорема 6.1.2).

А именно, показано, что для любого кодирования / Е Р{С) стоимость кодирования удовлетворяет следующему неравенству:

С(С,/) > рцкьрц,

вероятность правила - левый положительный собственный вектор для перронова корня г при нормировке 52^=1 V» = 1 и /у - число терминальных символов в правой части правила

В диссертационной работе доказано, что найденная нижняя оценка является неулучшаемой (теорема 6.2.1).

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

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

Тогда нижнюю оценку стоимости кодирования можно записать в следующем виде:

Заметим, что эта формула аналогична формуле, установленной К. Шенноном для эргодического источника. При нормировке ц = 1 компонента V; левого собственного вектора V — <••.,!%) играет роль частоты появления нетерминального символа к которому применяется одно из правил множества

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

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

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

1994. — том 6, вып. 3. — С. 73 - 88.

2. Жильцова Л. П. Оптимальное кодирование контекстно-свободных языков // Дискретный анализ и исследование операций. Новосибирск: — Издательство Института математики СО РАН. —

1995. - Том 2, N3. - С. 72.

3. Жильцова Л. П. Об энтропии контекстно-свободного языка // Тезисы докладов XI Всесоюзной конференции "Проблемы теоретической кибернетики". — Ульяновск: Изд-во СВНЦ. — 1996. - С . 65-66.

4. Жильцова Л. П. Кодирование стохастического языка, порожденного контекстно-свободной грамматикой с одним нетерминальным символом // Материалы IX Межгосударственной школы-семинара "Синтез и сложность управляющих системп(Нижний Новгород, 16 - 19 декабря 1998 г.) — М.: Изд-во механико-математического факультета МГУ. - 1999. - С. 13 - 18.

5. Жильцова Л. П. Асимптотически оптимальное кодирование стохастических контекстно-свободных языков // Труды III Международной конференции "Дискретные модели в теории управляющих систем"(22 - 27 июня 1998 г.) М.: Изд-во Диалог -МГУ. - 1998. - С. 34 - 36.

6. Жильцова Л. П. Закономерности применения правил в выводах слов КС-языка // Проблемы теоретической кибернетики. Тезисы докладов XII Международной конференции (НЛовгород, 17 -19 мая 1999 г.). — Москва: Изд-во механико-математического факультета МГУ. - 1999. - С. 74.

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

8. Жильцова Л. П. О нижней оценке стоимости кодирования стохастического контекстно-свободного языка // Вестник Нижегородского государственного университета. Математическое моделирование и оптимальное управление. — Н.Новгород: Изд-во Нижегородского государственного университета. — 2000. — Вып. 1 (22).-С. 73-82.

9. Жильцова Л. П. О закономерностях применения правил стохастической контекстно-свободной грамматики // Труды IV Международной конференции "Дискретные модели в теории управляющих систем11 (19 - 25 июня 2000 г.) — М.: Изд-во "Макс Пресс". - 2000. - С. 24 - 25.

10. Жильцова Л. П. Об обобщении результатов Шеннона на кодирование стохастических контекстно - свободных .языков // Материалы XI Межгосударственной школы-семинара "Синтез и сложность управляющих систем" (Н.Новгород, 20-25 ноября 2000 г.). ЧЛ. — М.: Изд-во центра прикладных исследований- при механико-математическом факультете МГУ. — С. 67 - 73.

11. Жильцова Л. П. Экономное кодирование стохастических контекстно - свободных языков // Дискретная математика и ее приложения.

Сборник лекций. М.: Изд-во центра прикладных исследований при механико-математическом факультете МГУ. — 2001. — С. 26 - 45.

12. Жильцова Л. П. О нижней оценке стоимости кодирования и асимптотически оптимальном кодировании стохастического контекстно-свободного языка // Дискретный анализ к исследование операций. — Новосибирск: Издательство Института математики СО РАН. - 2001.- Серия 1. - Том 8, N3. - С. 26 - 45.

13. Жильцова Л. П. О возможностях обобщения результатов Шеннона на кодирование стохастических контекстно - свободных языков // Сборник трудов семинара по дискретной математике и ее приложениям. — М.: Изд-во центра прикладных исследований при механико-математическом факультете МГУ. — 2001. — С. 308 - 312.

14. Жильцова Л. П. О нижней оценке стоимости кодирования стохастического контекстно-свободного языка в критическом случае // Материалы XII Межгосударственной школы-семинара "Синтез и сложность управляющих систем11. — М.: Изд-во центра прикладных исследований при механико-математическом факультете МГУ. — 2001. - С. 84 - 86.

15. Жильцова Л. П. Об энтропии и стоимости кодирования стохастического КС-языка // Материалы XIII Межгосударственной школы-семинара "Синтез и сложность управляющих систем".

— М.: Изд-во центра прикладных исследований при механико-математическом факультете МГУ. — 2002. — С. 73 - 76.

16. Жильцова Л. П. О закономерностях в деревьях вывода слов КС-языка в критическом случае // Проблемы теоретической кибернетики. Тезисы докладов XIII Международной конференции.

— М.:Изд-во центра прикладных исследований при механико-математическом факультете МГУ. — 2002. — С. 63.

17. Жильцова Л. П. О кодировании стохастических контекстно-свободных языков // Доклады РАН. — 2002. — ТЬм 383, N 4. — С. 451-453.

18. Жильцова Л. П. Закономерности в деревьях вывода слов стохастического контекстно-свободного языка и нижняя оценка стоимости

кодирования. Критический случай // Дискретный анализ и исследование операций. — Новосибирск: Издательство Института математики СО РАН. - 2003 - Серия 1. — Том 10, N3. - С. 23 -53.

19. Zhiltsova L. On Optimal Coding for Stochastic Context-Pree Languages with Unique Derivation // Proceedings of the 3rd International Conference "Developments in Language Theory". Thessaloniki, July 20 - 23, 1997.-P. 539-550.

20. Zhiltsova, L. On Entropy and Optimal Coding Cost for Stochastic Language // Rmdamenta Informaticae.—1998. — V.36. — P. 285 - 305.

ums

Подписано в печать 0<? с1/ Печать трафаретная

Объем 4.4. п.л. Тираж ЮО экз. Заказ

Отдел полиграфии AHO "МУК НГПУ" 603950,.г.Нижний Новгород, ГСП-37, ул.Ульянова, 1

Введение.

1. Основные определения и понятия, связанные со стохастическими КС-языками.

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

2.1. Основные определения, относящиеся к кодированию языков.

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

2.3. Связь энтропии стохастического КС-языка с матрицей первых моментов порождающей грамматики.

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

3.1. Некоторые предварительные результаты для стохастических КС-языков.

3.2. Моменты.

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

4. Нижняя оценка стоимости кодирования и асимптотически оптимальное кодирование. Докритический случай.

4.1. Определение стоимости кодирования.

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

4.3. Неулучшаемость нижней оценки стоимости кодирования и асимптотически оптимальное кодирование.

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

5.1. Предварительные результаты, основанные на результатах теории ветвящихся процессов.

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

6. Нижняя оценка стоимости кодирования и асимптотически оптимальное кодирование. Критический случай.

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

6.2. Неулучшаемость нижней оценки стоимости кодирования и асимптотически оптимальное кодирование.

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

Возможности сжатия информации определяются ее вероятностными и структурными свойствами.

Начало математическому исследованию задач экономного (в смысле сжатия информации) кодирования было положено работами К.Шеннона в 40-х годах XX века. В работе "Математическая теория связи "К.Шеннон рассмотрел задачу кодирования сообщений, генерируемых эргодическим источником с конечным числом состояний [36].

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

Вопросы экономного кодирования с учетом структурных свойств информации рассматривались в работах А.А.Маркова [29, 30]. Он изучал возможности сжатия сообщений, являющихся словами регулярного языка, при простом с алгоритмической точки зрения способе кодирования — алфавитном, или побуквенном, кодировании. А.А.Марков показал, что во многих случаях учет структурных свойств, описываемых с помощью регулярных языков, позволяет при алфавитном кодировании более эффективно сжимать информацию.

А.А.Марковым было введено понятие локальной модели языка сообщений и связанное с ней понятие обобщенно-префиксного кодирования, позволяющего строить при алфавитном кодировании более экономные коды по сравнению с известными кодами Хаффмана, Фано, Шеннона, учитывающими лишь вероятностные свойства кодируемой информации [39].

Продолжением этого направления являлись исследования автора настоящей работы, отраженные в [ 4 - 8]. В них рассматривались вопросы алфавитного кодирования контекстно-свободных языков (КС-языков), являющихся существенным расширением класса регулярных языков. Оказалось, что в классе контекстно-свободных языков даже для такого простого способа кодирования, как алфавитное, многие проблемы алгоритмически неразрешимы. К ним относятся проблема распознавания однозначности декодирования и проблема оптимального алфавитного кодирования.

В [7] показано, что для важных с точки зрения приложений подклассов КС-языков задача экономного алфавитного кодирования может решаться с использованием локальной модели языка сообщений и учитывающих локальную модель обобщенно-префиксных кодов [30].

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

Выбор класса языков объясняется тем, что КС-языки — одно из ближайших расширений регулярных языков. КС-языки являются также хорошей моделью для описания естественных языков и языков программирования и поэтому представляют практический интерес. Известны также примеры использования КС-языков для описания классов геометрических и физических объектов [40, 41].

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

II. Диссертация состоит из введения и шести глав.

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

2. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. — М: Мир, 1979.

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

4. Жильцова Л.П. Об алфавитном кодировании контекстно-свободных языков / / Комбинаторно-алгебраические методы в прикладной математике. Межвуз. сборник научных трудов / Под ред. Ал.А.Маркова. — Горький: Изд-во Горьковского ун-та, 1983. — С. 106 123.

5. Жильцова Л.П. Алфавитное кодирование контекстно-свободных языков // Диссертация на соискание ученой степени кандидата физико-математических наук. — НИИ прикладной математики и кибернетики при Горьковском госуниверситете, 1988.

6. Жильцова Л. П. Об алгоритмической сложности задач оптимального алфавитного кодирования для контекстно-свободных языков // Дискретная математика. — 1989. — Том 1, вып. 2. — С. 38 -51.

7. Жильцова Л.П. О нижней оценке стоимости кодирования для стохастических контекстно-свободных языков с однозначным выводом // Методы и системы технической диагностики. — Саратов: Изд-во Саратовского ун-та. — 1993. С. 64 65.

8. Жильцова Л.П. Кодирование стохастических контекстно-свободных языков с однозначным выводом // Дискретная математика. — 1994. — том 6, вып. 3. — С. 73-88.

9. Жильцова Л.П. Оптимальное кодирование контекстно-свободных языков // Дискретный анализ и исследование операций. Новосибирск:- Издательство Института математики СО РАН. — 1995. — Том 2, N3.- С. 72.

10. Жильцова Л.П. Об энтропии контекстно-свободного языка // Тезисы докладов XI Всесоюзной конференции "Проблемы теоретической кибернетики". — Ульяновск: Изд-во СВНЦ. — 1996. — С. 65 66.

11. Жильцова Л.П. Асимптотически оптимальное кодирование стохастических контекстно-свободных языков / / Труды III Международной конференции "Дискретные модели в теории управляющих систем"(22 27 июня 1998 г.) М.: Изд-во Диалог -МГУ. - 1998. - С. 34 - 36.

12. Жильцова Л.П. О закономерностях применения правил стохастической контекстно-свободной грамматики / / Труды IV Международной конференции "Дискретные модели в теории управляющих систем"(19 25 июня 2000 г.) — М.: Изд-во "Макс Пресс". - 2000. - С. 24 - 25.

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

14. Жильцова Л. П. Экономное кодирование стохастических контекстно свободных языков // Дискретная математика и ее приложения. Сборник лекций. М.: Изд-во центра прикладных исследований при механико-математическом факультете МГУ. — 2001. - С. 26 - 45.

15. Жильцова Л.П. О кодировании стохастических контекстно-свободных языков // Доклады РАН. — 2002. Том 383, N 4. - С. 451 -453.

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

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

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

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

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

21. Фихтенгольц Г.М. Основы математического анализа. — М.: Наука, 1964.

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

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

24. Шеннон К. Математическая теория связи. // Работы по теории информации и кибернетике. — М.: ИЛ, 1963. —■ С. 243 332.

25. Ширяев А.Н. Вероятность.— М.: Наука, 1980.

26. Эрли Дж. Эффективный алгоритм анализа контекстно-свободных языков // Языки и автоматы. М.: Мир. — 1975. — С. 47 - 70.

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

28. Delest М.Р., Viennot G. Algebraic languages and polyominoes enumeration. // Theor. Сотр. Sci. — 1984. 34. - P. 169 - 206.

29. Viennot G. Problemes combinatoires poses par la physique statistique. /7 Seminaire N. Bourbaki. Asterisque. 1985. — N 121 - 122. - P. 225 -246.

30. Zhiltsova L. On Optimal Coding for Stochastic Context-Free Languages with Unique Derivation // Proceedings of the 3rd International Conference "Developments in Language Theory". Thessaloniki, July 20 23, 1997. - P. 539 - 550.

31. Zhiltsova L. On Entropy and Optimal Coding Cost for Stochastic Language //Fundamenta Informaticae.— 1998. — V.36. — P. 285 305.