Кодирование длин серий ( RLE ) — это форма сжатия данных без потерь , при которой серии данных (последовательности, в которых одно и то же значение данных встречается во многих последовательных элементах данных) сохраняются как одно значение и количество данных, а не как исходный цикл. . Это наиболее эффективно для данных, содержащих множество таких прогонов, например простых графических изображений, таких как значки, штриховые рисунки, « Игра жизни Конвея » и анимация. Для файлов, у которых не так много прогонов, RLE может увеличить размер файла.
RLE также может использоваться для обозначения раннего формата графических файлов, поддерживаемого CompuServe для сжатия черно-белых изображений, но он был широко вытеснен их более поздним форматом обмена графикой (GIF). RLE также относится к малоиспользуемому формату изображения в Windows 3.x с расширением rle, которое представляет собой растровое изображение с кодировкой по длине, используемое для сжатия стартового экрана Windows 3.x.
Рассмотрим экран, содержащий простой черный текст на сплошном белом фоне. В пустом пространстве будет много длинных белых пикселей , а в тексте — множество коротких черных пикселей. Гипотетическая линия сканирования , где B представляет собой черный пиксель, а W — белый, может выглядеть следующим образом:
WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW С помощью алгоритма сжатия данных кодирования серий (RLE), примененного к приведенной выше гипотетической строке сканирования, ее можно отобразить следующим образом:
12W1B12W3B24W1B14W
Это можно интерпретировать как последовательность из двенадцати W, одной B, двенадцати W, трех B и т. д., и она представляет исходные 67 символов всего лишь из 18. Хотя фактический формат, используемый для хранения изображений, обычно является двоичным, а не символами ASCII . в этом случае принцип остается прежним. Этим методом можно сжать даже файлы двоичных данных; спецификации формата файла часто диктуют повторяющиеся байты в файлах в качестве места для заполнения. Однако новые методы сжатия, такие как DEFLATE, часто используют алгоритмы на основе LZ77 — обобщение кодирования по длинам серий, которое может использовать преимущества серий строк символов (например, BWWBWWBWWBWW).
Кодирование длины серии может быть выражено несколькими способами для учета свойств данных, а также дополнительных алгоритмов сжатия. Например, один популярный метод кодирует длину серий только для серий, состоящих из двух или более символов, используя символ «escape» для идентификации серий или используя сам символ в качестве escape-символа, так что каждый раз, когда символ появляется дважды, он обозначает серию. В предыдущем примере это дало бы следующее:
WW12BWW12BB3WW24BWW14Это будет интерпретироваться как серия из двенадцати W, серия B, серия из двенадцати W, серия из трех B и т. д. В данных, где серии выполняются реже, это может значительно улучшить степень сжатия.
Еще одним вопросом является применение дополнительных алгоритмов сжатия. Даже при извлечении серий частоты различных символов могут быть большими, что позволяет осуществлять дальнейшее сжатие; однако, если длины серий записаны в файле в тех местах, где они произошли, наличие этих чисел прерывает нормальный поток и затрудняет сжатие. Чтобы преодолеть эту проблему, некоторые кодировщики длин серий отделяют данные и escape-символы от длин серий, чтобы их можно было обрабатывать независимо. Для данных примера это приведет к двум выходным данным: строке « WWBWWBBWWBWW» и числам ( 12,12,3,24,14).
Схемы кодирования длин серий (RLE) использовались при передаче аналоговых телевизионных сигналов еще в 1967 году. [1] В 1983 году кодирование длин серий было запатентовано компанией Hitachi . [2] [3] [4] RLE особенно хорошо подходит для растровых изображений на основе палитры , таких как компьютерные значки , и был популярным методом сжатия изображений в ранних онлайн-сервисах, таких как CompuServe, до появления более сложных форматов, таких как GIF . [5] Он не очень хорошо работает с изображениями с непрерывным тоном, такими как фотографии, хотя JPEG использует его для коэффициентов, которые остаются после преобразования и квантования блоков изображения.
Общие форматы для закодированных данных включают Truevision TGA , PackBits (от Apple, используется в MacPaint ), PCX и ILBM . Международный союз электросвязи также описывает стандарт кодирования серийных цветов для факсимильных аппаратов, известный как T.45. [6] Стандарт, который объединяется с другими методами в модифицированное кодирование Хаффмана , [ нужна ссылка ] относительно эффективен, поскольку большинство отправляемых по факсу документов обычно представляют собой пустое пространство с редкими прерываниями черного цвета.