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