Кодирование длин серий

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

История

Идея кодирования длин серий впервые была реализована в механических телеграфных системах XIX века. В частности, в 1843 году американский изобретатель Сэмюэл Морзе предложил использовать сокращённые коды для часто повторяющихся букв в азбуке Морзе, что можно рассматривать как прообраз RLE. Однако в современном виде алгоритм был формализован в 1950-х годах с развитием цифровых вычислительных машин.

Первое широкое применение RLE получило в факсимильной связи (факсах), где изображения состоят из длинных последовательностей чёрных и белых точек. В 1960-х годах Международный союз электросвязи (ITU) стандартизировал методы RLE для передачи факсимильных сообщений (стандарты T.4 и T.6). В 1970-х годах алгоритм начал использоваться в ранних форматах растровой графики, таких как PCX (ZSoft Corporation, 1982) и BMP (Microsoft, 1990). С появлением более эффективных алгоритмов (LZW, Deflate) RLE уступил им в степени сжатия, но сохранил актуальность для специализированных задач.

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

Алгоритм RLE обрабатывает входной поток данных последовательно, выделяя непрерывные серии одинаковых значений. Каждая серия представляется в виде кортежа (count, value), где count — количество повторяющихся элементов, а value — само значение. Например, строка «AAAABBBCCDAA» преобразуется в «4A3B2C1D2A».

Формы представления

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

• Парная запись (наиболее распространённая): каждому символу предшествует число повторов. Например, «5A3B» означает пять символов A и три символа B.
• Битовая маска: для бинарных данных (0 и 1) длина серии кодируется фиксированным числом бит. Используется в факсимильных протоколах.
• Флаг повтора: специальный управляющий символ (escape-символ) указывает на начало сжатой последовательности. Например, в формате PCX после символа 0xC1 (193) следует длина серии (минус 1) и значение пикселя.

Обработка одиночных символов

Для предотвращения увеличения размера данных при отсутствии повторений (например, строка «ABCDE» при RLE даст «1A1B1C1D1E», что вдвое длиннее) применяются модификации:

• Минимальная длина серии: кодируются только серии длиной 3 и более символа. Одиночные символы остаются без изменений.
• Флаг сжатия: вводится специальный маркер, который указывает, что последующие данные являются сжатыми. Например, в формате BMP для 8-битных изображений используется байт 0x00 как флаг повтора.

Классификация

По типу данных

• Бинарное RLE: работает с последовательностями нулей и единиц. Применяется в факсах, штрих-кодах, некоторых форматах изображений (например, JBIG).
• Символьное RLE: оперирует произвольными байтами или символами. Используется в текстовых файлах, простых графических форматах (PCX, BMP).
• Адаптивное RLE: динамически изменяет параметры кодирования (длину серии, порог сжатия) в зависимости от статистики входных данных.

По способу кодирования длины

• Фиксированная длина: каждая длина серии занимает заранее определённое количество бит (например, 8 бит для длин от 1 до 255). Ограничивает максимальную длину серии.
• Переменная длина: длина серии кодируется с использованием префиксных кодов (например, код Хаффмана) или специальных маркеров продолжения. Позволяет обрабатывать произвольно длинные серии.
• Разностное кодирование: вместо длины серии записывается разность между текущим значением и предыдущим. Используется для данных с плавными изменениями (например, аудиосигналы).

Применение

Графические форматы

RLE является основным или вспомогательным методом сжатия в нескольких популярных форматах растровых изображений:

• BMP (Microsoft Windows Bitmap): поддерживает RLE-сжатие для 4-битных и 8-битных изображений (алгоритмы RLE4 и RLE8). Степень сжатия обычно невысока (2–5 раз) из-за ограничений формата.
• PCX (ZSoft PC Paintbrush): использует RLE с флагом повтора (байт со старшим битом, установленным в 1). Эффективен для изображений с большими одноцветными областями.
• TIFF (Tagged Image File Format): поддерживает RLE как один из вариантов сжатия (наряду с LZW и Deflate).
• ILBM (Interleaved Bitmap, формат Amiga): применяет RLE для сжатия графических данных в файлах IFF.

Факсимильная связь

В стандартах факсимильной связи (ITU T.4 и T.6) используется модифицированное RLE для сжатия чёрно-белых изображений. Алгоритм кодирует длины серий чёрных и белых точек, используя коды Хаффмана для наиболее вероятных длин. Степень сжатия достигает 10–20 раз для типичных документов.

Хранение и передача данных

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

Обработка изображений в реальном времени

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

Преимущества и недостатки

Преимущества

• Простота реализации: алгоритм требует минимальных вычислительных ресурсов и может быть реализован аппаратно (например, в факсимильных аппаратах).
• Высокая скорость: как сжатие, так и распаковка выполняются за линейное время O(n), где n — размер данных.
• Отсутствие потерь: исходные данные восстанавливаются полностью без искажений.
• Эффективность на однородных данных: для изображений с большими областями одного цвета (например, чертежи, текст) степень сжатия может достигать 50–100 раз.

Недостатки

• Низкая эффективность на случайных данных: для данных с редкими повторениями (например, фотографии, сжатые JPEG) RLE может увеличить размер в 1.5–2 раза.
• Отсутствие адаптации: алгоритм не учитывает статистические закономерности данных (например, повторяющиеся шаблоны, не являющиеся сериями).
• Ограничения на длину серии: при использовании фиксированного размера поля длины максимальная длина серии ограничена (например, 255 для 8-битного поля). Длинные серии приходится разбивать, что снижает эффективность.

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

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

• Алгоритм RLE используется в формате PNG (Portable Network Graphics) как часть фильтрации перед сжатием Deflate. Фильтр «Sub» и «Up» преобразуют изображение в последовательности, более удобные для RLE.
• В ранних версиях формата GIF (CompuServe, 1987) применялся RLE, но позже он был заменён на LZW для улучшения сжатия.
• В аудиосжатии RLE используется редко из-за низкой корреляции между соседними отсчётами. Однако существуют специализированные форматы (например, ADPCM с RLE) для речи с длинными паузами.
• В космической телеметрии (миссии NASA «Вояджер», 1977) RLE применялся для сжатия изображений планет, где большие области чёрного космоса позволяли достичь сжатия в 5–10 раз.

Источники

• Гонсалес Р., Вудс Р. Цифровая обработка изображений. — М.: Техносфера, 2005.
• Сэломон Д. Сжатие данных, изображений и звука. — М.: Техносфера, 2004.
• ITU-T Recommendation T.4: Standardization of Group 3 facsimile apparatus for document transmission. — International Telecommunication Union, 1993.
• Microsoft Corporation. Microsoft Windows Bitmap Format Specification. — 1990.
• ZSoft Corporation. PCX File Format Technical Reference Manual. — 1985.