Кодирование длины серии

Кодирование длин серий ( RLE ) — это форма сжатия данных без потерь , при которой серии данных (последовательные вхождения одного и того же значения данных) сохраняются как одно вхождение этого значения данных и количество его последовательных вхождений, а не как оригинальный пробег. В качестве воображаемого примера концепции при кодировании изображения, составленного из цветных точек, последовательность «зеленый зеленый зеленый зеленый зеленый зеленый зеленый зеленый зеленый» сокращается до «зеленый x 9». Это наиболее эффективно для данных, содержащих множество таких прогонов, например простых графических изображений, таких как значки, штриховые рисунки, игры и анимация. Для файлов, которые имеют небольшое количество запусков, кодирование их с помощью RLE может увеличить размер файла.

RLE может также относиться, в частности, к раннему формату графических файлов, поддерживаемому CompuServe для сжатия черно-белых изображений, который был широко вытеснен их более поздним форматом обмена графикой (GIF).

RLE также относится к малоиспользуемому формату изображений в Windows 3.x , который сохраняется с расширением файла. rle; это растровое изображение с кодировкой по длине, и этот формат использовался для стартового экрана Windows 3.x.

История и приложения

Схемы серийного кодирования (RLE) использовались при передаче аналоговых телевизионных сигналов еще в 1967 году. ^[1] длин серий запатентовала В 1983 году Hitachi кодирование . ^[2]^[3]^[4] RLE особенно хорошо подходит для растровых изображений на основе палитры (которые используют относительно мало цветов), таких как компьютерные значки , и был популярным методом сжатия изображений в ранних онлайн-сервисах, таких как CompuServe, до появления более сложных форматов, таких как GIF . ^[5] Он не очень хорошо работает с изображениями с непрерывными тонами (в которых используется очень много цветов), такими как фотографии, хотя JPEG использует его для коэффициентов, которые остаются после преобразования и квантования блоков изображения.

Общие форматы для закодированных данных включают Truevision TGA , PackBits (от Apple, используется в MacPaint ), PCX и ILBM . Международный союз электросвязи также описывает стандарт кодирования серийных цветов для факсимильных аппаратов, известный как T.45. ^[6] Этот стандарт цветового кодирования факсов, который наряду с другими методами включен в модифицированное кодирование Хаффмана , ^{[ нужна ссылка ]} относительно эффективен, поскольку большинство документов, отправляемых по факсу, состоят в основном из пустого пространства с редкими перерывами в черном цвете.

Алгоритм

RLE имеет пространственную сложность ⁠ $O(n)$ ⁠ , где $n$ — размер входных данных.

Алгоритм кодирования

Кодирование длины серии сжимает данные за счет уменьшения физического размера повторяющейся строки символов. Этот процесс включает преобразование входных данных в сжатый формат путем идентификации и подсчета последовательных вхождений каждого символа. Шаги следующие:

Пройдите входные данные.
Подсчитайте количество последовательных повторяющихся символов (длину серии).
Сохраните символ и длину его пробега.

Реализация Python

Импорт и вспомогательные функции

def rle_encode(iterable, *, length_first=True):    """    >>> "".join(rle_encode("AAAABBBCCDAA"))    '4A3B2C1D2A'    >>> "".join(rle_encode("AAAABBBCCDAA", length_first=False))    'A4B3C2D1A2'    """    return (        f"{ilen(g)}{k}" if length_first else f"{k}{ilen(g)}" # ilen(g): length of iterable g        for k, g in groupby(iterable)    )

^[7]

Алгоритм декодирования

Процесс декодирования включает восстановление исходных данных из закодированного формата путем повторения символов в соответствии с их количеством. Шаги следующие:

Пройдите по закодированным данным.
Для каждой пары счетчик-символ повторите подсчет символов несколько раз.
Добавьте эти символы в результирующую строку.

Реализация Python

Импорт

def rle_decode(iterable, *, length_first=True):    """    >>> "".join(rle_decode("4A3B2C1D2A"))    'AAAABBBCCDAA'    >>> "".join(rle_decode("A4B3C2D1A2", length_first=False))    'AAAABBBCCDAA'    """    return chain.from_iterable(        repeat(b, int(a)) if length_first else repeat(a, int(b))        for a, b in batched(iterable, 2)    )

^[7]

Пример

Рассмотрим экран, содержащий простой черный текст на сплошном белом фоне. В пустом пространстве будет много длинных белых пикселей , а в тексте — множество коротких черных пикселей. Гипотетическая линия сканирования , где 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: этот метод обрабатывает данные по одной строке, сканируя слева направо. Обычно он используется при сжатии изображений. Другие варианты этого метода включают сканирование данных по вертикали, диагонали или по блокам.
RLE с потерями: в этом варианте некоторые биты намеренно отбрасываются во время сжатия (часто путем установки одного или двух значащих битов каждого пикселя в 0). Это приводит к более высокой степени сжатия при минимальном влиянии на визуальное качество изображения.
Адаптивный RLE: использует различные схемы кодирования в зависимости от длины прогона для оптимизации степени сжатия. Например, для коротких прогонов может использоваться другой формат кодирования, чем для длинных.

См. также

Последовательность Колакоски
Последовательность «посмотри и скажи»
Сравнение форматов графических файлов
Кодирование Голомба
Преобразование Берроуза – Уиллера
Рекурсивная индексация
Продолжительность ограничена
Индекс растрового изображения
Нотация Форсайта-Эдвардса , которая использует кодирование длины серии для пустых мест в шахматных позициях.
СДУТЬ
Свертка
Кодирование Хаффмана
Арифметическое кодирование

Ссылки

^ Робинсон, АХ; Черри, К. (1967). «Результаты прототипа схемы сжатия телевизионной полосы пропускания». Труды IEEE . 55 (3). IEEE : 356–364. дои : 10.1109/PROC.1967.5493 .
^ «Патенты на кодирование длин серий» . Консорциум часто задаваемых вопросов в Интернете. 21 марта 1996 года . Проверено 14 июля 2019 г.
^ «Метод и система сжатия и восстановления данных» . Гугл Патенты . 7 августа 1984 года . Проверено 14 июля 2019 г.
^ «Метод записи данных» . Гугл Патенты . 8 августа 1983 года . Проверено 14 июля 2019 г.
^ Данн, Кристофер (1987). «Улыбнитесь! Вы на RLE!» (PDF) . Транзактор . 7 (6). Издательство Transactor : 16–18 . Проверено 6 декабря 2015 г.
^ Рекомендация T.45 (02/00): Цветовое кодирование по длинам серий . Международный союз электросвязи . 2000 . Проверено 6 декабря 2015 г.
^ Перейти обратно: ^а ^б https://more-itertools.readthedocs.io/en/stable/_modules/more_itertools/more.html#run_length

Внешние ссылки

Кодирование длин серий, реализованное на разных языках программирования (в Rosetta Code ).
Библиотека кодирования длины пролета с одним заголовком наименьшая из возможных реализаций (около 20 SLoC) в ANSI C. FOSS, совместимая с Truevision TGA , также поддерживает 8, 16, 24 и 32-битные элементы.

[robinson-1] Робинсон, АХ; Черри, К. (1967). «Результаты прототипа схемы сжатия телевизионной полосы пропускания». Труды IEEE . 55 (3). IEEE : 356–364. дои : 10.1109/PROC.1967.5493 .

[2] «Патенты на кодирование длин серий» . Консорциум часто задаваемых вопросов в Интернете. 21 марта 1996 года . Проверено 14 июля 2019 г.

[3] «Метод и система сжатия и восстановления данных» . Гугл Патенты . 7 августа 1984 года . Проверено 14 июля 2019 г.

[4] «Метод записи данных» . Гугл Патенты . 8 августа 1983 года . Проверено 14 июля 2019 г.

[transactor-5] Данн, Кристофер (1987). «Улыбнитесь! Вы на RLE!» (PDF) . Транзактор . 7 (6). Издательство Transactor : 16–18 . Проверено 6 декабря 2015 г.

[itu-6] Рекомендация T.45 (02/00): Цветовое кодирование по длинам серий . Международный союз электросвязи . 2000 . Проверено 6 декабря 2015 г.

[more-itertools-7] Перейти обратно: ^а ^б https://more-itertools.readthedocs.io/en/stable/_modules/more_itertools/more.html#run_length

[1]

[2]

[3]

[4]

[5]

[6]

[7]