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

• Жильцова, Лариса Павловна
• доктор физико-математических наук
• 2004

Оглавление диссертации доктор физико-математических наук Жильцова, Лариса Павловна

Введение.

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. Диссертация состоит из введения и шести глав.

Список литературы диссертационного исследования доктор физико-математических наук Жильцова, Лариса Павловна, 2004 год

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.