Кодирование длин серий
Кодирование длин серий (англ. run-length encoding, RLE) или кодирование повторов — алгоритм сжатия данных, заменяющий повторяющиеся символы (серии) на один символ и число его повторов. Серией называется последовательность, состоящая из нескольких одинаковых символов. При кодировании (упаковке, сжатии) строка одинаковых символов, составляющих серию, заменяется строкой, содержащей сам повторяющийся символ и количество его повторов.
Пример использования
Рассмотрим изображение, содержащее текст чёрного цвета на сплошном белом фоне. При построчном чтении пикселей такого изображения будут встречаться серии белых (фон) и чёрных (буквы) пикселей. Буквой B обозначим чёрный пиксель, а буквой W — белый. Рассмотрим некую произвольную строку изображения длиной 51 символ:
WWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW
Посчитаем количество символов:
- 4 символа «B»;
- 47 символов «W».
Итого найдено 5 серий. Заменим серии на число повторов и сам повторяющийся символ:
9W3B24W1B14W
Получилась последовательность из 12 символов. Исходная последовательность состояла из 51 символа. Данные были сжаты в 51/12≈4.25 раза.
Возьмём строку, состоящую из большого количества неповторяющихся символов:
ABCABCABCDDDFFFFFF
После сжатия методом RLE такая строка будет выглядеть так:
1A1B1C1A1B1C1A1B1C3D6F
Исходная строка состоит из 18 символов, а сжатая — из 22. Размер данных увеличился в 22/18≈1.22 раза.
Чтобы после сжатия размер данных не увеличивался, алфавит, в котором записаны длины серий, делят на две части (обычно равные). Например, алфавит целых чисел можно разделить на две части: положительные и отрицательные числа. Положительные числа используют для записи количества повторов одного символа, а отрицательные — для записи количества неодинаковых символов, следующих друг за другом.
Посчитаем символы с учётом вышесказанного:
- сначала друг за другом следуют 9 не одинаковых символов: «ABCABCABC»;
- затем записаны 3 символа «D»;
- наконец записаны 6 символов «F».
Сжатая строка запишется в виде:
-9ABCABCABC3D6F
Исходная строка состоит из 18 символов, а сжатая — из 15. Размер данных уменьшился в 18/15=1.2 раза.
Допустим, реализация метода RLE для записи длин серий (для подсчёта количества символов) использует переменную целочисленного типа со знаком «signed char». В такую переменную можно записать числа от -128 до 127 включительно. Как же быть, если длина серии равна 128 символам и более? В этом случае серию разделяют на части так, чтобы длина части не превышала 127 символов. Например, серия, состоящая из 256 символов «A», будет закодирована следующей строкой (256=127+127+2):
127A127A2A
Запись на некотором языке программирования алгоритма RLE с учётом этих ограничений нетривиальна.
Конечно, кодирование, которое используется для хранения изображений, оперирует с двоичными данными, а не с символами ASCII, как в рассмотренных примерах, однако принцип остаётся тем же.
Применение
Очевидно, что такое кодирование эффективно для данных, содержащих большое количество серий, например, для простых графических изображений, таких как иконки и графические рисунки. Однако это кодирование плохо подходит для изображений с плавным переходом тонов, таких как фотографии.
Распространённые форматы для упаковки данных с помощью RLE включают в себя PackBits, PCX и ILBM.
Методом кодирования длин серий могут быть сжаты произвольные файлы с двоичными данными, поскольку спецификации на форматы файлов часто включают в себя повторяющиеся байты в области выравнивания данных. Тем не менее, современные системы сжатия (например, Deflate) чаще используют алгоритмы на основе LZ77, которые являются обобщением метода кодирования длин серий и оперируют с последовательностями символов вида «BWWBWWBWWBWW».
Звуковые данные, которые имеют длинные последовательные серии байт (такие как низкокачественные звуковые семплы) могут быть сжаты с помощью RLE после того, как к ним будет применено Дельта-кодирование.
Примечания
Ссылки
- Run-length encoding - Rosetta Code (англ.) Rosetta Code