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

• Автор: Павлов, Игорь Викторович
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2002
• Место защиты: Уфа
• Количество страниц: 114 с.

Оглавление
Введение
Глава 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. Модели избыточности информации для последовательности V.
енмволов
2.2. Основной алгоритм кодирования
2.3. Использование цепей Маркова для кодирования классов .Ъ
символов
2.4. Адаптивные ачгоритмы сжатия данных.
2.5. Кодирование одиночных символов.
2.5.1. Использование контекста из предыдущих символов
2.5.2. Кодирование символа, следующего за Ьгстрокой.
2.6. Кодирование смещений.
2.7. Кодирование длин.
2.8. Алгоритмы сжатия данных с периодической структурой
2.8.1. Использование позиции байта внутри слова в виде
контекста.
2.8.2. Кодирование младших разрядов смещения.
2.9. Оценка эффективности алгоритма.
2 Выводы по второй главе.
Глава 3. Разработка программного обеспечения, реализующего предложенные алгоритмы сжатия данных и оценка их эффективности
3.1. Предварительные замечания
3.2. Структура программного обеспечения.
3.3. Структура модуля сжатия данных.7
3.4. Структуры модуля архивирования сжатых данных.
3.4.1. Структура архива
3.4.2. Структура служебного блока
3.4.3. Информация об использованных методах кодирования
3.4.4. Многоуровневое кодирование ,
3.4.5. Кодирование числовой информации
3.4.6. Хранение ассоциированной с содержимым файлов
информации
3.5. Алгоритмы сжатия исполняемых файлов
3.6. Оценка эффективности разработанного программного
обеспечения на примере сжатия данных, хранящихся в сети пепкЧ
3.6.1. Тестовые данные.
3.6.2. Методика сравнения
3.6.3. Результаты сравнения
3.7. Применение разработанного программного обеспечения для
сжатия данных, распространяемых через сеть Интернет в системе
дистанционного образования.
3.8. Выводы по третьей главе.
Заключение
Список литературы


При сжатии данных алгоритм LZ требует решения задачи поиска совпадающих последовательностей символов, что является нетривиальной задачей. Поэтому требования к ресурсам компьютера для процессов упаковки и распаковки данных различаются. Гак скорость распаковки обычно в 5 - раз больше скорости распаковки, при этом объем необходимой оперативной памяти для процесса распаковки в 3 - раз меньше объема необходимой для упаковки памяти. Скорость распаковки данных алгоритма LZ является наивысшей из зеех существующих алгоритмов сжатия данных. Поэтому данный алгоритм применяется в гсх случаях, когда высокая скорость распаковки данных является главным требованием. Недостатком алгоритма LZ является то, что он не обеспечивает высокой степени сжатия, такой, например, как у алгоритма PPM. Методы контекстуального предсказания (PPM) базируются на предсказании появлення символов во входном потоке. Используя полученное распределение вероятностей появления символов, поступающий символ кодируется с помощью арифметического кодирования. Для декодирования данных используется тот же алгоритм определения распределения вероятностей появления символов для каждого следующею символа. Следовательно, процессы упаковки и распаковки обладают одинаковой скоростью и одинаковыми требованиями к объему необходимой оперативной памяти. Достоинством алгоритма РРМ является сравнительно высокая степень сжатия, однако это сопровождается относительно низкой скоростью работы и повышенными требованиями к объему оперативной памяти компьютера пользователя. Алгоритм В№Т —это алгоритм обратимой перестановки символов во входном потоке, позволяющий достаточно эффективно сжимать полученный в результате преобразования блок данных [, ]. Алгоритм ВЛГГ не является симметричным, т. Алгоритм В№Т обладает высокой скоростью процессов упаковки и распаковки. К недостаткам алгоритма В\ Т можно отнести то, что для целого ряда типов данных, в частности, для исполняемых файлов, степень сжатия хуже, чем у алгоритмов РРМ и Л. Совместно с каждым из описанных выше алгоритмов моделирования, как уже было отмечено выше, используются алгоритмы кодирования. С помощью алгоритмов кодирования происходит формирование кодовых последовательностей потока сжатых данных с использованием полученных на этапе моделирования распределений вероятностей появления различных символов. В настоящее время используются два основных алгоритма кодирования: кодирование Хаффмана и арифметическое кодирование. При этом часто встречаемые символы получают более короткие кодовые последовательности, что и обеспечивает сжатие информации. Однако алгоритм Хаффмана обладает избыточностью, т. Степень избыточности зависит от размера алфавита, а также от значений вероятностей символов. Чем меньше размер алфавита, тем больше избыточность кодирования Хаффмана. Арифмет ическое кодирование решает ту же задачу, что и кодирование Хаффмана (обеспечивает кодирование символов при наличии информации о распределении вероятностей появления символов) (9, , , , , , , , ]. При этом избыточность арифметического кодирования практически равна нулю. Следует отметить, что скорость процесса арифметического кодирования меньше скорости кодирования Хаффмана, так как арифметическое кодирование использует относительно медленные операции деления и умножения. Однако в настоящее время разработаны модификации алгоритмов арифметического кодирования, которые позволяют сократить количество наиболее медленных операций деления, что сильно повышает скорость работы данного алгоритма. Из проведенного анализа видно, что ни один из перечисленных методов не обеспечивает одновременно высокую степень сжатия и высокую скорость распаковки, что затрудняет их использование в целом ряде практических областей, для которых характерны частые запросы на получение информации при относительно невысокой частоте ее обновления. Одним из возможных направлений преодоления указанных выше недостатков известных методов сжатия информации является модификация известных методов сжатия информации, в частности, алгоритма Лсмпсла Знва с целью повышения степени сжатия при сохранении высокой скорости распаковки, присущей данному алгоритму.