Кодирование стохастических контекстно-свободных языков

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.