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

• Автор: Жильцова, Лариса Павловна
• Шифр специальности: 01.01.09
• Научная степень: Докторская
• Год защиты: 2004
• Место защиты: Нижний Новгород
• Количество страниц: 142 с.

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].
При кодировании Шенноном учитывались главным образом вероятностные свойства сообщений, порождаемых эргодическим источником. Однако эти вероятностные свойства определялись как вероятностными свойствами состояний источника, так и синтаксическими (структурными) свойствами последовательностей символов, генерируемых источником.
Вопросы экономного кодирования с учетом структурных свойств информации рассматривались в работах A.A.Маркова [29, 30]. Он изучал возможности сжатия сообщений, являющихся словами регулярного языка, при простом с алгоритмической точки зрения способе кодирования — алфавитном, или побуквенном, кодировании. A.A.Марков показал, что во многих случаях учет структурных свойств, описываемых с помощью регулярных языков, позволяет при алфавитном кодировании более эффективно сжимать информацию.
А.А.Марковым было введено понятие локальной модели языка сообщений и связанное с ней понятие обобщенно-префиксного кодирования, позволяющего строить при алфавитном кодировании более экономные коды по сравнению с известными кодами Хаффмана, Фано, Шеннона, учитывающими лишь вероятностные свойства кодируемой информации [39],
Продолжением этого направления являлись исследования автора настоящей работы, отраженные в [ 4 - 8]. В них рассматривались

Поэтому
к к
1 - 1) ) ^2хірі°?) ■ (і + <Рі(п- !))■
3=1 / 1
Так как (1 + срфп — 1)) = ї^щ^гї) Д 1 ПРИ п —> сю, то
к к
.7=1 / І
(Л к
1 ~ ^Х^°^'ГП_1 ’ ^ ) Л Х1Р(°?)-
.7=1 / Ї
Положим Сі = 21^ЛДМ^ Тогда
к к
1 -Сіг"£х,- £>Р(ЯР).
.7=1 / *=і
Сравнивая верхнюю и нижнюю оценки, получаем утверждение леммы. Лемма доказана.
3.2. Моменты
Пусть Е = (£і,.., ,£*) — случайный вектор, а* = (аі аД — фиксированный вектор с целочисленными неотрицательными компонентами и а = оц + ... 4- а*. Обозначим
г?[а*] _ Л°ч] Лпк]
41 • • ■ 4п і
где Да1 = х(х — 1)... (х — а + 1). Математическое ожидание МНІ“*1 называется [311 факториальным момент,ом Е порядка а или, более подробно, а*-моментом. Е.
Пусть хгфф) - число нетерминалов Л,- в дереве вывода из Л, на ярусе і. Через АД.(£) обозначим а*—момент вектора Хг(і) = (х(4),... , аф(і)).
Примем специальные обозначения для моментов первых четырех порядков. Факториальные моменты первого порядка будем обозначать через «’(£). Для факториальных моментов второго порядка введем обозначения Ь‘^к(і). Таким образом, Ьф(/) = А/Д(Д(х* (£) — 1) и
Ь’Ді) = Мх^(і)х(і) при j ф к. Для факториальных моментов
Ях{п) >
Ях(п) >
Ях(п) >