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

Е. Р. ПАНТЕЛЕЕВ, А. Л. АЛЫКОВА

АЛГОРИТМЫ СЖАТИЯ
ДАННЫХ БЕЗ ПОТЕРЬ
Учебное пособие

•САНКТПЕТЕРБУРГ•МОСКВА•КРАСНОДАР•
•2021•

УДК 004.627
ББК 32.9я73
П 16

Пантелеев Е. Р. Алгоритмы сжатия данных без потерь : учебное
пособие для вузов / Е. Р. Пантелеев, А. Л. Алыкова. — СанктПетербург :
Лань, 2021. — 172 с. : ил. — Текст : непосредственный.
ISBN 9785811478200
Учебное пособие содержит описание алгоритмов сжатия данных без потерь,
включающее классификацию этих алгоритмов, их обсуждение на концептуальном
уровне и на уровне программной реализации, сравнительный анализ результатов
их практического применения, рекомендации по выполнению курсового проекта
по данной теме. Также обсуждаются смежные вопросы: особенности работы с
двоичными данными, формирования заголовочной части сжатого файла, приме
нение вспомогательных алгоритмов, повышающих эффективность сжатия, и
объектноориентированного подхода к реализации алгоритмов сжатия.
Пособие предназначено для бакалавров направления «Программная инже
нерия».

УДК 004.627
ББК 32.9я73

Обложка
П. И. ПОЛЯКОВА

© Издательство «Лань», 2021
© Е. Р. Пантелеев,
А. Л. Алыкова, 2021
© Издательство «Лань»,
художественное оформление, 2021

Содержание
Предисловие .................................................................................................... 5
1.

Введение .................................................................................................. 7
1.1.

2.

Вопросы для самоконтроля .......................................................... 13

Словарные алгоритмы сжатия.............................................................. 15
2.1.

Алгоритм кодирования длин серий (RLE) .................................... 15

2.1.1. Байт-ориентированный алгоритм ........................................ 16
2.1.2. Бинарный алгоритм ............................................................... 18
2.1.3. Обсуждение результатов....................................................... 23
2.2.

Алгоритм Лемпеля — Зива — Велча (LZW) .................................. 25

2.2.1. Кодер LZW ............................................................................... 27
2.2.2. Декодер LZW........................................................................... 33
2.2.3. Оптимизация хранения и поиска цепочек ........................... 39

3.

2.3.

Обсуждение результатов .............................................................. 41

2.4.

Вопросы и задания для самоконтроля ........................................ 43

Частотные алгоритмы сжатия ............................................................... 45
3.1.

Статические алгоритмы Шеннона — Фано и Хаффмана ............ 46

3.1.1. Построение дерева префиксных кодов
Шеннона — Фано ................................................................................ 48
3.1.2. Построение дерева префиксных кодов в алгоритме
Хаффмана............................................................................................. 52
3.2.

Адаптивный алгоритм Хаффмана ................................................. 64

3.2.1. Инициализация модели кодирования ................................. 64
3.2.2. Обновление модели кодирования ....................................... 66
3.2.3. Кодер динамического алгоритма Хаффмана ...................... 73
3.2.4. Декодер динамического алгоритма Хаффмана .................. 76
3

3.2.5. Обсуждение результатов....................................................... 78
3.3.

Алгоритм арифметического кодирования .................................. 79

3.3.1. Статическое арифметическое кодирование ........................ 81

4.

3.4.

Обсуждение результатов ............................................................ 106

3.5.

Вопросы и задания для самоконтроля ...................................... 108

Рекомендации по выполнению курсового проекта ......................... 111

Заключение .................................................................................................. 114
Приложения ................................................................................................. 116
П.1. Варианты заданий для курсового проектирования .................... 116
П.2. Вспомогательные алгоритмы ........................................................ 118
П.2.1. Работа с потоковыми данными
в двоичном формате ........................................................................ 119
П.2.2. Сохранение/восстановление атрибутов
сжимаемого файла ........................................................................... 127
П.2.3. Преобразование Бэрроуза — Уилера (BWT) ............................. 129
П.2.4. Хеширование по строковому ключу ..................................... 137
П.3. Оконный интерфейс программы сжатия ...................................... 139
П.4. Объектная реализация частотных алгоритмов сжатия ............... 145
Список литературы ...................................................................................... 170

4

Предисловие
Учебное пособие охватывает содержание раздела «Алгоритмы
сжатия данных» дисциплины «Алгоритмы и структуры данных», которая
читается для бакалавров, обучающихся по направлению подготовки
09.03.04 «Программная инженерия» по профилю --">