Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео

Ватолин Д., Ратушняк А., Смирнов М., Юкин В.5-86404-170-X

В книге описаны основные классические и современные методы сжатия: метод Хаффмана, арифметическое кодирование, LZ77, LZW, PPM, BWT, LPC и т. д. Разбираются алгоритмы, использующиеся в архиваторах Zip, HA, CabArc (*.cab-файлы), RAR, BZIP2, RK. Отдельный раздел посвящен алгоритмам сжатия изображений, использующимся в форматах PCX, TGA, GIF, TIFF, CCITT G-3, JPEG, JPEG2000. Рассмотрено фрактальное сжатие, вэйвлет-сжатие и др. Изложены принципы компрессии видеоданных, дан обзор стандартов MPEG, MPEG-2, MPEG-4, H.261 и H.263. Некоторые методы повышения сжатия на русском языке публикуются впервые. Книга содержит большое количество примеров и упражнений и ориентирована на студентов и преподавателей вузов. Материал книги позволяет самостоятельно несколькими способами написать архиватор с характеристиками, превосходящими программы типа pkzip и arj. Ответы на вопросы для самоконтроля и исходные тексты программ можно найти на сайте http://compression.ru/book/.

---

Table of contents :
Предисловие……Page 3
Обзор тем……Page 5
Базовые определения……Page 6
Названия методов……Page 9
Карта групп методов сжатия……Page 10
Базовые стратегии сжатия……Page 11
Сравнение алгоритмов по степени сжатия……Page 12
Замечание о методах, алгоритмах и программах……Page 15
РАЗДЕЛ 1. МЕТОДЫ СЖАТИЯ БЕЗ ПОТЕРЬ……Page 17
Разделение мантисс и экспонент……Page 19
Канонический алгоритм Хаффмана……Page 31
Арифметическое сжатие……Page 35
Нумерующее кодирование……Page 49
Векторное квантование……Page 52
Линейно-предсказывающее кодирование……Page 54
Субполосное кодирование……Page 67
Идея словарных методов……Page 75
Классические алгоритмы Зива -Лемпела……Page 77
Другие алгоритмы LZ……Page 90
Формат Deflate……Page 94
Пути улучшения сжатия для методов LZ……Page 106
Архиваторы и компрессоры, использующие алгоритмы LZ…….Page 116
Вопросы для самоконтроля……Page 117
Глава 4. Методы контекстного моделирования……Page 119
Классификация стратегий моделирования……Page 122
Контекстное моделирование……Page 124
Алгоритмы РРМ……Page 131
Оценка вероятности ухода……Page 142
Обновление счетчиков символов……Page 153
Повышение точности оценок в контекстных моделях высоких порядко……Page 155
Различные способы повышения точности предсказания……Page 160
РРМ и РРМ*……Page 165
Достоинства и недостатки РРМ……Page 166
Компрессоры и архиваторы, использующие контекстное
моделирование……Page 168
Обзор классических алгоритмов контекстного моделирования……Page 175
Сравнение алгоритмов контекстного моделирования……Page 178
Другие методы контекстного моделирования……Page 179
Вопросы для самоконтроля……Page 180
Преобразование Барроуза – Уилера……Page 183
Методы, используемые совместно с BWT…….Page 192
Способы сжатия преобразованных с помощью BWT данных……Page 205
Сортировка, используемая в BWT…….Page 212
Архиваторы, использующие BWTu ST……Page 220
Сортировка параллельных блоков……Page 229
Фрагментирование……Page 239
Глава 7. Предварительная обработка данных……Page 246
Препроцессинг текстов……Page 247
Препроцессинг нетекстовых данных……Page 262
Вопросы для самоконтроля……Page 267
Выбор метода сжатия……Page 268
Введение……Page 272
Классы изображений……Page 273
Классы приложений……Page 274
Критерии сравнения алгоритмов……Page 278
Методы обхода плоскости……Page 280
Вопросы для самоконтроля……Page 288
Алгоритм RLE……Page 289
Алгоритм LZW……Page 291
Алгоритм Хаффмана……Page 297
JBIG……Page 302
Lossless JPEG……Page 303
Проблемы алгоритмов сжатия с потерями……Page 304
Алгоритм JPEG……Page 306
Фрактальный алгоритм……Page 311
Рекурсивный (волновой) алгоритм……Page 321
Алгоритм JPEG 2000……Page 323
Заключение……Page 332
Глава 3. Различия между форматом и алгоритмом……Page 333
Введение……Page 338
Требования приложений к алгоритму……Page 339
Определение требований……Page 341
Обзор стандартов……Page 342
Описание алгоритма компрессии……Page 344
Использование векторов смещений блоков……Page 346
Другие пути повышения степени сжатия……Page 348
Motion-JPEG……Page 350
Н.261……Page 351
Н.263……Page 352
MPEG-2……Page 353
MPEG-4……Page 354
Сравнение стандартов……Page 357
Вопросы для самоконтроля……Page 358
Ссылки на программы и реализации алгоритмов……Page 360
П-1. Контекстный компрессор Dummy……Page 361
Сжатие двуцветного изображения……Page 366
Сжатие 16-цветного изображения……Page 367
Сжатие изображения в градациях серого……Page 368
Сжатие полноцветного изображения

……Page 369
Сжатие полноцветного изображения в 100раз……Page 370
УКАЗАТЕЛЬ ТЕРМИНОВ……Page 371