ирование длин серий (англ. run-length encoding, RLE) или ирование повторов — алгоритм сжатия данных, заменяющий повторяющиеся символы (серии) на один символ и число его повторов. Серией называется последовательность, состоящая из нескольких одинаковых символов. При ировании (упаковке, сжатии) строка одинаковых символов, составляющих серию, заменяется строкой, содержащей сам повторяющийся символ и количество его повторов.
Рассмотрим изображение, содержащее текст чёрного цвета на сплошном белом фоне. При построчном чтении пикселей такого изображения будут встречаться серии белых (фон) и чёрных (буквы) пикселей. Буквой B обозначим чёрный пиксель, а буквой W — белый. Рассмотрим некую произвольную строку изображения длиной 47 символов:
WWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWWПосчитаем количество символов:
Итого найдено 5 серий. Заменим серии на число повторов и сам повторяющийся символ:
9W3B24W1B14WПолучилась последовательность из 18 символов. Исходная последовательность состояла из 47 символов. Данные были сжаты в 47/18≈2.61 раза.
Возьмём строку, состоящую из большого количества неповторяющихся символов:
ABCABCABCDDDFFFFFFПосле сжатия методом RLE такая строка будет выглядеть так:
1A1B1C1A1B1C1A1B1C3D6FИсходная строка состоит из 18 символов, а сжатая — из 22. Размер данных увеличился в 22/18≈1.22 раза.
Чтобы после сжатия размер данных не увеличивался, алфавит, в котором записаны длины серий, делят на две части (обычно равные). Например, алфавит целых чисел можно разделить на две части: положительные и отрицательные числа. Положительные числа используют для записи количества повторов одного символа, а отрицательные — для записи количества неодинаковых символов, следующих друг за другом.
Посчитаем символы с учётом вышесказанного:
Сжатая строка запишется в виде:
-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 после того, как к ним будет применено Дельта-ирование.
|
Имеется викиучебник по теме «Реализации алгоритмов/ирование длин серий» |
|---|
 Методы сжатия | |||||||
|---|---|---|---|---|---|---|---|
| Теория |
| ||||||
| Без потерь |
| ||||||
| Аудио |
| ||||||
| Изображения |
| ||||||
| Видео |
| ||||||
 | Для улучшения этой статьи желательно:
|