Алгоритмы и структуры данных
(A.Иванов)
Сжатие данных
Владимир Витальевич Борисенко
http://mech.math.msu.su/~vvb/
Сжатие данных
-- без потери точности
-- с возможной потерей точности
(передается основная информация с потерей
незначительных деталей). Используется
для кодирования изображений, видео и
аудио информации.
Сжатие без потери информации
-- RLE
-- Коды Хаффмана
-- статические
-- динамические (адаптивный алгоритм)
-- Арифметическое кодирование
-- Алгоритмы сжатия из группы LZ
(LZ77, LZW, ...)
Сжатие изображений с потерей (JPEG),
аудио-информации, видео...
Алгоритм кодирования RLE
Run Length Encoding
aaaaaaaaaabbbbwwwwcddddddaaaaaaaa l = 33
В некоторых изображениях, когда используется
палитра с ограниченным количеством цветов --
черно-белые изображения, рисованных мультфильмах,
a 10 b 4 w 4 c 1 d 6 a 8 l = 12
байт, число повторений байта 0.255
Недостаток -- если бегущих подпоследовательностей
нет, то размер исходных данных
не уменьшается, а, наоборот,
увеличивается в 2 раза
abcdcba len = 7
a 1 b 1 c 1 d 1 c 1 b 1 a 1 len = 14
Способ 1
для постоянной подпоследовательности
в качестве начального символа использовать
сам кодируемый символ. Дальше он повторяется
(записывается дважды) и потом идет байт-множитель.
Пример:
aaabcdecccccbbbfggggh
aa3bcdecc5bb3fgg4h
ccccc bcde
cc5 bcde
Способ 2 для байтовой последовательности
Каждая подпоследовательность кодируется двумя
элементами:
(1) байт-префикс, (2) байт или
последовательность байтов
Байт-префикс для постоянной подпоследовательности
состоит из битов
0xxxxxxx
где xxxxxxx -- число повторений символа,
и дальше идет сам повторяющийся байт. Число повторений
не превосходит 127.
Байт-префикс для непостоянной подпоследовательности
состоит из битов
1xxxxxxx
где xxxxxxx задает длину подпоследовательности
без повторений. После идет сама подпоследовательность
указанной длины.
Пример:
aaaaabcdefgggggggggg len = 20
-----=====----------
5 5 10
00000101 a 10000101 bcdef 00001010 g
5 a 132 bcdef 10 g len = 6
В самом плохом случае, когда нет бегущих
подпоследовательностей, величина сообщения
увеличивается на множитель 128/127
Также можно использовать битовый алгоритм сжатия RLE
Здесь мы не представляем информацию в виде байтов,
а рассматриваем последовательность битов:
11010110001011111000000000111010101010...
--===--===--=====---------===---------
Идея -- кодировать повторяющиеся биты.
Последовательность из повторяющихся нулей кодируется
префикс 00xxxxxx, где xxxxxx -- число повторений
0..63 бита 0
(второй байт не используется!)
Последовательность из повторяющихся единиц кодируется
аналогично:
префикс 01xxxxxx, где xxxxxx -- число повторений
0..63 бита 1
Последовательность из неповторяющихся битов кодируется
так:
префикс 1xxxxxxx, где xxxxxx -- число 0..127
неповторящихся битов
и дальше все неповторющиеся биты:
В примере
11010110001011111000000000111010101010...
11 010 11 000
01000010 10000011 010 01000010 00000011
10 11111 000000000 111
10000010 01000101 00001001 01000011
010101010
10001001
Максимальная степень сжатия 63/8 ~= 8
В частности, RLE-алгоритм используется в
формате изображений PCX и некоторых других.
Кодирование Хафмана (Huffman Encoding)
======================================
Пусть у нас есть некоторый алфавит, или
набор элементарных сообщений
A = {a1, a2, ..., a_n}
Мы кодируем каждую букву двоичным кодом
C = {c1, c2, ..., c_n}
используя префиксный код (prefix free code).
Код одной буквы не может быть началом другой буквы:
a 101 b 101001 -- такой ситуации не может
=== быть.
Мы хотим построить префиксный код, который
минимизирует длину закодированного соббщения.
Пусть известны вероятности появления букв
в исходном сообщении
P(a1) = p1, P(a2) = p2, ..., P(a_n) = p_n.
Код Хаффмана строится на основе этих вероятностей.
Кодовое дерево
Упрядочиваем листья, соответствующие буквам
алфавита, по возрастанию их вероятностей.
Объединяем два самых редких узла, добавляя
корневой узел, в дерево из трех узлов.
Корень построенного дерева имеет вероятность,
равную сумме вероятностей двух сыновей.
Эти два узла удаляем из массива и добавляем в него
построенное дерево. Далее, упорядочиваем полученный
массив деревьев по возрастанию их вероятностей.
Повторяем процесс, пока в массиве не останется только
1 элемент -- это и будет статическое дерево кодов
Хаффмана.
Адаптивный алгоритм кодирования Хаффмана
========================================
По мере чтения исходного потока букв мы перестраиваем
дерево кодов Хаффмана так, чтобы оно отражало частоты
букв в обработанной части сообщения. По мере построения
кодового дерева мы выдаем закодированную
последовательность битов, т.е. мы одновременно
строим кодовое дерево и кодируем сообщение.
Получив из входного потока очередной исходный символ,
мы кодируем его с помощью уже построенного
кодового дерева. После этого мы изменяем кодовое дерево
в соответствии с измененными вероятностями после
получения этого исходного символа.
Получили символ -- закодировали его,
используя построенное ранее
кодовое дерево, и выдали
в выходной поток;
-- перестроили дерево с учетом
изменения частоты обработанного
символа.
Есть 2 алгоритма перестроения дерева Хаффмана:
1) алгоритм FGK, названный по фамилиям его авторов
Faller-Gallager-Knuth;
2) более современный и более удачный алгоритм
Vitter'а. Мы будем рассматривать
именно его.
В обоих алгоритмах используется специальный узел NYT
(или нулевой узел), с помощью которого в дерево
добавляются новые буквы.
NYT -- Not Yet Transmitted
Вероятность этого узла равна 0.
(Вместо вероятностей мы используем количество
вхождений буквы в исходное сообщение, т.е. целое число.)
Соглашение:
терминальные узлы дерева будем называть листьями leafs
и изображать квадратами;
внутренние узлы (intermediate nodes) будем изображать
кружками.
Новые буквы добавляются в дерево через узел NYT,
когда еще не все буквы алфавита присутствуют в
кодовом дереве. Узел NYT как бы изображает все
буквы, еще не поступившие на вход алгоритма,
поэтому сумма их частот всё еще равна нулю,
так что частота узла NYT равна нулю:
/
+-----+
| NYT |
| 0 |
+-----+
Когда поступает новая буква, например, буква S,
узел NYT заменяется на поддерево
/
/-----\
| 1 |
\-----/
/ \
+-----+ /-----\
| NYT | | S |
| 0 | | 1 |
+-----+ \-----/
И затем выполняется алгоритм перестроения дерева.
Адаптивное дерево в алгоритма Виттера
удовлетворяет следующим трем условиям:
(1) вероятность внутреннего узла равна сумме
вероятностей его сыновей (внутренний узел
всегда имеет ровно 2-х сыновей);
(2) если просматривать узлы дерева снизу-вверх и
слева направо, то вероятности узлов нестрого
возрастают;
(3) узлы-листья предшествуют промежуточным узлам
с той же вероятностью.
Вместо вероятностей в адаптавном дереве Хаффмана
хранятся частоты символов, т.е. для каждого символа
число его вхождений в просмотренную часть исходного
сообщения (целые числа).
Будем называть блоком подряд идущие узлы
одного и того же типа и с равной частотой.
Старший элемент блока -- самый правый (последний)
элемент блока. При упорядочивании узлов дерева
снизу-вверх -- слева направо блоки также
упорядочиваются. Блок из узлов-листьев всегда
предшествует блоку из внутренних узлов с той же
частой. Рассмотрит для примера следующее дерево:
7
/ \
3A 5
/ \
2B 2
/ \
0 2R
Самый левый узел с нулевой частотой -- это NYT.
Блоки в этом дереве -- это блок NYT
0,
блок листьев R, B с частотой 2
2R, 2B,
блок из одного внутреннего узла с частотой 2
2,
блок из одного листа A с частотой 3
3A,
блок из внутреннего узла
5
и блок из внутреннего узла
7
(корень дерева).
Идея алгоритма Виттера -- при добавлении новой буквы
или считывании буквы, которая уже есть в дереве,
мы перестраиваем дерево так, что чтобы выполнялись
все три указанные свойства. Перестроение осуществляется
следующим образом:
(1) сначала при необходимости узел перемещается
в своем блоке на лидирующую позицию --
максимально вправо -- путем перемещения
("скольжения") этого узла вправо;
"скольжением" называется перемещение
узла вправо путем многократного
последовательного обмена узла с его
очередным правым соседом;
(2) и затем выполняется процедура, которую
Виттер назвал SlideAndIncrement(p), где p --
ссылка на узел, частота которого увеличивается
на единицу. Название можно перевести как
"скольжение и увеличение". Перемещаемый узел
всегда изначально является лидирующим
(самым правым) в своем блоке. Рассматриваются
две ситуации.
(i) Узел p является листом, и следующий
блок состоит из внутренних узлов
с той же частотой, например,
4A, 4B, 4C, 4, 4, 4, 4
p
(ii) Узел p внутренний и следующий блок
состоит из листьев с частотой,
на единицу большей, например,
8, 8, 9A, 9B, 9C, 9D
p
В случае (i) узел p скользит вправо,
на каждом шаге обмениваясь с соседним правым
узлом (и его поддеревом), в результате
он в конце-концов становится на лидирующую
позицию в следующем блоке,
4A, 4B, 4C, 4, 4, 4, 4
p ----------^
а элементы следующего блока сдвигаются
на одну позицию влево:
4A, 4B, 4, 4, 4, 4, 4C
p
Затем частота узла p увеличивается на единицу:
4A, 4B, 4, 4, 4, 4, 5C
p
После этого указатель p перемещается к
родительскому узлу для p, и процедура
исправления повторяется для родительского узла,
пока мы не дойдем до корня дерева.
^p
|
4A, 4B, 4, 4, 4, 4, 5C
В случае (ii)
8, 8, 9A, 9B, 9C, 9D
p --------------^
узел p также скользит вправо, в результате
чего он в становится на лидирующую
позицию в следующем блоке
8, 9A, 9B, 9C, 9D, 8
p
Затем частота узла p увеличивается на единицу.
8, 9A, 9B, 9C, 9D, 9
p
После этого алгоритм переходит к исправлению
родительского узла для исходной позиции
узла p, т.е. в данном примере для новой
позиции узла 9A.
^p
|
8, 9A, 9B, 9C, 9D, 9
Для примера, закодируем сообщение
BARBARA
с помощью адаптивного алгоритма Виттера.
Adding B output: B
B
1
/ \
0 1B
Adding A output: B 0 A
B A
2 2
/ \ / \
1 1B Slide 1 --> 1B 1B 1
/ \ / \
0 1A 0 1A
Adding R output: B 0 A 10 R
B A R
3
/ \ 3
1B 2 Slide 1 --> 1B / \
/ \ 1 2
1 1A / \ / \
/ \ 0 1R 1A 1B
0 1R
Adding B output: B 0 A 10 R 11
B A R B
3 3
/ \ Slide 1B --> 1 / \
1 2 1B 2
/ \ / \ ^^ / \
0 1R 1A 1B 1A 1
^^ / \
0 1R
4
increment / \
1B 2B 2
^^ / \
1A 1
/ \
0 1R
Adding A output: B 0 A 10 R 11 10
B A R B A
4 4
/ \ / \
2B 2 2B 2
/ \ Slide 1A --> 1 / \
1A 1 1 1A
^^ / \ / \ ^^
0 1R 0 1R
5
/ \
increment 1A 2B 3
/ \
1 2A
/ \ ^^
0 1R
Adding R output: B 0 A 10 R 11 10 101
BARBAR B A R B A R
5 5
/ \ / \
>>> 2B 3 >>> 1 4
/ \ Slide 1 ---> 2B / \ / \
>>> 1 2A 0 2R 2A 2B
/ \ ^^
0 2R
6
increment 1 / \
>>> 2 4
/ \ / \
0 2R 2A 2B
Adding A output: B 0 A 10 R 11 10 101 10
BARBARA B A R B A R A
6 6
/ \ Slide to leader / \
2 4 2A ---> 2B 2 4
/ \ / \ / \ / \
0 2R 2A 2B 0 2R 2B 2A
^^ ^^
6
Slide 2A ---> 2 / \
2A 4
^^ / \
2B 2
/ \
0 2R
7
/ \
increment 2A 3A 4
^^ / \
2B 2
/ \
0 2R
Final result: B 0 A 10 R 11 10 101 10
Code length: 8 + 1 + 8 + 2 + 8 + 2 + 2 + 3 + 2 = 36 bit
Initial length: 8*7 = 56 bit