Из Википедии, свободной энциклопедии
Перейти к навигации Перейти к поиску
Не путать с ограничением по длине .

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

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

Пример [ править ]

Рассмотрим экран, содержащий простой черный текст на сплошном белом фоне. Будет много длинных серий белых пикселей в пустом пространстве и много коротких серий черных пикселей в тексте. Гипотетическая линия сканирования , где B представляет черный пиксель, а W представляет белый, может выглядеть следующим образом:

WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW

С помощью алгоритма сжатия данных с кодированием длин серий (RLE), примененного к приведенной выше гипотетической строке развертки, его можно визуализировать следующим образом:

12W1B12W3B24W1B14W

Это можно интерпретировать как последовательность двенадцати Ws, один B, двенадцать Ws, три Bs , и т.д., и представляет исходные 67 символов только 18. В то время как фактический формат , используемый для хранения изображений , как правило , двоичная , а не ASCII символов так принцип остается прежним. С помощью этого метода можно сжимать даже файлы двоичных данных; Спецификации формата файла часто диктуют повторение байтов в файлах в качестве места заполнения. Однако более новые методы сжатия, такие как DEFLATE, часто используют алгоритмы на основе LZ77 , обобщение кодирования длин серий, которое может использовать преимущества прогонов строк символов (например, BWWBWWBWWBWW).

Кодирование длин серий может быть выражено несколькими способами, чтобы учесть свойства данных, а также дополнительные алгоритмы сжатия. Например, один популярный метод кодирует длины серий только для серий из двух или более символов, используя символ «escape» для идентификации прогонов или используя сам символ как escape, так что каждый раз, когда символ появляется дважды, он обозначает прогон. В предыдущем примере это дало бы следующее:

WW12BWW12BB3WW24BWW14

Это можно интерпретировать как серию из двенадцати W, B, серию из двенадцати W, серию из трех B и т. Д. В данных, где прогоны реже, это может значительно улучшить степень сжатия.

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

История и приложения [ править ]

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

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

См. Также [ править ]

Ссылки [ править ]

  1. ^ Робинсон, AH; Черри, К. (1967). «Результаты прототипа схемы сжатия полосы пропускания телевидения». Труды IEEE . IEEE . 55 (3): 356–364. DOI : 10.1109 / PROC.1967.5493 .
  2. ^ "Патенты на кодирование длины тиража" . Консорциум часто задаваемых вопросов в Интернете . 21 марта 1996 . Проверено 14 июля 2019 .
  3. ^ «Метод и система сжатия и восстановления данных» . Патенты Google . 7 августа 1984 . Проверено 14 июля 2019 .
  4. ^ «Метод записи данных» . Патенты Google . 8 августа 1983 . Проверено 14 июля 2019 .
  5. ^ Данн, Кристофер (1987). «Улыбнись! Ты на РЛЭ!» (PDF) . Оператор . Издательство Transactor . 7 (6): 16–18 . Проверено 6 декабря 2015 .
  6. ^ Рекомендация T.45 (02/00): Кодирование цвета по длине прогона . Международный союз электросвязи . 2000 . Проверено 6 декабря 2015 .

Внешние ссылки [ править ]

  • Кодирование длин серий, реализованное на разных языках программирования (на Rosetta Code )