• Tutorial

Давным-давно, когда я был ещё наивным школьником, мне вдруг стало жутко любопытно: а каким же волшебным образом данные в архивах занимают меньше места? Оседлав свой верный диалап, я начал бороздить просторы Интернетов в поисках ответа, и нашёл множество статей с довольно подробным изложением интересующей меня информации. Но ни одна из них тогда не показалась мне простой для понимания - листинги кода казались китайской грамотой, а попытки понять необычную терминологию и разнообразные формулы не увенчивались успехом.

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

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

RLE - компактность единообразия

Алгоритм RLE является, наверное, самым простейшим из всех: суть его заключается в кодировании повторов. Другими словами, мы берём последовательности одинаковых элементов, и «схлопываем» их в пары «количество/значение». Например, строка вида «AAAAAAAABCCCC» может быть преобразована в запись вроде «8×A, B, 4×C». Это, в общем-то, всё, что надо знать об алгоритме.

Пример реализации

Допустим, у нас имеется набор неких целочисленных коэффициентов, которые могут принимать значения от 0 до 255. Логичным образом мы пришли к выводу, что разумно хранить этот набор в виде массива байт:
unsigned char data = { 0, 0, 0, 0, 0, 0, 4, 2, 0, 4, 4, 4, 4, 4, 4, 4, 80, 80, 80, 80, 0, 2, 2, 2, 2, 255, 255, 255, 255, 255, 0, 0 };

Для многих гораздо привычней будет видеть эти данные в виде hex-дампа:
0000: 00 00 00 00 00 00 04 02 00 04 04 04 04 04 04 04
0010: 50 50 50 50 00 02 02 02 02 FF FF FF FF FF 00 00

Подумав, мы решили, что хорошо бы для экономии места как-то сжимать такие наборы. Для этого мы проанализировали их и выявили закономерность: очень часто попадаются подпоследовательности, состоящие из одинаковых элементов. Конечно же, RLE для этого подойдёт как нельзя кстати!

Закодируем наши данные, используя свежеполученные знания: 6×0, 4, 2, 0, 7×4, 4×80, 0, 4×2, 5×255, 2×0.

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

Есть как минимум два выхода из этой ситуации:

1. В качестве индикатора сжатой цепочки выделить одно значение байта, а в случае коллизии с реальными данными экранировать их. Например, если использовать в «служебных» целях значение 255, то при встрече этого значения во входных данных мы вынуждены будем писать «255, 255» и после индикатора использовать максимум 254.
2. Структурировать закодированные данные, указывая количество не только для повторяемых, но и последующих далее одиночных элементов. Тогда мы будем заранее знать, где какие данные.

Первый способ в нашем случае не кажется эффективным, поэтому, пожалуй, прибегнем ко второму.

Итак, теперь у нас имеется два вида последовательностей: цепочки одиночных элементов (вроде «4, 2, 0») и цепочки одинаковых элементов (вроде «0, 0, 0, 0, 0, 0»). Выделим в «служебных» байтах один бит под тип последовательности: 0 - одиночные элементы, 1 - одинаковые. Возьмём для этого, скажем, старший бит байта.

В оставшихся 7 битах мы будем хранить длины последовательностей, т.е. максимальная длина кодируемой последовательности - 127 байт. Мы могли бы выделить под служебные нужды, допустим, два байта, но в нашем случае такие длинные последовательности встречаются крайне редко, поэтому проще и экономичней просто разбивать их на более короткие.

Получается, в выходной поток мы будем писать сперва длину последовательности, а далее либо одно повторяемое значение, либо цепочку неповторяемых элементов указанной длины.

Первое, что должно броситься в глаза - при таком раскладе у нас есть парочка неиспользуемых значений. Не может быть последовательностей с нулевой длиной, поэтому мы можем увеличить максимальную длину до 128 байт, отнимая от длины единицу при кодировании и прибавляя при декодировании. Таким образом, мы можем кодировать длины от 1 до 128 вместо длин от 0 до 127.

Второе, что можно заметить - не бывает последовательностей одинаковых элементов единичной длины. Поэтому, от значения длины таких последовательностей при кодировании мы будем отнимать ещё единичку, увеличив тем самым их максимальную длину до 129 (максимальная длина цепочки одиночных элементов по-прежнему равна 128). Т.е. цепочки одинаковых элементов у нас могут иметь длину от 2 до 129.

Закодируем наши данные снова, но теперь уже и в понятном для компьютера виде. Будем записывать служебные байты как , где T - тип последовательности, а L - длина. Будем сразу учитывать, что длины мы записываем в изменённом виде: при T=0 отнимаем от L единицу, при T=1 - двойку.

0, , 4, 2, 0, , 4, , 80, , 0, , 2, , 255, , 0

Попробуем декодировать наш результат:

• . T=1, значит следующий байт будет повторяться L+2 (4+2) раз: 0, 0, 0, 0, 0, 0.
• . T=0, значит просто читаем L+1 (2+1) байт: 4, 2, 0.
• . T=1, повторяем следующий байт 5+2 раз: 4, 4, 4, 4, 4, 4, 4.
• . T=1, повторяем следующий байт 2+2 раз: 80, 80, 80, 80.
• . T=0, читаем 0+1 байт: 0.
• . T=1, повторяем байт 2+2 раз: 2, 2, 2, 2.
• . T=1, повторяем байт 3+2 раз: 255, 255, 255, 255, 255.
• . T=1, повторяем байт 0+2 раз: 0, 0.

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

В итоге получаем следующее:
0000: 84 00 02 04 02 00 85 04 82 80 00 00 82 02 83 FF
0010: 80 00

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

Возможные улучшения

Эффективность алгоритма зависит не только от собственно алгоритма, но и от способа его реализации. Поэтому, для разных данных можно разрабатывать разные вариации кодирования и представления закодированных данных. Например, при кодировании изображений можно сделать цепочки переменной длины: выделить один бит под индикацию длинной цепочки, и если он выставлен в единицу, то хранить длину и в следующем байте тоже. Так мы жертвуем длиной коротких цепочек (65 элементов вместо 129), но зато даём возможность всего тремя байтами закодировать цепочки длиною до 16385 элементов (2 14 + 2)!

Дополнительная эффективность может быть достигнута путём использования эвристических методов кодирования. Например, закодируем нашим способом следующую цепочку: «ABBA». Мы получим « , A, , B, , A» - т.е. 4 байта мы превратили в 6, раздули исходные данные аж в полтора раза! И чем больше таких коротких чередующихся разнотипных последовательностей, тем больше избыточных данных. Если это учесть, то можно было бы закодировать результат как « , A, B, B, A» - мы бы потратили всего один лишний байт.

LZ77 - краткость в повторении

LZ77 - один из наиболее простых и известных алгоритмов в семействе LZ. Назван так в честь своих создателей: Абрахама Лемпеля (Abraham L empel) и Якоба Зива (Jacob Z iv). Цифры 77 в названии означают 1977 год, в котором была опубликована статья с описанием этого алгоритма.

Основная идея заключается в том, чтобы кодировать одинаковые последовательности элементов. Т.е., если во входных данных какая-то цепочка элементов встречается более одного раза, то все последующие её вхождения можно заменить «ссылками» на её первый экземпляр.

Как и остальные алгоритмы этого семейства семейства, LZ77 использует словарь, в котором хранятся встречаемые ранее последовательности. Для этого он применяет принцип т.н. «скользящего окна»: области, всегда находящейся перед текущей позицией кодирования, в рамках которой мы можем адресовать ссылки. Это окно и является динамическим словарём для данного алгоритма - каждому элементу в нём соответствует два атрибута: позиция в окне и длина. Хотя в физическом смысле это просто участок памяти, который мы уже закодировали.

Пример реализации

Попробуем теперь что-нибудь закодировать. Сгенерируем для этого какую-нибудь подходящую строку (заранее извиняюсь за её нелепость):

«The compression and the decompression leave an impression. Hahahahaha!»

Вот как она будет выглядеть в памяти (кодировка ANSI):
0000: 54 68 65 20 63 6F 6D 70 72 65 73 73 69 6F 6E 20 The compression
0010: 61 6E 64 20 74 68 65 20 64 65 63 6F 6D 70 72 65 and the decompre
0020: 73 73 69 6F 6E 20 6C 65 61 76 65 20 61 6E 20 69 ssion leave an i
0030: 6D 70 72 65 73 73 69 6F 6E 2E 20 48 61 68 61 68 mpression. Hahah
0040: 61 68 61 68 61 21 ahaha!

Мы ещё не определились с размером окна, но условимся, что он больше размера кодируемой строки. Попробуем найти все повторяющиеся цепочки символов. Цепочкой будем считать последовательность символов длиной более единицы. Если цепочка входит в состав более длинной повторяющейся цепочки, будем её игнорировать.

«The compression and t de leave[ an] i . Hah !»

Для пущей наглядности посмотрим на схему, где видны соответствия повторяемых последовательностей и их первых вхождений:

Пожалуй, единственным неясным моментом здесь будет последовательность «Hahahahaha!», ведь цепочке символов «ahahaha» соответствует короткая цепочка «ah». Но здесь нет ничего необычного, мы использовали кое-какой приём, позволяющий алгоритму иногда работать как описанный ранее RLE.

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

С этим разобрались. Теперь заменим найденные повторы на ссылки в словарь. Будем записывать ссылку в формате , где P - позиция первого вхождения цепочки в строке, L - её длина.

«The compression and t de leave i . Hah !»

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

«The compression and t de leave i . Hah !»

Теперь нам достаточно отнять P от текущей позиции кодирования, чтобы получить абсолютную позицию в строке.

Пришло время определиться с размером окна и максимальной длиной кодируемой фразы. Поскольку мы имеем дело с текстом, редко когда в нём будут встречаться особо длинные повторяющиеся последовательности. Так что выделим под их длину, скажем, 4 бита - лимита на 15 символов за раз нам вполне хватит.

А вот от размера окна уже зависит, насколько глубоко мы будем искать одинаковые цепочки. Поскольку мы имеем дело с небольшими текстами, то в самый раз будет дополнить используемое нами количество бит до двух байт: будем адресовать ссылки в диапазоне из 4096 байт, используя для этого 12 бит.

По опыту с RLE мы знаем, что не всякие значения могут быть использованы. Очевидно, что ссылка может иметь минимальное значение 1, поэтому, чтобы адресовать назад в диапазоне 1..4096, мы должны при кодировании отнимать от ссылки единицу, а при декодировании прибавлять обратно. То же самое с длинами последовательностей: вместо 0..15 будем использовать диапазон 2..17, поскольку с нулевыми длинами мы не работаем, а отдельные символы последовательностями не являются.

Итак, представим наш закодированный текст с учётом этих поправок:

«The compression and t de leave i . Hah !»

Теперь, опять же, нам надо как-то отделить сжатые цепочки от остальных данных. Самый распространённый способ - снова использовать структуру и прямо указывать, где сжатые данные, а где нет. Для этого мы разделим закодированные данные на группы по восемь элементов (символов или ссылок), а перед каждой из таких групп будем вставлять байт, где каждый бит соответствует типу элемента: 0 для символа и 1 для ссылки.

Разделяем на группы:

• «The comp»
• «ression »
• «and t de»
• « leave »
• «i . Hah »

Компонуем группы:

«{0,0,0,0,0,0,0,0} The comp{0,0,0,0,0,0,0,0} ression {0,0,0,0,0,1,0,0} and t de{1,0,0,0,0,0,1,0} leave {0,1,0,0,0,0,0,1} i . Hah {0} !»

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

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

В итоге наш сжатый поток будет выглядеть так:

0000: 00 54 68 65 20 63 6f 6d 70 00 72 65 73 73 69 6f #The comp#ressio
0010: 6e 20 04 61 6e 64 20 74 01 31 64 65 82 01 5a 6c n #and t##de###l
0020: 65 61 76 65 01 b1 20 41 69 02 97 2e 20 48 61 68 eave## #i##. Hah
0030: 00 15 00 21 00 00 00 00 00 00 00 00 00 00 00 00 ###!

Возможные улучшения

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

«The long goooooong. The loooooower bound.»

Найдём последовательности только для слова «loooooower»:

«The long goooooong. The wer bound.»

Для кодирования такого результата нам понадобится четыре байта на ссылки. Однако, более экономично было бы сделать так:

«The long goooooong. The l wer bound.»

Тогда мы потратили бы на один байт меньше.

Вместо заключения

Несмотря на свою простоту и, казалось бы, не слишком уж большую эффективность, эти алгоритмы до сих пор широко применяются в разнообразных областях IT-сферы.

Их плюс - простота и быстродействие, а на их принципах и их комбинациях могут быть основаны более сложные и эффективные алгоритмы.

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

Кодирование длин серий (англ. Run-length encoding, RLE) или Кодирование повторов - простой алгоритм сжатия данных, который оперирует сериями данных, то есть последовательностями, в которых один и тот же символ встречается несколько раз подряд. При кодировании строка одинаковых символов, составляющих серию, заменяется строкой, которая содержит сам повторяющийся символ и количество его повторов.

Характеристики алгоритма RLE:

Коэффициенты компрессии : Первый вариант: 32, 2, 0,5. Второй вариант: 64, 3, 128/129. (Лучший, средний, худший коэффициенты). Класс изображений : Ориентирован алгоритм на изображения с небольшим количеством цветов: деловую и научную графику. Симметричность: Примерно единица.

Характерные особенности : К положительным сторонам алгоритма, пожалуй, можно отнести только то, что он не требует дополнительной памяти при архивации и разархивации, а также быстро работает. Интересная особенность группового кодирования состоит в том, что степень архивации для некоторых изображений может быть существенно повышена всего лишь за счет изменения порядка цветов в палитре изображения.

Первый вариант алгоритма

Данный алгоритм необычайно прост в реализации. Групповое кодирование - от английского Run Length Encoding (RLE) - один из самых старых и самых простых алгоритмов архивации графики. Изображение в нем (как и в нескольких алгоритмах, описанных ниже) вытягивается в цепочку байт по строкам растра. Само сжатие в RLE происходит за счет того, что в исходном изображении встречаются цепочки одинаковых байт. Замена их на пары <счетчик повторений, значение > уменьшает избыточность данных.

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

Второй вариант алгоритма

Второй вариант этого алгоритма имеет больший максимальный коэффициент архивации и меньше увеличивает в размерах исходный файл.

29. Алгоритм сжатия lzw

Название алгоритм получил по первым буквам фамилий его разработчиков - Lempel , Ziv и Welch .

LZW-алгоритм основан на идее расширения алфавита, что позволяет использовать дополнительные символы для представления строк обычных символов. Используя, например, вместо 8-битовых ASCII-кодов 9-битовые, вы получаете дополнительные 256 символов. Работа компрессора сводится к построению таблицы, состоящей из строк и соответствующих им кодов. Алгоритм сжатия сводится к следующему: программа прочитывает очередной символ и добавляет его к строке. Если строка уже находится в таблице, чтение продолжается, если нет, данная строка добавляется к таблице строк. Чем больше будет повторяющихся строк, тем сильнее будут сжаты данные. Возвращаясь к примеру с телефоном, можно, проведя весьма упрощенную аналогию, сказать, что, сжимая запись 233 34 44 по LZW-методу, мы придем к введению новых строк - 333 и 444 и, выражая их дополнительными символами, сможем уменьшить длину записи.

Характеристики алгоритма LZW: Коэффициенты компрессии : Примерно 1000, 4, 5/7 (Лучший, средний, худший коэффициенты). Сжатие в 1000 раз достигается только на одноцветных изображениях размером кратным примерно 7 Мб. Класс изображений : Ориентирован LZW на 8-битные изображения, построенные на компьютере. Сжимает за счет одинаковых подцепочек в потоке. Симметричность : Почти симметричен, при условии оптимальной реализации операции поиска строки в таблице.

Характерные особенности : Ситуация, когда алгоритм увеличивает изображение, встречается крайне редко. LZW универсален - именно его варианты используются в обычных архиваторах.

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

Особенность LZW заключается в том, что для декомпрессии не надо сохранять таблицу строк в файл для распаковки. Алгоритм построен таким образом, что мы в состоянии восстановить таблицу строк, пользуясь только потоком кодов.

Еще 10-15 лет назад архиваторы использовались в основном для экономии места на жестких дисках и для того, чтобы уместить максимум данных на дискету. Однако времена изменились. Дискетами как средством переноса и хранения информации уже давно никто не пользуется, а стоимость накопителей стала настолько низкой, что никто даже не задумывается о сжатии данных с целью экономии места. Кроме того, объемы данных стали такими большими, что их архивация и разархивация с целью экономии места просто нецелесообразна, поскольку отнимает очень много времени. Ну действительно, сегодня объемы данных на накопителях пользователей измеряются терабайтами. А теперь представьте себе, сколько потребуется времени, чтобы заархивировать один терабайт данных. На это уйдет не один и даже не два часа, а как минимум часов 10-12, то есть компьютер придется оставить включенным на всю ночь.

Казалось бы, архиваторы сегодня должны постепенно утрачивать свою актуальность. Но ничего подобного не происходит. У подавляющего большинства пользователей среди прочих программ установлены архиваторы, либо они используют архиватор, встроенный в операционную систему Windows (другие ОС в данной публикации мы не рассматриваем).

Дело в том, что изменилось назначение архиваторов. Сегодня они используются преимущественно для выкладывания данных в Сеть. Большинство драйверов на сайтах производителей выкладываются именно в архивах, и большая часть программ на различных ресурсах также заархивированы. Кстати, и сам пользователь прежде чем выложить какие­либо данные в Сеть (например, на файлообменные ресурсы), запаковывает данные в архив.

Что касается российского рынка, то у нас наиболее распространенными являются три архиватора: WinRAR, WinZip и 7-Zip, представленные как в 32-, так и 64-битной версиях. Именно их мы и будем сравнивать в данной статье. Однако прежде кратко рассмотрим некоторые теоретические аспекты работы архиваторов.

Алгоритмы сжатия информации

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

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

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

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

Алгоритм RLE

Один из самых старых и самых простых методов сжатия информации - это алгоритм RLE (Run Length Encoding), то есть алгоритм кодирования серий последовательностей. Этот метод очень прост в реализации и представляет собой один из алгоритмов архивации, а суть его заключается в замене серии (группы) повторяющихся байтов на один кодирующий байт и счетчик числа их повторений. То есть группа одинаковых байтов заменятся на пару: <счетчик повторений, значение>, что сокращает избыточность данных.

В данном алгоритме признаком счетчика служат единицы в двух верхних битах считанного байта. К примеру, если первые два бита - это 11, то остальные 6 бит отводятся на счетчик, который может принимать значения от 1 до 64. Соответственно серию из 64 повторяющихся байтов можно определить всего двумя байтами, то есть сжать в 32 раза.

Есть и другой вариант реализации этого алгоритма, когда признаком счетчика является 1 в первом байте счетчика. В этом случае счетчик может принимать максимальное значение, равное 127, - а следовательно максимальная степень сжатия будет равна 64.

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

Метод RLE, как правило, весьма эффективен для сжатия растровых графических изображений (BMP, PCX, TIF, GIF), поскольку они содержат очень много длинных серий повторяющихся последовательностей байтов.

Ограничение информационного алфавита

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

В дальнейшем под информационным алфавитом мы будем подразумевать набор символов, используемый для кодирования информационной последовательности. К примеру, пусть имеется некоторое текстовое сообщение. Для кодировки каждой буквы этого сообщения используется ASCII-таблица, состоящая из 256 символов. При этом под кодирование каждого символа отводится ровно 8 бит (1 байт). В данном случае информационный алфавит - это все 256 символов кодировочной ASCII-таблицы.

Понятно, что в исходном текстовом сообщении могут применяться не все 256 символов ASCII-таблицы. К примеру, если речь идет о текстовом сообщении на русском языке, в котором нет цифр, то достаточно 64 символов (33 строчные и 31 заглавная буквы). Если добавить к этому знаки препинания, знаки абзаца и перехода на новую строку, станет понятно, что число символов не превысит 100. В этом случае можно использовать не 8-, а 7-битное кодирование символов, что позволяет получить таблицу из 128 символов. То есть мы как бы ограничиваем информационный алфавит, за счет чего можно уменьшить разрядность каждого колируемого символа. Можно пойти дальше - точно определить количество применяемых символов в текстовом сообщении. Если, к примеру, выяснится, что в сообщении задействуются всего 30 символов (включая символы перехода на новую строку), то можно использовать 5-битную кодировочную таблицу, содержащую 32 символа, и тогда степень сжатия текстового сообщения станет еще большей. Действительно, если в исходном сообщении применяется 8-битное кодирование символов, а в сжатом - 5-битное, то коэффициент сжатия будет 8/5.

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

У метода ограниченного алфавита есть и другие недостатки. Если исходное информационное сообщение содержит большое количество разнообразных символов, то понизить разрядность представления символов алфавита не удастся и данный способ просто не сработает. Предположим, к примеру, что в исходном информационном сообщении содержится 129 символов из 256-символьного алфавита. Воспользоваться 7-битным кодированием символов в данном случае не удастся, поскольку 7 бит позволят закодировать только 128 символов. Поэтому для 129 символов придется обратиться к тому же 8-битному кодированию, как и в исходном 256-символьном алфавите.

Коды переменной длины

Одним из главных недостатков рассмотренного нами гипотетического метода ограничения алфавита является то, что в нем применяется равномерный код, когда все символы информационного алфавита имеют одинаковую длину (8, 7 бит или меньше). Было бы логичнее использовать такую систему кодирования, при которой длина кода символа зависит от частоты его появления в информационном сообщении. То есть, если в исходном информационном сообщении некоторые символы встречаются чаще других, то для них оптимально использовать короткие коды, а для редко встречающихся -более длинные.

В качестве гипотетического примера рассмотрим следующее информационное сообщение: «авиакатастрофа» , которое содержит 14 символов. Предположим, что у нас имеется алфавит из 14 символов, который позволяет нам закодировать это сообщение. Если используется равномерный код, то на каждый символ алфавита потребуется 4 бита (длина кода в 4 бита позволит сформировать 16 символов). Однако нетрудно заметить, что в нашем информационном сообщении символ «а» встречается пять раз, символ «т» - два раза, а остальные символы - по одному разу. Если для символа «а» мы будем использовать код длиной 2 бит, для символа «т» - длиной 3 бита, а для остальных символов - длиной 4 бита, то мы наверняка сможем сэкономить. Нужно лишь понять, как именно строить коды переменной длины и как именно длина кода должна зависеть от частоты появления символа в информационном сообщении.

Если все символы входят в информационное сообщение с одинаковой частотой (равновероятны), то при информационном алфавите из N символов для кодирования каждого символа потребуется ровно log 2 N бит. Фактически это случай равномерного кода.

Если же символы имеют разную вероятность появления в информационном сообщении, то, согласно теории К. Шеннона, символу, вероятность появления которого равна p, оптимально и, что особенно важно, теоретически допустимо ставить в соответствие код длиной –log 2 p . Возвращаясь к нашему примеру с информационным сообщением «авиакатастрофа» и учитывая, что вероятность появления символа «а» (p(a)) составляет 5/14, вероятность появления символа «т» - 2/14, а вероятность появления всех остальных символов - 1/14, мы получим, что: для символа «a» оптимальная длина кода равна –log 2 (5/14) = 1,48 бит; для символа «т» - –log 2 (2/14) = 2,8 бит, а для всех остальных символов она составляет –log 2 (1/14) = 3,8. Поскольку в нашем случае длина кода может иметь только целочисленное значение, то, округляя, получим, что для символа «а» оптимально использовать код длиной 2 бита, для символа «т» - длиной 3 бита, а для остальных - длиной 4 бита.

Давайте посчитаем степень сжатия при использовании такого кодирования. Если бы применялся равномерный код на базе 14-символьного алфавита, то для кодирования слова «авиакатастрофа» потребовалось бы 56 бит. При использовании кодов переменной длины потребуется 5×2 бита + 2×3 бита + 7×4 бита = 44 бита, то есть коэффициент сжатия составит 1,27.

Теперь рассмотрим алгоритмы получения кодов переменной длины.

Префиксное кодирование

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

Поясним это свойство префиксных кодов на конкретном примере. Пусть имеется система из трех префиксных кодов: {0, 10, 11}. Как видим, более короткий код 0 не совпадает с началом более длинных кодов 10 и 11. Пусть код 0 задает символ «а», код 10 - символ «м», а код 11 - символ «р». Тогда слово «рама» кодируется последовательностью 110100. Попробуем раскодировать эту последовательность. Поскольку первый бит - это 1, то первый символ может быть только «м» или «р» и определяется значением второго бита. Поскольку второй бит - это 1, то первый символ - это «р». Третий бит - это 0, и он однозначно соответствует символу «а». Четвертый бит - это 1, то есть нужно смотреть на значение следующего бита, который равен 0, тогда третий символ - это «м». Последний бит - это 0, что однозначно соответствует символу «а». Таким образом, свойство префиксных кодов, заключающееся в том, что более короткие по длине коды не могут совпадать с началом более длинных кодов, позволяет однозначно декодировать закодированное префиксными кодами переменной длины информационное сообщение.

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

Поскольку в дереве не может быть циклов, от корневого узла к листовому всегда можно проложить один-единственный маршрут. Если ребра дерева пронумерованы, то каждому такому маршруту соответствует некоторая уникальная двоичная последовательность. Множество всех таких последовательностей будет образовывать систему префиксных кодов.

Для рассмотренного примера системы из трех префиксных кодов: {0, 10, 11}, которые задают символы «а», «м» и «р», кодовое дерево показано на рис. 1.

Рис. 1. Кодовое дерево для системы
из трех префиксных кодов: {0, 10, 11}

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

До сих пор мы рассматривали лишь идею префиксных кодов переменной длины. Что касается алгоритмов получения префиксных кодов, то их можно разработать достаточно много, но наибольшую известность получили два метода: Шеннона-Фано и Хаффмана.

Алгоритм Шеннона-Фано

Данный алгоритм получения префиксных кодов независимо друг от друга предложили Р. Фано и К. Шеннон, заключается он в следующем. На первом шаге все символы исходной информационной последовательности сортируются по убыванию или возрастанию вероятностей их появления (частоты их появления), после чего упорядоченный ряд символов в некотором месте делится на две части так, чтобы в каждой из них сумма частот символов была примерно одинакова. В качестве демонстрации рассмотрим уже знакомое нам слово «авиакатастрофа» .

Если символы, составляющие данное слово, отсортировать по убыванию частоты их появления, то получим следующую последовательность: {а(5), т(2), в(1), и(1), к(1), с(1), р(1), о(1), ф(1)} (в скобках указывается частота повторяемости символа в слове). Далее, нам нужно разделить эту последовательность на две части так, чтобы в каждой из них сумма частот символов была примерно одинаковой (насколько это возможно). Понятно, что раздел пройдет между символами «т» и «в», в результате чего образуется две последовательности: {а(5), т(2)} и {в(1), и(1), к(1), с(1), р(1), о(1), ф(1)}. Причем суммы частот повторяемости символов в первой и второй последовательностях будут одинаковы и равны 7.

На первом шаге деления последовательности символов мы получаем первую цифру кода каждого символа. Правило здесь простое: для тех символов, которые оказались в последовательности слева, код будет начинаться с «0», а для тех, что справа - с «1».

В частности, последовательность {а(5), т(2)} разделится на два отдельных символа: a(5) и т(2) (других вариантов деления нет). Тогда вторая цифра кода для символа «a» - это «0», а для символа «т» - «1». Поскольку в результате деления последовательности мы получили отдельные элементы, то они более не делятся и для символа «a» получаем код 00, а для символа «т» - код 01.

Последовательность {в(1), и(1), к(1), с(1), р(1), о(1), ф(1)} можно разделить либо на последовательности {в(1), и(1), к(1)} и {с(1), р(1), о(1), ф(1)}, либо на {в(1), и(1), к(1)}, {с(1)} и {р(1), о(1), ф(1)}.

В первом случае суммы частот повторяемости символов в первой и второй последовательностях будут 3 и 4 соответственно, а во втором случае - 4 и 3 соответственно. Для определенности воспользуемся первым вариантом.

Для символов полученной новой последовательности {в(1), и(1), к(1)} (это левая последовательность) первые две цифры кода будут 10, а для последовательности {с(1), р(1), о(1), ф(1)} - 11.

В нашем примере (рис. 2 и 3) получается следующая система префиксных кодов: «a» - 00, «т» - 01, «в» - 100, «и» - 1010, «к» - 1011, «с» - 1100, «р» - 1101, «о» - 1110, «ф» - 1111. Как нетрудно заметить, более короткие коды не являются началом более длинных кодов, то есть выполняется главное свойство префиксных кодов.

Рис. 2. Демонстрация алгоритма Шеннона-Фано

Рис. 3. Кодовое дерево для слова «авиакатастрофа»
в алгоритме Шеннона-Фано

Алгоритм Хаффмана

Алгоритм Хаффмана - это еще один алгоритм получения префиксных кодов переменной длины. В отличие от алгоритма Шеннона-Фано, который предусматривает построение кодового дерева сверху вниз, данный алгоритм подразумевает построение кодового дерева в обратном порядке, то есть снизу вверх (от листовых узлов к корневому узлу).

На первом этапе, как и в алгоритме Шеннона-Фано, исходная последовательность символов сортируется в порядке убывания частоты повторяемости символов (элементов последовательности). Для рассмотренного ранее примера со словом «авиакатастрофа» получим следующую отсортированную последовательность элементов: {а(5), т(2), в(1), и(1), к(1), с(1), р(1), о(1), ф(1)}.

Далее два последних элемента последовательности заменяются на новый элемент S1, которому приписывается повторяемость, равная сумме повторяемостей исходных элементов. Затем производится новая сортировка элементов последовательности в соответствии с их повторяемостью. В нашем случае два последних элемента o(1) и ф(1) заменяются на элемент S1(2), а вновь отсортированная последовательность примет вид: {а(5), т(2), S1(2), в(1), и(1), к(1), с(1), р(1)}.

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

Рис. 4. Демонстрация алгоритма Хаффмана
на примере слова «авиакатастрофа»

Одновременно с замещением элементов и пересортировкой последовательности строится кодовое бинарное дерево. Алгоритм построения дерева очень прост: операция объединения (замещения) двух элементов последовательности порождает новый узловой элемент на кодовом дереве. То есть если смотреть на дерево снизу вверх, ребра кодового дерева всегда исходят из замещаемых элементов и сходятся в новом узловом элементе, соответствующем элементу последовательности, полученному путем замещения (рис. 5). При этом левому ребру кодового дерева можно присвоить значение «0», а правому - «1». Эти значения в дальнейшем будут служить элементами префиксного кода.

Рис. 5. Построение кодового дерева
в алгоритме Хаффмана
(замещение элементов «o» и «ф»
новым элементом S1)

Полное кодовое дерево, построенное по алгоритму Хаффмана для слова «авиакатастрофа» , показано на рис. 6.

Рис. 6. Полное кодовое дерево для слова «авиакатастрофа»,
построенное по алгоритму Хаффмана

Пройдясь по ребрам кодового дерева сверху вниз, легко получить префиксные коды для всех символов нашего информационного алфавита:

Если теперь попытаться написать слово «авиакатастрофа» в кодировке Хаффмана, то получим 41-битную последовательность 0 1101 11000 0 11001 0 111 0 1010 111 1011 1000 1001 0. Интересно отметить, что при использовании префиксных кодов Шеннона-Фано мы также получим 41-битную последовательность для слова «авиакатастрофа». То есть в конкретном примере эффективность кодирования Хаффмана и Шеннона-Фано одинакова. Но если учесть, что реальный информационный алфавит - это 256 символов (а не 14, как в нашем примере), а реальные информационные последовательности - это любые по своему содержанию и длине файлы, то возникает вопрос об оптимальном префиксном коде, то есть коде, который позволяет получить минимальную по длине выходную последовательность.

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

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

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

Как мы уже отмечали, согласно критерию Шеннона, оптимальным является такой код, в котором под каждый символ отводится код длиной –log 2 p бит. И если, к примеру, вероятность какого-то символа составляет 0,2, то оптимальная длина его кода будет равна –log 2 0,2 = 2,3 бит. Понятно, что префиксные коды не могут обеспечить такую длину кода, а потому не являются оптимальными. Вообще длина кода, определяемая критерием Шеннона, - это лишь теоритический предел. Вопрос лишь в том, какой способ кодирования позволяет максимально приблизиться к этому теоретическому пределу. Префиксные коды переменной длины эффективны и достаточно просты в реализации, однако существуют и более эффективные способы кодирования, в частности алгоритм арифметического кодирования.

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

Идея алгоритма арифметического кодирования заключается в следующем. Как и во всех рассмотренных ранее способах кодирования, каждый символ исходной информационной последовательности характеризуется его вероятностью. Исходной незакодированной последовательности ставится в соответствие полуинтервал }