| | | | | В | в | е | д | е | н | и | е | | в | | с | ж | а | т | и | е | | д | а | н | н | ы | х | : | | М | е | т | о | д | | с | ж | а | т | и | я | | Х | а | ф | ф | м | а | н | а | | и | | р | о | д | с | т | в | е | н | н | ы | е | | м | е | т | о | д | ы | . | | | | | |
| Арифметическое кодирование. Замещающие компрессоры. Семейство компрессоров |
| 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 | ] |
| |