Евгений Рафаилович Пантелеев , Алевтина Леонидовна Алыкова - Алгоритмы сжатия данных без потерь : учебное пособие для вузов

«Разработка программно-информационных систем». Дисциплина «Алгоритмы и структуры
данных» разработана в Ивановском государственном энергетическом
университете (ИГЭУ) на кафедре программного обеспечения компьютерных систем. Рабочая программа дисциплины предусматривает выполнение курсового проекта по разделу «Алгоритмы сжатия данных».
Освоение материала учебного пособия предполагает знание алгоритмических языков, наличие навыков написания объектно-ориентированных программ, а также формируемых в ходе изучения предшествующих разделов дисциплины «Алгоритмы и структуры данных» умений определять и использовать абстрактные типы данных и строить порядковые оценки вычислительной эффективности алгоритмов.
Цель учебного пособия — сформировать теоретическую базу, необходимую для реализации алгоритмов сжатия данных без потерь информации, и продемонстрировать возможности практического применения этих знаний для самостоятельной реализации алгоритмов сжатия
в ходе выполнения курсового проекта по дисциплине. Для достижения
этих целей в пособии обсуждается классификация алгоритмов сжатия,
модели кодирования, лежащие в основе алгоритмов сжатия без потерь,
сами алгоритмы, как на концептуальном уровне, так и на уровне их программной реализации, а также практические рекомендации по выполнению курсового проекта.
Убедиться в том, что алгоритм сжатия выполняет свою главную
функцию, то есть уменьшает объем входных данных — естественное желание разработчика. Поэтому в структуре пособия предусмотрены разделы, содержащие результаты испытаний и их обсуждение. Для чистоты
эксперимента использовались файлы, заведомо не являющиеся продуктом применения алгоритмов сжатия. Это монохромные растровые файлы формата bmp (последовательность точек экранного изображения),
текстовые файлы (последовательность символьных строк переменной
5

длины) и файлы исполняемого формата (управляющая информация для
загрузчика и образ памяти задачи). Приведенное обсуждение результатов испытаний не претендует на общность выводов, касающихся эффективности того или иного алгоритма — для этого объем испытаний явно
недостаточен. Авторы и не ставили перед собой такой задачи. Скорее,
эти испытания являются поводом для рассуждений о влиянии тех или
иных параметров настройки на эффективность алгоритмов сжатия.
В основу учебного пособия положены материалы читаемого в
ИГЭУ одним из авторов лекционного курса по дисциплине «Алгоритмы и
структуры данных», а также целый ряд отечественных и зарубежных публикаций по этой теме. В их числе — электронный ресурс «Всё о сжатии
данных, изображений и видео» (http://compression.ru/), специализирующийся на сборе и публикации материалов по теме. Хотелось бы особо выделить монографию [1] «The Data Compression Book» — книга о сжатии
данных, которая удачно сочетает доступное изложение концепций алгоритмов сжатия с глубоким обсуждением тонкостей программной реализации этих концепций на языке C. Однако с момента выхода этой книги
технологии программирования заметно усовершенствовались, а аппаратные возможности компьютеров выросли на порядок. Это делает актуальной попытку увидеть старые проблемы с новых позиций. Круг рассматриваемых в учебном пособии вопросов ограничен обсуждением алгоритмов
сжатия данных без потерь информации. Это ограничение, а также отбор
алгоритмов для детального рассмотрения, продиктовано ограниченным
объемом учебного курса и не нарушает логику изучения темы.
Все программы, сопровождающие обсуждение алгоритмов сжатия, написаны на языке C++. Этот выбор обусловлен тем, что языки C/C++
являются базой для целого семейства C-подобных языков программирования. В их число входят Java, C#, Python и др. Следовательно, программный код должен быть понятен широкому кругу читателей.
В тексте пособия приводятся только ключевые фрагменты программного кода, демонстрирующие особенности реализации алгоритмов. Необходимые для полноценной реализации вспомогательные алгоритмы приведены в Приложении в разделе П.2, в разделах П.3 и П.4
представлено описание программного кода. Весь программный код реализован в среде Visual Studio 2019.
6

1. Введение
Words are like leaves; and where they most abound,
Much fruit of sense beneath is rarely found1.
Alexander Pope

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