RLE сжатие
RLE обозначает Run Length Encoding. Это алгоритм сжатия без потерь, который эффективно сжимает только определенные типы данных.
Как работает RLE
RLE - самый простой алгоритм сжатия. Он заменяет последовательность одинаковых данных в файле образцом и количеством его повторов.
Попробуем сжать следующую последовательность данных (17 байт):
ABBBBBBBBBCDEEEEF
При использовании RLE сжатия, сжатый файл займет 10 байт и будет выглядеть так:
A *8B C D *4E F
Как можно увидеть, повторяющиеся данные были заменены управляющим символом (*), числом повторов и самим символом. Управляющий символ не фиксирован и может отличаться в различных реализациях.
Если символ, соответствующий управляющему, встречается в сжимаемом файле, он кодируется, как отдельный символ.
Как можно видеть, RLE сжатие эффективно для сжатия последовательностей, где одинаковые символы идут 4 и более раз подряд. Дело в том, что сжатие трех символов не приводит к уменьшению файла, а сжатие двух символов увеличивает его.
Важно знать, что существует множество реализаций этого алгоритма. Вышеприведенный пример демонстрирует основные принципы RLE сжатия. Некоторые реализации этого метода адаптируются под определенные виды сжимаемых данных.
Достоинства и недостатки
Этот алгоритм очень легок в реализации и не требует больших процессорных затрат. Но RLE сжатие эффективно только на файлах, содержащих большие объемы повторяющихся данных. Это могут быть текстовые файлы, содержащие большое количество пробелов для отбивок или битмапы, содержащие большие черные или белые области. Цветные битмапы, сгенеренные на компьютере, тоже могут хорошо сжиматься.
Где используется RLE сжатие
RLE сжатие используется в следующих форматах файлов:
