Примеры алгоритмы архивации и сжатия информации с применением различных программных средств

Основным критерием различия между алгоритмами сжатия наличие или отсутствие потерь. В общем случае алгоритмы сжатия без потерь универсальны в том смысле, что их применение безусловно возможно для данных любого типа, в то время как возможность применения сжатия с потерями должна быть обоснована.

Различные алгоритмы могут требовать различного количества ресурсов вычислительной системы, на которых они реализованы:

• — оперативной памяти (под промежуточные данные);
• — постоянной памяти (под код программы и константы);
• — процессорного времени.

В целом, эти требования зависят от сложности и «интеллектуальности» алгоритма. Общая тенденция такова: чем эффективнее и универсальнее алгоритм, тем большие требования к вычислительным ресурсам он предъявляет. Тем не менее, в специфических случаях простые и компактные алгоритмы могут работать не хуже сложных и универсальных.

Так как алгоритмы сжатия и восстановления работают в паре, имеет значение соотношение системных требований к ним. Нередко можно усложнив один алгоритм значительно упростить другой. Таким образом, возможны три варианта:

Алгоритм сжатия требует больших вычислительных ресурсов, нежели алгоритм восстановления.

Это наиболее распространённое соотношение, характерное для случаев, когда однократно сжатые данные будут использоваться многократно. В качестве примера можно привести цифровые аудиои видеопроигрыватели.

Алгоритмы сжатия и восстановления требуют приблизительно равных вычислительных ресурсов.

Наиболее приемлемый вариант для линий связи, когда сжатие и восстановление происходит однократно на двух её концах (например, в цифровой телефонии).

Алгоритм сжатия существенно менее требователен, чем алгоритм восстановления.

Такая ситуация характерна для случаев, когда процедура сжатия реализуется простым, часто портативным устройством, для которого объём доступных ресурсов весьма критичен.

Описание и особенности некоторых алгоритмов архивации Рассмотрим следующие алгоритмы сжатия:

• 1) RLE
• 2) коды Хаффмана
• 3) метод «стопкикниг» (MTF — Move to Font)
• 4) арифметическое кодирование

RLE.

Алгоритм RLE (RunLengthEncoding, упаковка, кодирование длин серий), является самым быстрым, простым и понятным алгоритмом сжатия данных и при этом иногда оказывается весьма эффективным. Именно подобный алгоритм используется для сжатия изображений в файлах PCX. Он заключается в следующем: любой последовательности повторяющихся входных символов ставится в соответствие набор из трех выходных символов: первый-байт префикса, говорящий о том, что встретилась входная повторяющаяся последовательность, второй-байт, определяющий длину входной последовательности, третий-сам входной символ —. Лучше всего работу алгоритма пояснить на конкретном примере.

Например: пусть имеется (шестнадцатиричный) текст вида.

05 05 05 05 05 05 01 01 03 03 03 03 03 03 05 03 FF FFFFFF.

из 20 байт. Выберем в качестве префикса байт FF. Тогда на выходе архиватора мы получим последовательность.

FF 06 05 FF 02 01 FF 06 03 FF 01 05 FF 01 03 FF 04 FF.

Ее длина-18 байт, то есть достигнуто некоторое сжатие. Однако, нетрудно заметить, что при кодировании некоторых символов размер выходного кода возрастает (например, вместо 01 01 — FF 02 01). Очевидно, одиночные или дважды (трижды) повторяющиеся символы кодировать не имеет смысла — их надо записывать в явном виде. Получим новую последовательность:

FF 06 05 01 01 FF 06 03 05 03 FF 04 FF.

длиной 13 байт. Достигнутая степень сжатия: 13/20 = 65%.

Нетрудно заметить, что префикс может совпасть с одним из входных символов. В этом случае входной символ может быть заменен своим «префиксным» представлением, например:

FF то же самое, что и FF 01 FF (три байта вместо одного).

Поэтому, от правильного выбора префикса зависит качество самого алгоритма сжатия, так как, если бы в нашем исходном тексте часто встречались одиночные символы FF, размер выходного текста мог бы даже превысить входной. В общем, случае в качестве префикса следует выбирать самый редкий символ входного алфавита.

Можно сделать следующий шаг, повышающий степень сжатия, если объединить префикс и длину в одном байте. Пусть префикс-число F0… FF, где вторая цифра определяет длину length от 0 до 15. В этом случае выходной код будет двухбайтным, но мы сужаем диапазон представления длины с 255 до 15 символов и еще более ограничиваем себя в выборе префикса. Выходной же текст для нашего примера будет иметь вид:

F6 05 F2 01 F6 03 05 03 F4 FF.

Длина-10 байт, степень сжатия-50%.

Далее, так как последовательность длиной от 0 до 3 мы условились не кодировать, код length удобно использовать со смещением на три, то есть 00=3, 0F=18, FF=258, упаковывая за один раз более длинные цепочки.

Если одиночные символы встречаются достаточно редко, хорошей может оказаться модификация алгоритма RLE вообще без префикса, только. В этом случае одиночные символы также обязательно должны кодироваться в префиксном виде, чтобы декодировщик мог различить их в выходном потоке:

06 05 02 01 06 03 01 05 01 03 04 FF.

Длина-12 байт, степень сжатия-60%.

Возможен вариант алгоритма, когда вместо длины length кодируется позиция относительно начала текста distance первого символа, отличающегося от предыдущего. Для нашего примера это будет выходная строка вида:

01 05 07 01 09 03 0 °F 05 10 03 11 FF.

Таблица 1. Вывод по алгоритму RLE.

Здесь и далее приняты следующие обозначения: РО — распространение ошибки, ВИ — возрастание избыточности. Степень сжатия, скорость и используемая оперативная память оцениваются по десятибалльной системе с точки зрения автора. Чем больше величина, тем лучше указанный параметр (выше скорость работы, выше степень сжатия и меньшая потребляемая память).

Работа: в реальном масштабе времени и в потоке.

Основное применение: РСХ, сжатие изображений.

Коды Хаффмана.

Наиболее эффективным кодом переменной длины, в котором ни одно слово не совпадает с началом другого (т.е. префиксный код) является код Хаффмана.

Пусть l1,…, lk-положительные целые числа (k>0). Для того, чтобы существовал префиксный код, длины слов которого равны l1,…, lk, необходимо и достаточно выполнение неравенства Крафта:

Все префиксные коды являются кодами со свойством однозначного декодирования, но не наоборот (например, однозначно декодируемый код 0, 01, 011, 0111,… не является префиксным). Избыточность дешифрируемого кодирования неотрицательна. Для кода Хаффмана (Шеннона) избыточность не превышает 1, т. е. 0 R 1. Длина кода Шеннона равна.

|ai| = -log (p (ai)),.

а длина кода Хаффмана не превышает величины |ai|.

Отсюда, в частности следует вывод, что чем больше длина Т символов входного алфавита (для которого строится код Хаффмана), тем меньше избыточность выходного текста и тем выше степень сжатия. Однако, как будет видно в дальнейшем, при этом значительно возрастают требования к памяти данных и к быстродействию программы, поскольку количество кодов равно количеству символов исходных букв. Избыточность кода Хаффмана в значительной мере зависит, как следует из приведенной формулы, от того, на сколько вероятности появления символов близки к отрицательным степеням числа 2. Для двухсимвольного алфавита, например, код Хаффмана никогда не сможет дать сокращения избыточности, пусть даже вероятности различаются на несколько порядков.

Рассмотрим построение кода Хаффмана на простом примере:

пусть есть текст ABACCADAА. При кодировке двоичным кодом постоянной длины вида:

A — 00, B — 01, C — 10, D — 11.

мы получим сообщение 100 101 000 110 000 длиной 18 бит. Теперь построим код Хаффмана, используя дерево Хаффмана.

Для этого первоначально требуется просмотреть весь исходный текст и получить вероятность (или, что проще — частоту) каждого входящего в него символа. Далее, возьмем два самых редких кода и объединим их в единый узел, частота появления которого равна сумме частот появления входящих в него символов. Рассматривая этот узел, как новый символ, объединяющий два предыдущих, будем повторять операцию слияния символов до тех пор, пока не останется ни одной буквы из входного алфавита. Получим дерево, где листьями являются символы входного алфавита, а узлами — соединение символов из листов-потомков данного узла. Рассматривая каждую левую ветвь как 0, а правую как 1 и спускаясь по дереву вниз до листьев, получим код любого символа:

A — 0, B — 110, C — 10, D — 111.

Исходное сообщение после кодирования станет 11 001 010 011 100 (15 бит). Степень сжатия: 15/18 = 83%. Легко убедиться, что имея коды Хаффмана, можно однозначно восстановить первоначальный текст Другой алгоритм построения оптимальных префиксных кодов, дающий аналогичный результат, был предложен Шенноном и Фано.

Недостатком такого кодирования является тот факт, что вместе с закодированным сообщением необходимо передавать также и построенную таблицу кодов (дерево), что снижает величину сжатия. Однако существует динамический алгоритм построения дерева Хаффмана, при котором кодовая таблица обновляется самим кодировщиком и (синхронно и аналогично) декодировщиком в процессе работы после получения каждого очередного символа. Получаемые при этом коды оказываются квазиоптимальными, поэтому текст сжимается несколько хуже. Более того, возрастают сложность алгоритма и время работы программы (хотя она и становится однопроходной), поэтому, в настоящее время динамический алгоритм почти полностью уступил место статическому.

Следующим вариантом рассматриваемого алгоритма является фиксированный алгоритм Хаффмена, сочетающий в себе достоинства двух предыдущих — высокую скорость работы, простоту и отсутствие дополнительного словаря, создающего излишнюю избыточность. Идея его в том, чтобы пользоваться некоторым усредненным по многим текстам деревом, одинаковым для кодировщика и декодировщика. Такое дерево не надо строить и передавать вместе с текстом, а значит-отпадает необходимость первого прохода. Но, с другой стороны, усредненное фиксированное дерево оказывается еще более неоптимальным, чем динамическое. Поэтому, иногда может быть удобно иметь несколько фиксированных деревьев для разных видов информации.

Вариантами дерева Хаффмана следует также считать деревья, полученные для монотонных источников. Эти источники имеют два важных для наших целей свойства: нет необходимости вычислять частоты появления символов входного текста — как следствие, однопроходный алгоритм; дерево Хаффмана для таких источников может быть представлено в виде вектора из нескольких байтов, каждый из которых обозначает количество кодов дерева определенной длины, например: запись 1,1,0,2,4 говорит о том, что в дереве имеется по одному коду длин 1 и 2 бита, 0 кодов длиной 3 бита, 2 кода длиной 4 бита и 4 кода длиной 5 бит. Сумма всех чисел в записи даст количество символов в алфавите.

Основное применение: универсальный, сжатие текстов и бинарной информации. Динамический алгоритм построения кода Хаффмана используется в архиваторе ICE, статический — в LHA, ARJ. Статический алгоритм Шеннона-Фано используется архиватором PKZIP. Применяется для сжатия изображений (формат JPEG).

Метод «стопки книг» (MTF).

Сравнительно недавно появилась еще одна разновидность адаптивного алгоритма Хаффмана, описанная Рябко, а затем Бентли и названная, соответственно, алгоритмом стопки книг или «двигай вверх» («MTF-MoveToFront»). Каждому символу (букве) присваивается код в зависимости от его положения в алфавите — чем ближе символ к началу алфавита — тем короче код (в качестве кода можно использовать, например, код дерева для монотонных источников). После кодирования очередного символа мы помещаем его в начало алфавита, сдвигая все остальные буквы на одну позицию вглубь. Через некоторое время наиболее часто встречаемые символы сгруппируются в начале, что и требуется для успешного кодирования. Работа алгоритма, действительно, напоминает перекладывание наиболее нужных книг из глубин библиотеки ближе к верху, вследствие чего потом их будет легче найти (аналогия с обыденной жизнью).

Таблица 2. Вывод по методу «стопки книг».

Арифметическое кодирование.

Арифметическое кодирование является методом, позволяющим упаковывать символы входного алфавита без потерь при условии, что известно распределение частот этих символов. Арифметическое кодирование является оптимальным, достигая теоретической границы степени сжатия H0. Однако, коды Хаффмана в предыдущем разделе мы тоже называли оптимальными. Как объяснить этот парадокс? Ответ заключается в следующем: коды Хаффмана являются неблочными, т. е. каждой букве входного алфавита ставится в соответствие определенный выходной код. Арифметическое кодирование-блочное и выходной код является уникальным для каждого из возможных входных сообщений; его нельзя разбить на коды отдельных символов.

Текст, сжатый арифметическим кодером, рассматривается как некоторая двоичная дробь из интервала (0, 1). Результат сжатия можно представить как последовательность двоичных цифр из записи этой дроби. Каждый символ исходного текста представляется отрезком на числовой оси с длиной, равной вероятности его появления и началом, совпадающим с концом отрезка символа, предшествующего ему в алфавите. Сумма всех отрезков, очевидно должна равняться единице. Если рассматривать на каждом шаге текущий интервал как целое, то каждый вновь поступивший входной символ «вырезает» из него подинтервал пропорционально своей длине и положению.

Поясним работу метода на примере.

Пусть алфавит состоит из двух символов: «a» и «b» с вероятностями соответственно ¾ и ¼.

Рассмотрим (открытый справа) интервал (0, 1). Разобьем его на части, длина которых пропорциональна вероятностям символов. В нашем случае это (0, ¾) и (¾, 1).Суть алгоритма в следующем: каждому слову во входном алфавите соответствует некоторый подинтервал из (0, 1).Пустому слову соответствует весь интервал (0, 1). После получения каждого очередного символа арифметический кодер уменьшает интервал, выбирая ту его часть, которая соответствует вновь поступившему символу. Кодом сообщения является интервал, выделенный после обработки всех его символов, точнее, число минимальной длины, входящее в этот интервал. Длина полученного интервала пропорциональна вероятности появления кодируемого текста.

Построение интервала для сообщения «АВГ…».

Выполним алгоритм для цепочки «aaba».

Таблица 3. Построение арифметического кода.

На первом шаге мы берем первые ¾ интервала, соответствующие символу «а», затем оставляем от него еще только ¾. После третьего шага от предыдущего интервала останется его правая четверть в соответствии с положением и вероятностью символа «b». И, наконец, на четвертом шаге мы оставляем лишь первые ¾ от результата. Это и есть интервал, которому принадлежит исходное сообщение.

В качестве кода можно взять любое число из диапазона, полученного на шаге 4. В качестве кода мы можем выбрать, например, самый короткий код из интервала, равный 0.1 и получить четырехкратное сокращение объема текста. Для сравнения, код Хаффмана не смог бы сжать подобное сообщение, однако, на практике выигрыш обычно невелик и предпочтение отдается более простому и быстрому алгоритму из предыдущего раздела.

Арифметический декодер работает синхронно с кодером: начав с интервала (0, 1), он последовательно определяет символы входной цепочки. В частности, в нашем случае он вначале разделит (пропорционально частотам символов) интервал (0, 1) на (0, 0.11) и (0.11, 1). Поскольку число 0.1 (переданный кодером код цепочки «aaba») находится в первом из них, можно получить первый символ: «a». Затем делим первый подинтервал (0, 0.11) на (0, 0.1001) и (0.1001, 0.1100) (пропорционально частотам символов). Опять выбираем первый, так как 0 < 0.1 < 0.1001. Продолжая этот процесс, мы однозначно декодируем все четыре символа.

При рассмотрении этого метода возникают две проблемы: во-первых, необходима вещественная арифметика, вообще говоря, неограниченной точности, и во-вторых, результат кодирования становится известен лишь при окончании входного потока. Дальнейшие исследования, однако, показали, что можно практически без потерь обойтись целочисленной арифметикой небольшой точности (16−32 разряда), а также добиться инкрементальной работы алгоритма: цифры кода могут выдаваться последовательно по мере чтения входного потока.

Подобно алгоритму Хаффмана, арифметический кодер также является двупроходным и требует передачи вместе с закодированным текстом еще и таблицы частот символов. Вообще, эти алгоритмы очень похожи и могут легко взаимозаменяться. Следовательно, существует адаптивный алгоритм арифметического кодирования со всеми вытекающими достоинствами и недостатками. Его основное отличие от статического в том, что новые интервалы вероятности перерассчитываются после получения каждого следующего символа из входного потока.

Работа: в реальном масштабе времени и в потоке (кроме статического).

Основное применение: универсальный, сжатие текстов. Используется в архиваторе LZARI, для сжатия изображений (JPEG).