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

Этот алгоритм (известный в англоязычной литературе как 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-х байтовую схему.