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

• Автор: Борисов, Александр Евгеньевич
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2006
• Место защиты: Нижний Новгород
• Количество страниц: 100 с. : ил.

1 Введение
1.1 Постановка задачи и общая характеристика работы
1.2 Основные определения и обозначения
1.3 Формулировка основных результатов
2 Оценка средней длины кода для стохастического языка
3 Закономерности в деревьях вывода слов и оптимальное кодирование. Докритический случай
3.1 Основные определения и обозначения
3.2 Вероятности продолжения
3.3 Закономерности в деревьях вывода слов. Случай простого перронова корня
3.4 Закономерности в деревьях вывода слов. Случай кратного перронова корня
3.5 Оценки моментов второго и более высоких порядков для
кратного перронова корпя
3.6 Дисперсия числа применений правил в деревьях вывода
3.7 Пример грамматики с двумя классами нетерминалов
3.8 Оценка стоимости оптимального кодирования
3.9 Алгоритм асимптотически оптимального кодирования
4 Закономерности в деревьях вывода слов и оптимальное кодирование. Критический случай
4.1 Случай кратного перронова корня
4.1.1 Вероятности продолжения
4.1.2 Математические ожидания числа применений правил в деревьях вывода
4.1.3 Энтропия и стоимость оптимального кодирования
4.1.4 Алгоритм оптимального кодирования
4.2 Случай простого перронова корпя
4.2.1 Вероятности продолжения и вероятности деревьев вывода фиксированной высоты
4.2.2 Распределение нетерминалов на фиксированном ярусе дерева вывода
4.2.3 Математические ожидания числа применений правил в деревьях вывода
4.2.4 Алгоритм оптимального кодирования

5 Заключение

1. Введение
1.1 Постановка задачи и общая характеристика работы
Вопросы оптимального кодирования сообщений (слов), порождаемых некоторым вероятностным источником, возникают в задачах, связанных с передачей и храпением информации. Под оптимальным кодированием, как правило, понимают кодирование, которое даст максимальную степень сжатия информации (отношение длины исходного слова к длине его кода). Возможная степень сжатия информации определяется вероятностными и структурными свойствами источника информации. Вероятностные свойства учитывают частоты символов или фрагментов в исходном слове, а структурные (синтаксические) - правила построения слов (например, в словах русского языка не встречается сочетаний типа БББ, ЩЩ, слова не начинаются с мягкого знака).
Хорошо известны и широко используются на практике алгоритмы побуквенпого кодирования, которые учитывают только частоты букв. Наиболее известными являются алгоритмы Хаффмана [32], Фапо [23], Шеннона [22], алгоритм арифметического кодирования [30], [31], которые применяются при отсутствии априорных знаний о структуре кодируемых слов (сообщений). Существуют также динамические версии этих алгоритмов, которые в процессе работы обновляют таблицу частот символов. Такие алгоритмы строят вероятностную модель языка в процессе получения па вход новых символов.
Хорошо известны также словарные методы сжатия, основанные на учете часто повторяемых фрагментов в кодируемом тексте. Здесь следует выделить алгоритмы Лемпеля-Зива 11^77 и ЛЛ$> [28],[29], и их многочисленные модификации.
Задача кодирования, учитывающего синтаксические свойства сообщений, была впервые рассмотрена К.Шснноном в [22]. Им был рассмотрен вероятностный источник сообщений с конечным числом состояний. Шеиион доказал, что в случае эргодичности источника все сообщения большой длины N разбиваются на два класса: множество сообщений, вероятность которых стремится к 0 при N —> оо, и множество оставшихся сообщений с приблизительно одинаковыми вероятностями и буквенным составом. Такой источник фактически соот-

=4і* • t (“г") +°м)=4} • V2+o(t).
Пользуясь неравенством
M(SJ(0) < M{Sii(t)) < M(si(t)) + М(%(1)) + М(4(0),
находим, что
1 (н-
(1)

'tJ?

(1 + °(1)) ^ M(Sij(t)/t) < - -±- + 0{ogct)) (1 + 0(1))
при то —> ею, где С2 = тах(с, сД. Таким образом, устремляя то (а значит, и £) к бесконечности, получаем необходимое.
Для случая г > к доказательство проводится аналогично. Единственное отличие заключается в оценке 5? (£):
л /і ^ І — -7" /0
M(5ê(0) = < • E —7—(і + «(1)) +4J • E 7(1 + 0(1))
T—Tq l T-Tq l
=4’-é ^(i+»(i))+47É )(i+o(i)) = (+)++,).(/2+0(f).
r=l & r=i Г
Эта теорема показывает, что величина M(Sij(t)/t) стремится к константе при t —» 00, как и в неразложимом случае.
3.6 Дисперсия числа применений правил в деревьях вывода
Теперь оценим дисперсию величин 5Д(Д/£.
Теорема 3.6.1 Для КС-грамматики с матрицей первых моментов, имеющей вид (1.2.1) при г = г' = г" < 1 и Ь —► оо справедливы соотношения

D(Sij(t)/t) -+ (Д/J /12 при г < ki, D(Sij(t)/t) -» (uf - 4^) Л2 ПРИ і > ki,
где величины Jf- определены формулами (3.5.5).