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

В книге описаны основные классические и современные методы сжатия: метод Хаффмана, арифметическое кодирование, LZ77, LZW, РРМ, BWT, LPC и т. д. Разбираются алгоритмы, использующиеся в архиваторах Zip, НА, СавАгс (\*. саb-файлы), RAR, BZIP2, RK. Отдельный раздел посвящен алгоритмам сжатия изображений, использующимся в форматах PCX, TGA, GIF, TIFF, CCITT G-3, JPEG, JPEG2000. Рассмотрено фрактальное сжатие, вэйвлет-сжатие и др. Изложены принципы компрессии видеоданных, дан обзор стандартов MPEG, MPEG.2, MPEG-4, Н.261 и Н.263. Некоторые методы повышения сжатия на русском языке публикуются впервые. Книга содержит большое количество примеров и упражнений и ориентирована на студентов и преподавателей вузов. Материал книги позволяет самостоятельно несколькими способами написать архиватор с характеристиками, превосходящими программы типа pkzip и arj. Предисловие......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