PreScriptum: Хоть это и не посвящено вирмейкерству, но кодерство
и вирмейкерство связанно, поэтому в целях всеобщего повышения уровня
образования представляю вам эту статейку :)
В общем, когда я еще начинал вирмейкерствовать,я долго думал как же работают
архиваторы. Долго думал и ничего умнее не придумал как купить книжку под
названием "Форматы Графических Файлов". Как ни странно там оказалось вполне
достаточно для понимания LZW,Хаффмана,RLE и арифметического сжатия.
Потом увидел Win32.LZSlow (SMT/SMF) и увидел что там не LZW,хотя и стоит
LZ :)
В общем решил разобраться. Полазил по инету и нашел кое что,чем хочу с вами
поделится.
Оглавление
1. Сжатие основанное на словарях
a. LZ77
b. LZSS
c. LZ78
d. LZW
2. На различности длины кода
a. Деревья Шано-Фаннона
b. Деревья Хафмана
4. Сжатие повторяющихся величин (RLE)
a. Basic RLE
b. PackBits
Арифметическое сжатие тут не рассматривается так как довольно сложное в
понимании, и очень трудно реализуемое на практике.
1. Сжатие основанное на словарях
Этот тип сжатия использует некоторую область памяти как словарь. Общий принцип
заменять длинные последовательности на более короткие величины.
A. LZ77
Принцип сжатия
Упаковщик ищет внутри окна (некоторой ограниченной области) наиболее длинную
последовательность совпадающюю с данными упаковываемыми на текущей позиции
и пишит на выход указатель на найденную последовательность и один байт
содержащий кол-во совпавших байт. Так как возможно что не попадется такая
последовательность, нельзя просто послать в выходной поток нулевой указатель
и нулевую длину. LZ77 решает это просто: после каждого указателя он выдает
первый символ в буффере после совпавшей последовательности и иначе выдает
нулевой указатель и символ в текущей позиции. Вобщем на выход подается
указатель на последовательность,длина последовательности и доп. символ.
Алгоритм сжатия:
1. Установим позицию сжатия на входной поток
2. Найдем наиболее длинную последовательность в окне сжатия
3. Посылаем на вывод пару (P,C) с следующими значениями
P - указатель на последовательность которая совпала
C - первый символ который не совпал
4. Если еще есть данные то передвигаем окно сжатия на 1 вперед и
прыгаем на 2.
Пример сжатия:
Pos 123456789
Char AABCBBABC
Шаг Позиция Совпадение Символ Вывод
1 1 -- A (0,0)A
2 2 A B (1,1)B
3 4 -- C (0,0)C
4 5 B B (2,1)B
5 7 AB C (5,2)C
Распаковка:
Читаем пару (P,C) Пишим последовательность из P и символ C.
Практические замечания:
Уровень сжатия очень неплохой для многих типов данный, но сжатие довольно
требовательное к ресурсам системы,а значит и ко времени. С другой строны
распаковка очень проста и очень быстрая. Использование памяти минимальны.
B. LZSS
Различия с LZ77
LZ77 если не находит последовательности которая удовлетворяет условиям,
пересылает сам символ после каждого указазателя. Это решение содержит
избыточность или лишние символы будут использоватся при след. сравнении.
LZSS решает эту проблему иначе - указатель посылается в выходной поток если
длина совпавшей последовательности > чем длина самого указателя. Естественно
придется использовать доп. бит для определения есть ли указатель или нет
Алгоритм сжатия
1. Устанавливаем позицию на начало сжимаемых данных
2. Найдем наиболее длинную последовательность в окне которая совпадает
с данными на текущей позиции
* P := указатель на данную последовательность
* L := Длина последовательности
3. L >= MIN_LENGTH ?
* Да. Выдаем на выход (P,L) и сдвигаем текущию позицию
сжатия на L символов
* Нет. Посылаем на выход текущий символ и сдвигаем позицию
сжатия на 1.
4. Если еще есть данные,то идем на 2
Пример
Pos 1234567890
Char AABBCBBAAB
Шаг Позиция Совпадение Выход
1 1 -- A
2 2 A A
3 3 -- B
4 4 B B
5 5 -- C
6 6 BB (3,2)
7 8 AAB (7,3)
Распаковка
Окно движится по сжатым данным также как и при упаковке,проверяет что сейчас
идет - символ или указатель на символы и в соответствии с данной информацией
распаковывает код.
Сравнение с LZ77
Алгоритм сжимает данные лучше чем LZ77 примерно с аналогичными требованиями к
процессору и памяти. Распаковка также проста и быстра как и для LZ77.
Реализации
Данный принцип используется почти во всех известных архиваторах (PkZip,ARJ,
LHArc,ZOO,и тд). Конечно каждый архиватор реализует метод по своему.
LZSS можно удачно скомбинировать с методами сжатия основанными на переменной
длине кода (Хаффман,Шано-Фаннон),например PkZip v.1.0 использовал LZSS в
комбинации с сжатием Шано-Фаннона,а ARJ с Хаффманом (последние версии PkZip
пакуют Хаффманом)
C. LZ78
Сжатие
В начале сжатия словарь пуст. Для того что бы обьяснить принцип сжатия,
представим что словарь уже содержит некоторые строки.
У нас есть строка нулевой длины. Мы берем символ из входного потока добавляем
его к строке. Ищем данную строку в нашем словаре. Если строка уже имеется, то
добавляем к строке следующий символ и тд. Предположим мы достигли того момента
когда строки нет. Пускай P - строка без последнего добавленного символа,а
C - последний добавленный символ. Тогда мы посылаем в выходной поток код
соответсвующий строке P и символ C,и добавляем P+C в словарь.
Если словарь пуст то на выход посылаем 0 и символ C.
Алгоритм сжатия
1. Делаем словарь пустым, P - пустая строка
2. C := следующий символ в потоке
3. P+C есть в словаре ?
a. Есть. P := P+C
b. Нет
i. Посылаем два обьекта на выход
* Код отвечающий строке P в словере или 0
* Символ С,в таком же виде как он в входном потоке
ii. Добавляем строку P+C в словарь
iii. Очищаем P
4. Есть еще символы для сжатия ?
a. Есть. Прыжок на 2
b. Нет
i. Если P - не пустая строка,посылаем на выход
P
ii. Конец
Распаковка
В начале словарь пуст. Читаем пару - код(K) и символ(C). P := строка из словаря
соответствующая коду(K). Выкидываем на выход P+C и добавляем в словарь P+C.
Алгоритм распаковки
1. Словарь пуст
2. W := следующий код
3. C := символ следующий за ним
4. Посылаем на выход строку.W (может быть пустой) и символ C
5. Добавляем строку.W+C в словарь
6. Есть еще данные ?
i. Да. На 2
ii. Нет. Конец
Пример
Pos 123456789
Char ABBCBCABA
Шаг Позиция Словарь Выход
1 1 A (0,A)
2 2 B (0,B)
3 3 BC (2,C)
4 5 BCA (3,A)
5 8 BA (2,A)
Заключение
Наибольшее преимущество перед LZ77 - уменьшилось кол-во сравнений строк на
каждом шаге сжатия. Степень сжатия примерно аналогична LZ77.
D. LZW
В этом алгоритме используется аналогичны принцип LZ78 со следующим добавлением
* В начальном словаре содержатся все символы от 0-255 (8бит)
Отличия в сжатии
* Только кодовые слова идут на выход. Это значит словарь должен быть
заполнен при старте начальными значениями.
* Так как все возможные односимвольные строки уже в словаре,то в каждом
цикле сжатия используется однобайтовый префикс.Строка которая ищется в словаре
имеет минимум 2 байта.
* Алгоритм сделан так,что словарь при распаковке реконструируется без
лишних данных в потоке.
Алгоритм сжатия
1. В начале словарь содержит все возможные корни (256 символов) и строка
P - пуста
2. C := следующий символ в входном потоке
3. Строка P+C находится в словаре ?
a. Если да,то P := P+C
b. Нет
i. Выдаем на выход код соответствующий строке P
ii. Добавляем P+C в словарь
iii. P := C (P содержит один символ C)
4. Есть еще данные ?
a. Да. На 2
b. Нет.
i. Выдаем на выход код для P
ii. The End
Принцип распаковки
В начале слоарь содержит теже 256 символов.
Предположим что словарь содержит дополнительно несколько не однобайтовых
строк. Алгоритм запоминает предидущее кодовое слово (pW) и читает текущее
кодовое слово(cW), посылает на выход строку соответствующюю cW. Потом
добавляет в словарь строку.pW+первый символ строки.cW. Сосбственно это и был
дополнительный символ из LZ78. Следуя принципу, создание словаря при распаковке
всегда на один шаг раньше чем создание словаря при упаковке.
Особенный случай происходит когда cW не содержится в словаре. Это может
случится потому что создание словаря при распаковке немного отстало от словаря
при упаковке,причина - когда алгоритм сжатия читает строку которая только-что
была добавлена в словарь. Во время распаковки данная строка еще не присутсвует
в словаре. Решение простое: если строка не существует, то берем первый символ
предидущей строки и добавляем к оной этот символ,записываем получившиеся в
словарь и на выход.
Алгоритм распаковки:
1. В начале словарь содержит все корни (256 символов)
2. cW := Первый код в потоке
3. Посылаем на выход строку.cW
4. pW := cW
5. cW := след. код в потоке
6. Строка.cW есть в словаре ?
* Есть.
i. Посылаем на выход строку.cW
ii. P := строка.pW
iii. C := Первый символ строки cW
iv. Запишем строку P+C в словарь
* Нет
i. P := Строка.pW
ii. C := первый символ строки.pW
ii. Подаем на выход строку P+C и добавляем ее
в словарь
7. Есть еще данные ?
* Да. На 4
* Нет. The End
Пример
Сжатие
Pos 123456789
Char ABBABABAC
Начальный словарь: 123
ABC
Шаг Позиция Словарь Выход
1 1 (4)AB (1)
2 2 (5)BB (2)
3 3 (6)BA (2)
4 4 (7)ABA (4)
5 6 (8)ABAC (7)
6 -- -- (3)
Распаковка
Шаг Код Выход Словарь
1 (1) A --
2 (2) B (4)AB
3 (2) B (5)BB
4 (4) AB (6)BA
5 (7) ABA (7)ABA
6 (3) C (8)ABAC
Исследуем шаг 4. Предыдущий код (2) сохранен в pW и cW содержит 4.
Строка.cW содержит "AB". Строка.pW содержит "B". Расширенная первым
символом строки.cW в словарь добавляется "BA" с индексом (6).
Идем на 5 шаг. Содержимое cW = (4) копируется в pW и новое значение
cW берется из потока. В словаре 7-го элемента еще нет,значит мы берем
строку.pW ("AB"),добавляем к ней первый символ оной строки ("A") и
получаем "ABA" которую собственно и сохраняем в словаре и подаем на
выход.
Практические замечания
Этот метод очень популярен на практике. Преимуществе перед всеми
LZ-основанными алгоритмами в скорости,так как не надо производить множество
сравнений строк. Другие улучшения,такие как различная длина кода в зависимости
от размера словаря,удаления лишних строк и тд,только улучшают сжатие.
Данный метод запатентован компанией Unisys, но она разрешает свободное
использование алгоритма в некоммерческих целях. Интересно - Е.Рошаль использовал
LZW :) ?
2. Сжатие основанное на различности длины кода
Основная идея сжатия - для наиболее встречающихся символов пишем более короткие
коды и для менее встречающихся более длинные. Недостаток данных методов-
приходится сохранять древовидную структуру при упаковке,в результате чего
мелкие фалы становятся намного больше.
a. Сжатие Шано-Фаннона
Алгоритм:
I. Сортируем символы в порядке возрастания
II. Делим их на две части
III.Первой части присваиваем 0 и второй части 1
IV. Идем к шагу II,рекурсивно деля получившиеся части до тех
пор,пока в обеих частях не останется по 1 элементу
Пример: (символы отсортированны в порядке убывания)
Дерево Код
a-\_____/-0 00
b-/ 0 \-1 01
c-\ ______/-0 100
d-| / 0 \-1 101
e-\____/ ____/-0 1100
f-/ 1 \__/ 0 \-1 1101
g-| 1 \____/-0 1110
h-/ 1 \-1 1111
Распаковка проста. Берем бит. Смотрим по дереву куда идти. Так повторяем
до конца ветви. Записываем символ соответствующий данной ветви. И так
снова пока не достигнем конца распаковываемых данных.
b. Сжатие Хаффмана
В общем очень похоже на сжатие по Шано-Фаннону,однако есть конструктивные
различия.
Принцип сжатия:
1. Получаем информацию о степени встречаемости того или иного символа.
2. Строим дерево в соответствии с полученной информацией
3. Для каждого символа из входного потока пишем соответствующий ему
код
Пример
abbbcccddeeeeeeeeef
Частота появления: a:1,b:3,c:3,d:2,e:9,f:1
Дерево:
0/\1
/ (e)
/\1
0/ \
/ 0/\1
/ (b) (c)
0/\1
/ \
(d) 0/\1
(a) (f)
Собственно сам упакованный код:
a = 0010
b = 010
c = 011
d = 000
e = 1
f = 0011
Распаковка аналогично деревьям Шано-Фаннона.
4. Сжатие повторяющихся величин (RLE)
Данный принцип сжатия основан на избыточности данных: вместо aaaa можно
написать 4a :)
1. Basic RLE
Вообще шаровой метод. Какой-то байт используется как идентификатор.
Для пример он = 0. Тогда после этого байта можно написать число повт. символов,
а после числа сам символ. Так как длина не может = 0,то собственно число
(длина) = 0 не определено,след. можно использовать его для замещения самого 0.
Пример:
abbcbaaaaacb(0)(0)(0)(0)a(0)a
(x) - байт с x-ым значением
Упакованное: a (0)(2)b cb (0)(5)a cb (0)(4)(0) a (0)(0) a
2. PackBits
Собственно данный принцип RLE предложила Apple в 198? году.
У нас есть байт с содержимым X. Если X>127 (бит 7 установлен), то за
байтом следует 1 байт который повторяется X-128 раз. Если бит не установлен
то за байтом следует X байт,с которыми ничего сделать нельзя.
Пример:
aaabcbdfaaabbbccc
(128+3)a (5)bcbdf (128+3)a (128+3)b (128+3)c
Заключение патолого-анатома :)
1. Зачем раскидываться лишними битами ? В выходной поток пишем то кол-во
бит которое нам на текущий момент необходимо.
2. Хафман и Шано-Фаанон плохи для мелких файлов (я так и не придумал что
делать с деревом - оно получается довольно обьемное,а ведь его сохранять
нужно.)
3. Как я не пытался Хаффмана сделать, сжатия у меня никогда не выходило :( )
файлы процентов на 5 становились больше. Видимо дерево неправильно строю.
Может кто-то поделится оптимальным построением ?
Вот так вот. Замечания и предложения пишите на [email protected]
P.S. В приложении есть пример немного тормознутого LZ78,и вполне работающих
PackBits упаковщика/распаковщика и LZ77.
Deviator/HAZARD.
|
