stringtranslate.com

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

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

RLE может также относиться к раннему формату графических файлов, поддерживаемому CompuServe для сжатия черно-белых изображений, который был повсеместно вытеснен более поздним форматом Graphics Interchange Format (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 имеет пространственную сложность ⁠ ⁠ , где n — размер входных данных.

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

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

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

Реализация на Python

Импорт и вспомогательные функции
из  itertools  импорт  повторить ,  сжать ,  сгруппироватьdef  ilen ( iterable ): """  Возвращает количество элементов в итерируемом объекте.  >>> ilen(x for x in range(1000000) if x % 3 == 0)  333334  """  # использование zip() для обертывания входных данных кортежами из 1, которые compress() считывает как истинные значения.  return  sum ( compress ( repeat ( 1 ),  zip ( iterable )))
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): длина итерируемого g для k , g in groupby ( iterable ) )

[7]

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

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

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

Реализация на Python

Импорт
из  цепочки импорта itertools  , повтор , пакетный   
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 и т. д. В данных, где серии встречаются реже, это может значительно улучшить степень сжатия.

Еще один вопрос — применение дополнительных алгоритмов сжатия. Даже при извлечении серий частоты различных символов могут быть большими, что позволяет выполнить дальнейшее сжатие; однако, если длины серий записаны в файле в местах, где они возникли, наличие этих чисел прерывает нормальный поток и затрудняет сжатие. Чтобы преодолеть это, некоторые кодировщики длин серий отделяют данные и экранирующие символы от длин серий, так что их можно обрабатывать независимо. Для данных примера это приведет к двум выводам: строке " WWBWWBBWWBWW" и числам ( 12,12,3,24,14).

Варианты

Смотрите также

Ссылки

  1. ^ Робинсон, AH; Черри, C. (1967). "Результаты прототипа схемы сжатия полосы пропускания телевидения". Труды IEEE . 55 (3). IEEE : 356–364. doi :10.1109/PROC.1967.5493.
  2. ^ "Run Length Encoding Patents". Internet FAQ Consortium. 21 марта 1996 г. Получено 14 июля 2019 г.
  3. ^ "Метод и система сжатия и восстановления данных". Google Patents . 7 августа 1984 г. Получено 14 июля 2019 г.
  4. ^ "Метод записи данных". Google Patents . 8 августа 1983 г. Получено 14 июля 2019 г.
  5. ^ Данн, Кристофер (1987). «Улыбнитесь! Вы на RLE!» (PDF) . The Transactor . 7 (6). Transactor Publishing : 16–18 . Получено 06.12.2015 .
  6. ^ Рекомендация T.45 (02/00): Кодирование цвета по длине серии. Международный союз электросвязи . 2000. Получено 06.12.2015 .
  7. ^ ab "more-itertools 10.4.0 documentation". Август 2024 г.

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