| | | | В | в | е | д | е | н | и | е | | в | | с | ж | а | т | и | е | | д | а | н | н | ы | х | : | | М | е | т | о | д | | с | ж | а | т | и | я | | Х | а | ф | ф | м | а | н | а | | и | | р | о | д | с | т | в | е | н | н | ы | е | | м | е | т | о | д | ы | . | | | | | |
Арифметическое кодирование. Замещающие компрессоры. Семейство компрессоров |
LZ78. Семейство компрессоров LZ77 |
|
Написано Петером Гатманом ( | Peter Gutmann | ). |
|
| Метод сжатия Хаффмана и родственные методы | |
| Сжатие Хаффмана | - статистический метод сжатия, который уменьшает среднюю |
длину кодового слова для символов алфавита. Код Хаффмана является примером |
кода, оптимального в случае, когда все вероятности появления символов в |
сообщении - целые отрицательные степени двойки. Код Хаффмана может быть |
построен по следующему алгоритму: |
(1) Выписываем в ряд все символы алфавита в порядке возрастания или |
убывания вероятности их появления в тексте; |
(2) Последовательно объединяем два символа с наименьшими вероятностями |
появления в новый составной символ, вероятность появления которого полагается |
равной сумме вероятностей составляющих его символов; в конце концов мы |
построим дерево, каждый узел которого имеет суммарную вероятность всех узлов, |
находящихся ниже него; |
(3) Прослеживаем путь к каждому листу дерева помечая направление к каждому |
узлу (например, направо - 1, налево - 0). |
Для заданного распределения частот символов может существовать несколько |
возможных кодов Хаффмана. Возможно определить 'каноническое' дерево Хаффмана, |
выбрав одно из возможных деревьев. Такое кононическое дерево может быть очень |
компактно, передавая только длину в битах для каждого кодового слова. Такой |
метод используется в большинстве архиваторов (pkzip, lha, zoo, arj, ...). |
Родственным методом для кодирования Хаффмана является | кодирование | |
Шеннона-Фано | , которое осуществляется следующим образом: |
(1) Делим множество символов на два подмножества так, чтобы сумма |
вероятностей появления символов одного подмножества была примерно равна сумме |
вероятностей появления символов другого. Для левого подмножества каждому |
символу приписываем "0", для правого - "1". |
(2) Повторяем шаг (1) до тех пор, пока все подмножества не будут состоять |
из одного элемента. |
Алгоритм создания кода Хаффмана называется снизу-вверх, а Шеннона-Фано - |
сверху-вниз. Кодирование по Хаффману всегда дает оптимальные коды, по |
Шеннону-Фано иногда используется немного больше бит. |
[См. также | "Практическое кодирование по Хаффману" | ] |
|
| Арифметическое кодирование | |
Может показаться что кодирование Хаффмана или Шеннона-Фано лучшее средство |
для сжатия. Однако это не так. Как было замечено выше, эти методы оптимальны |
только в том случае, когда все символы в сообщении имеют вероятности появления |
равные целым отрицательным степеням двойки, что в общем случае не так. |
Метод | арифметического кодирования | не имеет этого ограничения: он достигает |
одинакового эффекта так как рассматривает сообщение как единое целое (что для |
кодирования по Хаффману потребовало бы нумерации каждого из всех возможных |
сообщений), и таким образом достигает теоретической энтропийной границы |
эффективности сжатия для любого источника. |
Работа арифметического кодера состоит в представлении числа интервалом |
вещественных чисел от 0 до 1. По мере увеличения длины сообщения, интервал, |
необходимый для его представления, становится все меньше и менье, а число бит, |
необходимых для задания этого интервала, увеличивается. Каждый символ собщения |
по порядку сокращает этот интервал пропорционально вероятности появления этого |
символа. Наиболее вероятный символ меньше всех сокращает интервал, и таким |
образом добавляет меньше бит к коду сообщения. |
|
1 Codewords |
+-----------+-----------+-----------+ /-----\ |
| |8/9 YY | Detail |<- 31/32 .11111 |
| +-----------+-----------+<- 15/16 .1111 |
| Y | | too small |<- 14/16 .1110 |
|2/3 | YX | for text |<- 6/8 .110 |
+-----------+-----------+-----------+ |
| | |16/27 XYY |<- 10/16 .1010 |
| | +-----------+ |
| | XY | | |
| | | XYX |<- 4/8 .100 |
| |4/9 | | |
| +-----------+-----------+ |
| | | | |
| X | | XXY |<- 3/8 .011 |
| | |8/27 | |
| | +-----------+ |
| | XX | | |
| | | |<- 1/4 .01 |
| | | XXX | |
| | | | |
|0 | | | |
+-----------+-----------+-----------+ |
В качестве примера арифметического кодирования рассмотрим пример, алфавит |
состоит из двух символов X и Y с вероятностями 0.66 и 0.33. Кодируя такое |
сообщение, посмотрим на первый символ: если это символ X, выбираем нижнюю |
часть, если же это символ Y, выбираем верхнюю часть. Продолжая таким образом |
для трех символов, мы получим кодовые слова, показанные справа от диаграммы |
наверху - они находятся путем отыскания соответствующей ячейки на интервале |
для конкретного набора символов и записи ее в виде двоичной дроби. На |
практике, необходимо добавить специальный символ "конец данных", не |
представленный в этом простом примере. |
В этом примере арифметический код не полностью эффективен, по причине |
сжатия короткого сообщения - на длинных сообщениях эффективность кодирования |
реально приближается к 100%. |
Теперь когда у нас есть эффективный метод кодирования, что мы можем сделать |
с ним ? То что нам надо - метод построения модели данных, которую мы можем |
затем использовать вместе с кодером. Простейшей моделью, например, является |
фиксированная таблица вероятностей стандартных букв ангийского текста, которую |
мы можем использовать для получения вероятностей букв. Улучшением этого метода |
является использование | адаптивной модели | , другими словами, модели, которая для |
сжатия последующих данных приспосабливает себя по уже сжатым данным. Мы можем |
преобразовать фиксированную модель в адаптивную изменяя вероятности символов |
после кодирования каждого нового символа. Однако, мы можем зделать больше, чем |
это. |
Использование вероятностей символов по отдельности - не совсем хорошая |
оценка для энтропии данных: мы можем также использовать вероятности сочетаний |
символов. Лучшие из известных на сей момент компрессоры, использующие этот |
подход: DMC (Dynamic Markov Coding) начинает работу с марковской модели |
0-порядка и постепенно расширяет начальную модель в процессе сжатия; PPM |
(Prediction by Partial Matching), ищет появления сжимаемого текста в контексте |
n-го порядка. Оба метода таким образом получают более лучшую модель сжимаемых |
данных, и в сочетании с арифметическим кодированием, приводят к лучшей степени |
сжатия. |
Итак, если кодеры, основанные на арифметическом кодировании, так хороши, |
почему они не используются широко ? Не считая того, что они относительно новы |
и не успели войти в повсеместное использование, есть еще один существенный |
недостаток: они требуют гораздо больше вычислительных ресурсов, как ресурсов |
процессора, так и памяти. Построение сложных моделей для сжатия может не |
закончится из-за нехватки памяти (особенно в случае DMC, когда модель может |
неограниченно расти); и само арифметическое кодирование требует решения |
числовых задач большого объема. Однако существуют альтернативные способы, - |
класс компрессоров обычно называемых | замещающими | или | словарными компрессорами | . |
|
| Замещающие компрессоры | |
Основная идея, используемая в замещающих компрессорах состоит в замене |
появления определенной фразы или группы байт во фрагменте данных ссылкой на |
предыдущее появление этой фразы. Существуют два основных класса методов, |
названных в честь Якоба Зива (Jakob Ziv) и Абрахама Лемпеля (Abraham Lempel), |
впервые предложивших их в | 1977 | и | 1978 | . |
|
| Семейство компрессоров LZ78 | |
Методы LZ78 помещают фразы в | словарь | и затем, при повторном появлении |
определенной фразы, заменяют эту фразу ее индексом в словаре. Существует |
несколько алгоритмов сжатия, основанных на этом принципе, различающихся |
главным образом в способе ведения словаря. Наиболее известным методом (в |
действительности, наиболее известным среди всех компресоров Лемпеля-Зива, |
зачастую (ошибочно) называемым как "Сжатие Лемпеля-Зива") является метод LZW |
Терри Уэлча (Terry Welch), предложенный в | 1984 | для реализации в аппаратуре |
высокопроизводительных дисковых контроллеров. |
|
Входная строка: /WED/WE/WEE/WEB |
Символ на входе: Код на выходе: Новый код и соответ. строка |
/W / 256 = /W |
E W 257 = WE |
D E 258 = ED |
/ D 259 = D/ |
WE 256 260 = /WE |
/ E 261 = E/ |
WEE 260 262 = /WEE |
/W 261 263 = E/W |
EB 257 264 = WEB |
<END> B |
|
LZW работает со словарем объемом 4K, в котором входы 0-255 указывают на |
отдельные байты, а входы 256-4095 указывают на подстроки. Каждый раз как |
разбирается новая подсрока, генерируется новый код. Новые подсроки образуются |
добавлением текущего символа K к концу текущей строки w. Алгоритм сжатия LZW |
таков: |
set w = NIL |
loop |
read a character K |
if wK exists in the dictionary |
w = wK |
else |
output the code for w |
add wK to the string table |
w = K |
endloop |
Пример выполнения LZW на (очень избыточной) входной строке можно посмотреть |
на диаграмме наверху. Подстроки строятся символ за символом начиная с кода |
256. Алгоритм LZW разжатия получает на вход поток кодов и использует их для |
точного воспроизведения оригинальных данных. Также как и алгоритм сжатия, |
расжиматель добавляет новые подстроки в словарь каждый раз, когда считывает |
новый код. Все, что ему требуется делать в добавок - преобразовать каждый |
поступающий код в строку и вывести ее на выход. Пример работы LZW |
декомпрессора показан ниже. |
|
Входня строка: /WED<256>E<260><261><257>B |
Код на входе: Подстр. на выходе Новый код и соответ. подстрока: |
/ / |
W W 256 = /W |
E E 257 = WE |
D D 258 = ED |
256 /W 259 = D/ |
E E 260 = /WE |
260 /WE 261 = E/ |
261 E/ 262 = /WEE |
257 WE 263 = E/W |
B B 264 = WEB |
Наиболее замечательным свойством этого типа сжатия является то, что весь |
словарь передается декодеру неявно. По окончании выполнения, декодер будет |
иметь словарь идентичный имеющемуся у кодера и полностью построенный как часть |
процесса декодирования. |
Сегодня LZW чаще встречается в варианте, известном как LZC, после его |
использования в UNIX программе "compress". В этом варианте указатели не имеют |
фиксированной длинны. В начале работы длина равна 9 битам, а затем |
увеличивается до максимально возможного значения по мере использования всех |
указателей предыдущей длинны. Кроме того, словарь не фиксируется при его |
заполнении как в LZW - программа непрерывно отслеживает степень сжатия, и как |
только она начинает уменьшаться, словарь целиком опорожняется и создается |
заново из небольшого фрагмента входного потока. Более новые методы используют |
некотрые модификации LRU алгоритма для уничтожения менее используемых подстрок |
по заполнении словаря вместо его полного опорожнения. |
Наконец, не все методы строят словарь добавлением одного символа к концу |
текущей подстроки. Альтернативным способом является объединение двух |
предыдущих подстрок (LZMW), который приводит к более быстрому построению более |
длинных подстрок, чем построение символ за символом в других методах. |
Недостатком этого метода является то, что более сложные структуры данных |
необходимы для хранения словаря. |
[Хорошим введением в LZW, MW, AP и Y кодировнаие дается в пакете yabba. См. |
ftp-ссылку в | [2] | , расширение .Y] |
|
| Семейство компрессоров LZ77 | |
Методы LZ77 отслеживают последние обработанные n байт данных, и когда |
встречается фраза, которая уже была, вместо нее выдается пара значений, |
соответствующая позиции фразы в буфере предыстории и длине фразы. В сущности, |
компрессор передвигает | окно | фиксированного размера по потоку данных (в |
основном называемое | скользящим окном | ), и позиция в паре (позиция, длина) |
обозначает позицию фразы внутри этого окна. Наиболее используемые алгоритмы |
происходят от метода LZSS, описанного Джеймсом Сторером (James Storer) и |
Томасом Шимански (Thomas Szymanski) в | 1982 | . В этом копрессоре используется |
окно размером N байт и | буфер предпросмотра | , содержимое которого ищется в окне: |
while( lookAheadBuffer not empty ) |
{ |
get a pointer ( position, match ) to the longest match in the window |
for the lookahead buffer; |
|
if( length > MINIMUM_MATCH_LENGTH ) |
{ |
output a ( position, length ) pair; |
shift the window length characters along; |
} |
else |
{ |
output the first character in the lookahead buffer; |
shift the window 1 character along; |
} |
} |
Расжатие просто и быстро: Если встречается пара (позиция, длина), на выход |
копируется (длина) байт из окна начиная с позиции (позиция). |
Методы, использующие "скользящее окно", могут быть упрощены нумеруя входной |
текст по модулю N, создавая таким образом кольцевой буфер. "Скользящее окно" |
автоматически создает LRU эффект, который должен быть явно реализован в LZ78 |
методах. Варианты этого метода применяют дополнительное сжатие выхода LZSS |
компрессора, включая простой код переменной длинны (LZB), динамическое |
кодирование Хаффмана (LZH), и кодирование Шеннона-Фано (ZIP 1.x)), все они |
дают некоторый выигрыш по сравнению с основной схемой, особенно когда данные |
несколько случайны и комрпессор LZSS дает небольшой эффект. |
Позднее был изобретен алгоритм, комбинирующий идеи LZ77 и LZ78, и |
называемый LZFG. LZFG использует стандартное "скользящее окно", но хранит |
данные в модифицированной древовидной структуре данных и выдает в качестве |
кода позицию текста в дереве. Т.к. LZFG только вставляет целые | фразы | в |
словарь, он должен работать быстрее любого другого компрессора LZ77. |
Все популярные архиваторы (arj, lha, zip, zoo) являются вариациями на тему |
LZ77. |
[ Учебник по некторым алгоритмам сжатия доступен на | www.cs.sfu.ca | ] |
|