Run-Length Encoding

Run-Length Encoding (RLE, кодирование длин серий) — это простейший алгоритм сжатия данных без потерь, основанный на замене последовательностей повторяющихся символов (серий) на пару «количество повторений — сам символ». Относится к классу словарных методов и является одним из первых и наиболее интуитивно понятных способов уменьшения объёма информации.

Принцип работы

Алгоритм RLE обрабатывает входной поток данных последовательно, обнаруживая повторяющиеся элементы. Когда встречается серия из двух и более одинаковых символов, она заменяется на специальный код, который обычно состоит из двух частей: счётчика (числа повторений) и самого символа. Если символ встречается только один раз, он может быть передан без изменений или с флагом единичного вхождения.

Например, строка «AAAABBBCCDAA» будет закодирована как «4A3B2C1D2A» или, в некоторых реализациях, с использованием управляющих байтов для различения сжатых и несжатых фрагментов. Степень сжатия зависит от длины и количества повторяющихся серий.

Разновидности реализации

Существует несколько способов представления закодированных данных:

• Фиксированная длина счётчика — счётчик занимает заданное количество бит (например, 8 бит), что ограничивает максимальную длину серии (255 для 8-битного счётчика). При превышении лимита серия разбивается на несколько.
• Динамическая длина счётчика — счётчик может быть переменной длины, что позволяет кодировать сколь угодно длинные серии, но усложняет декодирование.
• Использование флагов — вводятся специальные управляющие байты (escape-символы), которые указывают, является ли следующий байт счётчиком или обычным символом. Это позволяет различать сжатые и несжатые участки данных.

История

Метод кодирования длин серий имеет давнюю историю, восходящую к ранним телеграфным системам. В середине XX века, с развитием компьютерной техники, RLE стал применяться для сжатия растровых изображений, где часто встречаются большие области одинакового цвета. Алгоритм получил широкое распространение в 1970–1980-х годах благодаря своей простоте и эффективности для определённых типов данных.

Одним из первых форматов, активно использовавших RLE, был формат PCX, разработанный компанией ZSoft в 1982 году. Позднее RLE был включён в стандарты факсимильной связи (Group 3 и Group 4), где используется для сжатия чёрно-белых изображений. В 1990-х годах метод применялся в форматах BMP, TIFF и некоторых других.

Применение

RLE наиболее эффективен для данных, содержащих длинные последовательности одинаковых значений. Основные области применения:

• Растровая графика — сжатие изображений с большими однотонными областями (чертежи, схемы, логотипы, факсимильные сообщения). Форматы: PCX, BMP (опционально), TIFF (опционально), IFF-ILBM.
• Факсимильная связь — стандарты ITU-T T.4 и T.6 используют модифицированное RLE для сжатия чёрно-белых факсимильных страниц.
• Аудиоданные — в некоторых простых аудиоформатах (например, 8-битные PCM с низким разрешением) RLE может применяться для сжатия пауз или тишины.
• Простые текстовые данные — сжатие логов, конфигурационных файлов и других текстов с повторяющимися строками или символами.
• Промежуточное представление — RLE часто используется как один из этапов в более сложных алгоритмах сжатия (например, в JPEG после этапа квантования для сжатия последовательностей нулей).

Ограничения

RLE неэффективен для данных с высокой энтропией, где каждый символ уникален или повторяется редко. В таких случаях объём закодированных данных может превышать исходный (так называемое «отрицательное сжатие»). Например, строка «ABCDEFGHIJ» будет закодирована как «1A1B1C1D1E1F1G1H1I1J», что вдвое длиннее оригинала. Для преодоления этого недостатка часто применяются модификации с флагами, которые позволяют передавать неповторяющиеся участки без изменений.

Примеры

Пример 1: Простое кодирование

Исходная строка: WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWB

Закодированная строка: 12W1B12W3B24W1B

Коэффициент сжатия: 33 символа → 14 символов (сжатие в ~2.4 раза).

Пример 2: Изображение

Чёрно-белое изображение размером 100×100 пикселей, где первые 50 строк — белые, а остальные 50 — чёрные. Без сжатия: 10 000 пикселей. С RLE: 2 пары (50 строк белых, 50 строк чёрных), что даёт огромный коэффициент сжатия.

Пример 3: Неэффективное применение

Исходная строка: ABCABCABC

Закодированная строка: 1A1B1C1A1B1C1A1B1C

Результат: 9 символов → 18 символов (расширение в 2 раза).

Сравнение с другими методами

RLE является одним из самых простых алгоритмов сжатия. В отличие от более сложных методов, таких как LZ77, LZW или арифметическое кодирование, RLE не требует построения словарей или вероятностных моделей. Это делает его быстрым и малозатратным по вычислительным ресурсам, но ограничивает область применения.

В современных системах RLE редко используется как самостоятельный метод сжатия, чаще — как вспомогательный этап в комбинированных алгоритмах (например, в формате PNG после фильтрации изображений или в сжатии данных с разреженными матрицами).

Интересные факты

• В факсимильной связи Group 3 используется модифицированное RLE (Modified Huffman), которое сочетает кодирование длин серий с кодами Хаффмана для достижения лучшего сжатия чёрно-белых документов.
• Алгоритм RLE применялся в ранних компьютерных играх для сжатия графических спрайтов и фонов, где преобладали однотонные области.
• В формате BMP RLE-сжатие является опциональным и поддерживается только для 4- и 8-битных изображений.

Источники

• Д. Сэломон. «Сжатие данных, изображений и звука». — М.: Техносфера, 2004.
• К. Д. Барсуков. «Методы сжатия данных». — М.: Горячая линия — Телеком, 2006.
• Стандарт ITU-T T.4 (Факсимильная связь Group 3).
• Спецификация формата файлов BMP (Microsoft Corporation).