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

Введение.

Глава 1. Статические и адаптивные методы кодирования.

1.1. Статический код Хаффмана.

1.2. Адаптивный код Хаффмана.

1.3. Ранговое и интервальное кодирование.

1.4. Арифметическое кодирование.

1.5. Выводы.

Глава 2. Параметрически адаптивное кодирование.

2.1. Конструктивное определение параметрической системы кодовых множеств.

2.2. Дескриптивное определение параметрической системы кодовых множеств и оценка ожидаемой длины кодового слова.

2.3. Алгоритмы параметрически адаптивного кодирования.

2.4. Ранговая перестановочная схема.

2.5. Об использование ссылочных структур в ранговой схеме.

2.6. Вероятностная перестановочная схема.

2.7. Ранговая перестановочная схема с логарифмической зависимостью числа перестановок от размерности алфавита.

2.8. Об адаптивной оценке параметра кодирования.

2.9. Выводы.

Глава 3. Реализации и прикладной анализ адаптивных схем.

3.1. Система модельных реализаций.

3.2. Тестовые модели данных и система оценок.

3.3. Модели с распределением равномерного типа.

3.4. Модели с распределением нормального типа.

3.5. Модели с распределением геометрического типа.

3.6. Выводы.

Глава 4. Применение параметрически адаптивного кодирования для решения прикладных задач компрессии данных.

4.1. Особенности кодирования в словарных методах Лемпела - Зива.

4.2. Параметрически адаптивное кодирование избыточных длин и смещений текстовых фрагментов в схеме LZ77.

4.3. Реализация Ь277-кодера с параметрически адаптивным кодированием избыточных длин и смещений (LZP).

4.4. Применение LZP-кодера в задачах компрессии данных.

4.5. Выводы.

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

Первый - вероятностный, базирующийся на основных положениях Шенноновской теории информации [66,18] и традиционно представленный статистической теорией оптимального кодирования, - основан на использовании для каждого символа а & А, где А - кодируемый алфавит, кода с длиной близкой по величине -1 ogp(a), где р(а) - вероятность (или частота появления в кодируемом потоке) символа а. Широко известны классические алгоритмы построения близких к оптимальным множеств кодовых слов для заданных алфавитов по известным (статические алгоритмы) или динамически вычисляемым (адаптивные [64] или, иначе, динамические [25] алгоритмы) оценкам вероятностей их элементов (символов, букв, слов). Это алгоритмы кодирования фиксированных алфавитов и соответствующие им коды, известные как коды Шеннона[66,18], Хаффмана [66,18,19,21,25], алфавитные коды Гилберта-Мура др., а также, занимающий по ряду причин особое место в указанном ряду, арифметический код [39,38,37,20,42].

Второй - словарный [2] - основан на выделении тем или иным способом из кодируемого потока данных характерных для него фрагментов-строк, фактически составляющих некоторый новый алфавит (словарь), в терминах которого далее производится кодирование. Реконструируя словарь источника, эти алгоритмы решают задачу в некотором смысле обратную вероятностным. Несколько упрощая, можно сказать, что если канонические алгоритм ы оптимального кодирования имеют целью установить соответствие: алфавит => оптимальный код, то методы второй группы устанавливают для кодируемой последовательности отображение: избыточный код ^ оптимальный алфавит (словарь). Заметим, что дискретная задача построения оптимального словаря для некоторой последовательности символов, т.е. определения такого способа ее разбивки на составляющие словарь фрагменты, который минимизирует суммарную длину последовательности после статистически оптимального кодирования, относится к числу NP-трудных [44]. К словарной методам относится достаточно широкий спектр методов статического и полуадаптивного словарного кодирования (см. обзор [2]), но ' более эффективными и потому широко применяемыми на практике являются адаптивные словарные алгоритмы, базирующиеся на методах, впервые предложенных и обоснованных в работах Дж.Зива и А.Лемпела [29,50,49]. Эти алгоритмы объединяются родовым названием алгоритмов Лемпела-Зива или просто LZ-методов. Наиболее широко известны следующие их модификации[2]: LZ77 [50], LZ78 [49], LZW (алгоритм Лемпела-Зива-Велча) [47], LZR[41], LZSS[43], LZB[3], LZH[6], LZC[45], LZT[31,46], LZJ[22], LZFG[17], Несмотря на существенные алгоритмические отличия LZ-схем от традиционного статистического алфавитного кодирования, математическое их обоснование носит классический теоретико-информационный характер [50,49], где доказано, что метод LZ77 при достаточно большом размере окна просмотра не хуже любого полуадаптивного словарного метода, a LZ78 для стационарных эргодических источников асимптотически оптимален по длине кодируемой последовательности [49], или, иначе говоря, "LZ78 приводит бесконечно длинную последовательность к минимальному размеру, определяемому энтропией [эргодического] источника"[2]. В практических реализациях LZ-методов (коммерческие программные продукты COMPRESS, LHA, архиваторы ZIP-формата и т.д.) для достижения высокой степени компрессии данных и с учетом практических ограничений на время и объем используемой памяти практически всегда используется сочетание одного из вариантов LZ-анализа сообщения и статистически оптимального кодирования его результатов, реализующее тем самым двухступенчатую схему: избыточный код => алфавит (словарь) => оптимальный код. LZ-схема может быть при этом полуадаптивной. Например, популярный в перечисленных выше программных продуктах метод сжатия "deflate" использует поблочное LZ-кодирование с последующим включением в заголовок каждого закодированного блока таблиц статистически оптимальных кодов длин и смещений входящих в него строк.

В связи со значительным увеличением доступной оперативной памяти ЭВМ и быстродействия процессоров со второй половины 80-х годов получил развитие новый подход к компрессии данных, прямо развивающий традиционное кодирование алфавита по вероятностным оценкам, но при этом использующий адаптивные вычисления условных вероятностных распределений для символов исходного алфавита кодируемого сообщения. В зависимости от способа динамического вычисления вероятных оценок различают две группы методов этого типа [2]: контекстно-ограниченные («finite context modelling»), которые используют оценки вероятностей символов алфавита сообщения, условных по предшествующему контексту конечной (ограниченной) длины (алгоритмы DAFC [27], ADSM [1], группа методов РРМ [7,32], WORD [33]); и вероятностные модели автоматов с конечным числом состояний [2], использующие способ формирования в процессе кодирования динамической модели автомата с конечным числом состояний, распознающим кодируемую последовательность. Один из наиболее эффективных алгоритмов последнего типа использует двоичный алфавит и пытается строить модель конечного автомата с вероятностными переходами между состояниями близкую к вероятностной цепи марковского типа. Этот метод известен как динамическое марковское сжатие DMC [8], достигает значительного коэффициента сжатия для многих типов компьютерных файлов данных, включая текстовые, и имеет достаточно высокую скорость работы. Как контекстные, так и автоматные схемы используют арифметический код, позволяющий при обработке непрерывной последовательности кодировать символы с близкими к единице вероятностями так, что их вклад в длину результирующего кода приближается к нулю. Именно эта особенность арифметического кода позволяет указанным схемам для широкого диапазона типов данных достигать более высокой степени сжатия, чем у лучших реализаций 1^£-схем. При этом, однако, в отличие от последних они требуют вычислений в вещественной области и больших объемов доступной памяти для хранения текущих контекстов. Кроме того они уступают Ь2-методам в принципиально достижимой эффективности распаковки.

С появлением указанных алгоритмических схем компрессии данных было предложено разделить комплекс решаемых задач на две независимые составляющие [2,36]:

1. кодирование, как способ формирования кода сообщения по его вероятности;

2. моделирование структурных и статистических характеристик кодируемого источника для построения адекватных алгоритмов оценок вероятностей вырабатываемых им сообщений.

В соответствии с этой концепцией, получившей распространение в настоящее время, к задачам моделирования относят разработку контекстно-ограниченных схем и вероятностных моделей автоматов с конечным числом состояний. Словарные схемы группы Лемпела-Зива методы) в этом контексте обычно не рассматриваются [2].

Однако помимо вероятностных методов кодирования известны также алгоритмы, не использующие для формирования кода непосредственные вероятностные оценки [63,14]. К их числу относится алгоритм адаптивного кодирования, впервые предложенный в Б.Я.Рябко в [63] под названием "стопка книг" и далее независимо Дж.Л.Бентли с соавторами в [5] и П.Элайесом в [14]. В соответствии с этим алгоритмом кодер до начала кодирования вводит некоторый, в общем случае произвольный, линейный порядок Я на множестве кодируемых сообщений (символов) и далее код каждого кодируемого символа а определяется как функц л его ранга г(а), т.е. номера в упорядочении Я. Закодировав первый поступивший символ, кодер перемещает его на первое в Я место, после чего эта процедура последовательно повторяется для каждого символа входного потока. Адаптивность алгоритма при этом полностью определяется указанным динамическим изменением структуры а для кодирования рангов используется некоторое фиксированное множество кодовых слов переменной длины.

Подобным же образом для формирования кода сообщения вместо ранга может использоваться величина интервала между текущим и предыдущим его появлениями в выходном потоке источника. Интервал измеряется в единицах числа сообщений. Такое кодирование предложено в [14] и названо там интервальным. Заметим, что здесь просматривается определенная аналогия с кодированием смещений строк, разыскиваемых алгоритмом LZ17 в скользящем по тексту окне. В базовом варианте LZ77 длина кода определяется величиной скользящего окна как 1 где п„ - размер окна, но избыточность такого представления довольно велика. Минимальную избыточность здесь можно получить применением кода, вычисленного по точным оценкам вероятностей соответствующих смещений. Однако, как показано в разделе 4.1, для полностью адаптивного Ь277 с большой величиной скользящего окна получение таких оценок может быть затруднительным по ряду принципиальных и технических причин. В связи с этим концептуально задача кодирования рассматривается нами в следующей постановке.

Пусть имеется алфавит А= {сг0,а1,.,ап} (без ограничения общности положим \оё2(п + 1) N = {1,2,.+ 1,.}) и А1 = {-у = х1х2.Х|у||х/- еЛ,|л|</} есть множество всех строк длиной не более 1 над алфавитом А. Требуется кодировать строки вида 5-х1х2.хт, ¿еГ некоторого произвольно выбранного из А1 подмножества Тс А*. Символы каждой строки поступают на вход кодера последовательно, а его состояние и, соответственно, выходной код в каждый момент времени могут определяться лишь закодированной частью текущей строки и не зависят от строк, закодированных ранее. Пусть, кроме того, статистика распределения частот символов по всему множеству Т, а также в любой отдельной строке sei неизвестна. Необходимо определить алгоритм, сопоставляющий каждому i -му символу х, еА кодируемой строки seT однозначно декодируемое двоичное кодовое слово длиной ¡¡(s) бит так, чтобы суммарная длина всех двоичных кодовых слов и, соответственно, ее средняя величина на один кодируемый символ L были минимальными: М / s) /2\s\~> ™п' где N " Длина строки 5 в символах алфавита А . seT ¿=1 / seT

Обозначим через ps, статистическую частоту символа а, еА в строке sein введем величину hs=-tpsib*psi со 1

Средняя длина двоичного кодового слова закодированной строки 1 И

5 равная = — У /. где |s| - длина строки s в символах исходного алфавита

А. Назовем алгоритм сжимающим, если в результате его применения на множестве Т средняя длина кода // по множеству Т асимптотически пропорциональна среднему величины hs по тому же множеству Г, или более точно

И" ILs(2) ser

Величина rj может служить характеристикой степени сжатия алгоритма.

Алгоритмы, кодирующие строку за два просмотра двоичными кодовыми словами близкой к величине (-log//,) длины, часто определяемые как оптимальные, имеют Однако оптимальность таких алгоритмов например, неадаптивного кода Хаффмана или арифметического) строго определена лишь для класса кодов, длина которых в процессе кодирования последовательности сообщений (в указанной постановочной терминологии -строки s) не меняется. Адаптивные же алгоритмы могут обладать существенно более высокой степенью сжатия за счет динамической настройки кода при изменении статистических параметров кодируемой последовательности, и, соответственно, иметь 7/ < 1.

Поясним сказанное на примере. Предположим, что строка .V длиной т символов из алфавита размерности п (/? = 2а, с/ - целое ) содержит в точности по (т/п) символов каждого вида и, кроме того, состоит из р (р = 2е\>е<ё -целое) подстрок, - таких, что если некоторый символ aj встречается в какой-либо подстроке, то его нет ни в какой другой. Таким образом, алфавит делится на р непересекающихся подмножеств равной мощности и элементы каждого из них составляют какую-либо одну подстроку строки 5 длиной (т! р). В этом случае оптимальный статический алгоритм кодирования Хаффмана, очевидно, построит равномерный код длины с1. Адаптивный же алгоритм теоретически может использовать в пределе (без учета периода перестройки кода) р различных кодов (каждый для кодирования отдельной подстроки) и средняя длина его двоичного кодового слова при достаточно большом т приблизится к величине (¿-е) бит.

В настоящей работе предлагаются и исследуются ранговые й интервальные схемы, в которых для кодирования произвольной строки л еЛ' из символов алфавита А = {а0,а1,.,ап} используется не одно фиксированное множество кодовых слов, как это предполагается в [63,14,5], а некоторый параметрически определенный класс префиксно-свободных множеств кодовых слов с различной степенью зависимости длин кодовых слов от их индексов в множествах данного класса. Метод кодирования основан на адаптивной настройке значения параметра, обеспечивающего на каждом шаге выбор квазиоптимального для текущей статистики источника множества кодовых слов используемого класса, и потому обозначается далее как параметрически адаптивный. Показано, что при указанном методе кодирования независимого источника можно получить среднюю длину кодового слова асимптотически приближающуюся к величине Н(0) + с, где Н{0) - энтропия источника на алфавите А (т.е. вычисленная по мсппепепению вероятностей Q= {Qo,Qi,.,Qn\Qi = prob(ai),aj gA}), с - константа не зависящая от мощности кодируемого алфавита. Верхняя граница величины с определяется структурой класса кодовых множеств и способом адаптивной настройки параметра при последовательном [65] кодировании. Для ранговых перестановочных и интервальных схем при использовании предлагаемого класса кодовых множеств получена асимптотическая граничная оценка с <2. Прикладное моделирование независимых источников (модели 0-го порядка [2]) с различным статистическим типом распределения показало, что независимо от мощности алфавита источника с « 0,7 для различных перестановочных схем и с «1,9 для интервальных (при кодировании последовательностей с длиной, несколько меньшей мощности алфавита сообщений с «2,0). Для распределений геометрического типа при прямом применении параметрически адаптивного кода без каких либо перестановок с «0,2 для H(Q)> 2,5. Указанные оценки сохраняются при непрерывном адаптивном кодировании модельных последовательностей с различными статистическими характеристиками. Предлагается использование метода для кодирования смещений и длин строковых фрагментов неограниченного диапазона в алгоритмах компрессии данных на основе LZ77. Соответственно, реализована утилита компрессии LZP, использующая для поиска строковых фрагментов в скользящем окне, размер которого ограничивается лишь объемом доступной программе памяти, алгоритм "deflate" (разновидность LZ77, широко применяемая программными компрессии формата ZIP) и использующая для кодирования избыточных длин и смещений строковых фрагментов в данном окне указанный выше параметрически адаптивный код. Цель исследования. Разработка эффективных алгоритмов компрессии данных с использованием метода параметрически адаптивного кодирования для применения в информационно-вычислительных системах общего назначения.

В соответствии с поставленной целью исследования в настоящей работе выполнены:

• анализ статических и адаптивных методов вероятностного, рангового и интервального кодирования двоичными кодами переменной длины;

• разработка структуры и исследование системы кодовых множеств С(м>), допускающей параметрическое определение;

• разработка базового алгоритма параметрически адаптивного кодирования в системе кодовых множеств С(м>)\

• теоретическая оценка избыточности при кодирования базовым параметрически адаптивным алгоритмом в предложенной системе кодовых множеств С(м>)\

• разработка параметрически адаптивного алгоритма кодирования с использованием простой ранговой схемы перестановок (по принципу «стопка книг»[63]);

• разработка параметрически адаптивного алгоритма кодирования с использованием вероятностной схемы перестановок;

• разработка параметрически адаптивного алгоритма кодирования с использованием ранговой схемы перестановок с логарифмической зависимостью сложности от мощности алфавита кодируемого источника;

• исследование различных схем адаптивной настройки параметра при кодировании в системе кодовых множеств СЫ!)\

• разработка системы тестовых программных реализаций комплекса адаптивных алгоритмов вероятностного, рангового, интервального и непосредственного параметрически адаптивного кодирования для алфавитов различной мощности;

• тестовый сравнительный анализ комплекса алгоритмов адаптивного кодирования с использованием системы тестовых программных реализаций для моделей данных 0-го порядка и различных статистических типов распределения вероятностей (равномерного, нормального, геометрического);

• разработка алгоритма совмещенного динамического кодирования Хаффмана с параметрически адаптивным кодированием избыточных индексов для применения в Ь2-методах компрессии данных с неограниченным диапазоном словарных индексов и длин словарных фрагментов;

• разработка экспериментальной реализации утилиты компрессии данных LZP на базе метода LZ77 с использованием разработанного алгоритма параметрически адаптивного кодирования избыточных длин и смещений текстовых фрагментов в скользящем окне, величина которого ограничивается лишь доступной программе памятью;

• экспериментальная сравнительная оценка эффективности применения параметрически адаптивного кодирования в Ь2-методах с использованием утилиты компрессии данных и утилиты архивирования WinZip 7.0 811-1 в качестве базового аналога.

Метод исследования. Для решении поставленных задач использованы методы теории информации, математического моделирования, принципы системного анализа, алгоритмические методы теории вычислительных процессов.

Методика исследования опирается на иерархическую схему "Задача -метод - алгоритм - реализация" с оценкой характеристик эффективности по параметрам избыточности результатов кодирования, требуемого объема памяти вычислительной системы и временных затрат.

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

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

Вычислительной техники Дагестанского Государственного технического университета в 1997-2001гг.

Практические результаты включают:

• метод построения и структуру определяемой параметрически системы множеств кодовых слов переменной длины для применения в адаптивных алгоритмах понижающего избыточность кодирования источников сообщений с неопределенной или изменяющейся статистикой;

• методы, алгоритмы и программные реализации параметрически адаптивного кодирования в системе двоичных кодовых множеств переменной длины с использованием интервальной, а также ранговой, вероятностной и логарифмической перестановочных схем для источников независимых сообщений (модель данных 0-го порядка [2]) с неизвестной либо изменяющейся статистикой;

• метод, алгоритм и программная реализация динамического кодирования Хаффмана с параметрически адаптивным кодированием избыточных индексов для применения в Ь2-методах компрессии данных с неограниченным диапазоном словарных индексов и длин словарных фрагментов;

• метод, алгоритм и программная реализация утилиты компрессии данных LZP на базе метода 1^77 с использованием параметрически адаптивного кодирования избыточных длин и смещений текстовых фрагментов в скользящем окне, величина которого ограничивается лишь доступной программе памятью.

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

Внедрение результатов работы. Результаты работы использованы:

• в программном обеспечении автоматизированной системы управления «АСУ ВУЗ» для компрессии файлов баз данных и форм отчетности подсистемы «Текущая аттестация».

• в процессе подготовки студентов специальностей «Вычислительная техника» и «Программирование» на кафедре Вычислительной Техники Дагестанского Государственного Технического Университета в' части учебно-методического обеспечения лабораторного и лекционных циклов по дисциплинам «Системное программное обеспечение ЭВМ» и «Операционные системы ЭВМ».

Апробация работы. Основные результаты работы докладывались и обсуждались:

• на 2-м международном симпозиуме «Мониторинг и прогнозирование чрезвычайных ситуаций», г. Махачкала, 1997г.;

• на 3-й международной научно-технической конференции «Интерактивные системы: Проблемы человеко-компьютерного взаимодействия / ИС99», г. Ульяновск, 1999г.;

• на республиканской научно-практической конференции «Информационные и телекоммуникационные системы: состояние и перспективы развития», г. Махачкала, 8-10 ноября 2000 г.

• на итоговых научно-технических конференциях профессорско-преподавательского состава Дагестанского Государственного Технического Университета в 1997-1999гг.

Публикации. Всего автором опубликовано 27 работ, в том числе 9 непосредственно по результатам настоящей диссертации.

Диссертационная работа состоит из введения, 4 глав основного раздела, заключения, списка литературы и 5 разделов приложений. Основной раздел изложен на 139 страницах машинописного текста, который поясняется 33 рисунками и 2 таблицами, а также включает библиографию из 66

4.5. Выводы.

На основе анализа особенностей методов кодирования, используемых в LZ-aлгopитмax компрессии, обосновано применение метода параметрически адаптивного кодирования выходных данных LZ-кoдepa без ограничения диапазона используемых значений. Предложен алгоритм динамического кодирования Хаффмана совмещенного с параметрически адаптивным кодированием избыточных длин и смещений для применения в LZ77 методах компрессии. Разработано программное обеспечение экспериментальной версии утилиты LZP компрессии файлов данных с использованием указанного выше алгоритма . Проведенная апробация эффективности применения утилиты LZP путем сравнительного анализа результатов ее применения для компрессии файлов данных различного формата. Результаты тестовой апробации доказывают целесообразность применения предложенного алгоритма в LZ77-методах, существенно увеличивая степень сжатия объемных массивов данных текстовых и гипертекстовых форматов, файлов программных библиотек, файлов баз данных различного формата и других данных большого объема со значительной избыточностью (более 3 бит/символ) по сравнению с базовым аналогом использующим ограничение окна просмотра. В качестве базового аналога использовалась утилита архивирования для ОС Windows WinZip© 7.0 SR-1. При использовании утилиты LZP для компрессии файлов исполняемых программ, WinHelp-файлов со сжатием текста и большей части файлов небольшого объема (менее 32К) уровень сжатия несколько меньше (0,5-1%), чем получаемый в результате применения базового аналога. В связи с этим в дальнейшем необходима доработка алгоритмов инициализации дерева Хаффмана, используемого для кодирования смещений, проработка стратегий 1^77-анализа и общая технологическая проработка реализации для повышения производительности.

Заключение

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

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

Формальная бесконечность составляющих параметрически определяемый класс кодовых множеств, относительно невысокая избыточность в области больших диапазонов кодируемых величин и низкая вычислительная сложность метода позволили применить ею для адаптивного кодирования длин и смещений словарных фрагментов 15 1,/Л7-схеме компрессии без ограничения размера скользящего окна. Практическая реализация данного подхода в программной утилите компрессии файлов данных LZP (в приложении к работе приведены исходные тексты оценочной экспериментальной реализации) подтверждает эффективность его использования для компрессии данных различного формата, - в особенности гипертекстовых документов значительного объема, форматированных текстовых документов различного типа, баз данных и сопутствующих им

134 вспомогательных индексных файлов, библиотечных файлов объектных модулей и т.д.

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

1.Abramson D.M. An adaptive dependency source model for data compression. Commun.ACM 32,1 (Jan. 1989.),77-83.

2. Bell Т., Witten LH., Cleary J.G. Modeling for text compression. ACM Computing Surveys. Vol.21, No.4 (Dec. 1989), pp.557-591.

3. Bell T.C. A unifying theory and improvements for existing approaches to text compression. Ph.D. dissertation, 1987, Dept. of Computer Science, Univ. of Canterbury, New Zealand.

4. Bently J.L. and Yao A.C. "An almost optimal algorithm unbounded searching". Inf. Processing Lett., vol. 5, no. 3, pp. 82-87, Aug. 1976.

5. Bently J.L., Sleatör D., Tarjan R.E. and Wey V.K. A locally adaptive data compression scheme, in Proceedings of Twelfth Second Allerton Conference on Communication, Control and Computing, Oct. 1984, pp. 233-242.

6. Brent R.P. A linear algorithm for data compression. Aust. Comput. J., 1987, 19,2, 64-68.

7. Cleary J.G. and Witten I.H. Data compression using adaptive coding and partial string matching. IEEE Trans. Commun. COM-32, 4(Apr. 1984.),396-402.

8. Connack G.V. and Horspool R.N. Data compression using dynamic Markov modelling.Comput. J. 30,6(Dec. 1987.), 541-550.

9. Davisson L.D. and Leon-Garcia A. "A source matching approach to finding miniinax codes", IEEE Trans. Inform. Theory, vol. IT-26, no. 2, pp. 166-174, March 1980.

10. Deutsch L.P. "'Deflate' Compressed Data Format Specification" (файл ftp://ftp.uii.net:/pub/archiving/zip/doc/dellate-l. 1 .doc)

11. Elias P. "Minimax optimal universal codeword sets", IEEE I rans. Inform. Theory, vol. IT-29, no. 4, pp. 491-502, July 1983.

12. Elias P. "Minimum times and memories needed to compute values of a function", J. Comput. Syst. Sci., vol. 9, no. 2, pp. 196-212, Oct. 1974.

13. Elias P. "Universal codeword sets and representation of the integers" IEEE Trans. Inform. Theory, Vol. IT-21, no. 2, pp. 194-203, March 1975.

14. Elias P. Interval and Recency Rank Source Coding: Two On-Line Adaptive Variable-Length Schemes. IEEE Transactions on information theory, vol. ГГ-33, № 1, January, 1987, pp. 3-10.

15. Even S. and Rode M. "Economical encoding of commas between strings", Comm. Assoc. for Сотр. Mach., vol. 21, no. 4, pp. 315-317, April 1978.

16. Faller N. "An adaptive system for data compression" in Conference Record, Asilomar Conference on Circuits, System and Computers, 7th conference, 1973, pp. 593-597.

17. Fiala E.R. and Greene D.H. Data compression with finite windows. Commun.ACM 32,4(Apr. 1989.),490-505.

18. Gallager R.G. Information Theory and Reliable Communication. New York: Wiley, 1968. (Перевод: Р.Г. Галлагер. Теория информации и надежная связь. М. Сов. Радио. 1974г.)

19. Gallager R.G. Variations on a Theme by Huffman. IEEE Transactions on information theory, vol. IT-24, no.6, nov. 1978, pp.668-674.

20. Guazzo M. 1980. A general minimum-redundancy source-coding algorithm. IEEE Trans.Inf Theory IT-26, 1 (Jan.), 15-25.

21. Huffman D.A. "A method for the construction of minimum redundancy codes". Proc. IRE, vol. 40, pp. 1098-1101, 1952. (Пер. ДА Хаффмен. Метод построения кодов с минимальной избыточностью. Кибернетический сборник, вып. 3, М„ ИЛ, 1961, стр. 79-87.)

22. Jakobsson M. Compression of character string by an adaptive dictionary. BIT 1985,25,4, 593-603.

23. Jones D.W. Application of splay trees to data compression. Commun.ACM 31,8(Aug. 1988 ), pp.996-1007.

24. Knuth D. E. The Art of Computer Programming., vol. 3, Sorting and Searching. Reading, MA: Addison-Wesley, 1973, 1973, pp.398-403.(Перевод Кнут Д.Е. Искусство программирования. Т.З. М. Мир. 1983)

25. Knuth D.E. "Dinamic Huffman coding" J. Algorithms, vol. 6, pp. 163-180, June 1985.

26. Langdon G.G. An introduction to arithmetic coding. IBM J.Res.Dev. 28,2(Mar. 1984.), 135-149. Introduction to arithmetic coding from the point of view of hardware implementation.

27. Langdon G.G. and Rissanen J.J. A doubly-adaptive file compression algorithms. IEEE Trans.Commun. COM-31, ll(Nov. 1983.), 1253-1255.

28. Langdon G.G. and Rissanen J.J. A simple general binary source code. IEEE Trans.Inf.Theory IT-28 (Sept. 1982.),800-803.

29. Lempel A., Ziv J. On the complexity of finite sequences. IEEE Trans.Inf.Theory IT-22,l(Jan. 1976.), pp75-81.

30. Levenstein V.I. "The redundancy and deceleration of a sparative encoding of the natural numbers" Probl. Cybern.no. l,pp. 173-179, 1968.

31. Miller V.S. and Wegman M.N. Variations on a theme by Ziv and Lempel. In Combinatorial Algorithms on Words.A.Apostolico and Z.Galil, Eds.NATO ASI Series, 1984, Vol.F12.Springer-Verlag,Berlin,pp. 131-140.

32. Moffat A. A note on the PPM data compression algorithm. Res.Rept. 1988/7, Dept.of Computer Science, Univ. of Melbourne, Victoria, Australia.

33. Moffat A. Word based text compression. Res.Rept. 1987.,Dept.of Computer Science, Univ.of Melbourne,Victoria, Australia.

34. Pasco R. Source coding algorithms for fast data compression. Ph.D. dissertation. 1976.Dept.of Electrical Engineering, Stanford Univ. An early exposition of the idea of arithmetic coding, but lacking the idea of incremental operation.

35. Rissanen J. "Minimax codes Tof finite alphabets", IEEE trans. Inform. Theory, vol. IT-24, no. 3, pp. 389-392, May 1978.

36. Rissanen J.J. and Langdon G.G. Universal modeling and coding. IEEE Trans.Inf.Theory IT-27,1 (Jan. 1981.), 12-23.

37. Rissanen J.J.,Langdon G.G. Arithmetic coding. IBM J.Res.Dev.23,2(Mar. 1979.),149-162. Describes a broad class of arithmetic codes.

38. Rissanen J.J. Arithmetic codings as number representations. Acta Polytechnic Scandinavica, Math 31(Dec. 1979.),44-51. Further develops arithmetic coding as a practical technique for data representation.

39. Rissanen J.J. Generalized Kraft inequality and arithmetic coding. IBM J.Res.Dev.20,(May. 1976.),198-203. Another early exposition of the idea of arithmetic coding.

40. Rivest R. "On self-organizing search heuristics", Comm. Assoc. Сотр. Pvlach., vol. 19, no. 2, pp. 63-67, Feb. 1976.

41. Roden M., Pratt V.R. and Even S. Linear algorithm for data compression via string matching. J.ACM 28,l(Jan. 1981.),16-24.

42. Rubin F. Arithmetic stream coding using llxed precision registers. IEEE Trans.Inf.Theory IT-25,6(Nov. 1979.),672-675.

43. Thomas S.W., McKie J., Davies S., Turkowski K., Woods J.A.,Orost J.VV. 1985. Compress (Version 4.0) program and documentation. Размещена на joe@petsd.UUCP.

44. Tischer P. A modified Lempel-Ziv-Welch data compression scheme. Aust.Comp.Sci.Commun. 1987, 9,1,262-272.

45. Welch T.A. A Technique for High-Performance Data Compression .IEEE Computer, 17,6,(June 1984.),pp.8-19

46. Winer A.D. "An upper Ы-" ' on the entropy series" inform. Contr., vol. 20, pp. 176-181.1972.

47. Ziv J. Lempel A. Compression of Individual Sequences Via Variable Rate Coding. IEEE Trans. Inform. Theory. 1978. V.24.№ 5. p.530-536.

48. Ziv J.,Lempel A. A universal algorithms for sequental data compression. IEEE Trans.Inf.Theory IT-23,3,3(May 1977.),337-343.

49. Гаджиев Ю.А. MTF-алгоритм с логарифмической зависимостью сложности от мощности кодируемого алфавита. ИЛ №19-022-01, Махачкала, ДагЦПТИ, 2001г.

50. Гаджиев Ю.А. Адаптивное кодирование смещений и длин словарных фрагментов неограниченного числового диапазона для применения в LZ77-методах с расширенным скользящим окном. ИЛ №19-023-01, Махачкала, ДагЦНТИ, 2001г.

51. Гаджиев Ю.А. Кодеры Хаффмана. В сб. статей "Теоретические и прикладные вопросы информатики Махачкала, 2000г.,стр. 109-122.

52. Гаджиев Ю.А. Об избыточности кодирования в параметрически адаптивной ранговой схеме. Вестник ДГТУ. Технические науки. Вып. 2, Махачкала, 1998г., стр.23-26.

53. Гаджиев Ю.А. Параметрически адаптивный ранговый код. Вестник /О 'ТУ. Технические науки. Вып. 1, Махачкала, 1997 г., стр.30-33.

54. Гаджиев Ю.А. Параметрическое семейство кодов, порождаемых кодом Элайеса Cj. Вестник Дагестанского научного центра РАН. Вып. 11, Махачкала, 2001г. (в печати).

55. Гаджиев Ю.А. Последовательный адаптивный код для MTF-моделей. ИЛ №19-021-01, Махачкала, ДагЦНТИ, 2001г.

56. Гилберт Э.Н., Мур Э.Ф. Двоичные кодовые системы переменной длины. Кибернетический сборник №3. М .ПИЛ. 1961г., стр. 103-141.

57. Рябко Б.Я. Сжатие данных с помощью стопки книг. Проблемы передачи информации 1980, Т. 16, №4, стр. 16-21.

58. Штарьков Ю.М. Адаптивное кодирвапие дискретных источников. В сб. «Кодирование в сложных системах», АН СССР, Научный совет по комплексной проблеме «Кибернетика», Изд. «Наука», М., 1974г., стр. 164168.

59. Штарьков Ю.М. Универсальное последовательное кодирование отдельных сообщений. Проблемы передачи информации. 1987, Т.23, №3, стр.3-17.

60. Яглом A.M., Яглом И.М. Вероятность и информация, М., 1973, 512 стр. с ил л.