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

Алгоритм RLE (Run Length Coding, кодирование длин повторов) – один из самых простых. Сжатие в этом алгоритма производится за счет того, что в изображении встречаются последовательности одинаковых байтов. Замена этих последовательностей на два значения (счетчик повторений и значение) уменьшает избыточность данных. Существует две реализации алгоритма (Рис. 3.1 ).

Рисунок 3.1. Два варианта алгоритма RLE

Первый вариант учитывает только повторы. Для этого первый байт содержит признак счетчика (единицы в двух старших разрядах), а также шестиразрядный счетчик, имеющий 64 состояния. Второй байт содержит общее повторяющееся значение последовательности.

Таким образом, в лучшем случае можно сжать строку из 64 повторяющихся байт до двух байт, т.е. коэффициент сжатия составит 32. В худшем случае, когда все байты последовательности не повторяются общий объем данных не только не уменьшается, а наоборот увеличивается в два раза.

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

В лучшем случае алгоритм сжимает последовательность в 64 раза, а в худшем случае будет небольшое увеличение последовательности (к каждым 128 байтам добавится еще один байт).

В чистом виде это алгоритм применяется для сжатия изображений с небольшим числом цветов (деловая графика). Для сжатия цифрового фото и видеоинформации он используется в сочетании с другими алгоритмами.