RLE и идея сжатия без потерь

Самый простой способ сжатия без потерь: заменить длинные цепочки одинаковых символов парой «символ + сколько раз».

RLE (Run-Length Encoding, кодирование длин серий) — метод сжатия без потерь, при котором подряд идущие одинаковые элементы заменяются одной парой: значение элемента и длина серии (сколько раз он повторяется).

Хаффман и префиксные коды экономят на частоте символов. RLE работает иначе — он экономит на повторах. Если в данных есть длинные одинаковые участки (фон картинки, поля документа, тишина в звуке), RLE сжимает их очень компактно и при этом мгновенно. Это древний, но до сих пор живой приём: он встроен в форматы BMP, PCX, TGA, в передачу факсов и как этап в более сложных схемах.

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

Идея проста. Возьмём строку:

AAAAABBBCCCCCCCD

В ней пять «A», три «B», шесть «C», одна «D». Запишем как пары «символ, количество»:

A5 B3 C6 D1

Было 15 символов — стало 8. Декодирование тривиально и точно: читаем пару, выводим символ нужное число раз. Никакая информация не теряется — это и есть сжатие без потерь: распаковка даёт ровно исходные данные, бит в бит.

Коэффициент сжатия считают как отношение объёмов:

$$ k = \frac{V_{\text{исходный}}}{V_{\text{сжатый}}} $$

Для примера выше (если пара занимает столько же, сколько символ) $k = 15/8 \approx 1{,}9$ — почти вдвое.

Когда RLE выигрывает, а когда вредит

RLE эффективен ровно там, где много длинных серий. Чёрно-белый скан текста: строка — это длинные участки белого с короткими чёрными штрихами букв. Однотонный фон логотипа. Иконки с заливками. Здесь RLE сжимает в разы.

А вот на данных без повторов RLE не просто бесполезен — он увеличивает объём. Возьмём строку ABCDEF: серий нет, каждая длины 1. Наивная запись:

A1 B1 C1 D1 E1 F1

Было 6 символов — стало 12 «единиц» данных. Объём вырос вдвое! Поэтому RLE применяют только к подходящим данным (изображения с заливками, факсы), а универсальные архиваторы используют его лишь как вспомогательный этап рядом с другими методами. Текст на естественном языке или уже сжатый файл (JPEG, MP3) RLE сжать почти не сможет.

Как это работает: реализация на Python

Напишем пару функций — кодер и декодер — и проверим, что распаковка восстанавливает исходную строку (свойство обратимости).

def rle_encode(s):
    if not s:
        return ""
    result = []
    prev = s[0]
    count = 1
    for ch in s[1:]:
        if ch == prev:
            count += 1
        else:
            result.append(prev + str(count))
            prev = ch
            count = 1
    result.append(prev + str(count))
    return "".join(result)

def rle_decode(code):
    result = []
    i = 0
    while i < len(code):
        ch = code[i]
        i += 1
        num = ""
        while i < len(code) and code[i].isdigit():
            num += code[i]
            i += 1
        result.append(ch * int(num))
    return "".join(result)

data = "AAAAABBBCCCCCCD"
encoded = rle_encode(data)
decoded = rle_decode(encoded)

print("Исходная :", data, "(", len(data), "симв.)")
print("Сжатая   :", encoded, "(", len(encoded), "симв.)")
print("Распаковка:", decoded)
print("Совпадает с исходной:", decoded == data)

Вывод:

Исходная : AAAAABBBCCCCCCD ( 15 симв.)
Сжатая   : A5B3C6D1 ( 8 симв.)
Распаковка: AAAAABBBCCCCCCD
Совпадает с исходной: True

Последняя строка — главная проверка любого сжатия без потерь: декодированные данные обязаны точно совпасть с исходными. Проверим, что на «плохих» данных объём растёт:

def rle_encode(s):
    if not s:
        return ""
    out, prev, count = [], s[0], 1
    for ch in s[1:]:
        if ch == prev:
            count += 1
        else:
            out.append(prev + str(count))
            prev, count = ch, 1
    out.append(prev + str(count))
    return "".join(out)

for data in ["WWWWWWWWWWWW", "ABCDEF"]:
    enc = rle_encode(data)
    print(data, "->", enc, "| было", len(data), "стало", len(enc))

Вывод:

WWWWWWWWWWWW -> W12 | было 12 стало 3
ABCDEF -> A1B1C1D1E1F1 | было 6 стало 12

Видно обе ситуации: длинная серия из 12 символов ужалась до 3, а данные без повторов раздулись вдвое.

Связь с форматами

RLE — не учебная игрушка, а рабочий механизм. В формате BMP есть режимы RLE4 и RLE8: пиксели кодируются парами «количество, цвет», что отлично сжимает скриншоты с большими одноцветными зонами. Факс (стандарты Group 3/4) передаёт чёрно-белую страницу как длины чёрных и белых серий вдоль строки — именно поэтому факс эффективен на тексте. В PCX и TGA RLE — основной способ сжатия. А в архиваторах и в PNG он часто работает как первый, подготовительный шаг перед более мощными методами вроде Хаффмана.

Частые ошибки

• Думают, что RLE сжимает что угодно. На данных без повторов он раздувает объём — это фундаментальное свойство, а не баг.
• Забывают про обратимость. Сжатие без потерь обязано восстанавливать исходник бит в бит; проверяйте условием decoded == data.
• Путают с сжатием с потерями. RLE ничего не «выбрасывает» — в отличие от JPEG или MP3, он не теряет ни байта.
• Неверно парсят длину при декодировании. Если длина серии многозначная (например A12), нужно читать все подряд идущие цифры, а не одну.

Итоги

• RLE заменяет серию одинаковых элементов парой «значение + длина серии».
• Это сжатие без потерь: распаковка восстанавливает исходные данные точно, бит в бит.
• Выигрывает на длинных сериях (сканы, заливки, факсы), вредит на данных без повторов — там объём растёт.
• Коэффициент сжатия $k = V_{\text{исх}} / V_{\text{сжат}}$.
• Применяется в BMP (RLE4/RLE8), факсах (Group 3/4), PCX, TGA и как подготовительный этап в архиваторах и PNG.
• Обратимость — обязательное свойство любого алгоритма сжатия без потерь.