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

Description

Учебное пособие содержит описание алгоритмов сжатия данных без потерь, включающее классификацию этих алгоритмов, их обсуждение на концептуальном уровне и на уровне программной реализации, сравнительный анализ результатов их практического применения, рекомендации по выполнению курсового проекта по данной теме. Также обсуждаются смежные вопросы: особенности работы с двоичными данными, формирования заголовочной части сжатого файла, применение вспомогательных алгоритмов, повышающих эффективность сжатия, и объектно ориентированного подхода к реализации алгоритмов сжатия. Пособие предназначено для бакалавров направления «Программная инженерия». Предисловие 1. Введение 1.1. Вопросы для самоконтроля 2. Словарные алгоритмы сжатия 2.1. Алгоритм кодирования длин серий (RLE) 2.1.1. Байт-ориентированный алгоритм 2.1.2. Бинарный алгоритм 2.1.2.1. Бинарный кодер 2.1.2.2. Бинарный декодер 2.1.3. Обсуждение результатов 2.2. Алгоритм Лемпеля — Зива — Велча (LZW) 2.2.1. Кодер LZW 2.2.2. Декодер LZW 2.2.3. Оптимизация хранения и поиска цепочек 2.3. Обсуждение результатов 2.4. Вопросы и задания для самоконтроля 3. Частотные алгоритмы сжатия 3.1. Статические алгоритмы Шеннона — Фано и Хаффмана 3.1.1. Построение дерева префиксных кодов Шеннона — Фано 3.1.2. Построение дерева префиксных кодов в алгоритме Хаффмана 3.1.2.1. Кодер статического алгоритма 3.1.2.2. Декодер статического алгоритма 3.2. Адаптивный алгоритм Хаффмана 3.2.1. Инициализация модели кодирования 3.2.2. Обновление модели кодирования 3.2.3. Кодер динамического алгоритма Хаффмана 3.2.4. Декодер динамического алгоритма Хаффмана 3.2.5. Обсуждение результатов 3.3. Алгоритм арифметического кодирования 3.3.1. Статическое арифметическое кодирование 3.3.1.1. Целочисленное арифметическое кодирование 3.3.1.1.1. Алгоритм целочисленного кодирования 3.3.1.1.2. Алгоритм целочисленного декодирования 3.3.1.1.3. Проблемы реализации Кодер Декодер 3.3.1.2. Адаптивное целочисленное арифметическое кодирование 3.4. Обсуждение результатов 3.5. Вопросы и задания для самоконтроля 4. Рекомендации по выполнению курсового проекта Заключение Приложения П.1. Варианты заданий для курсового проектирования П.2. Вспомогательные алгоритмы П.2.1. Работа с потоковыми данными в двоичном формате П.2.2. Сохранение/восстановление атрибутов сжимаемого файла П.2.3. Преобразование Бэрроуза — Уилера (BWT) Программная реализация BWT П.2.4. Хеширование по строковому ключу П.3. Оконный интерфейс программы сжатия П.4. Объектная реализация частотных алгоритмов сжатия Список литературы