Войти
Кодирование длин серий ( RLE) является одной из форм без потерь сжатия данных, в котором выполняется из данных (последовательностей, в которых такое же значение данных происходит во многих последовательных элементах данных) хранятся в виде одного значения данных и подсчет, а не в качестве первоначального запуска. Это наиболее эффективно для данных, содержащих множество таких прогонов, например простых графических изображений, таких как значки, линейные рисунки, «Игра жизни» Конвея и анимации. Для файлов, которые не имеют большого количества запусков, RLE может увеличить размер файла.
RLE также может использоваться для обозначения раннего формата графического файла, поддерживаемого CompuServe для сжатия черно-белых изображений, но был широко вытеснен их более поздним форматом обмена графическими данными (GIF). RLE также относится к малоиспользуемому формату изображения в Windows 3.x с расширением rle, которое представляет собой растровое изображение с кодировкой длин серий, используемое для сжатия стартового экрана Windows 3.x.
Рассмотрим экран, содержащий простой черный текст на сплошном белом фоне над гипотетической линией сканирования, его можно отобразить следующим образом:
12W1B12W3B24W1B14W2WЭто можно интерпретировать как последовательность двенадцати Ws, один B, двенадцать Ws, три Bs, и т.д., и представляет исходные 67 символов только 18. В то время как фактический формат, используемый для хранения изображений, как правило, двоичная, а не ASCII символов так принцип остается прежним. С помощью этого метода можно сжимать даже файлы двоичных данных; Спецификации формата файла часто диктуют повторение байтов в файлах в качестве места для заполнения. Однако более новые методы сжатия, такие как DEFLATE, часто используют алгоритмы на основе LZ77, обобщение кодирования длин серий, которое может использовать преимущества прогонов строк символов (например, BWWBWWBWWBWW).
Кодирование длин серий может быть выражено несколькими способами, чтобы учесть свойства данных, а также дополнительные алгоритмы сжатия. Например, один популярный метод кодирует длины серий только для серий из двух или более символов, используя символ «escape» для идентификации прогонов или используя сам символ как escape, так что каждый раз, когда символ появляется дважды, он обозначает прогон. В предыдущем примере это дало бы следующее:
WW12BWW12BB3WW24BWW14Это можно интерпретировать как серию из двенадцати W, B, серию из двенадцати W, серию из трех B и т. Д. В данных, где прогоны реже, это может значительно улучшить степень сжатия.
Еще один вопрос - применение дополнительных алгоритмов сжатия. Даже с извлеченными сериями частота различных символов может быть большой, что позволяет производить дальнейшее сжатие; однако, если длины прогонов записаны в файле в тех местах, где выполнялись прогоны, наличие этих чисел прерывает нормальный поток и затрудняет сжатие. Чтобы преодолеть это, некоторые кодеры длин серий отделяют символы данных и escape-символы от длин серий, так что они могут обрабатываться независимо. Для данных примера это приведет к двум выходным данным: строке " WWBWWBBWWBWW" и числам ( 12,12,3,24,14).
Схемы кодирования длин серий (RLE) использовались при передаче аналоговых телевизионных сигналов еще в 1967 году. В 1983 году Hitachi запатентовала кодирование длин серий. RLE особенно хорошо подходит для растровых изображений на основе палитры, таких как значки компьютеров, и был популярным методом сжатия изображений в ранних онлайн-сервисах, таких как CompuServe, до появления более сложных форматов, таких как GIF. Он плохо работает с изображениями с непрерывным тоном, такими как фотографии, хотя JPEG использует его для коэффициентов, которые остаются после преобразования и квантования блоков изображения.
Общие форматы для длин серий кодируемых данных включают Truevision TGA, Packbits, PCX и ILBM. Международный союз электросвязи также описывает стандарт для кодирования по длине прогона цвета для факсимильных машин, известных как T.45. Стандарт, который в сочетании с другими методами в модифицированное кодировании Хаффмана, является относительно эффективным, поскольку большинство факсимильных документов обычно белого пространство, с редкими перерывами черными.
