Алгоритм RLE

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

Формальная модель и корректность

Условие однозначной декодируемости

Чтобы декодер однозначно восстановил исходные данные, формат должен быть самоопределяемым:

• границы ℓ и a известны (фиксированные размеры полей или явные разделители);

• ни одна кодовая последовательность не является префиксом другой (нет неоднозначности);

• предусмотрено поведение при большой длине серии (ограничение и разбиение).

Варианты форматов RLE

1. Пары фиксированной длины:
   

   • ℓ – байт (1…255), a – байт (символ). Пара = 2 байта. Серии длиннее 255 делятся на несколько пар. Простой и однозначный формат (типичен для учебных задач ЕГЭ).

2. Маркерный (escape-byte):  
   

   • Выделяется специальный байт ESC. Последовательности вида ESC <символ> <длина> означают повтор; одиночные байты идут «как есть». Нужна экранировка самого ESC.

3. Смешанный (литералы + повторы, «пакетный»):  
   

   • Заголовок блока указывает, копировать ли «как есть» N последующих байтов (literal run) или повторить один байт K раз (repeat run). Такой подход уменьшает раздувание на «шуме».

Для задач ЕГЭ чаще всего задаётся простой фиксированный формат «1 байт длины + 1 байт символа» без заголовков.

Оценка сжатия, сложность и граничные случаи

1. Оценка объёма
   

   Пусть исходник – n байт (8 бит на символ). В фиксированном формате пара = 2 байта.

   • Если строка состоит из m серий, то код занимает 2m байт.

   • Лучший случай: одна серия (m=1). Тогда 222 байта против n байт → выигрыш ≈n/2 раз.

   • Худший случай: все серии длины 1 (m=n). Тогда код равен 2n байт (увеличение в 2 раза).

2. Сложность
   

   Алгоритмы кодирования и декодирования однопроходные:

   • Время: O(n).

   • Память: O(1) (стриминговая обработка).

3. Важные граничные случаи
   

   • Серии длиннее максимально допустимого ℓmax​ (например, 255) нужно разбивать на несколько пар.

   • Пустые данные (n=0) – корректный нулевой вывод.

   • Отсутствие повторов приводит к раздуванию. Смешанные схемы (литералы + повторы) это смягчают.

   • В маркерных схемах требуется экранирование самого маркера (иначе неоднозначность).

Правила корректной реализации

1. Фиксируйте формат до расчётов (сколько байтов под длину? есть ли заголовки? стартовый цвет для ч/б изображений? есть ли заголовок строки?).

2. Серии > ℓ_max делите на блоки ℓ_max,ℓ_max,…,остаток.

3. Инвариант кодера: «накапливай текущий символ и его длину; при смене символа или достижении ℓ_max ​ – выгружай пару».

4. Инвариант декодера: «читай пару → выпиши ℓ копий символа; счётчик длины не должен быть 0».

5. Проверяйте крайние случаи: начало/конец файла, единичные и очень длинные серии, присутствие маркера (для escape-схем).

Псевдокод (фиксированный формат: 1 байт длины + 1 байт символа)

1. Кодирование

RLE_ENCODE(bytes a[0..n-1]):

    if n == 0: return []

    out = []

    cur = a[0]; len = 1

    for i from 1 to n-1:

        if a[i] == cur and len < 255:

            len += 1

        else:

            out.append(len)      // 1 байт

            out.append(cur)      // 1 байт

            cur = a[i]

            len = 1

    // финальный сброс

    out.append(len)

    out.append(cur)

    return out

2. Декодирование

RLE_DECODE(bytes r[0..m-1]):  // m чётно

    out = []

    for j from 0 to m-1 step 2:

        len = r[j]

        sym = r[j+1]

        repeat out.append(sym) exactly len times

    return out

Методика решения типичных заданий ЕГЭ

1. Внимательно прочитать формат: как хранится длина (в битах/байтах, десятичной строкой и т. п.), как хранится символ, есть ли заголовок/служебные поля.

2. Разложить строку на серии и подсчитать их длины.

3. Учитывать ограничение на ℓ_max и при необходимости делить серию.

4. Посчитать объём по формуле формата (сумма по всем парам + служебные байты).

5. Сравнить с исходным объёмом и сделать вывод об эффективности.

Пять упражнений с подробным разбором

Упражнение 1. Простое кодирование текстовой строки

Условие. Дана строка ASCII AAAABBBCCDAA (12 байт). Используется фиксированный RLE-формат: каждая пара – 1 байт длины + 1 байт символа (макс. длина серии 255). Закодируйте строку и вычислите размер результата.

Решение. Разложение на серии:

• A×4, B×3, C×2, D×1, A×2.
  Код (в шестнадцатеричных байтах, символы в ASCII):

• 04 41 03 42 02 43 01 44 02 41.
  Размер: 5 пар × 2 байта = 10 байт. Исходник – 12 байт.
  Ответ. Код: 04 41 03 42 02 43 01 44 02 41, объём 10 байт (экономия ~16,7%).

Упражнение 2. Декодирование RLE-последовательности

Условие. Дана RLE-последовательность (байты в hex): 05 41 01 42 03 41 02 43. Восстановите исходную строку ASCII и укажите длину.

Решение. Пары:

• 05 41 → A×5 → AAAAA
• 01 42 → B×1 → B
• 03 41 → A×3 → AAA
• 02 43 → C×2 → CC
  Конкатенация: AAAAA + B + AAA + CC = AAAAABAAACC.
  Длина: 5 + 1 + 3 + 2 = 11.
  Ответ. AAAAABAAACC, 11 символов.

Упражнение 3. Строка пикселей (ч/б) и выгода RLE

Условие. Строка бинарного изображения длиной 1000 пикселей состоит из серий: 0×700, 1×50, 0×80, 1×170 (первый пиксель – ноль). Применяется специальный формат для ч/б-строк:

• 1 байт «стартовый цвет» (0 или 1);

• далее – последовательность длин серий по 1 байту (макс. 255), чередующихся по цвету, начиная с стартового.
  Подсчитайте размер RLE-строки и сравните с несжатым представлением (по 1 биту на пиксель).

Решение. Нужно разбить серии >255:

• 0×700 → 255, 255, 190 (три байта);

• 1×50 → 50 (один байт);

• 0×80 → 80 (один байт);

• 1×170 → 170 (один байт).
  Итого длины: 3 + 1 + 1 + 1 = 6 байт + 1 байт стартового цвета = 7 байт.
  Несжатый вид: 1000 бит = ⌈1000/8⌉=125 байт.
  Ответ. RLE: 7 байт против 125 байт (сжатие ~17,9×).

Упражнение 4. Худший случай для фиксированного RLE

Условие. Исходный файл – 10 000 байт, все соседние символы различны (ни одной серии длиной >1). Фиксированный формат: 1 байт длины + 1 байт символа. Найдите объём RLE-кода и коэффициент увеличения.

Решение. Каждая серия длиной 1 → 10 000 серий → 10 000 пар по 2 байта = 20 000 байт.
Коэффициент увеличения: 20000/10000=220000 / 10000 = 220000/10000=2.
Ответ. 20 000 байт (раздувание в 2 раза).

Упражнение 5. Маркерная схема и экранирование

Условие. Рассмотрим маркерный формат с ESC = 0xFF. Кодирование:

• FF <символ> <k> означает «повторить <символ> ровно <k> раз», где 1≤k≤255.

• Литералы копируются как есть, кроме байта FF, который должен экранироваться как FF FF 01 (один повтор FF).
  Закодируйте последовательность байтов (в hex): 41 41 41 41 FF FF 42 42 42 и укажите итоговый объём.

Решение.

• 41 повторяется 4 раза → FF 41 04.

• Далее два подряд FF: каждый FF как литерал кодируется FF FF 01, но поскольку их серия из двух, допустимо объединить: FF FF 02 (повтор FF два раза) – так короче.

• 42 повторяется 3 раза → FF 42 03.
  Итог: FF 41 04 FF FF 02 FF 42 03 (9 байт).
  Оригинал: 9 байт. На этом наборе – без выигрыша, но формат корректен и однозначен.
  Ответ. Код: FF 41 04 FF FF 02 FF 42 03, объём 9 байт (ни сжатия, ни раздувания).

Практические замечания и ошибки

• Не смешивайте формат! Если в условии ЕГЭ сказано «1 байт длины + 1 байт символа», нельзя трактовать длину как десятичную строку.

• Длины серии не могут быть 0; серия длиной 256 и более разбивается.

• Учёт служебных байтов (стартовый цвет, заголовок, выравнивание до байта) обязателен в подсчётах.

• Маркерные схемы требуют чётких правил экранирования, иначе декодирование неоднозначно.

• Смешанные данные (мало повторов) лучше кодировать «пакетным» RLE (литералы+повторы) – в учебных задачах это иногда явно прописано.

Заключение

RLE – базовый инструмент сжатия без потерь, опирающийся на простую идею замены повторов компактным описанием серии. Его сила – в прозрачности, однопроходности и предсказуемости; его слабость – в «шумных» данных. Для ЕГЭ важно уметь:

1. корректно разложить строку на серии;

2. строго следовать формату;

3. учитывать ограничения длины и служебные поля;

4. точно считать объёмы до/после кодирования;

5. понимать граничные случаи эффективности.

Освоив эти шаги, вы безошибочно решите типовые и усложнённые задания на RLE.