автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Вопросы эффективности приближенных методов алфавитного кодирования регулярных языков

РГБ. ОД 2 О МАЙ

На правах рукописи

КОЧЕТОВ Александр Акимович

ВОПРОСЫ ЭФФЕКТИВНОСТИ ПРИБЛИЖЕННЫХ МЕТОДОВ АЛФАВИТНОГО КОДИРОВАНИЯ РЕГУЛЯРНЫХ ЯЗЫКОВ

05.13.17 — Теоретические основы информатики

Автореферат

диссертации на соискание ученой степени кандидата физико-математических наук

Нижний Новгород, 1996

Работа выполнена в Научно-исследовательском институте прикладной математики и кибернетики при Нижегородском государственном университете им. Н. И. Лобачевского.

Научный руководитель — доктор физико-математических наук, профессор

А. А. Марков

Официальные оппоненты:

доктор физико-математических наук В. М. Сидельников,

кандидат физико-математических наук В. Е. Алексеев.

Ведущая организация — Институт прикладной математики РАН.

Защита состоится « 1-С/_199^ г. в. часов

на заседании диссертационного совета КР 063.43.01 научно-исследовательского института прикладной математики и кибернетики при Нижегородском .госуниверситете им. Н. И. Лобачевского по адресу: 603005, Нижний Новгород, ул. Ульянова, д. 10.

С диссертацией можно ознакомиться в научной библиотеке НИИ прикладной математики и кибернетики.

Автореферат разослан « З-А^ » ¿2-__199-^ г.

Ученый секретарь диссертационного совета доктор технических наук, профессор

Ю. Л. Кетков

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы

Поиск эффективного представления больших объемов данных дня их передачи или хранения — важная проблема многих областей современной науки н техники. Алфавитное кодирование яоыков — одна но основных моделей дискретной математики, предназначенная для изучения вопросов наиболее экономного представления информации.

Основой алгоритма оптимального алфавитного кодирования языка L является построение матрицы оптимального кодирования M(L), представляющей из себя множество наборов длин кодовых слов всех вооможных оптимальных ходовИзвестно, что данная задача в полном объеме — трудная. Например, для контекстно-свободных языков она алгоритмически неразрешима 3, для некоторых постановок этой задачи в классе регулярных языков доказана ее JVP-полнота Сложность рассматриваемой задачи обусловливает необходимость разработки приближенных алгоритмов и методов для исследования конкретных классов языков.

С другой стороны, для классического случая алфавитного кодирования языка В', состоящею но всех сообщений в алфавите В, матрица М{В*) имеет простое аналитик ческое описание с помощью неравенства Мах-Миллана, и известен быстрый алгоритм Хаффмана построения оптимального кода. Есть и другие классы регулярных языков, для которых сложность алгоритма оптимального кодирования сравнима со сложностью' алгоритма Хаффмана.

А.А.Марков установил, что задача построения матрицы оптимального кодирования алгоритмически разрешима для широкого класса регулярных языков, получивших название вполне регулярны* J. Эти языки порождаются регулярными источниками, в которых из каждого состояния существует ориентированный путь в любое другое состояние. При получении »того результата был использован так называемый принцип равномерного пополнения. Этот принцип заключается в утверждении о том, что при любом допустимом кодировании произвольного подмножества букв алфавита языка оставшиеся буквы можно закодировать словами равной длины.

Для класса всех регулярных языков вопрос об алгоритмической разрешимости за-

'Мармв A.A. Введепе в теоргс юдкровми. • М.: Hayn, 1982.

2Жюгьцоб& Л.П. Об алфавитном юдхров&нп юктегстно-свободЕых каыхов // Коибгааторжо-алгебракчесне методы в ириладно« м&теиатпе: Межвуз. тенатп. сб. к&учн. тр. / Под ред. Ач.А.Марюва; Горы. гос. ук-т. ГЬрмн, 1983. С.106-123.

'Марков A.A. О ошсшосп вффеииностж апфавиюго юдхровакы от яаихл сообщен! // ДАН СССР. 1981. Т.258. С.304-507,

дачи построения матрицы M(L) остается открытым. При этом известно, что принцип равномерного пополнения на все регулярные языки не может быть распространен.

Эти трудности, появляющиеся за пределами масса вполне регулярных языков, возникают уже для автоматных источник® с двумя состояниями, у которых одно состояние — начальное, оба состояния являются заключительными, существует переход из начального состояния во второе и запрещен переход из второго состояния в начальное. Класс языков, которые порождаются данными источниками, обозначен через Щ. Tax как в источниках, порождающих языки из Щ, переход из первого состояния во второе может быть осуществлен только один раз, данные языки являются объединением конечного числа языков из более уокого класса, обозначенного через Класс .Rf состоит из языков класса Щ таких, у которых в порождающих их источниках из начального состояния во второе ведет только одна дуга. Отметим, что любые два различные источника такого вида порождают различные языки из JiJ. Языки из класса .flf разбиваются на шестнадцать типов в зависимости от структуры порождающих их источников. Среди них выделено шесть типов языков, которые названы базовыми. Они характеризуются тем, что любой нетривиальный язык из класса Щ содержит в качестве подмножества некоторый язык базового типа.

Цель работы

1. Исследование возможности применения принципа равномерного пополнения для регулярных языков, не являющихся вполне регулярными, и более подробно для языков из класса Щ-

2. Исследование качественных особенностей двоичного алфавитного кодирования шести типов базовых в классе Щ языков.

Научная новизна

1. Доказано, что только для двух типов языков из Щ принцип равномерного пополнения не может быть обоснован. В работе предложено обобщение данного принципа, заключающееся в том, что пополнение может состоять из ограниченного числа блоков слов одинаковой длины. Показано, что для класса Щ минимальное число блоков не превосходит двух, а для произвольного регулярного языка в худшем случае число блоков не меньше числа состояний порождающего данный язык автоматного источника.

2. Подробно исследовано оптимальное алфавитное кодирование базовых в классе Щ языков. Языки двух типов принадлежат ранее изученному классу вполне регулярных

языков и обращению класса вполне регулярных языков. Для остальных четырех типов языков (они обозначены в работе Loe, LeP, Lea, 1>а) получены следующие результаты: Lea: получено описание множества дешифруемых кодов и доказана алгоритмическая раорешимость задачи построения матрицы оптимального кодирования;

¿с« Lep\ получено описание множеств дешифруемых кодов, построены матрицы оптимального кодирования и разработаны полиномиальные алгоритмы оптимального кодирования;

Lei- получено описание множества дешифруемых кодов, построена матрица оптимального кодирования, для ряда случаев описан полиномиальный алгоритм оптимального кодирования, исследована эффективность приближенных методов кодирования в общем случае.

Теоретическая и практическая ценность

Работа имеет теоретическую направленность. Полученные результаты могут быть испольоованы в дальнейших исследованиях в теории кодирования и при обучении студентов по специальности "прикладная математика". Алгоритмические реоультаты могут быть использованы при решении практических оадач экономного представления информации.

Апробация работы

Результаты, представленные в диссертации, докладывались на Всесоюзных конференциях по проблемам теоретической кибернетики (Саратов, 1983, Горький, 1988, Волгоград, 1990), на Всесоюзных семинарах по дискретной математике и ее приложениям (Москва, 1986, 1989), на Межгосударственных школах-семинарах по синтезу и сложности управляющих систем (Н.Новгород, 1992,1996), на семинарах в Нижегородском и Московском университетах.

Публикации

Основные реоультаты диссертации опубликованы в работах [1-9], список которых приведен в конце автореферата.

Структура диссертации

Диссертация состоит из введения, четырех глав и списка литературы.

Содержание работы

Пусть А = {о1(..., о,} — алфавит канала связи, ? > 2, £ = {61,... ,6т} — алфавит языка сообщении X, X С В*, где В' — множество всех слов в алфавите В, включающее пустое слово А длины ноль. Через В+ обозначим множество всех непустых слов в алфавите В, то есть В+ = В*\{А}. Алфавитное кодирование /у задается схемой:

¿1 -V 1/1,

к "а,

где 6 А* — элементарные коды, соответствующие буквам € В, г = 1,т. Множество V = {1/1,1/2,...,!/„} называется кодом, определяющим /у, а набор ¡(V) = (¿1, ¿2, • • •, 1т)) где и =| г/, | — дайна элементарного кода VI , называется спектром длин элементарных кодов кода V. При алфавитном кодировании /у каждому слову 6,,... языка исходных сообщений Ь соответствует оакоррованное сообщение М^ч.. определяемое по правилу

Мк, ■ ■ ■ К) = ми •. ■ ми = % ■ ■ ■

где Ь,. € В) Уч еУ,з =

Одним из основных требований, которым должно отвечать любое кодирование, является взаимная однозначность кодирующего отображения /у в языке X, то есть из того, что а,/? £ X и а ф /?, должно следовать /у(а) ф Коды, удовлетворяющие данному требованию, будем называть дешифруемыми и через У(Х) будем обозначать множество всех дешифруемых кодов языка £.

Дм сообщения а 6 X стоимость кодирования /у определяется как число букв закодированного сообщения, приходящихся на одну букву исходного сообщения а:

I

где Ра = (pi,... iPm) — частотная характеристика сообщения а, р, = ^ и |a|i — число вхождений буквы Ь, в а. Код К, минимизирующий значение С(а, V) на множестве V(L) всех дешифруемых юдов язьиа L, называется оптимальным. Спектры ходов из V(i), которые могут быть оптимальными для сообщений из L, образуют матрицу оптимального кодирования М(Ь), которая конечна для любого языка. Через k(L) обозначим максимальный элемент матрицы оптимального кодирования M(L).

В первой главе определяется класс Щ и рассматривается вопрос о применимости к языкам ©того класса принципа равномерного пополнения.

Обозначим через Щ класс языков, которые порождаются автоматными регулярными источниками с двумя состояниями qo и qi, где состояние qo — начальное, оба состояния являются заключительными, существует дуга из qo в qi и переход из состояния qi в состояние q0 запрещен.

Пусть а — произвольное сообщение в алфавите В, а £ В+. Моделью сообщения а назовем любой язык L С В* такой, что а 6 L.

Пусть а € L. Источник, порождающий язык называется приводимым относительно а, если существует хотя бы одна дуга, после удаления которой вместе с приписанной ей буквой оставшийся источник порождает язык I' и а 6 i'. В противном случае источник называется неприводимым относительно а. Язык, соответствующий неприводимому относительно а источнику, называется минимальной моделью сообщения а. Множество всех минимальных моделей из Щ для всевозможных а 6 В+ совпадает с Щ.

Языки из Щ разбиваются на несколько типов следующим образом. Каждая буква 6 6 В для языка Ь^Щ переводит пару (q0> qi) состояний порождающего L источника в пару (Ь(?о),£>Ы)> гДе &Ы £ {?о,<?1,0}, &Ы 6 {<?i,0}- Выражение b(qt) = 0 , г е {0,1}, означает, что из состояния q; дуга с буквой Ь не выходит. В противном случае значением l(qi) является состояние, в которое ведет эта дуга. Алфавит В в общем случае разбивается на пять подмножеств, где для всех букв одного и того же подмножества образы пары (<?0)?i) совпадают. Каждое подмножество обозначается буквой согласно следующей схеме:

Тип буквы (К?о), Н?1»

С М)

D (?i>7i)

Е (91,0)

F (в, ft)

G (?o,?i)

Тип Т языка L есть множество имен подмножеств, которым принадлежат соста-

ваяющие его буквы, то есть Т С {G, D, Е, F, G}, Т ф 0. Язык типа Т будем далее обооначать через Lf. Так как подмножества букв Е и D, переводящие источник из состояния до в состояние удовлетворяют условию

\EUD\ = 1,

то будем обооначать оти подмножества в типах языков маленькими буквами е и d.

Языки класса Щ разбиваются на 16 типов: £«, Li, Lct, Lep, Lta, Led, Li?, Lia, LqsF, Lcea, Lepa, Lap, Lada, Lipg, Lc-fg, Lcîfg- ® первой главе доказано, что только к языкам двух типов Lap и LcsFq принцип равномерного пополнения не может быть применим, а для языков остальных 14 типов данный принцип справедлив.

Языки L,. и Li назовем элементарными. Кодирование элементарных языков тривиально. Языки Ьсе> Lea, Led> Ldp, Lia, алфавит которых разбивается ровно на два подмножества однотипных букв, назовем базовыми.

Во второй и третьей главах подробно исследуется алфавитное кодирование базовых типов языков из Щ. Для двух из них основные проблемы алфавитного кодирования уже решены: язык Lia совпадает с языком всех сообщений, который порождается источником с одним состоянием, а язык Ld? есть обращение языка, являющегося вполне регулярным. Для каждого из оставшихся языков описывается множество дешифруемых кодов V{L), изучается матрица оптимального кодирования M{L), оценивается величина k(L) и анализируется алгоритм оптимального кодирования.

Так как любой язык в Щ, за исключением элементарных, содержит в качестве подмножества по крайней мере один из языков базового типа, то результаты, полученные для языков базовых типов, могут быть использованы при анализе кодирования остальных языков из

Пусть Lfi, Lt" 6 Щ- Запись 1т Ct 1т< будет означать, что Т С Т". Пусть Vji (Lf«) есть ограничение множества дешифруемых кодов языка L?» на множество букв с типами из Т. Множество Vp {Lt») получается из множества V(Iyn ) отбрасыванием в каждом коде слов, соответствующих буквам с типами из Т"\Т'. Аналогично, Mt>{Lt») определяется как матрица, которая образуется из столбцов матрицы оптимального кодирования M {Liu), соответствующих буквам с типами из Г'.

Если Lp Ci Lt", то справедливы следующие соотношения:

а). Vji(Lj4i) С V(It');

б), каждая строка из Мт>{Ьр>) мажорирует либо совпадает хотя бы с одним спектром из M{Lp)\

в). k(Lpi) > k(Lp).

Пусть L — произвольный язык базового типа в алфавите В и пусть X есть множество букв алфавита В за вычетом буквы, переводящей порождающий язык L источник

ив состояния до в q¡. (В случае языков Le, и Lei имеем X = С, а в случае языков Lep и Leg множество X совпадает соответственно с множествами F и G.) Для языка L произвольный дешифруемый код имеет вид V = Ух U {и}, где Vx — множество элементарных кодов букв множества X, а слово и кодирует либо букву е, либо d. Пусть Iх — спектр кода Vx. Для взаимной однозначности кодирования языка L необходимо, чтобы код Vx принадлежал множеству то есть элементы спектра 1х должны

удовлетворять неравенству Мак-Миллана. Исходя из этого, при исследовании множества V(I) определяется, какие коды из V{X") могут быть дополнены еще одним словом, соответствующим в зависимости от языка либо букве е, либо букве d, с сохранением взаимной однозначности кодирования в языке L. Эти дополненные коды и образуют множество дешифруемых кодоз языка L.

Разобьем множество V(X*) на два подмножества: множество Vffpf") полных кодов, чьи спектры удовлетворяют равенству Мак-Миллана, и множество VH(X*) кодов, чьи спектры удовлетворяют строгому неравенству Мак-Миллана. В диссертации показано, что коды из Va(X*) всегда могут быть доопределены еще одним словом с сохранением взаимной однозначности кодирования в любом языке базового типа. В этом случае может быть использована "техника, разработанная А.А.Марковым для вполне регулярных языков. Далее при исследовании множеств дешифруемых кодов будут анализироваться только коды из Vn(X*).

Во второй главе исследуется кодирование языков трех базовых типов Lct,Lcp,LeQt у которых переход из первого состояния во второе осуществляется нециклической буквой е.

В языке Z'eGf никакой код из V„ (G*) не может быть пополнен каким-либо словом, соответствующим букве е, с сохранением взаимной однозначности кодирования. Получена верхняя оценка для k(Lea). Таким образом, для языков типа L& доказана алгоритмическая разрешимость задачи построения матрицы оптимального кодирования.

В случае языка Lce множество V„(C*) разбивается на четыре подмножества в зависимости от наличия у кода или его обращения свойства префкксности и свойства самосинхронизации. Доказано, что коды, обращения которых обладают свойством префкксности и свойством самосинхронизации, не могут быть пополнены. Коды из остальных трех подмножеств множества УД(С") допускают расширение. В работе описаны множества возможных расширений дм всех трех случаев,

Матрица оптимального кодирования M(Lc<¡) выглядит следующим образом: часть, соответствующая буквам ио множества С, совпадает с матрицей оптимального кодирования языка всех сообщений, а буква е кодируется одной буквой. Алгоритм оптимального кодирования для языков данного типа практически совпадает с алгоритмом Хаффмана.

В языке Ltp любой код из V„(F") пополним. Матрица оптимального кодирования и алгоритм оптимального кодирования такие же, как для языка Ьае-

Третья глава целиком посвящена исследованию кодирования языка Las- Доказано, что из множества Vn(C*) только коды, являющиеся обращениями префиксных кодов, не могут быть пополнены. Во всех остальных случаях расширение возможно. Для множества полных префиксных кодов, из которых в дальнейшем строятся оптимальные коды в языке La, получено описание множества слов, являющихся допустимыми олементарными кодами буквы d.

Пусть m = |С|. Для описания матрицы оптимального кодирования M[Lcd) введена специальная функция f(ii,..., im). Функция ((¡i,..., im) определена как наименьшее целое число n, n > 1, для которого найдутся /,■ и /у, 1 < i,j < те, такие, что ф Ц (mod n). В случае, когда ii = = ... = 1т, значение ..., lm) не определено.

Пусть max(li,. .., im) есть наибольший элемент в наборе (h,.lm), a — длина элементарного хода буквы cf. Матрица оптимального кодирования языка La состоит из двух блоков и имеет следующий вид:

M(LCB) = {(ii, • • ■, L U) = E 2_,i = 1. ■U = «ii, • • • » Uï U ¿=1

l)№> • • ■, L, 1) : ё24 = 1 - .....'->}.

«=î

В работе описано поведение функции Одним из ее свойств является то, что функция £ может быть равна только степени простого числа. Величина функции £ на наборах из M(Lci) оценивается следующим образом:

2

f (ii, • • •, • 1о8г bg2 т.

Величина k(La) при этом не превосходит мощности множества С.

Алгоритм оптимального кодирования для языков данного типа, сравнимый по сложности с алгоритмом Хаффмана, описан для случаев, когда мощность множества С кратна трем или когда частота буквы d не меньше минимальной из частот букв множества С. В остальных случаях могут быть использованы приближенные методы, которые обсуждаются в четвертой главе.

В четвертой главе исследуется обобщенный принцип равномерного пополнения для класса регулярных языков и приближенные методы коррования для языка Led-

В первой главе показано, что не для всех языков множества справедлив принцип равномерного пополнения. К языкам, для которых принцип равномерного пополнения

несправедлив, можно применять его обобщение. Обобщение принципа равномерного пополнения заключается в том, что множество незакодированных букв разбивается на ограниченное число подмножеств, для 1аждого из хоторых можно построить равномерный ход.

Через h(L, V') обозначается минимальное число подмножеств в разбиении множества незакодированных букв, позволяющее для данного частичного кода V' в языке L применить "простой" или обобщенный принцип равномерного пополнения. Пусть

h{L) = max^L.n

где максимум берется по всем возможным частичным кодам в языке L. Пусть далее R есть произвольное подмножество регулярных языков, тогда

h{R) = max h(L).

L£R

Для исследуемого в работе класа Щ доказано, что h(R!¡) = 2.

Пусть Ri обозначает множество регулярных языков, порождаемых автоматными источниками с i состояниями. Показано, что с ростом числа состояний возрастает и

величина /¡(Л;), а. именно, h(Ri) > г, где i = 1,2,____

Далее в четвертой главе исследуется эффективность приближенных методов кодирования для языка Led' Рассматривается метод оптимального обобщенно префиксного кодирования и метод Хаффмана. Метод обобщенно префиксного кодирования характеризуется тем, что при кодировании используются только дешифруемые коды с конечной задержкой декодирования. В диссертации получено описание матрицы оптимального обобщенно префиксного кодирования с (задержкой декодирования, не превосходящей размерности алфавита языка, и разработан эффективный метод построения оптимального кода, обладающего данной задержкой декодирования,

Для оценки эффективности этого метода введем следующие обозначения. Пусть Pi — частота буквы d, pm¡„ — минимум частот букв множества С, m = |(7|. Если Pi > Pmm> то стоимость обобщенно префиксного кодирования совпадает со стоимостью оптимального кодирования, в противном случае их разность не превышает

Под кодированием методом Хаффмана понимается кодирование языка Ьы как языка всех сообщений в алфавите G U d, Эффективность этого метода ниже эффективности метода обобщенно префиксного кодирования. Доказано, что разность стоимости кодирования методом Хаффмана и стоимости оптимального кодирования в худшем случае ' превышает

Список работ, опубликованных по теме диссертации

1. Кочетов A.A. Алфавитное двоичное кодирование произведения свободной полугруппы и свободной моногенной полугруппы // Тез. дом. VI Всесоюо. юнф. "Проблемы теоретически кибернетики". Саратов, 1983. 4.1. С.107.

2. Кочетов A.A. Алфавитное двоичное кодирование языков, разложимых в произведение двух свободных полутрупп // Труды 3 Конф. мол. ученых НИИ прикл. мат. и кибернет. и фак. вычисл. мат. и кибернет. Горы, ун-та. Горький, 1984. C.146-15D. 5836-84 Деп.

3. Кочетов A.A. Алфавитное двоичное кодирование произведения свободной полугруппы и свободной моногенной полутруппы // Материалы Всесоюзного семинара по дискретной математике и ее приложениям. М.: изд-во Моск.ун-та, 1986. С.197.

4. Кочетов A.A. Об обращении регулярных языков // Материалы 4 Науч. конф. мол. ученых НИИ прикл. мат. и кибернет. и фак. вычисл. мат. и кибернет. Горьк. ун-та. Горький, 1986. С.96-98. 4227-В86 Деп.

5. Кочетов A.A. Об одном свойстве полных префиксных кодов // Тез. докл. VI Науч. конф. мол. ученых Волго-Вятского региона. Горький, 1986. С.104.

6. Кочетов A.A. Нециклические буквы и пополнимость кодов // Тез. докл. VII Науч. конф. мол. ученых Волго-Вятского региона. Горький, 1987. С.98.

7. Кочетов A.A. Оптимальное кодирование произведения свободной полугруппы и свободной моногенной полугруппы // Тез. докл. VIII Всесоюз. конф. "Проблемы теоретической кибернетики". Горький, 1988. 4.1. С.177.

8. Кочетов A.A. О равномерной пополнимости при алфавитном кодировании регулярных языков // Тез. докл. IX Всесоюа. конф. "Проблемы теоретической кибернетики". Волгоград, 1990. 4.1(2). С.35.

9. Кочетов A.A. Алгоритм оптимального алфавитного кодирования на примере одного регулярного языка Ц Вестник Верхне-Волжского отделения Академии технологических наук Российской Федерации; серия: Высокие технологии в радиоэлектронике, Н.Новгород, 1(2)/96. С. 123-129.