Алгоритм rle

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

Рассмотрим идею сжатия данных по методу RLE (это не метод, а идея):

• во входной последовательности все повторяющиеся цепочки байтов заменяются на фрагменты {управляющий байт, повторяющийся байт}, причем управляющийся байт должен иметь значение 128+длина цепочки. Эта формула означает, что старший бит управляющего байта всегда равен 1 для цепочки повторяющихся байтов (символов);

• все неповторяющиеся цепочки байтов заменяются на фрагменты {управляющий байт, цепочка неповторяющихся байтов}, причем управляющий байт имеет значение 0+длина цепочки. Эта формула, означает, что старший бит управляющего байта для неповторяющейся цепочки равен 0.

Ограничения – длина обрабатываемого фрагмента не должна превосходить 127 байтов.

Схема распаковки:

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

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

Пример. Надо упаковать методом RLE следующую последовательность

11111111 11111111 11111111 11111111 11111111

11110000 00001111 11000011 10101010 10101010

10101010 10101010

Результат

10000101 11111111 00000011 11110000 00001111

11000011 10000100 10101010

Таким образом, 12 байт упаковали в 8 байт, и значит, коэффициент сжатия равен 2/3, т.е. 66 процентов.

Различные реализации данного метода используются в графических файлах форматов PCX, BMP, при факсимильной передаче информации. Для текстовой информации метод RLE неэффективен.