Введение к работе
Актуальность темы
Поиск эффективного представления больших объемов данных для их передачи или хранения — важная проблема многих областей современной науки и техники. Алфавитное кодирование яоыхов — одна но основных моделей дискретной математики, предназначенная для изучения вопросов наиболее экономного представления информации.
Основой алгоритма оптимального алфавитного копирования языка является построение матрицы оптимальною кодирования М(X), представляющей из себя множество наборов длин кодовых слов всех возможных оптимальных ходов1. Известно, что данная задача в полном объеме — трудная. Например, для контекстно-свободных языков она алгоритмически неразрешима 3, для некоторых постановок этой задачи в классе регулярных языков доказана ее JVP-полнота 1. Сложность рассматриваемой задачи обусловливает необходимость разработки приближенных алгоритмов и методов для исследования конкретных классов языков.
С другой стороны, для классического случая алфавитного кодирования языка В', состоящего но всех сообщений в алфавите В, матрица М(В*) имеет простое аналитическое описание с помощью неравенства М&х-Миллана, и известен быстрых алгоритм Хаффмана построения оптимального хода. Есть и другие классы регулярных языков, для которых сложность алгоритма оптимального кодирования сравнима со сложностью' алгоритма Хаффмана.
А.А.Марков установил, что задача построения матрицы оптимального кодирования алгоритмически разрешима для широкого класса регулярных языков, получивших название вполне регулярных J. Эти языки порождаются регулярными источниками, в которых из каждого состояния существует ориентированный путь в любое другое состояние. При получении этого результата был использован так называемый принцип равномерного пополнения. Этот принцип заключается в утверждении о том, что при любом допустимом кодировании произвольного подмножества букв алфавита языка оставшиеся буквы можно закодировать словами равной длины.
Для класса всех регулярных языков вопрос об алгоритмической разрешимости за-
'Марюв А.А. Ввєдепе в теорію юдіров&таї. М.: Hayta, 1982.
2Жітгьцов& Л.П. Об алфавитном іодірованн ижтектно-свободяых гоытов // Коибгааторжо-мгебракчесне методы в приладної м&тематпе: Межвуз. тенатп. сб. ж&учн. тр. / Под реп. Ал.А.М&рюва; Горы. roc. уж-т. Гормжї, 1983. С.106-123.
'Марков А.А. О оавіспюсті зффеїтівностж аяфавітгого юдіровавха от яоыха сообщепі // ДАН СССР. 1981. Т.258. С.304-507,
дачи построения матрицы M(L) остается открытым. При этом известно, что принцип равномерного пополнения на все регулярные языхи не может быть распространен.
Эти трудности, появляющиеся за пределами хласса вполне регулярных языхов, возникают уже для автоматных источнихов с двумя состояниями, у которых одно состояние — начальное, оба состояния являются заключительными, существует переход из начального состояния во второе и запрещен переход из второго состояния в начальное. Класс языков, которые порождаются данными источниками, обозначен через R%. Tax как в источнихах, порождающих языхи из Щ, переход из первого состояния во второе может быть осуществлен толыо один раз, данные языхи являются объединением конечного числа языков из более уохого класса, обозначенного через Щ. Класс Щ состоит из языков класса Щ таких, у которых в порождающих их источниках из начального состояния во второе ведет толыо одна дуга. Отметим, что любые два различные источника такого вида порождают различные языхи из Щ. Языхи из класса Щ разбиваются на шестнадцать типов в зависимости от структуры порождающих их источнихов. Среди них выделено шесть типов язьііов, хоторые названы базовыми. Они характеризуются тем, что любой нетривиальный язык из класса Щ содержит в качестве подмножества некоторый язык базового типа.
Цель работы
-
Исследование возможности применения принципа равномерного пополнения для регулярных языков, не являющихся вполне регулярными, и более подробно для языков ио класса Щ
-
Исследование качественных особенностей двоичного алфавитного кодирования шести типов базовых в классе Щ языков.
Научная новизна
-
Доказано, что тольхо для двух типов языхов из Щ принцип равномерного пополнения не может быть обоснован. В работе предложено обобщение данного принрпа, заключающееся в том, что пополнение может состоять из ограниченного числа блоков слов одинаковой длины. Показано, что для хласса Щ минимальное число блоков не превосходит двух, а для произвольного регулярного языха в худшем случае число блохов не меньше числа состояний порождающего данный язык автоматного источника.
-
Подробно исследовано оптимальное алфавитное кодирование базовых в классе Щ языков. Языки двух типов принадлежат ранее изученноиу классу вполне регулярных
языков и обращению класса вполне регулярных языков. Для остальных четырех типов языков (они обозначены в работе La, «/?, Ьеа, Ьа) получены следующие результаты:
Lea' получено описание множества дешифруемых кодов и доказана алгоритмическая разрешимость задачи построения матрицы оптимального кодирования;
^Се, «?' получено описание множеств дешифруемых кодов, построены матрицы оптимального кодирования и разработаны полиномиальные алгоритмы оптимального кодирования;
Led- получено описание множества дешифруемых кодов, построена матрица оптимального кодирования, для ряда случаев описан полиномиальный алгоритм оптимального кодирования, исследована эффективность приближенных методов кодирования в общем случае.
Теоретическая и практическая ценность
Работа имеет теоретическую направленность. Полученные результаты могут быть использованы в дальнейших исследованиях в теории кодирования и при обучении студентов по специальности "прикладная математика". Алгоритмические результаты могут быть использованы при решении практических оадач экономного представления информации.
Апробация работы
Результаты, представленные в диссертации, докладывались на Всесоюзных конференциях по проблемам теоретической кибернетики (Саратов, 1983, Горький, 1988, Волгоград, 1990), на Всесоюзных семинарах по дискретной математике и ее приложениям (Москва, 1986, 1989), на Межгосударственных школах-семинарах по синтезу и сложности управляющих систем (Н.Новгород, 1992,1996), на семинарах в Нижегородском и Московском университетах.
Публикации
Основные результаты диссертации опубликованы в работах [1-9], список которых приведен в конце автореферата.
Структура диссертации
Диссертация состоит из введения, четырех глав и списка литературы.
