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