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

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

.

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

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

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

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

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

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

• скорость распаковки (декодирования) данных- 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]. При этом избыточность арифметического кодирования практически равна нулю. Следует отметить, что скорость процесса арифметического кодирования меньше скорости кодирования Хаффмана, так как арифметическое кодирование использует относительно медленные операции деления и умножения. Однако в настоящее время разработаны модификации алгоритмов арифметического кодирования, которые позволяют сократить количество наиболее медленных операций деления, что сильно повышает скорость работы данного алгоритма.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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% финансовые затраты на следующие задачи:

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

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

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

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

ЗАКЛЮЧЕНИЕ

.

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

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

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

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

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

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

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

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

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

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

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