1 Сжатие без потерь Дмитрий Ватолин Московский Государственный Университет CS MSU Graphics&Media Lab Version 2.2. - презентация

1

2 1 Сжатие без потерь Дмитрий Ватолин Московский Государственный Университет CS MSU Graphics&Media Lab Version 2.2

3 CS MSU Graphics & Media Lab (Video Group) Материалы о сжатии В мае 2002 года на базе нашей лаборатории был создан сервер «Все о сжатии»: Сейчас сайт содержит более 600Мб информации и является крупнейшим русскоязычным сайтом по сжатию. На сайте выложена книга Д.Ватолин, М.Смирнов, А.Ратушняк, В.Юкин «Методы сжатия данных», Диалог-МИФИ, Данный курс дополняет ее в областях сжатия аудио, изображений и 3D-видео.

4 CS MSU Graphics & Media Lab (Video Group) Цель лекций Целью данных лекций является рассказ об избранных базовых и новых технологиях, использующихся при сжатии звука, изображений и видео. Первыми рассказываются методы сжатия без потерь, базовые для остальных методов.

5 CS MSU Graphics & Media Lab (Video Group) Структура материала u Введение Общие понятия сжатия Теорема Шеннона u Методы сжатия Метод Хаффмана Арифметическое сжатие PPM BWT (MTF) LZ-Huffman

6 CS MSU Graphics & Media Lab (Video Group) Методы сжатия без потерь Методы сжатия без потерь разделяют на две категории: u Методы сжатия источников данных без памяти (т.е. не учитывающих последовательность символов) u Методы сжатия источников с памятью

7 CS MSU Graphics & Media Lab (Video Group) Методы сжатия источников без памяти u Сжатие по Хаффману Самый известный и распространенный метод. Сдает позиции более мощному арифметическому сжатию. u Арифметическое сжатие Наилучший на сегодня метод по степени сжатия. Имеет быструю реализацию, крайне гибок. u Сжатие с кодами Райса-Голомба Используется как компромисс между методом Хаффмана и Арифметическим, когда есть ограничения на вычислительную сложность.. (также известны нумерующие кодирование, разделение мантисс и экспонент, коды Элиаса, Фибоначчи и др.)

8 CS MSU Graphics & Media Lab (Video Group) Методы сжатия источников с памятью u Словарные методы сжатия (LZ, LZW. Давний универсальный метод (ZIP), используется для сжатия в GIF & PNG) u Методы контекстного моделирования (PPM. Новый универсальный метод. Позволяет добиться максимальных результатов.) u Сжатие с использованием преобразования Барроуза-Уилера и других сортирующих преобразований (BWT, ST. Используется в основном для текста.)

9 CS MSU Graphics & Media Lab (Video Group) Алгоритм Хаффмана Использует только частоту появления одинаковых байт в изображении. Сопоставляет символам входного потока, которые встречаются большее число раз, цепочку бит меньшей длины. И, напротив, встречающимся редко цепочку большей длины. Для сбора статистики требует двух проходов по изображению.

10 CS MSU Graphics & Media Lab (Video Group) Алгоритм Хаффмана-2

11 CS MSU Graphics & Media Lab (Video Group) Алгоритм Хаффмана-3 u Коэффициенты компрессии: 8, 1,5, 1 (Лучший, средний, худший коэффициенты). u Использование: Практически не применяется в чистом виде. Обычно используется как один из этапов компрессии в более сложных схемах. u Симметричность: 2 (за счет того, что требует двух проходов по массиву сжимаемых данных). u Характерные особенности: Единственный алгоритм, который не увеличивает размера исходных данных в худшем случае (если не считать необходимости хранить таблицу перекодировки вместе с файлом).

12 CS MSU Graphics & Media Lab (Video Group) Теорема Шеннона Теорема о кодировании источника: Элемент s i, вероятность появления которого равняется p(s i ), выгоднее всего представлять –log 2 p(s i ) битами. Если при кодировании размер кодов всегда в точности получается равным –log 2 p(s i ) битам, то в этом случае длина закодированной последовательности будет минимальной для всех возможных способов кодирования.

13 CS MSU Graphics & Media Lab (Video Group) Энтропия источника Если распределение вероятностей F = {p(s i )} неизменно, и вероятности появления элементов независимы, то мы можем найти среднюю длину кодов как среднее взвешенное: Это значение также называется энтропией распределения вероятностей F или энтропией источника в заданный момент времени.

14 CS MSU Graphics & Media Lab (Video Group) Структура материала u Введение Общие понятия сжатия Теорема Шеннона u Методы сжатия Метод Хаффмана Арифметическое сжатие PPM BWT (MTF) LZ-Huffman

15 CS MSU Graphics & Media Lab (Video Group) Арифметическое сжатие Основная идея: Мы представляем кодируемый текст в виде длинной дроби. Для этого берется интервал [0, 1) (0 включается, 1 нет), который разбивается на подынтервалы с длинами, пропорциональными вероятностям появления символов в потоке.

16 CS MSU Graphics & Media Lab (Video Group) AC: Пример Пусть мы сжимаем текст "КОВ.КОРОВА" СимволВероятностьИнтервал О0.3[0.0; 0.3) К0.2[0.3; 0.5) В0.2[0.5; 0.7) Р0.1[0.7; 0.8) А0.1[0.8; 0.9) "."0.1[0.9; 1.0)

17 CS MSU Graphics & Media Lab (Video Group) AC: Визуальное представление Графически соответствующую процедуру можно представить так:

18 CS MSU Graphics & Media Lab (Video Group) АС: Пример Берем исходный интервал и кодируем текст: Изначально интервал[0, 1). Символ "К"[0.3; 0.5)получаем [0.3; 0.5). Символ "О"[0.0; 0.3)получаем [0.3; 0.36). Символ "В"[0.5; 0.7)получаем [0.33; 0.342). Символ "."[0.9; 1.0)получаем [0,3408; 0.342).

19 CS MSU Graphics & Media Lab (Video Group) АС: Процедура сжатия Если обозначить интервал символа c, как [a[c]; b[c]), а кодируемый интервал для i-го символа потока как [l i, h i ). То алгоритм компрессии запишется как: l 0 =0; h 0 =1; i=0; while(not DataFile.EOF()){ c = DataFile.ReadSymbol(); i++; l i = l i-1 + a[c]·(h i-1 - l i-1 ); h i = l i-1 + b[c]·(h i-1 - l i-1 ); };

20 CS MSU Graphics & Media Lab (Video Group) АС: Процедура распаковки Алгоритм декомпрессии выглядит так: l 0 =0; h 0 =1; value=File.Code(); for(i=0; i

21 CS MSU Graphics & Media Lab (Video Group) АС: Двоичные дроби Заметим, что мы можем приближать получающуюся дробь с помощью двоичной дроби

22 CS MSU Graphics & Media Lab (Video Group) АС: Бесконечное сжатие Пример: один бит "1" (двоичное число "0.1") для наших интервалов однозначно задает цепочку "ВОООООООООО…" сколь угодно большой длины.

23 CS MSU Graphics & Media Lab (Video Group) АС: Целочисленные вероятности Перейдем к целочисленным коэффициентам: JСимвол (c j )Вероятностьb[cj]b[cj] 00 1О33 2К25 3В27 4Р18 5А19 6"."110

24 CS MSU Graphics & Media Lab (Video Group) АС: Пример нормализации Движение подынтервалов при реальном сжатии В выходной поток

25 CS MSU Graphics & Media Lab (Video Group) АС: Реальный пример процедуры сжатия l 0 =0; h 0 =65535; i=0; delitel= b[c last ]; // =10 First_qtr = (h 0 +1)/4; Half = First_qtr*2; // = = Third_qtr = First_qtr*3; bits_to_follow =0; // = 49152, Сколько бит сбрасывать while(not DataFile.EOF()) { c = DataFile.ReadSymbol(); // Читаем символ j = IndexForSymbol(c); i++ // Находим его индекс l i = l i-1 + b[j-1]*(h i-1 - l i-1 + 1)/delitel; h i = l i-1 + b[j ]*(h i-1 - l i-1 + 1)/delitel - 1; for(;;) { // Обрабатываем варианты if(h i < Half) // переполнения bits_plus_follow(0); else if(l i >= Half) { bits_plus_follow(1); l i -= Half; h i -= Half; } else if((h i = Third_qtr)){ bits_to_follow++; l i -= First_qtr; h i -= First_qtr; } else break; l i +=l i ; h i += h i +1; }

26 CS MSU Graphics & Media Lab (Video Group) АС: Реальный пример процедуры сжатия (2) // Процедура сброса найденных бит в файл void bits_plus_follow (int bit) { CompressedFile.WriteBit(bit); for(; bits_to_follow > 0; bits_to_follow--) CompressedFile.WriteBit(!bit); }

27 CS MSU Graphics & Media Lab (Video Group) АС: Работа целочисленного алгоритма Пример сжатия цепочки: i Символ (c j ) hihihihi lililili Нормали з: h i Нормализ : l i Вывод К О В К О

28 CS MSU Graphics & Media Lab (Video Group) АС: Характеристики Характеристики арифметического сжатия: u Позволяет сжимать несколько сильнее, чем алгоритм Хаффмана u Работает медленнее, чем алгоритм Хаффмана u Допускает как статическую, так и динамическую (адаптивную) реализацию

29 CS MSU Graphics & Media Lab (Video Group) АС: Сравнение с алгоритмом Хаффмана

30 CS MSU Graphics & Media Lab (Video Group) АС: Пример Пусть есть два символа a и b с вероятностями 253/256 и 3/256 Для арифметического сжатия мы потратим на цепочку из 256 байт –log 2 (253/256)·253– log 2 (3/256)·3 = , т.е. 24 бита. При кодировании по Хаффману мы закодируем a и b как 0 и 1, и потратим 1·253+1·3=256 битов, т.е. в 10 раз больше

31 CS MSU Graphics & Media Lab (Video Group) Повышение степени сжатия Методы повышения степени сжатия: u Применение динамических таблиц u Изменение агрессивности динамической подстройки u Инициализация таблиц (несколько таблиц) u Использование переключения между таблицами u Увеличение точности вычислений (в int & double) u Использование PPM

32 CS MSU Graphics & Media Lab (Video Group) Структура материала u Введение Общие понятия сжатия Теорема Шеннона u Методы сжатия Метод Хаффмана Арифметическое сжатие PPM BWT (MTF) LZ-Huffman

33 CS MSU Graphics & Media Lab (Video Group) PPM: Идея Классический PPM (prediction by partial matching) - это метод контекстно-зависимого моделирования ограниченного порядка, позволяющий оценить вероятность символа в зависимости от предыдущих символов. Строку символов, непосредственно предшествующую текущему символу, будем называть контекстом. Если для оценки вероятности используется контекст длины N, то мы имеем дело с контекстно- ограниченной моделью степени N или порядка N.

34 CS MSU Graphics & Media Lab (Video Group) PPM: Общая схема алгоритма Важно, что каждый новый символ кодируется на оценке его вероятности

35 CS MSU Graphics & Media Lab (Video Group) PPM: Пример модели 0 Простой пример – модель порядка 0: тогда вероятность следующего символа будет зависеть от того, как часто он встречался ранее.

36 CS MSU Graphics & Media Lab (Video Group) PPM: Пример модели 1 Простой пример – модель порядка 1: тогда вероятность следующего символа будет зависеть от предыдущего символа.

37 CS MSU Graphics & Media Lab (Video Group) PPM: варианты моделирования u Статическое Используется фиксированная модель u Полуадаптивное Модель сохраняется в файле u Адаптивное (динамическое) Модель изменяется в процессе сжатия и распаковки u Блочно-адаптивное Модель меняется сильно между блоками разных данных

38 CS MSU Graphics & Media Lab (Video Group) PPM: Выбор сложности модели Зависимости степени сжатия от длины модели для текстовых данных

39 CS MSU Graphics & Media Lab (Video Group) PPM: Принципы сжатия сигналов В модели сигнала - используются знания о важности частей сигнала для человека В модели коэффициентов используются знания об избыточности коэффициентов.

40 CS MSU Graphics & Media Lab (Video Group) PPM: Сжатие изображений Используется преобразование цветовых пространств и т.д. Модели сигнала: DCT Wavelets Fractals (Аффинное преобразование)

41 CS MSU Graphics & Media Lab (Video Group) PPM: Сжатие видео u Используется преобразование цветовых пространств (избыточность по цвету). u Используется компенсация движения (избыточность по времени). Модели сигнала: DCT Wavelet Object-oriented

42 CS MSU Graphics & Media Lab (Video Group) PPM: Сжатие звука u Используется маскирование по частоте (избыточность по частоте). u Используется маскирование по времени. u Используется избыточность стерео-сигнала. Модели сигнала: MDCT DCT FFT Wavelets

43 CS MSU Graphics & Media Lab (Video Group) Задача: общая постановка u Программа умеет получать на вход файл и по опции «с» - сжимать его, по опции «d» распаковывать его. u Задается метод сжатия – арифметический (обязателен) и PPM. u Язык реализации – консольное приложение на С или С++ Пример: compress c in_file.doc out_file.cmp ppm compress d out_file.cmp out_file.doc

44 CS MSU Graphics & Media Lab (Video Group) Задача: Требования u Арифметическое сжатие – только классический алгоритм (методы его оптимизации разбирались) u За использование чужих текстов или совместное написание – дисквалификация. u Оцениваться будет степень сжатия файлов, отдаваемых на вход программы. u Распакованный файл должен совпадать с паковавшимся!!!

45 CS MSU Graphics & Media Lab (Video Group) Задача: Улучшение результата Методы повышения степени сжатия: u Применение динамических таблиц u Изменение агрессивности динамической подстройки u Инициализация таблиц (несколько таблиц) u Использование переключения между таблицами u Увеличение точности вычислений (в int & double)

46 CS MSU Graphics & Media Lab (Video Group) Задача: Сроки u Срок начала задания – 15 октября u Срок сдачи задания – 05 ноября u Сдаются: Исходный текст в виде компилируемого проекта Пояснения (read_me) с указанием фамилии, группы и номера зачетной книжки Скомпилированная программа и пример u Готовое задание высылается по адресу

47 CS MSU Graphics & Media Lab (Video Group) Структура материала u Введение Общие понятия сжатия Теорема Шеннона u Методы сжатия Метод Хаффмана Арифметическое сжатие PPM BWT (MTF) LZ-Huffman

48 CS MSU Graphics & Media Lab (Video Group) BWT / Идея BWT (Burrows-Wheeler Transform) – преобразование Бароуза-Уилера – предназначено для того, чтобы сделать сжатие потока данных более эффективным. Алгоритм опубликован в 1994 (разработан – в 1983). Мы переставляем символы выходного потока таким образом, что применяемый далее алгоритм становится более эффективен.

49 CS MSU Graphics & Media Lab (Video Group) BWT / Шаг 1 Пусть мы сжимаем строку символов «абракадабра». Подготовим все ее циклические перестановки. абракадабра бракадабраа ракадабрааб акадабраабр кадабраабра адабраабрак дабраабрака абраабракад браабракада раабракадаб аабракадабр

50 CS MSU Graphics & Media Lab (Video Group) BWT / Шаг 2 Пометим в получившейся матрице исходную строку и отсортируем все строки в соответствии с лексикографичес- ким порядком символов. 0аабракадабр 1абраабракад 2абракадабра – исх. строка 3адабраабрак 4акадабраабр 5браабракада 6бракадабраа 7дабраабрака 8кадабраабра 9раабракадаб 10ракадабрааб

51 CS MSU Graphics & Media Lab (Video Group) BWT / Шаг 3 Выписываем символы последнего столбца и запоминаем номер исходной строки среди отсортированных. Получаем результат преобразования BWT: «рдакраааабб», 2 Длина результата и состав символов – как в исходной цепочке. аабракадабр абраабракад абракадабра - 2 адабраабрак акадабраабр браабракада бракадабраа дабраабрака кадабраабра раабракадаб ракадабрааб

52 CS MSU Graphics & Media Lab (Video Group) BWT / Суть «Фокус» BWT в том, что полученной цепочки «рдакраааабб» и числа 2 достаточно для воссоздания исходной цепочки. Зачем это нужно? Если мы преобразуем таким образом достаточно длинный текст, со словами the, The, then, when, that, то мы получим на выходе цепочку в которой будет столько t подряд, сколько слов the в исходной цепочке, потом будет идти столько T, сколько The и т.д. Происходит сортировка по «частоте сочетаний» ………… he... t he...T he... t hen... t hen...w hen... t …………

53 CS MSU Graphics & Media Lab (Video Group) Обратное BWT / Шаг 1 Итак! Мы получили на вход In={рдакраааабб}, 2 Отсортируем полученную цепочку символов. Нам известно, что строки матрицы были отсортированы по порядку, начиная с первого символа. Поэтому в результате такой сортировки мы получили первый столбец исходной матрицы. 0а 1а 2а 3а 4а 5б 6 б 7д 8к 9р 10р

54 CS MSU Graphics & Media Lab (Video Group) Обратное BWT / Шаг 2 Поскольку последний столбец по условию задачи нам известен, добавим его в полученную матрицу. 0а р 1а д 2а а 3а к 4а р 5б а 6б а 7д а 8к а 9р б 10р б

55 CS MSU Graphics & Media Lab (Video Group) Обратное BWT / Шаг 3 Строки матрицы были получены в результате циклического сдвига исходной строки. То есть, символы последнего и первого столбцов образуют друг с другом пары. И нам ничто не может помешать отсортировать эти пары, поскольку обязательно существуют такие строки в матрице, которые начинаются с этих пар. Заодно допишем в матрицу и последний столбец (рдакраааабб). 0 аа р 1 аб д 2 аб а 3 ад к 4 ак р 5 бр а 6 бр а 7 да а 8 ка а 9 ра б 10ра б

56 CS MSU Graphics & Media Lab (Video Group) Обратное BWT / Идея Заметим, что шаг 3 можно повторить еще раз, отсортировав уже тройки символов. Повторяем этот шаг столько раз, сколько необходимо для восстановления всей таблицы, а потом берем из нее строку с номером 2 в качестве исходной.

57 CS MSU Graphics & Media Lab (Video Group) Обратное BWT полностью 0ааб раабр......р аабракада.раабракадабр 1абр дабра......д абраабрак.дабраабракад 2абр аабра......а абракадаб.аабракадабра 3ада кадаб......к адабраабр.кадабраабрак 4ака ракад......р акадабраа.ракадабраабр 5бра абраа......а...браабрака.абраабракада 6бра абрак......а бракадабр.абракадабраа 7даб адабр......а дабраабра.адабраабрака 8кад акада......а кадабрааб.акадабраабра 9раа брааб......б раабракад.браабракадаб 10рак брака......б ракадабра.бракадабрааб

58 CS MSU Graphics & Media Lab (Video Group) Обратное BWT Быстрый вариант (1) Запишем порядок строк после сортировки и перед сортировкой. номер строки номер новой строки переносим последний столбец 2а а0аа р 5б а1аб д 6б а2аб а 7д а3ад к 8к а4ак р 9р б5бр а 10р б6бр а 1а д7да а 3а к8ка а 0а р9ра б 4а р10ра б

59 CS MSU Graphics & Media Lab (Video Group) Обратное BWT Быстрый вариант (2) Полученный вектор T = { 2, 5, 6, 7, 8, 9, 10, 1, 3, 0, 4 }, содержит номера позиций символов, упорядоченных в соответствии с положением в алфавите, в строке, которую нам надо декодировать. Начинаем декодирование со второго элемента. T[2] = 6, T[6] = 10, T[10] = 4, T[4] = 8… Получаем цепочку: 6, 10, 4, 8, 3, 7, 1, 5, 9, 0, 2 А теперь, выписываем соответствующие символы из исходной цепочки (In[6], In[10]…). Получаем абракадабра 2 0 р 5 1д 6 2а 7 3к 8 4р 9 5а 10 6а 1 7а 3 8а 0 9б 4 10б

60 CS MSU Graphics & Media Lab (Video Group) BWT – Характеристики Характеристики BWT: u Работает сравнительно медленно u Требует достаточно много памяти u Позволяющее значительно поднять степень сжатия, в особенности на текстовых данных.

61 CS MSU Graphics & Media Lab (Video Group) Метод MTF Метод MTF (Move To Front) – русское название «метод стопки книг» Идея крайне проста: u Мы получаем из потока новый символ (название книги), u Помещаем в выходной поток ее номер в стопке u Кладем книгу в начало стопки ………… he... t he...T he... t hen... t hen...w hen... t …………

62 CS MSU Graphics & Media Lab (Video Group) Метод MTF / Псевдокод N – число символов в алфавите. M[N] – упорядоченный список символов. M[0] соответствует верхней книге стопки, M[N-1] нижней. x – очередной символ int tmp1, tmp2, i=0; tmp1 = M[i]; while( tmp1 != x ) { tmp2 = tmp1; i++; tmp1 = M[i]; M[i] = tmp2; } M[0] = x; Обработаем 'рдакраааабб': СимволСписокВыход рабдкр4 драбдк3 адрабк2 кадрбк4 ркадрб3 аркадб2 ааркдб0 а 0 а 0 б 4 ббаркд0 Получим ' ':

63 CS MSU Graphics & Media Lab (Video Group) Метод MTF / Пример Пусть есть цепочка: 'bbbbcccccdddddaaaaab' Если сжимать ее по Хаффману, то вероятность всех символов ¼ и потребуется 20*2 = 40 бит Предположим, что начальный упорядоченный список символов выглядит как {'a', 'b', 'c', 'd'}. bbbbcccccdddddaaaaab исходная строка строка после MTF Получившуюся строку можно упаковать по Хаффману в 15*1 + 3* = 27 бит СимволВероятностьКод Хаффмана 03/40 33/ / /20111

64 CS MSU Graphics & Media Lab (Video Group) Метод MTF / Применение u MTF наиболее эффективно применять на цепочках, получающихся после BWT. Общая схема алгоритма при этом выглядит как: BWT >> MTF >> RLE >> арифметич. сжатие u Изредка MTF эффективен и просто перед словарными методами.

65 CS MSU Graphics & Media Lab (Video Group) Структура материала u Введение Общие понятия сжатия Теорема Шеннона u Методы сжатия Метод Хаффмана Арифметическое сжатие PPM BWT (MTF) LZ-Huffman

66 CS MSU Graphics & Media Lab (Video Group) LZ-Huffman 1. Основные идеи и понятия Деревья Хаффмана Repeated offsets 2. Алгоритм LZX Предобработка Сжатие информации Типы блоков Кодирование деревьев

67 CS MSU Graphics & Media Lab (Video Group) Модификация LZ77 LZ77 Деревья Хаффмана Масштабируемое окно LZX

68 CS MSU Graphics & Media Lab (Video Group) Деревья Хаффмана Если два элемента имеют одинаковую длину пути, то элемент с меньшей частотой должен располагаться левее.

69 CS MSU Graphics & Media Lab (Video Group) Деревья Хаффмана 2.Если вершина имеет потомков, то все остальные вершины с той же длиной пути, лежащие левее, также должны иметь потомков. 3. Дерево должно содержать как минимум два элемента.

70 CS MSU Graphics & Media Lab (Video Group) Деревья, используемые в алгоритме 1. Основное дерево (main tree). 2. Дерево длин (length tree). 3. Дерево выровненных смещений (aligned offset tree), pre-деревья (pre-tree), etc.

71 CS MSU Graphics & Media Lab (Video Group) LZ-Huffman 1. Основные идеи и понятия Деревья Хаффмана Repeated offsets 2. Алгоритм LZX Предобработка Сжатие информации Типы блоков Кодирование деревьев

72 CS MSU Graphics & Media Lab (Video Group) Repeated Offsets (LZ77 modifications) u Идея: отдельно хранить три наиболее часто употребляемых смещения (вернее их коды (repeated offset codes)) в отдельном списке. u Структура списка : R0 – самое последнее смещение R1 – предпоследнее смещение R2 – третье по счету.

73 CS MSU Graphics & Media Lab (Video Group) Работа со списком смещений Match offset X where...Operation X R0 and X R1 and X R2R2 R1 R1 R0 R0 X X = R0None X = R1 swap R0 R1 X = R2 swap R0 R2

74 CS MSU Graphics & Media Lab (Video Group) LZ-Huffman 1. Основные идеи и понятия Деревья Хаффмана Repeated offsets 2. Алгоритм LZX Предобработка Сжатие информации Типы блоков Кодирование деревьев

75 CS MSU Graphics & Media Lab (Video Group) Алгоритм LZX HeaderBlock … Формат данных:

76 CS MSU Graphics & Media Lab (Video Group) 0 1Most significant 16 bits of file translation size Least significant 16 bits of file translation size Если первый бит равен 1, то имеется предварительная обработка. В таком случае за ним идет дополнительная информация о параметрах предварительного кодирования. Алгоритм LZX

77 CS MSU Graphics & Media Lab (Video Group) Содержание 1. Основные идеи и понятия Деревья Хаффмана Repeated offsets 2. Алгоритм LZX Предобработка Сжатие информации Типы блоков данных Кодирование деревьев

78 CS MSU Graphics & Media Lab (Video Group) Предобработка Цель: Предварительная обработка для улучшения сжатия 32х-разрядных исполняемых файлов (.exe,.dll,.ocx, …)

79 CS MSU Graphics & Media Lab (Video Group) Предобработка Реализация: Замена во всех командах CALL (код E8h) относительного смещения на абсолютное. Остальные данные не меняются.

80 CS MSU Graphics & Media Lab (Video Group) Предобработка (Поясняющая диаграмма) Loop … E8 a11 a12 a13 E8 a21 a22 a23 E8 a31 a32 a33 До Loop … E8 a1 a2 a3 После

81 CS MSU Graphics & Media Lab (Video Group) Предобработка (Pseudocode) CALL byte sequence (E8 followed by 32 bit offset) E8 r0 r1 r2 r3 Performing the relative-to-absolute conversion relative_offset = r0 + (r1

82 CS MSU Graphics & Media Lab (Video Group) LZ-Huffman 1. Основные идеи и понятия Деревья Хаффмана Repeated offsets 2. Алгоритм LZX Предобработка Сжатие информации Типы блоков данных Кодирование деревьев

83 CS MSU Graphics & Media Lab (Video Group) Сжатие информации (кодирование символов) Блок HeaderData Unmatched symbolsMatched symbols Одиночные символыПодстановки

84 CS MSU Graphics & Media Lab (Video Group) Одиночные символы (unmatched symbols) Все 256 стандартных символов ASCII кодируются при помощи дерева Хаффмана. Что позволяет наиболее частые (для данного файла) символы кодировать меньшим количеством бит, а менее частые – большим. Символы представляются элементами 0…(NUM_CHARS-1) основного дерева Хаффмана (main tree).

85 CS MSU Graphics & Media Lab (Video Group) Кодирование подстановок Идея: Искать большие повторяющиеся последовательности. Записывать их один раз и давать им код. Далее ссылаться на них только по этому коду (несколько бит).

86 CS MSU Graphics & Media Lab (Video Group) Кодирование подстановок Match lengthMatch offset Formatted offset Position slotPosition footerLength header Length/Position header Verbatim position bits 3 Aligned offset bits Length footer Length tree 2Main tree 1 Aligned offset tree 4 OUTPUT

87 CS MSU Graphics & Media Lab (Video Group) Кодирование подстановок Подстановка задается двумя параметрами: u длина подстановки (match length) u cмещение подстановки (match offset) относительно текущей позиции

88 CS MSU Graphics & Media Lab (Video Group) Преобразование смещения Match lengthMatch offset Formatted offset Position slotPosition footerLength header Length/Position header Verbatim position bits 3 Aligned offset bits Length footer Length tree 2Main tree 1 Aligned offset tree 4 OUTPUT

89 CS MSU Graphics & Media Lab (Video Group) Преобразование смещения (Match offset Formatted offset) Converting a match offset to a formatted offset if (offset = = R0) formatted offset = 0; else if (offset = = R1) formatted offset = 1; else if (offset = = R2) formatted offset = 2; else formatted offset = offset + 2;

90 CS MSU Graphics & Media Lab (Video Group) Таблица смещений Encoded offsetReal offset 0Most recent non-repeated match offset 1Second most recent non-repeated match offset 2Third most recent non-repeated match offset 31 (closest allowable) x+2X WINDOW_SIZE-1 (maximum possible) WINDOW_SIZE-3

91 CS MSU Graphics & Media Lab (Video Group) Преобразование смещения Match lengthMatch offset Position slotPosition footerLength header Length/Position header Verbatim position bits 3 Aligned offset bits Length footer Length tree 2Main tree 1 Aligned offset tree 4 OUTPUT Formatted offset

92 CS MSU Graphics & Media Lab (Video Group) Преобразование смещения (Formatted offset Position slot, Position footer) Position slotPosition footer Форматированное смещение bits

93 CS MSU Graphics & Media Lab (Video Group) Таблица преобразования смещения Position slot number Base positionNumber of position footer bits Range of base position and position footer

94 CS MSU Graphics & Media Lab (Video Group) Определение значения величины position footer N (position slot)extra_bits[n] (number of position footer bits)

95 CS MSU Graphics & Media Lab (Video Group) Вычисление значений position slot и position footer Calculating the position slot and position footer position_slot = calculate_position_slot(formatted_offset); position_footer_bits = extra_bits(position_slot); if (position_footer_bits > 0) position_footer = formatted_offset & ((1

96 CS MSU Graphics & Media Lab (Video Group) Position footer Match lengthMatch offset Formatted offset Position slotLength header Length/Position header Verbatim position bits 3 Aligned offset bits Length footer Length tree 2Main tree 1 Aligned offset tree 4 OUTPUT Position footer

97 CS MSU Graphics & Media Lab (Video Group) Position footer Verbatim bitsAligned offset bits Есть выравнивание? нетда

98 CS MSU Graphics & Media Lab (Video Group) Position footer (code) if (block_type = = aligned_offset_block){ if (formatted_offset > 3; } else{ verbatim_bits = position_footer; aligned_offset = null; }

99 CS MSU Graphics & Media Lab (Video Group) Преобразование длины смещения Match lengthMatch offset Formatted offset Position slotPosition footerLength header Length/Position header Verbatim position bits 3 Aligned offset bits Length footer Length tree 2Main tree 1 Aligned offset tree 4 OUTPUT

100 CS MSU Graphics & Media Lab (Video Group) Преобразование длины смещения (Match length Length header, Length footer) Pseudocode for obtaining the length header and footer if (match_length

101 CS MSU Graphics & Media Lab (Video Group) Пример Match lengthLength headerLength footer value 2 (MIN_MATCH)0None (MAX_MATCH)7248

102 CS MSU Graphics & Media Lab (Video Group) Diagram of match sub- components Match lengthMatch offset Formatted offset Position footer Length/Position header Verbatim position bits 3 Aligned offset bits Length footer Length tree 2Main tree 1 Aligned offset tree 4 OUTPUT Length headerPosition slot

103 CS MSU Graphics & Media Lab (Video Group) Length header, Position slot Length / Position header len_pos_header = (position_slot

104 CS MSU Graphics & Media Lab (Video Group) Кодирование подстановки Match lengthMatch offset Formatted offset Position slotPosition footerLength header Length/Position header Aligned offset bits Length footer OUTPUT Verbatim position bits 3 Length tree 2Main tree1 Aligned offset tree 4

105 CS MSU Graphics & Media Lab (Video Group) Кодирование подстановки (Encoding a match) Используется до 4-ех полей: 1.Output element (len_pos_header + NUM_CHARS) from the main tree 2.If length_footer != null, then output element length_footer from the length tree 3.If verbatim_bits != null, then output verbatim_bits 4.If aligned_offset_bits != null, then output element aligned_offset from the aligned offset tree

106 CS MSU Graphics & Media Lab (Video Group) LZ-Huffman 1. Основные идеи и понятия Деревья Хаффмана Repeated offsets 2. Алгоритм LZX Предобработка Сжатие информации Типы блоков данных Кодирование деревьев

107 CS MSU Graphics & Media Lab (Video Group) Типы блоков Первые три бита блока указывают, к какому типу он относится. 0Undefined 1Verbatim block 2Aligned offset block 3Uncompressed block 4-7Undefined не определено сжатый блок без сжатия не определено выровненные смещения

108 CS MSU Graphics & Media Lab (Video Group) Блок без сжатия 1-16 bits4 bytes n bytes zero padding R0R1R2Uncompressed data R0, R1, R2 – элементы списка смещений

109 CS MSU Graphics & Media Lab (Video Group) Сжатый блок EntryCommentsSize Number of uncompressed bytes accounted for in this block Range of bits Pre-tree for first 256 elements of main tree 20 elements, 4 bits each80 bits Path lengths of first 256 elements of main tree Encoded using pre-treeVariable Pre-tree for remainder of main tree20 elements, 4 bits each80 bits Path lengths of remaining elements of main tree Encoded using pre-treeVariable Pre-tree for length tree20 elements, 4 bits each80 bits Path lengths of elements in length tree Encoded using pre-treeVariable Compressed literalsDescribed laterVariable

110 CS MSU Graphics & Media Lab (Video Group) Сжатый блок (диаграмма) 24 bits 80 bitsVariable80 bitsVariable80 bits Variable SizePre-tree for 256 elem of main tree Path lengths for 256 elem of main tree Pre-tree for remainder of main tree Path lengths for remainder of main tree Pre- tree for length tree Path lengths for length tree Compressed literals

111 CS MSU Graphics & Media Lab (Video Group) Блок выровненных смещений EntryCommentsSize Number of uncompressed bytes accounted for in this block Range of bits Pre-tree for first 256 elements of main tree 20 elements, 4 bits each80 bits Path lengths of first 256 elements of main tree Encoded using pre-treeVariable Pre-tree for remainder of main tree20 elements, 4 bits each80 bits Path lengths of remaining elements of main tree Encoded using pre-treeVariable Pre-tree for length tree20 elements, 4 bits each80 bits Path lengths of elements in length treeEncoded using pre-treeVariable Aligned offset tree8 elements, 3 bits each24 bits Compressed literalsDescribed laterVariable

112 CS MSU Graphics & Media Lab (Video Group) Блок выровненных смещений (диаграмма) 24 bits 80 bits Variable80 bitsVariable80 bits Variable24 bitsVariable SizePre- tree for 256 elem of main tree Path lengths for 256 elem of main tree Pre-tree for remainder of main tree Path lengths for remainder of main tree Pre- tree for length tree Path lengths for length tree Aligned offset tree Compressed literals

113 CS MSU Graphics & Media Lab (Video Group) LZ-Huffman 1. Основные идеи и понятия Деревья Хаффмана Repeated offsets 2. Алгоритм LZX Предобработка Сжатие информации Типы блоков Кодирование деревьев

114 CS MSU Graphics & Media Lab (Video Group) Кодирование деревьев (Encoding of trees) 1. Основное дерево (main tree) кодируется в виде двух компонент:одно дерево для одиночных символов (unmatched symbols), другое для подстановок (matches). 2. С учетом ограничений на дерево Хаффмана, достаточно кодировать только длину пути (path length) каждого элемента.

115 CS MSU Graphics & Media Lab (Video Group) Кодирование деревьев (Encoding of trees) 3. Для каждого блока – отдельное основное дерево: невыгодно кодировать заново лучше закодировать разницу между длиной пути в дереве первого блока и длиной пути в дереве следующего блока (для каждого элемента).

116 CS MSU Graphics & Media Lab (Video Group) Каждый элемент имеет длину пути от 0 до 16 включительно. Кодирование пути Сколько элементов имеют одинаковую длину пути ENCODING run length encoding один несколько Output Кодирование деревьев (Encoding of trees)

117 CS MSU Graphics & Media Lab (Video Group) Кодирование длины пути (диаграмма) CodeOperation 0-16Len[x] = (prev_len[x] + code) mod 17 17Zeroes = getbits(4) Len[x] = 0 for next (4 + Zeroes) elements 18Zeroes = getbits(5) Len[x] = 0 for next (20 + Zeroes) elements 19Same = getbits(1) Decode new Code Value = (prev_len[x] + Code) mod 17 Len[x] = Value for next (4 + Same) elements

118 CS MSU Graphics & Media Lab (Video Group) u Коды 0-16 применяются, если только один элемент имеет соответствующую длину пути. u Коды применяются для дополнительного преобразования Run-Length Encoding. В результате получаем 20 кодовых элементов, которые можно закодировать 5 битами. Но здесь также применяется оптимизация (вспомогательные деревья или pre-trees) Кодирование длины пути (пояснение)

119 CS MSU Graphics & Media Lab (Video Group) Сжатие деревьев при помощи вспомогательных деревьев 20 кодов основного дерева кодируются в зависимости от частоты их появления при помощи вспомогательного дерева (pre-tree). Структура самого вспомогательного дерева не кодируется и имеет фиксированный размер 80 бит (20 элементов по 4 бита).

120 CS MSU Graphics & Media Lab (Video Group) Вспомогательные деревья (pre-trees) Length of tree code 04 bits Length of tree code 14 bits Length of tree code 24 bits …… Length of tree code 184 bits Length of tree code 194 bits

121 CS MSU Graphics & Media Lab (Video Group) Задания u Задания по курсу расположены на странице курса: