Сложность сжатия информации тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

АКАДЕМИЯ НАУК СССР Вычислительный центр

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

Кричевский Рафаил Евсеевич

УДК 519.72 •

, СЛОЖНОСТЬ ЛСАТИЯ ИНФОРМАЦИИ

01.01.09 - математическая кибернетика

Автореферат диссертации на соискание ученой степени доктора фиэико-ыатематических наук

МОСКВА - 1988

| Работа выполнена в Институте математики СО АН ССбР. |

Официальные оппоненты* доктор фидико-математических наук ;

В.М.СИДЕЛЬНИКОВ • \

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

А.О.СЛИСЕНКО |

доктор технических наук | И.А.УШАКОВ '

Ведущая организация - Математический институт им.В.А.Стек'

!

I лова АН СССР (Ленинградское отде- |

! ление) '

; Защита диссертации состоится " " • - 1988

года в_часов на заседании специализированного совета >

Д 002.32.02 при Вычислительном центре АН СССР по адресу» ; 117967 Москва, ГСПЛ, у*. Вавилова, 40,

С диссертацией можно ознакомиться в библиотеке ВЦ АН СССР.

Автореферат разослан " * 1988 г, , ;

■■ I: ■ ■ ■:'■ ' ' ' ■

Ученый секретарь

специализированного совета л. ^

к.ф.-м.а. I ^У! С.М.Швартин

; ' ' ! ОЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ . _ . " .

и !

^^'Актуальность проблемы. В информатике часто -.встречается «¿дача"компактного представления .(сжатия)данных.-Она является ; предметом изучения раздела теории информации, называемого "кодирование источников". Лсновной цель» этого раздела было 'нахож~■ дение предельно достижимого сжатия информации. ' .•:

Источники информации принято разбивать на два класса; ; комбинаторные или словари, задаваемые множеством допустимых [! сообщений,'и вероятностные, задаваемые-распределением вероят- | ностей сообщений. Дня простейших комбинаторных источников пре~ цельно возможное сжатие было найдено "пионером теории, Р.Хартли

в-1928 г. Для протых вероятностных источников это было сделано

!

в -работе К.Шеннона п 1948 г.-Дата появления этой работы считается, днем ровдения теории информации. ; ;

Задача нахождения предельного возможного сжатия, или, пто эквивалентно, количества создаваемой информации, интенсивно разрабатывалась многими учеными, ¡¿а упомянем работы Д.Бленуэлла, 1.М.Гельфавда и А.М.Яглома, А,Н.Колмогорова и Б.^Тихомирова» •ЦС.Шнскера, А.Я.Хинчина, Д.К.Заддеева, Р.Фано. К настоящ му зремеки"эта задача решена для широкого класса источников сообщений. Естественно, что возник вопрос о цене, которую мы доллар -йлатить за приближение к предельно возможному сжатию.

Новое направление в теории кодирования источника занклавт-■я* изучением слоаности сзатия информации. Оно возникло как ло-ическое продолжение первых исследований в этой о&ласта. В ;ервой работе автора 1956 года в качества показателя сложности

была выбрана длина кодового блоке.. Эта работа уточняет теорему» Шеннона о бесшумном кодировании: у Шенноьа найдена верхняя,, а, в работе автора - нижняя оценка избыточности.

После -выяснения' зависимости между длиной кодируемых слов и избыточностью оказалось возможным сдел .ть следующий шаг. В качестве показателей сложности были взяты общепринятые в информатике длина программы и время вычислений. Цель направления - изучить,, как* возрастают: эти показатели с увеличением сжатия,, т.е. .с уменьшением избыточности. Необходимо найти нижние оценки "ложности. Трудность состоит в"построении сжимающих алгоритмов, сложность которых асимптотически равнялась бы низшей оценке (/ли была бы близка к ней). .

Обратимся теперь к ватаой для информатики задаче размещен кия и поиска слов в памяти компьютера. Ей посвящена значительная часть й тома энциклопедии Д.Кнута, книги С.С.Лаврова и Л.И.Гончаровой, Т.Кохонена, Т.Ткори и Д«Фрая, а также многие другие книжные и журнальные публикации. Разработано и продол-* хает разрабатываться большое число алгоритмов поиска. Отметим, что интересные'идеи ло поводу организации поиска высказывались в свое время А.А.Ляпуновым. Публикации его учеников Ю.И «Журавле за и А.Л.Ершова были'в числе первых-на эту тему.

Одчако-задачи сжатия и поиска информации рассматривались обособленно. В результате не была найдена предельная возможная длина поисковых программ, и нельзя было сказать, насколько "далек от оптимума,тот или иной метод. Актуальным стал вопрос нахождения ккжн::: оценок сложности программ поиска и построения асимптотически наилучгг-х алгоритмов.

Он стад предзетой рассмотрения направления, изучающего

ложность сжатия/ При этом подлежащая размещению а памяти ин-орлация считается произведенной некоторым комбинаторным источ-иком. И поиск, и сжатие-изучамтся одновременно.

Отдельно отметим_ важнейший из поисковых мегодов - хеширо-ание. Все работы основаны на предположении, что функция, пере-одящая слово в его адрр". (хеш-функция) выбрана,удачно. Совер» енно естественные вопросы о том,. сколько раз такой выбор при-ется повторить, или какая програшная Сложность необходима ; ля хеширования словарей данного объема, в литературе не рас-матривались, (

Цель работы. Целью диссертации является изучение завися- ¡¡, ости между степенью и сложностью сжатия информации для основ-', их типов её источников. Поиск рассматривается как частный слу-ай сжатия« Ставится задача нахоздения оптимальных или близки;« ним поисковых и сжимающих алгоритмов. Основное взимание уде-яется конечным источникам. Степень .сжатия характеризуется т-ыточностью, а его сложность - длиной сжимающей программы, водится функция, равная минимальной сложности, необходимой ля достижения заданной избыточности (функция слогшость - из» точность)» ,

Основные результаты диссертации» Получены асимптоткческио ценки функции сложность » избыточность для вероятностных и оыбинаторных" источников. ' ^

Построен оптимальный алгоритм сжатия и нумерации словарей. Обнаружен эффект удвоения энтропии£ при.росте избыточнос-и свыше 100$ сложность сжатия и поиска резко падает, становясь инейной из экспоненциальной (относительно длины лов).

Доказано, что для большинства каналов с аддитивный вуиои зврстная верхняя граница Вароаыова-Гильберта для объеяа г рулевого корревтирулцего кода асимптотически наудучз&еыа„ Следо-

• 6

( ^ателькб* для таких каналов эта граница служит также и нижней

ц ^ревосхрдит известную границу Хеммингг.. I Установлена асимптотика мощности универсальных нумерующих

\ ^цржеств.

^ Построены новые семейства хеш-фуда-дий,и доказано, что они ; близки к оптимальным.

У Предложен эффективный способ построен;..; близких к опти-I «аяьнш программ вычисления частичных булевых функций.

Оценена функция сложность - избыточность для источников I Бернулли« . " _ ■ •

.• Найдены, оценки, длины блокад необходимой для достижения заданной избыточности при.кодировании источников Бернулли.

Найдена асимптотика избыточности универсального кодирования источников Бернулли. . ' -'. Построены асимптотически оптимальные адаптивные коды для источников Бернулли* . ■ .

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

Научная новизна. Б таблице ыы сравниваем полученные в . ■ диссертации алгоритмы поиска и сжатия с ранее известными.

Словарь ^ содержит { 5 ( слов длиныГЬ . Сильна;, поисковая

прогр^-Ама нумерует его слова и переводит его дополнение в 0 ;

слабая только нумерует его слова. При хешировании допустимо

склеивание слов в цепочки. Объем таблицы» где размещается £ »

. 151 яг

равен , оч ~ . называется коэффициентом загрузки,

% ^ » $ - избыточность, - энтропия

Сложность алгоритмов поиска

Алгоритм поиска Длина программы .Используемая память Время вычислений Средняя длина цепочек Сильный Илй ела бый V

Поиск в неупорядоченной таблице 0(п) 1 ^

Поиск а упорядоченной таблице (¡{•п. ООг). тт) :1

Обычный побуквенный поиск оОя^т); ,'01н.)г 0( н) - 4. V/

Нумерационный алгоритм Ковера ШУ. 0(2Ч) ±

Слабый побуквенный поиск, теорема 4.3 ш. 0(К) ' 1 V/ -

Сильный побуквенный. поиск, теорема 4.4 ш ОСИ) " 1 ^ ;

Слабый поиск . теорема 4.1 {Я -Ш-. оси) 0(Ю . 1 -V/

Линейное хеширование теорема 4.5. ОН ОСн) . сС у,

Полиномиальное хеширование, теорема 4.5 ои 0 (к) О) у, г^ К/

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

Алгоритм теоремы 4.1 (197о год) является асимптотически оптималькш. В 1982 году К.Ыельхорн опубликовал алгоритм, который хуже алгоритма теоремы 4,1 в константу рад.

Вопрос о нижних и верхних оценках ыоц^ости кодов является в теории информации центральным. Для каналов с произвольны! шумом верхняя оцек..а установлена В.Д.ГоппоЯ. х'с, что она, как

правило, является и нижней, обнаружено" впервые, так же как и эффект удвоения энтропии.

Теорема 3.1 о мощности универсальных множеств, опублико-> ванная в 1976 году, была переоткрыта Комлошем и Фридманом в 1984 году, »ни называют эти множества разделяющими.

Семейства хеш-функций,.эффективность которых близка к эффективности хеш-функций, построенных автором в 1984 году, определены Кэмлоае.м, Фридманом и Семереди в том же году. Одна ко б работе 6тих авторов отсутствуют нижние оценки сложности "¡хеширования.

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

"Асимптотика избыточности универсального'кодирования источников Бернулли получена впервые. Ранее Б.М„3?итингофом опуб ликована неравномерная верхняя оценка этой величины.

Адаптивные коды бьши найдены автором з 1968 году. Коды такого вида строились, затем Е.Гилбертом'(1971 год), Т„Ковером (1972 год), И.Вайдой в 197с." году, а также другими авторами.. . Все эти коды асимптотически уступают кодам теоремы 5.3.

. Апробация работы."Результаты диссертации докладывались я Международном конгресс. математиков в Москве в 1566 году, на 3, 4, 5 и 6 Международных симпозиумах по теории информации •в Таллине, Ленинграде,'Тбилиси» Ташкенте (1973, 1976, 1979, 1964 г.г.), на 7 и 8 Всесоюзных конференциях по теории кодирс вания (Ьилькюс, 1978, луйбысев, 1981), на 3 Чехословацко-Вен-герска-Советскои семинаре по теории информации в Чехословакии 1550 гоД, на конференции по теории информации в Венгрии, 197с

год» на 2 и 3 Семинарах по'сложности вычислений в Гродно и Кулдиге (1983, 1985 годы)»' а также на семинарах ИМ СО АН, ВЦ Ш СССР, ЛОЖ АН СССР, МГУ. Все результаты опубликованы в работах I - 21 v В том случае», если работа имеет соавторов, i в диссертацию включались, т.олька, рэзудьтагк* тлученные лично -автором. ' • . v

Использование результатов диссеатахжуь. Направление» изучающее сложность -сжатия информацииh развивалось а работах уча- j ников автора, РД.Ходак выяснил,, какие-преимущества дает не- f блочное кодирование, источников с. конечной: памятью. В.К.Трофи-ыовым найдена асимптотика разных'типов универсального кодиро- j вания для источников Маркова. Развивая метод автора для получения нижних оценок избыточности универсального кодирования, [ Б.Я.Рябко установил ваяную связь между универсальнымкодированием и кодированием.канала, переогкрытув затем.Л.Дэвисоном и А.Леон-Гарсиа. Используя теорему 5.3, Б.Я.Рябко, получил близкое к окончательному решение известной задачи Кнута и Злайеса о динамическом-кодировании.

Результаты работы используются в монографии Чисара и Кёркз-ра, в статьях Ёабкина, Гоппы, Дэвисона, Леон-Гарсиа, Сгарр^, Риссанена» Элайеса, Казаноса, Лонго и Неметца, Монтгомери. Такие результаты работы,. как эффективный алгоритм размещения словаря в памяти, оценки длин тестов, оценки качества-универсальных кодов, предназначены для использования в научных исследованиях. Они уяе применяются в космических исследованиях, при построении определеителей растений и яивоьных, а такай в учебном процессе в МГУ и Новосибирском институт связи.

Методы работь. В диссертации разработаны'новые методы

получения нижних оценок избыточности универсального кодирования и мощности универсальных множеств, а также методы построения прогрьл», сложность которых близка к нижним оценкам. В нервом направлении, изучающем сложность сжатия, используются также методы теори" корректирующих кодов: ыегсд случайного кодирования и коды над полямиТалуа. С другой стороны, полученные в рамках этого направления результаты'имеют применение'в теории кодов, как, например, утверждение'об оценке Варшамова-Гилберта

Структура работы. Работа состоит из введения л. шести глаг В приложении приводятся данные'о некоторых применениях работы, р^ъем работы 169 страниц, список цитированной литературы содержит 87 названий,'в том числе 21 публикация по теме диссертации, >

ОПИСАНИЕ РШН'

Б перрй главе мы напоминаем основные понятия теории инф ^цич» которые используются в диссертации. Это понятия источника, кода, энтропии, избыточности. Как это принято вслед за Хартли, Шенноном 55 Колмогоровым, мы различаем источники двух типов: вероятностные, задаваемые некоторой мерой, и йомбинато ные, задаваемые множеством допустим^-слов. Основное внимание уделяеия конечным вариантам этих источников. Степень сжатия информации характеризуется избыточностью, которая равна относительному превышению средней длины кода над энтропией источника. Приводятся некоторые простые свойства этих понятий.

Б 1.3 задача поиска слов в памяти компьютера интерпретируется теоретико-информационным образом: словарь считается источником, а адреса слов считаются их кодами. При этом мето-

ни, допускающие присвоение раз:!ым словам одинаковых адрёсоЬ (хеш-методы), включаются в обцуЬ схему'.; Они соответствуют списочным кодам источника, а средняя -длина цепочек слов с одинако-зым адресом "характеризуется шЦеисом коДа! Выделяются сильные •етода поиска, позволяющие опЬеДёляй. наличие в слозаре искомо»* 'О слова. Задача вычислс.шя булевык функций также рассматриёа- ¡, !тся с точки, зрения теории информации! Кодом функции служит' фогракма ее вычисления на компьютере. |

В § 1.5 мы вводим основные величины, изучении которых |>' освящена диссертация. Это - минимальная прог-

пымная сложность, достаточная для кодирования комбинаторного ,'' сточника, по рождающего слова длины ¡Ъ с энтропией % . Коди~'; звание имеет избыточность -¿> й индекс сь . При ■ а >0 мы име-.! дело с хеширование:«, а при Ц-О с йкьективньм кодирован!*-Величину )£ (^)Т; Р',0) обозначаем через Т, • Зуни-ш Т/ 'Р) равна сложности скатил ■'до степени инфор-

щии, порождаемой комбинаторным источником с энтропией. . «алогичная величина для сильного кодирования ке зависит от .0

«л-*--

обозначается через ^ - •

Минимальная программная сложность кодирования с избыточ-

стьа ^р вероятностного источника, порожцагщего слова длины

Я •

с энтропией Ъ , равна ^р) , а та а величина

я источников Вернуяли равна (И, Т, у) . Изучение асиыпто-ческого поведения функций £0,т,„ 41 & (.111 ^ р / является основной цедьи диссертации.

Для оценки к, _р) не обходимо знать веяичннн {,■() $) - избыточность кодирования источника. аернулл:г и ^ (Д ) - избыточность кодирования источников Вернула» пр.:

наличии выборки длины Ь . .В частности, ^ 2 (.<£) равно 1

избыточности унивгреального кодирования источников Бернулли.. Эти величины представляют самостоятельный интерес. ; . Самостоятельный интерес представляет также и .используемое , при оценке £ $ а) понятие. СЪ -универсального множества. Множество эквикластерных отображений из Р $ Е^ »

Г^'сСЯ"г называется & -универсальным, если для кавдо-

, го - Е*Ь, ( ~ ^ оно содержит отображение, индекс которого на £ не превышает <Х> (эквикластерными называем отображения, принимающие каадое из своих значений одинаковое число раз). Мощность минимального Л-универсального множества обозначим ■ . . .

■ Во второй главе мы приводим такие модификации употребительных методов поиска, которые нам потребуются в четвертой главе при построении оптимальных- сжимателей. В § 2.1 рассмат-. рл-^ается лексикографический поиск, программная сложность которого раена % • для источников с -энтропией , что . ' соответствует оценке - ^ • & « В лемме 2.2.оценивается сложность лексикографического поиска, который проводит-< ся в рамках некоторого заранее заданного разбиения исходного словаря. В § 2.2 мы переходим к побуквенному. поиску, который ведется посредством изучения в некоторой -последовательности бука разыскиваемого-в словаре (кодируемого) слова. Сложность этого вида поиска равна % ЬХ . В лемме 2.4 мы •• оцениваем сложность двухступенчатого побуквенного поискЬ. При этом, добравшись до листьев некоторого дерева, мы переходам в новые деревья, и начинаем нумерацию енова. Эта позволяет укоротить поисковую программу. В § 2«3 вначале излагается нуме- -

„рационный метод Ковера. Он дает оценку что является асимптотическим минимумом для сильного пдиска. Однако метод Ковера требует экспоненциально больших времени работы и памяти. В лемме 2.5 мы приводим двухступенчатую модификацию этого метода для равномерных деревьев.

Глава 3 посвящена оценкам мощности универсальных множеств. В ней основными результатами являются теоремы 3.1 и 3.2, где оценивается число % Р>, а также теорема 3.3, где излагается- метод построения -универсальных множеств.

В § I, в лемме 3.1 находятся вероятности встретить словарь или отображение с данным набором мощностей кластеров. • Далее, в лемме 3.2 эти вероятности приближаются распределением Пуассона. Используя лемму 3.1,мы можем установить утверждение 3.1: наименьший средний индекс имеет эквикластерное отображение. Эта утверждение служит теоретическим объяснением того факта, что на практике используются именно такие отображения в .качестве.хеширующих. Поскольку эквнкластерныз:отображения превосходят все другие, мы только их включаем в универсальные множества.... у '

В лемме 3.3 мы находим вероятности больших уклонений индекса для эквинластерных отображений, используя неравенства С.Н.Бернятейна, В.В.Петрова я С.В.Нагаева. Они относк :ся к суммам одинаково распределенных независимых случайных величии. Однако в теореме 3.1, пункты б) и в), у нас появятся зависимые случайные величины с разнили.распределениями. .Дяг оценки вероятностей больших уклонений в этой ситуации мы доказываем лемму 3.5» а предварительно - чисто арифметическое неравенство леммы .-3.4. ■'; ;- •

В тёореме 3.1 устанавливается оценка для мощности О -универсального множества, или мнояеетва нумераторов!

fof N Си, ^ р) ^ eog e -i -í il ^C'i- ChJ>)) • ^^^

При этом используется метод случайного, кодирования. В теореме 3.2 такая оценка находится для мощности &-универсального множества при &>€> . Верхние оценки получаются вновь методом случайного кодирования.^Нижние оценки при J3 ¿ ~ ^^ сразу вытёкают из леммы 3.3. Однако при J5 ^ - ле'/:Ма 3.3

дает тривиальные результаты, и здесь для доказательства раз-patíoiák другой метод; позволяющий получить достаточно точную' оценку. Теорема 3:2 устанавливает, что при переходе избыточ-

■ - • v. ■ ч &<|ó¿, .•-"-.

ности через — мощность. -универсального множества

резко падает.

В теореме 3;3 доказано,* что (¡1 ,t) -код яв^яётся^Т1!)^-^] -универсальным множеством для ¿ловарей мощности . На основе этой теЬремы строятся хеш-функции с небольшим индексом в главе 4. Следствие 3.Í устанавливает существование столбца, который делит словарь 5 ^á две близкие по мощности половины. Это следствие используется в лемме 3.6, где строится сбалансированное двухступенчатое поисковое дерево. Такое дерево является осно- ' вой ведения оптимального побуквенного поиска в § 3. Близкая к теореме 3.3 лемма 3.7 говорит, что в любом (ЬД) -коде £ найдутся U\ | S | позиций, в. который все слова кода различны.

В глава _ 4 излагаются основные результаты диссертации-относящиеся к комбинаторным песочникам. В теореме 4.1 доказано, что

л-нт/>

если коэффициент загрузки ск-% -Сомт , а.й теореме 4.2 - что . ч •

ХСЬ.Т^)-^ при .

, при . Для доказательства

этих теорем используются полученные в предыдущих главах результаты. Чтобы построить оптимальный нумератор, мы вначале разбиваем словарь на классы смежности относительно некоторого кода Еоуза-Чоудхури, а затем ведем лексикографический поиск в рам-яах этого разбиения (лемма 2,2), На определенном этапе поиск прекращается, и мы выбираем, согласно лемме 3.7, тестовые раз. ряды нумеруемого слова. После этого лексикографический гэиск возобновляется, но с использованием лишь тестовых разрядов. Наконец, на некотором специально выбранном шаге, используем универсальный нумератор (теорема 3,1). В следствия 4.1 устанавливается эффект удвоения.энтропии: величина экспоненциально велика при ^ и линейна по Гь при. В следствии 4.2 доказано, что для большинства кодов с аддитив- ■ ным шумом оценка Варшамова-Гилбзрта является наилучшей возможной. .

3 §§ 4.1, 4.2 кодирование производится с использованием универсальных нумераторов, построение которых весьма трудоемко. В теореме 4.3 строится нумератор, сложность которого равна С ■ I 5) • ^^ К/ , т.е. несколько выше оптимума. Однако этот нумератор очень просто находится По словарй ^ . При этол используются леммы 2.4, 3.6 и следствие 3.1. В теореме 4.4 .

15

с помощью этого нумератора мы получаем сильный нумератор, т.е. равный 0 на дополнении словаря ^ , и доказываем, что

Qi" НТ

оС (и.чО/^/Ь 'H'(,-t-T) . Время поиска для всех нумера-

торов равно ОСИ"). Из теоремы 4.4 вытекают два следствия. В следствии 4.3 строится программа вычисления частичной булевой функции, определенной на множестве ^ слов длины fü . Сложность этой программы равна С'ISl- ¡Ъ » а время работы 0[h) . Это больше» чем сложность оптимальной программы,: построенной Э.Юечипоруком и Д.^.Шоломовьм* однако, в отличие от оптимальных программ,, ttaaa программа просто строится по функции. В следствии 4.4 для будз?оП функции, равной единице _ на множестве '(jt(S }~rCJ O^T^i » строится программа ее

вычисления с минимальной сдщрфэдью ^. h. ) и временем • Заметим»/что если, построить программу вычисления такой фукции на основе созданных и.В.Лупановым схем, то такая программа будеф иметь ту „се сложность, но существенно большее время работы* - " •

Основным резудададом; §,- 4.,4 является теорема 4.5^ где устанавливается, что, ори. ' Р ^ _ сложность, хеширо-

. : . К X

вания ^(KjT^/ü) экспоненциально велика,_ а.при

р>,_ J^ü эта сложность становиз&я; линейной по .

В доказательстве использугтся,:^врреМы« Зч/З? Ж 3*3»,; Предлагаются ' методы хеширования,, близкие к- оптимальным по объему необходимой памяти и по времени вычислениях.

В главе 5 изучаются вероятностные источники. В лемме 5.1 .. рассматривается множество Источников, порождающих Т" равновероятных слов длины Ку , и оценивается число источников, для рторых средняя стоимость данного отображения не превышает-

16

заданной. Используя эту лемму, мы доказываем в теореме 5.1,

вероятностных источников уже экспоненциально сложно. Этот результат контрастирует со следствием 5.1: для комбинаторных - источников нетривиальное'сжатие при тлеет линейную .

сложность.

Сжатие произвольных вероятностных источников очень трудоемко, Однако сжатие информации, порожденной подклассами вероятностных источниковр оказывается достаточно просто реализуемым. Мы изучаем в §§ 5.2, 5,3 важнейший такой подкласс, источники Бернулли. При этом для оценки сложности кодирования

Ь (Т^) мы нувдаемся в оценках избыточности ¡З.С4>

а такие избыточности универсального кодирования Й. С^ ) и адаптивного кодирования й.и СТ} • Эти величины представляют и самостоятельный интерес. В теореме 5,2 доказано, что для любого источника $ о конечной память», кроме источника Бернулли с согласованными вероятностями, 2) » ГД®

- длина блока. Отсюда вытекает (следствие 5.1), чт'» 8 '

X Си^Т, ~) }-ъ , и кодирование с избыточностью, меньшей , невозможно. Теорема 5.2 дополняет теорему Шеннона о кодировании для бесшумного поиска: теорема Шеннона мает верхкш, а теорема 5,2 - ниянюю оценку избыточности.

В § 5.3 основной является теорема-5.3, где находится асимптотическая оценка избыточности адаптивного кодирования!

Р

чф

Ьнм^. ~Ь -г Л

где - объем- алфавита, Ь - объем выборки, К» - длина

блока. В доказательстве попользуется усреднение по распределению Дирихле. Предварительно в лемме 5.2 находится равномерная . оценка разности между средней эмпирической энтропией и энтропией. Неравномерная оценка, полученная Г.П.Башариным для наших целей оказывается недостаточной. В следствии 5.2 оценивается избыточность универсального кодирования источников Бернулли:

Ш) - ^ Щъ

В следствии -5.3 находим оценку сложности кодирования источников Бернуллиа

Глава 6 посвящена приложению некоторых результатов диссертации .к научным исследованиям. В § 6,1 конструируется простой алгоритм раЕ Ювдания данных в памяти компьютера При этом время поиска почти минимально,. В •§ 5.2 показано, -что, донская небольшую .ошибку* -Мы можем существенно сократить дайну теста для почти ¡всех ¡паблиц. Предварительное линейное преобразование позволяет сократить эту длину всегда. Эти факты полезны во многих применениях жестов. В § 6,3 описываются приложения методов универсального кодирования к сжатию данных и построению определителей. Эти методы нашли практическое использование.

Основные утверждения, выносимые на защиту;

Теоремы 4.1 и 4.2, дающие асимптотические оценки сложности

' ^(Ь) сжатия с избыточностью р источника с энтропией '¿Г 4 "

при ¿ - i ~nrf

4L Кт, ?) - % t

№,7,?) - OW ,

Теорема 4.5, устанавливающая, что сложность хеширования с индексом а и избыточностью J> источников с энтропией Т. экспоненциально велика п,и J3- и линейна при р - .

ьг

Теорема 5.3, дающая асимптотику избыточности адаптивного кодирования блоками длины УЬ при.известной выборке длины h и объеме алфавита ; •

Публикации по теме диссертации;

1. Кричевский P.E. Длина блока, необходимая для получения заданной избыточности. - ДАН СССР, 1965, т.171, № I, с. 37-40.

2. Кричевский P.E. Связь между избыточностью кодирования и достоверность» сведений об источнике. - Проблемы передачи информации, IS68, т.4, № 3, с. 48-57. -

3. Кричевский P.S. Лекции по теории информации. - Новосибирск, изд. НГУ, 1970, 82 с. -V

4. Кричевский P.E. Оптимальное кодирование источн"ка на основе наблюдений. - Проблемы передачи информации, 1975,.т.И,

№ 4, с. 37-42.

5. Кричевский P.S. Сложность нумерации конечного множества

слов» - ДАН СССР, 1976, т.228, i 2, с. 287-290.

6» Кричевский Р.Е. Побуквенная нумерация двоичных словарей. - ДАН CCCPS -1978, -г.239, р 5, с0 1044-1047.

7. Кричевский Р.Е, Оптимальный поиск-информации. - Проблемы кибернетики, 1979, № 35, с. 159-180.

8» Кричевский Р.Е. Почти инъективные отображения и хеш-функции. - ДАН СССР, 1984, т.277, № 5, с. 1053-1056,,

9. Кричевский Р.Е. Эффект удвоения энтропии. - ДАН СПСР, т.28, 1985, т.284, » 4, с. 795-798. «...

IQ. Krichevsky R.E. Trofimov V.K. The performance of universal Encoding, IEEE Trans, on Inf. Theory, 1931, v. 27,N 2, p. 199-207.

11. Krichevsky R.E., Ryabko B.Y., Harifconov A.Y. Optimal key for taxons ordered in accordance with thein frequencies, QiscsvAppl. Math. 1981, v. 3 f( 1, p. 67-72.

12. Krichevsf"/ R.E. Optimal Hashing. - Information and Control, 1984, . v. 62 К 1, p. 64-92.

Тезисы докладов

13. Кричевский Р.Е. Длина блока,, необходимая для получения заданной избыточности» - В кц.; Тезисы кратких научных

'сообщений Международного конгресса математиков, секция 13, М., 1966, с. 23-24,

14. Кричевский Р.Е. Оптимальное кодирование неполностью известного источника, - В кн.5 "Тезисы Ш Международного симпозиума по теории информации", Москва-Таллин, Наука, 19739

• с. 93-97.

15. Кричевский Р.Е. Сложность кодирования произвольного источника. - В кн.| 4 Международный симпозиум по теории информации. Москва-Ленинград, 19<о,

16. КричеЕский Р.Е,,Нумерационное побуквенное кодирование источника. - В кн.I Тезисы 7 Всесоюзной конференции по теории кодирования, Вильнюс, 1978, с. .93-90.

17. Кричевский Р.Е. Универсальное кодирование и колкзгоровская сложность. - В кн.: 5 Международный симпозиум по теорий инфордации, Москва-Тбилиси.

18. Кричевский Р.Е.» Трофимов В.К. Универсальное кодирование произвольного множества марковских источников. - В кн.г1. Тезисы 8 Всесоюзной конференции по теории информации, Куйбышев, I9SI, е.- 40-43. . '

19. Krichevsky R.E., Trofimov V.K. Optimal coding of unknown sources -CoUoq. Math. Soc. J. Bo?., Topics in Inf. Tfi_».Hungary, 1975, c. 425-430. ' Г

20. Krichevsky R.E., Trofimov V.K. Optima I SampTebased encoding marfcov < sources, 3 Cz.-Sov. Kurs. Setn. on Inf. Theory, LibHcs, 1980, p. . 131-133. .

25. Krichevsky R.E. List source encoding and information retrieval - В кн.: б межд. симпозиум по теории информации, Москва-Ташкент, 1984, с. 221-224. .