Кодирование длин серий
Материал из Википедии — свободной энциклопедии
Кодирование длин серий (англ. Run-length encoding, RLE) или Кодирование повторов — это очень простой алгоритм сжатия данных, который оперирует сериями данных, то есть последовательностями, в которых один и тот же символ встречается несколько раз подряд. При кодировании строка одинаковых символов, составляющих серию, заменяется строкой, которая содержит сам повторяющийся символ и количество его повторов.
[править] Пример использования
Рассмотрим изображение, содержащий простой чёрный текст на сплошном белом фоне. Здесь будет много серий белых пикселей в пустых местах, и много коротких серий чёрных пикселей в тексте. В качестве примера приведена некая произвольная строка изображения в черно-белом варианте. Здесь B представляет чёрный пиксель, а W обозначает белый:
WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW
Если мы применим простое кодирование длин серий к этой строке, то получим следующее:
12WB12W3B24WB14W
Последняя запись интерпретируется как "двенадцать W", "одна B", "двенадцать W", "три B" и т. д. Таким образом, код представляет исходные 67 символов в виде всего лишь 16.
Конечно, кодирование, которое используется для хранения изображений, оперирует с двоичными данными, а не с символами ASCII, как в рассмотренном примере, однако принцип остаётся тот же.
[править] Применение
Очевидно, что такое кодирование эффективно для данных, содержащих большое количество серий, например, для простых графических изображений, таких как иконки и графические рисунки. Однако это кодирование плохо подходит для изображений с плавным переходом тонов, таких как фотографии. Несмотря на это, JPEG довольно эффективно его использует на коэффициентах, которые остаются после преобразования и квантования блоков изображения.
Распространённые форматы для упаковки данных с помощью RLE включают в себя PackBits, PCX и ILBM.
Методом кодирования длин серий могут быть сжаты произвольные файлы с двоичными данными, поскольку спецификации на форматы файлов часто включают в себя повторяющиеся байты в области выравнивания данных. Тем не менее, современные системы сжатия (например, DEFLATE) чаще используют алгоритмы на основе LZ77, которые являются обобщением метода кодирования длин серий и оперируют с последовательностями символов вида "BWWBWWBWWBWW".
Звуковые данные, которые имеют длинные последовательные серии байт (такие как низкокачественные звуковые сэмплы) могут быть сжаты с помощью RLE после того, как к ним будет применено Дельта-кодирование.
