Последовательное адаптивное кодирование в параметрически определенной системе счетных двоичных кодов для применения в алгоритмах LZ-компрессии

• Автор: Гаджиев, Юрий Абдурахманович
• Шифр специальности: 05.13.17
• Научная степень: Кандидатская
• Год защиты: 2001
• Место защиты: Махачкала
• Количество страниц: 192 с. : ил

Содержание
Введение

Глава 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. Параметрически адаптивное кодирование избыточных длин и смещений текстовых фрагментов в схеме 2Л1
4.3. Реализация Г7кодера с параметрически адаптивным кодированием избыточных длин и смещений .
4.4. Применение ЬХРкодера в задачах компрессии данных
4.5. Выводы.
Заключение
Литература


Соответственно, реализована утилита компрессии LZP, использующая для поиска строковых фрагментов в скользящем окне, размер которого ограничивается лишь объемом доступной программе памяти, алгоритм “deflate” (разновидность LZ, широко применяемая программными компрессии формата ZIP) и использующая для кодирования избыточных длин и смещений строковых фрагментов в данном окне указанный выше параметрически адаптивный код. Цель исследования. Разработка эффективных алгоритмов компрессии данных с использованием метода параметрически адаптивного кодирования для применения в информационно-вычислительных системах общего назначения. Ь2-методах с использованием утилиты компрессии данных Р и утилиты архивирования VinZip 7. ЯК-1 в качестве базового аналога. Метод исследования. Для решении поставленных задач использованы методы теории информации, математического моделирования, принципы системного анализа, алгоритмические методы теории вычислительных процессов. Методика исследования опирается на иерархическую схему "Задача -метод - алгоритм - реализация” с оценкой характеристик эффективности по параметрам избыточности результатов кодирования, требуемого объема памяти вычислительной системы и временных затрат. Принципиальный вклад в развитие методов и алгоритмов адаптивного кодирования, а также основной полученный в работе и выносимый на защиту научный результат - метод и алгоритм последовательною адаптивного кодирования источников сообщений в параметрически определяемой системе множеств кодовых слов переменной длины. Практическая ценность. Вычислительной техники Дагестанского Государственного технического университета в - гг. Предложенные в работе методы, алгоритмы и программные реализации могут использоваться для решения задачи понижения избыточности представления данных как в информационно-вычислительных комплексах общего назначения, так и иных программно-технических системах хранения, обработки и передачи информации. Внедрение результатов работы. АСУ ВУЗ» ятя компрессии файлов баз данных и форм отчетности подсистемы «Текущая аттестация». Вычислительная техника» и «Программирование» на кафедре Вычислительной Техники Дагестанского Государственного Технического Университета в’ части учебно-методического обеспечения лабораторного и лекционных циклов по дисциплинам «Системное программное обеспечение ЭВМ» и «Операционные системы ЭВМ». Апробация работы. Мониторинг и прогнозирование чрезвычайных ситуаций», г. Махачкала, г. Интерактивные системы: Проблемы человеко-компьютерного взаимодействия / ИС», г. Ульяновск, г. Информационные и телекоммуникационные системы: состояние и перспективы развития», г. Махачкала, 8- ноября г. Дагестанского Государственного Технического Университета в -гг. Публикации. Всего автором опубликовано работ, в том числе 9 непосредственно по результатам настоящей диссертации. Диссертационная работа состоит из введения, 4 глав основного раздела, заключения, списка литературы и 5 разделов приложений. Общий объем диссертации, включая приложения, составляет 2 страницы. Полученные данные позволили локализовать область эффективности приложений метода параметрически адаптивного кодирования. Это источники с геометрическим типом вероятностного распределения, источники со значительной нестационарностыо, кодирование последовательностей сообщений ограниченной длины из алфавитов большой мощности. В четвертой главе на основе выполненного ранее прикладного анализа предложен и реализован алгоритм динамического кодирования Хаффмана с параметрически адаптивным кодированием избыточных значений для применения в алгоритмах компрессии данных на базе LZ. Алгоритм позволяет снять ограничение на диапазон кодируемых длин и смещений словарных фрагментов в скользящем окне метода LZ. Сложность кодирования и память под структуры данных, требуемые для его выполнения при этом определяются числом узлов деревьев Хаффмана, используемых для кодирования начальных значений длин/литералов и смещений. В реализации используются значения 0 и , соответственно. С использованием указанного алгоритма выполнена программная реализация утилиты компрессии данных LZP. Применение утилиты показало ее эффективность для компрессии файлов данных различного типа.