Алгоритм группового кодирования

Этот алгоритм (известный в англоязычной литературе как RLE – Run Length Encoding) является самым простым и, как следствие, самым быстрым и нетребовательным к ресурсам ЭВМ.

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

                               AAAAAAAAbbbbbCCCCCCC

будет закодирована как

                                           8A5b7C

Так как исходная строка занимала 20 байт, а кодированная – 6 байт, то в результате достигается коэффициент сжатия k»3,3.

Примечание: при вычислении коэффициента сжатия в алгоритмах RLE и LZW(см. далее) принять, что любой символ исходных данных, а также счётчик числа повторений (в RLE) и номер ссылки из словаря (в LZW) занимают ровно 1 байт.

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

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

Для устранения этого негативного эффекта обычно используется следующий приём. Такие «неудобные» последовательности кодируют специальным пакетом, состоящим из 3-х из частей: в 1-ю часть записывается счетчик повторений, равный 0; во 2-ю – число символов в группе и, наконец, - сами несжатые данные (их называют литеральной группой). Такая оптимизация несколько усложняет алгоритм группового кодирования (нужно каким-то образом отыскивать литеральные группы), но зато позволяет избежать эффекта «обратного сжатия».

Пример

Исходная строка символов  

AbCdEEEEE (9 байт)

после кодирования без учёта литеральных групп примет вид

                                           1A1b1C1d5E (10 байт),

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

                                                       04AbCd5E (8 байт).

Рис. 2. Блок-схема алгоритма RLE (без учёта литеральных групп)

Очевидно, критерием целесообразности использования литеральных групп для некоторого набора из n символов, принадлежащих исходному потоку данных, является выполнение условия n+2 £ N, где N – число байт, получившихся при стандартном RLE-кодировании того же набора символов ( в предыдущем примере для набора AbCd это условие примет вид 4+2 £ 8, следовательно, есть эффект от кодирования литеральной группы).

В другом варианте кодирования литеральных групп пакет состоит из 2-х частей: в 1-ю часть записывается число символов в группе (£127); во 2-ю – несжатые данные. При распаковке пакеты литеральных групп отличают от обычных по старшему биту первого байта пакета: если он установлен в 0 – значит это счетчик повторений (диапазон 1-127), если в 1 – то это количество символов в литеральной группе (диапазон 2-127).

Тот или иной вариант оказывается более оптимальным в различных случаях. Например, если в потоке входных данных есть много больших групп одинаковых символов (около 255) и мало групп неодинаковых, то эффективнее использовать 3-х байтовую схему кодирования литеральных групп. В противном случае предпочтительнее использовать 2-х байтовую схему.

Алгоритм сжатия LZW

Данный алгоритм, созданный в 1984 году Терри Уэлчем, является модификацией метода сжатия LZ, который впервые разработали А.Лемпель и Я.Зив в 1977 году. Первые буквы фамилий ученых, принявших участие в создании алгоритма, дали ему название LZW.

LZW относится к группе словарных методов сжатия, которые разбивают входной поток данных на слова. Словом называется последовательность символов (байт). Совокупность всех слов называется словарем, в котором каждое слово содержится под своим номером (индексом, ссылкой). В выходной поток записываются только ссылки. Эффект сжатия возникает за счет того, что длина ссылок, как правило, меньше и длины слов. Словарь формируется итеративно, по ходу работы алгоритма сжатия/распаковки.

Алгоритм LZW является симметричным, причем основное время затрачивается на составление словаря. Этот метод особенно хорош для сжатия изображений с пиксельной глубиной до 8 бит/пиксель, содержащих много коротких пиксельных групп. Для таких изображений LZW обычно более эффективен, чем алгоритм группового кодирования RLE, причем эффективность сжатия тем выше, чем длиннее поток входных данных, т.е. чем больше изображение.

Рассмотрим подробнее схему работы алгоритма. Априорно считается, что словарь уже содержит N однобуквенных слов, где N – количество символов в алфавите. Алфавитом называется множество всех возможных символов, которые могут встретиться во входном потоке данных. Выбираем очередной символ из входного потока: если в словаре есть слова, начинающиеся с него, то выбираем следующий символ. Так повторяем до тех пор, пока не окажется, что образовавшегося нет в словаре. Тогда набранная комбинация представима в виде «W+c», где W - слово из словаря, с – отличающийся символ. В выходной (сжатый) поток записывается только номер слова W, а набор новой комбинации начинается с символа с.

Ниже представлено подробное описание алгоритма LZW.

[1] Инициализация словаря символами алфавита;

[2] Слово W = <пусто>;

[3] c = <следующий символ в потоке данных>;

[4] Входит ли слово Wc в словарь?

Да: W=Wc;

Переход к шагу [3].

Нет: Добавить Wс в словарь;

     Записать номер слова W в выходной поток.

[5] Есть ли ещё символы во входном потоке?

Да: Переход к шагу [3];

Нет: Завершение работы алгоритма.

Пример

Сжать методом LZW цепочку символов

a b b a a b b a a b a b b a a a a b a a b b a

Инициализируем словарь символами а и b, так как другие символы в цепочке не встречаются. Берём первый символ из входного потока – а. Есть ли это слово (пока односимвольное) в словаре? Есть, тогда берём следующий символ из потока – b и присоединяем его к текущему слову, т.е. к а. Есть ли получившееся слово ab в словаре? Нет, тогда добавляем его в словарь, а в выходной поток записываем номер слова а. Теперь набор новой комбинации начинается с символа b. Берём следующий (третий) символ из входного потока – b и добавляем его к текущему слову – b. Есть ли слово bb в словаре? Нет - добавляем его в словарь, а в выходной поток записываем номер слова b, и т. д. В результате получаем следующий словарь:

a | b| b | a | a b | b a | a b | a b b | a a | a a | b a a | b b | a

0 1 1 0 2 4 2 6   5 5  7  3 0

и сжатый выходной поток, состоящий только из ссылок (номеров слов):

0 1 1 0 2 4 2 6 5 5 7 3 0

Если предположить, что входной поток был байтовым, и на каждую ссылку отводится тоже один байт, то получаем коэффициент сжатия k=23/13»1.7

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

В реальных программах сжатия алгоритм LZW редко применяется в чистом виде. Это связано с преодолением некоторых практических трудностей при реализации. Одна из них связана с тем, что словарь имеет ограниченный размер, так как под код ссылки отводиться некое фиксированное количество бит. Например, если ссылка кодируется одним байтом, то словарь может вместить максимум различных слов. Следовательно, существует риск переполнения, поэтому фиксированный размер словаря снижает эффективность сжатия. Для решения этой проблемы на практике применяют различные стратегии ведения словаря. В целях повышения скорости работы алгоритма применяют также оптимизацию поиска слов с использованием древовидной структуры словаря или хеш-таблиц. Кроме этого, для достижения максимального сжатия, выходной поток алгоритма LZW кодируется одним из статистических методов, например кодом Хаффмана. Такая схема сжатия используется в широко известных архиваторах RAR и ZIP.