автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Модифицированный алгоритм Лемпела - Зива эффективного сжатия информации с использованием статистических прогнозирующих моделей

Введение.

Глава 1. Алгоритм цифрового поиска совпадающих последовательностей символов для сжатия данных методом Лемпела — Зива.

1.1. Предварительные замечания.

1.2. Постановка задачи поиска совпадающих последовательностей символов.

1.3. Алгоритм цифрового поиска.

1.4. Оценка эффективности алгоритма.

1.5. Варианты построения алгоритма.

1.5.1. Удаление одиночных строк.

1.5.2. Блочное удаление строк.

1.6. Сочетание алгоритма цифрового поиска с алгоритмами хеширования.

1.7. Практические аспекты построения алгоритмов поиска.

1.7.1. Оценка объема необходимой памяти.

1.7.2. Управление распределением памяти.

1.8. Выводы по первой главе.

Глава 2. Модифицированный алгоритм Лемпела — Зива сжатия информации

2.1. Модели избыточности информации для последовательности LZ-символов.

2.2. Основной алгоритм кодирования.

2.3. Использование цепей Маркова для кодирования классов LZ-символов.

2.4. Адаптивные алгоритмы сжатия данных.

2.5. Кодирование одиночных символов.

2.5.1. Использование контекста из предыдущих символов.

2.5.2. Кодирование символа, следующего за LZ-строкой.

2.6. Кодирование смещений.

2.7. Кодирование длин.

2.8. Алгоритмы сжатия данных с периодической структурой.

2.8.1. Использование позиции байта внутри слова в виде контекста.

2.8.2. Кодирование младших разрядов смещения.

2.9. Оценка эффективности алгоритма.

2.10. Выводы по второй главе.

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

3.1. Предварительные замечания.

3.2. Структура программного обеспечения.

3.3. Структура модуля сжатия данных.

3.4. Структуры модуля архивирования сжатых данных.

3.4.1. Структура архива.

3.4.2. Структура служебного блока.

3.4.3. Информация об использованных методах кодирования.

3.4.4. Многоуровневое кодирование.

3.4.5. Кодирование числовой информации.

3.4.6. Хранение ассоциированной с содержимым файлов информации.

3.5. Алгоритмы сжатия исполняемых файлов.

3.6. Оценка эффективности разработанного программного обеспечения на примере сжатия данных, хранящихся в сети Internet.

3.6.1. Тестовые данные.

3.6.2. Методика сравнения.

3.6.3. Результаты сравнения.

3.7. Применение разработанного программного обеспечения для сжатия данных, распространяемых через сеть Интернет в системе дистанционного образования.

3.8. Выводы по третьей главе.

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

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

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

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

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

• степень сжатия, то есть отношение длины исходных данных к длине данных в сжатом виде;

• скорость упаковки (кодирования) данных;

• скорость распаковки (декодирования) данных; 6

• требования к ресурсам компьютеров, производящих упаковку и распаковку данных.

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

Известно, что алгоритмы, которые обеспечивают наибольшую степень сжатия, потребляют больше ресурсов (оперативной памяти) и требуют больше времени на работу. Не существует алгоритма, который бы одновременно обладал самой высокой скоростью и самой высокой степенью сжатия. Поэтому для каждой задачи выбирают "компромиссный" алгоритм сжатия, обеспечивающий показатели по скорости работы и степени сжатия, которые подходят именно для данной задачи.

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

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

Принято процесс сжатия делить на два этапа: моделирование, в результате которого определяются вероятности появления значений символов во входном потоке, и кодирование, в результате которого исходный поток символов преобразуется в сжатый (т. е. с меньшим числом символов) поток [71].

В настоящее время существует несколько основных алгоритмов моделирования для сжатия без потерь:

• алгоритм Лемпела — Зива (LZ);

• методы контекстуального предсказания (prediction by partial match, PPM);

• алгоритм обратимой перестановки символов во входном потоке "Burrows Wheeler Transform" (BWT).

Сущность алгоритма Лемпела — Зива (LZ) состоит в том, что символы (или группы символов) заменяются указателем на то место, где они в тексте уже ранее появлялись [10, 90]. При сжатии данных алгоритм LZ требует решения задачи поиска совпадающих последовательностей символов, что является нетривиальной задачей. Поэтому требования к ресурсам компьютера для процессов упаковки и распаковки данных различаются. Так скорость распаковки обычно в 5 - 10 раз больше скорости распаковки, при этом объем необходимой оперативной памяти для процесса распаковки в 3 - 20 раз меньше объема необходимой для упаковки памяти. Скорость распаковки данных алгоритма LZ является наивысшей из всех существующих алгоритмов сжатия данных. Поэтому данный алгоритм применяется в тех случаях, когда высокая скорость распаковки данных является главным требованием. Недостатком алгоритма LZ является то, что он не обеспечивает высокой степени сжатия, такой, например, как у алгоритма РРМ.

Методы контекстуального предсказания (РРМ) базируются на предсказании появления символов во входном потоке. Алгоритм РРМ для каждой позиции в тексте рассматривает контекст (группу из нескольких предыдущих символов) и определяет вероятности появления различных символов для данного 8 контекста на основе статистического анализа появлений различных символов в уже просмотренном тексте в позициях с таким же контекстом [26, 32, 34, 65, 79]. Используя полученное распределение вероятностей появления символов, поступающий символ кодируется с помощью арифметического кодирования. Для декодирования данных используется тот же алгоритм определения распределения вероятностей появления символов для каждого следующего символа. Следовательно, процессы упаковки и распаковки обладают одинаковой скоростью и одинаковыми требованиями к объему необходимой оперативной памяти. Достоинством алгоритма РРМ является сравнительно высокая степень сжатия, однако это сопровождается относительно низкой скоростью работы и повышенными требованиями к объему оперативной памяти компьютера пользователя.

Алгоритм BWT—это алгоритм обратимой перестановки символов во входном потоке, позволяющий достаточно эффективно сжимать полученный в результате преобразования блок данных [33, 39]. Алгоритм BWT не является симметричным, т.е. алгоритмы упаковки и распаковки различаются. Алгоритм BWT обладает высокой скоростью процессов упаковки и распаковки. К недостаткам алгоритма BWT можно отнести то, что для целого ряда типов данных, в частности, для исполняемых файлов, степень сжатия хуже, чем у алгоритмов РРМ и LZ.

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

Принцип действия кодирования Хаффмана основывается на том, чтобы поставить в соответствие каждому символу определенную последователь9 ность битов, длина которой определяется в соответствии с вероятностью данного символа [5, 8, 20, 47]. При этом часто встречаемые символы получают более короткие кодовые последовательности, что и обеспечивает сжатие информации. Однако алгоритм Хаффмана обладает избыточностью, т.е. не обеспечивает максимально возможной степени сжатия. Степень избыточности зависит от размера алфавита, а также от значений вероятностей символов. Чем меньше размер алфавита, тем больше избыточность кодирования Хаффмана.

Арифметическое кодирование решает ту же задачу, что и кодирование Хаффмана (обеспечивает кодирование символов при наличии информации о распределении вероятностей появления символов) [9, 16, 38, 46, 66, 68, 73, 81, 86]. При этом избыточность арифметического кодирования практически равна нулю. Следует отметить, что скорость процесса арифметического кодирования меньше скорости кодирования Хаффмана, так как арифметическое кодирование использует относительно медленные операции деления и умножения. Однако в настоящее время разработаны модификации алгоритмов арифметического кодирования, которые позволяют сократить количество наиболее медленных операций деления, что сильно повышает скорость работы данного алгоритма.

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

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

10

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

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

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

• недостаточная скорость адаптации алгоритмов сжатия в условиях частого изменения статистических показателей сжимаемого текста.

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

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

11

Задачи исследования

Для достижения обозначенной выше цели в диссертационной работе поставлены и решены следующие задачи:

1. Разработка эффективных алгоритмов поиска совпадающих последовательностей символов для сжатия данных с помощью алгоритма Лемпела — Зива.

2. Разработка статистических прогнозирующих моделей, позволяющих более точно определять вероятности появления LZ-символов.

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

4. Создание программного обеспечения, реализующее разработанные алгоритмы сжатия и архивирования данных.

5. Проверка эффективности разработанного программного обеспечения на примере организации хранения и передачи информации в системах дистанционного обучения.

Методы исследования

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

На защиту выносятся:

1. Алгоритм поиска совпадающих последовательностей символов.

2. Статистические прогнозирующие модели для определения вероятностей появления LZ-символов, основанные на использовании аппарата цепей Маркова.

3. Алгоритмы адаптивного кодирования LZ-символов.

4. Программное обеспечение, реализующее разработанный модифицированный алгоритм Лемпела —- Зива.

12

Научная новизна работы заключается в следующем:

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

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

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

Практическая значимость работы:

1. Разработанная модификация алгоритма Лемпела — Зива обеспечивает увеличение степени сжатия по сравнению с известными его вариантами на 10-40 % в зависимости от данных. Скорость разработанного алгоритма составляет примерно 500 Кб/с при кодировании и 5-10 Мб/с при декодировании данных на компьютере с тактовой частотой 1 ГГц.

2. Разработано программное обеспечение в виде нового архиватора файлов "7-Zip", реализующее разработанные алгоритмы сжатия и

13 архивирования данных. Программное обеспечение данного архиватора имеет открытую архитектуру, что позволяет использовать новые методы архивирования и сжатия данных с помощью добавления соответствующих модулей. Данный архиватор доступен для пользователя по адресу www.7-zip.org.

3. Экспериментальная проверка эффективности архиватора на примере использования его в системе дистанционного образования показала, что применение данной программы позволяет снизить в среднем на 10-40% финансовые затраты на следующие задачи:

• хранение учебной информации на сервере;

• передачу учебной информации по линии связи сервера с сетью Интернет;

• передачу учебной информации по линии связи конечного пользователя (обучающегося) с провайдером Интернет-услуг.

Объем и структура работы

Диссертационная работа состоит из введения, трех глав, заключения, библиографии и 2 приложений. Основная часть содержит 106 страниц и включает в себя 9 рисунков и 5 таблиц. Список литературы содержит 91 наименование. В Приложениях приведены: руководство пользователя программы 7-Zip и акт внедрения.

3.8. Выводы по третьей главе

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

2. Создан новый архиватор данных "7-Zip", реализующий разработанные алгоритмы сжатия и архивирования данных. Программное обеспечение данного архиватора имеет открытую архитектуру, что позволяет добавлять поддержку новых методов архивирования и сжатия с помощью добавления соответствующих модулей. Данный архиватор доступен для пользователя по адресу www.7-zip.org.

3. Экспериментальная проверка эффективности архиватора на примере использования его в системе дистанционного образования показала, что применение данной программы позволяет снизить на 5-40% финансовые затраты на следующие задачи:

• хранение учебной информации на сервере;

• передачу учебной информации по линии связи сервера с сетью Интернет;

• передачу учебной информации по линии связи конечного пользователя (обучающегося) с провайдером Интернет-услуг.

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

97

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

98 можного изменения статистических показателей сжимаемого текста.

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

4. Экспериментальная проверка эффективности архиватора на примере использования его в системе дистанционного образования показала, что применение данной программы позволяет снизить в среднем на 5-40% финансовые затраты на следующие задачи:

• хранение учебной информации на сервере;

• передачу учебной информации по линии связи сервера с сетью Интернет;

• передачу учебной информации по линии связи конечного пользователя (обучающегося) с провайдером Интернет-услуг.

99

1. Вентцель Е.С., Овчаров Л.А. Теория случайных процессов и ее инженерные приложения. — М.: Наука, 1991. — 383 с.

2. Кабальнов Ю.С., Павлов И.В. Использование цифрового поиска для сжатия данных методом Лемпела — Зива / Уфимск. гос. авиац. техн. ун-т — Уфа, 2001. — 12 с. Деп. в ВИНИТИ 22.01.01, N169-B2001.

3. Кабальнов Ю.С., Павлов И.В. Усовершенствования алгоритма сжатия данных Лемпела — Зива / Уфимск. гос. авиац. техн. ун-т — Уфа, 2001. — 9 с. Деп. в ВИНИТИ 22.01.01, N168-B2001.

4. Кабальнов Ю.С., Павлов И.В. Модели и алгоритмы сжатия информации // Вестник УГАТУ. 2001. N 2. С. 97-104.

5. Кадач А.В. Эффективные алгоритмы неискажающего сжатия текстовой информации. Диссертация. — Новосибирск, 1997. — 200 с.

6. Кнут Д.Е. Искусство программирования. Т. 1. Основные алгоритмы. 3-е изд. — М.: Вилиямс, 2000. — 720 с.

7. Кнут Д.Е. Искусство программирования. Т.З: Сортировка и поиск. 2-е изд. — М.: Вилиямс, 2000. — 822с.

8. Мастрюков Д. Алгоритмы сжатия информации. Часть 1. Сжатие по Хаф-фмену // Монитор.— 1993. — N 7-8. — С. 14-24.

9. Мастрюков Д. Алгоритмы сжатия информации. Часть 2. Арифметическое кодирование // Монитор.— 1994. — N 1. — С. 20-27.

10. Мастрюков Д. Алгоритмы сжатия информации. Часть 3. Алгоритмы группы LZ // Монитор.— 1994. — N 2. — С. 10-19.

11. Павлов И.В. Алгоритм поиска совпадений для LZ-сжатия на основе двоичного дерева // Теоретическая информатика — 2000: от теории к практике: труды международной научной конференции. — Уфа: УГАТУ, 2000. — С. 92-96.

12. Павлов И.В. Эффективный алгоритм сжатия данных для систем космической связи // Пилотируемая космонавтика: становление, проблемы, перспективы: тезисы докладов научно-практической конференции. -— Уфа: УГАТУ, 2001. —С. 30.

13. Павлов И.В. Модифицированный алгоритм сжатия данных Лемпела -Зива // Проблемы техники и технологии телекоммуникаций: тезисы докладов международной научно-технической конференции. — Уфа: УГАТУ, 2001. —С. 40-41.

14. Павлов И.В. Алгоритм сжатия исполняемых файлов // Интеллектуальные системы управления и обработки информации: тезисы докладов международной молодежной научно-технической конференции. — Уфа: УГАТУ, 2001. —С. 99.

15. Потапов В.Н. Теория информации. Кодирование дискретных вероятностных источников: учебное пособие. — Новосибирск, 1999. — 71 с.

16. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. — М.: Мир, 1980. — 476 с.

17. Рябко Б.Я. Эффективный метод кодирования источников информации, использующий алгоритм быстрого умножения // Проблемы передачи информации. — 1995. — Т. 31,N3. — С. 3-13.

18. Шеннон К. Работы по теории информации и кибернетике. М.: Издательство иностранной литературы, 1963. — 829 с.

19. Юсупова Н.И., Миронов В.В. Основы теории информации для информа-тиков. — Уфа, 2001. — 160 с.

20. Andersson A., Larsson N.J., Swanson К. Suffix trees on words // Lect. Notes101

21. Computer Sci. — 1996.— Vol. 1075.—P. 102-115.

22. Andersson A., Nilsson S. Efficient implementation of suffix trees // Software — Practice and Experience. — 1995. — Vol. 25, N 2. —P. 129-141.

23. Bell T.C. A Unifying Theory and Improvements for Existing Approaches to Text Compression // PhD thesis. — Dept of Computer Sci., Univ. of Canterbury.— 1987.

24. Bell T.C. Better OPM/L test compression // IEEE Trans. Communs. — 1986.

25. Vol. 34, N 12. — P. 1176-1182.

26. Bell T.C., Cleary J.G, Witten I.H. Text Compression. — Englewood Cliffs, NJ: Prentice-Hall, 1990.

27. Bell T.C., Cleary J.G, Witten I.H. Modeling for text compression // ACM Computing Surveys. — 1989. Vol. 21, N 4, — P. 557-591.

28. Bell T.C., Kulp D. Longest-match string searching for Ziv-Lempel compression // Software — Practice and Experience. — 1993. — Vol. 23, N 7. — P. 757-772.

29. Bender P.E., Wolf J.K. New asymptotic bounds and improvements on the Lempel-Ziv data compression algorithm // IEEE Trans. Inform. Theory. ■— 1991. Vol. 37, N3. — P.721-729.

30. Bloom C. LZP: a new data compression algorithm. http://www.cbloom.com/, 1996.

31. Bloom C. Solving the Problems of Context Modeling. — http://www.cbloom.com/, 1998.

32. Brent R.P. A linear algorithm for data compression // Aust. Comuter J. — 1987. —Vol. 19, N 2. — P.64-68.

33. Bunton S. On-Line Stochastic Processes in Data Compression // PhD thesis.

34. Dept. of Сотр. Sci. Univ. of Washington. — 1996.

35. Burrows M., Wheeler D.J. A Block-Sorting Lossless Data Compression Algorithm: SRC Research Report 124, Digital Systems Research Center. — Palo Alto, 1994.102

36. Cleary J.G., Teahan W.J., Witten I.H. Unbounded Length contexts for PPM I I Proc. IEEE Data Compression Conference, Snowbird, Utah. — 1995. — P. 52-61.

37. Cormack G.Y., Horspool R.N. Data compression using dynamic Markov modeling // The Computer Journal, — 1987. — Vol. 30, N 6. — P 541-550.

38. Deutsch P. RFC 1951: DEFLATE Compressed Data Format Specification.http://www.rfc-editor.org/.

39. Deutsch P. RFC 1952: GZIP file format specification.http://www.rfc-editor.org/.

40. Fenwick P.M. A New Data Structure for Cumulative Probability Tables: an Improved Frequency-to-Symbol Algorithm, Auckland, 1995 (The University of , Department of Computer Science Report No 110). — http://www.cs.auckland.ac.nz/~peter-f/.

41. Fenwick P.M. Block sorting text compression // Australasian Computer Science Conference, ACSC'96, Melbourne, Australia, 1996. — http://www.cs.auckland.ac.nz/~peter-f/.

42. Fenwick P.M. Compression of Unicode Files. Snowbird, // Proc. IEEE Data Compression Conference, Snowbird, Utah. — 1998. — P. 547.

43. Fenwick P.M. Symbol Ranking text compressors // Proc. IEEE Data Compression Conference, Snowbird, Utah. — 1997. — http ://www. cs .auckland. ac. nz/~peter-f/.

44. Fenwick P.M., Gutmann P.C. Fast LZ77 string matching. Auckland, 1994. — (Tech. Rep. / Dept. of Сотр. Sci., Auckland Univ., N TR-102).

45. Fiala E.R. Green D.H. Data compression with finite windows // Communs. ACM. — 1988. — Vol. 32, N 4. — P. 490-505.

46. Gavish A. Match-length functions for data compression // IEEE Trans. Inform. Theory. — 1996. — Vol. 42, N 5. — P. 1375-1380.

47. Hirschberg D.S., Lelewer D.A. Data compression // ACM Computing Surveys. — 1987. Vol. 19, N 3. — P. 261-297.103

48. Howard P.G. The Design and Analysis of Efficient Lossless Data Compression Systems // PhD thesis. Department of Computer Science, Brown University, Providence, Rhode Island. — 1993.

49. Huffman D.A. A method for the constructing of minimum-redundancy codes // Proc. IRE. — 1952. — Vol. 40. — P. 1998-1101.

50. Jacobsson M. Compression of character strings by an adaptive dictionary // BIT. — 1985. — Vol. 25, N 4. — P.593-603.

51. Jones D.W. Application of splay trees to data compression // Communs ACM.1988. — Vol. 31, N 8. — P. 996-1007.

52. Katajainen J., Raita T. An approximation algorithm for space-optimal encoding of a text // Computer J. — 1989. — Vol. 32, N 3. — P. 228-237.

53. Larson N.J. Extended Application of Suffix Trees to Data Compression // Proc. IEEE Data Compression Conference, Snowbird, Utah, — 1996. — P. 190-199.

54. Larson N.J. Structures of String Matching and Data Compression // PhD thesis. — Dept. of Сотр. Sci. Lund Univ.— 1999.

55. Larson N.J., Moffat A. Offline Dictionary-Based Compression // Proc. IEEE Data Compression Conference, Snowbird, Utah, — 1999. — P. 296-305.

56. Larsson J. Extended Application of Suffix Trees to Data Compression. — http ://www.dna. lth.se/~j esper/.

57. Lekatsas H., Wolf W. Code Compression for Embedded Systems // Proc. of the 35th Conference on Design Automation, Moscone center, San Francico, California, USA. — 1998. — P. 516-521.

58. Lekatsas H., Wolf W. Random Access Decompression Using Binary Arithmetic Coding // Proc. IEEE Data Compression Conference, Snowbird, Utah. — 1999:—P. 306-315.

59. Lekatsas H., Wolf W., Henkel J. Arithmetic Coding for Low Power Embedded System Design // Proc. IEEE Data Compression Conference, Snowbird, Utah,2000: —P. 430-439.104

60. Lekatsas H., Wolf W., Henkel J. Code compression for low power embedded system design // Proc. of the 37th Conference on Design Automation, Los Angeles, CA, USA. — P. 294-299.

61. Lelewer D.A. Hirchberg D.S. An order-2 context model for data compression with reduced time and space requirements. Irvine, 1990. (Tech. Rep. / Dept. of Inform. And Сотр. Sci. Univ. of California, NICS-TR-90-33).

62. Lempel A., Ziv J. On the complexity of finite sequences // IEEE Trans. Inform. Theory. — 1976. Vol. 22, N 1. — P. 75-81.

63. Manber U., Myers G. Suffix arrays: A new method for online string searching // Proc. 1st ACM-SIAM Symposium on Descrete Algorithms (SODA). — 1990. —P. 319-327.

64. McCreight E.M. A space-economical suffix tree construction algorithm // J. ACM. — 1976. — Vol. 23, N 2. — P. 262-272.

65. Merret Т.Н., Shang H. Trie methods for representing text // Foundations of Data Organization and Algorithms: 4th International Conference (FODO' 93).1993. —P. 130-145.

66. Miller V.S., Wegman M.N. — Variations on a theme by Ziv and Lempel. — 1984. — (Tech. Rep. / 1MB Research Division, N RC 10630).

67. Moffat A., Bell T.C., Witten I.H. Lossless Compression for Text and Images.1995.

68. Moffat A.M. Linear time adaptive arithmetic coding // IEEE Trans. Inform. Theory. — 1990. — Vol. 36, N 2. — P. 401-406.

69. Moffat A.M. Word based text compression // Software — Practice and Experience. — 1989. — Vol. 19. N 2. — P. 185-198.

70. Moffat A.M., Witten I.H., Neal R.M. Arithmetic coding revisited // Proc. IEEE Data Compression Conference, Snowbird, Utah. — 1995. — P. 202211.

71. Morrison D.R. PATRICIA — Practical Algorithm To Retrieve Information coded in Alphanumeric // J. ACM. — 1968. — Vol. 15, N 3. — P. 514-534.105

72. Nilsson S. Radix Sorting and Searching // PhD thesis. — Dept. of Сотр. Sci., Lund Univ. — 1996.

73. Rissanen J.J. Langdon G.G. Universal modeling and coding // IEEE Trans. Inform. Theory. — 1981, —Vol. 27, N 1.— P. 12-23.

74. Rodeh M., Pratt V.R., Even S. Linear algorithm for data compression via string matching // J. ACM. — 1981. — Vol. 28, N 1. — P. 16-24.

75. Rubin F. Aithmetic stream coding using fixed precision registers // IEEE Trans. Inform. Theory. — 1979. — Vol.25, N 6. — P.672-675.

76. Rubin F. Experiments in text file compression // Communs. ACM. — 1996. — Vol. 19, N 11. — P.617-623.

77. Sleater D.S., Tarjan R.E. Self-Adjusting binary search trees // J. ACM. — 1985. — Vol. 32, N 3— P.652-686.

78. Storer J.A. Data compression: Methods and Theory. — Rockwille, ML: Computer Science Press, 1988.

79. Storer J.A. Szymansky T.G. Data Compression via textual substitution // J.ACM. — 1982. — Vol.25, N 4. — P. 928-951.

80. Teahan W. J., Cleary J. G. Models of English Text. // Proc. IEEE Data Compression Conference, Snowbird, Utah. — 1997. — P. 12-21.

81. Teahan W.J. Cleary J.G. The entropy of English using PPM-based models // Proc. IEEE Data Compression Conference, Snowbird, Utah. — 1996. P. 6372.

82. Teahan W.J. Probability estimation for PPM. New Zeland Computer Scince Research Students Conference. — Waikato, 1995.

83. Teahula J., Raita T. Aithmetic coding into fixed-length codewords // IEEE Trans. Inform. Theory. — 1994. — Vol. 40, N 1. — P. 219-223.

84. Ukkonen E. On-line construction of suffix trees // Algorithica. — 1995. — Vol. 14, N 3. — P. 249-260.7

85. Wagner R.A. Algorithm 444: An algorithm for extracting phrases in a space-optimal fashion // Communs. ACM. — 1973. Vol. 16, N 3. — P. 148-152.

86. Williams R.N. Adaptive Data Compression. — Kluwer Academic Publishers, Norwell, MA, 1991.

87. Williams R.N. An extremely fast Ziv-Lempel data compression algorithm // Proc. IEEE Data Compression Conference, Snowbird, Utah, — 1991: — P. 362-371.

88. Witten I.H., Neal R.M., Cleary J.G. Arithmetic coding for data compression // Communs. ACM. — 1987. — Vol. 30, N 6. — P 520-540.

89. Wyner A.D., Wyner A.J. Improved redundancy of a version of the Lempel-Ziv algorithm // IEEE Trans. Inform. Theory. — 1995. — Vol. 41, N 3. — P. 723731.

90. Wyner A.D., Ziv J. The sliding-window Lempel-Ziv algorithm is asymptotically optimal // Proc. IEEE. — 1994. — Vol. 82, N 6. — P. 872-876.

91. Yokoo H. Improved variations relating the Ziv-Lempel and Welch-type algorithms for sequential data compression // IEEE Trans. Inform. Theory. — 1992. — Vol. 38, N 1. — P. 73-81.

92. Ziv J. Lempel A. A universal algorithm for sequential data compression // IEEE Trans. Inform. Theory. — 1977. — Vol. 23, N 3. — P. 337-343.

93. Ziv J. Lempel A. Compression of individuals sequences via variable-rate coding // IEEE Trans. Inform. Theory. — 1978. — Vol. 24, N 5. — P. 530-536.107