Кодирование длин серий
Материал из Википедии — свободной энциклопедии
Кодирование длин серий (Run-length encoding, RLE) — это очень простая форма сжатия данных в которой серии данных (т.е. последовательности в которых одно и то же значение данных встречается во многих последовательных элементах данных) сохраняются в виде одиночного значения данных и их количества, вместо оригинальной серии. Это часто используется на данных, которые содержат много таких серий; например, простые графические изображения, такие как иконки и графические рисунки.
Например, рассмотрим экран, содержащий простой чёрный текст на сплошном белом фоне. Здесь будет много серий белых пикселей в пустых местах, и много коротких серий чёрных пикселей в тексте. Допустим возьмём гипотетическую одиночную линию сканирования, с B представляющую чёрный пиксель и W обозначающую белый:
WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW
Если мы применим простое кодирование длин серий к верхней гипотетической линии сканирования, то получим следующее:
12WB12W3B24WB14W
Интерпретируем это как двенадцать W, одну B, двенадцать W, три B и т.д. Код таким образом представляет оригинальные 67 символов в виде только 16. Конечно, настоящий формат, который используется для хранения изображений является двоичным, нежели в виде символов ASCII как этот, но принцип остаётся тот же. Каждый файл с двоичными данными может быть сжат используя этот метод. спецификации на форматы файлов часто включают в себя повторяющиеся байты как пространство для выравнивания данных. Но несмотря на это, новейшие системы сжатия часто используют дефляцию или другие алгоритмы, базирующиеся на LZ77, которые также рассматривают последовательности строк символов (таких как BWWBWWBWWBWW).
Распространённые форматы для упаковки данных с помощью RLE включают в себя PackBits, PCX и ILBM.
Кодирование длин серий выполняет сжатие данных без потерь и хорошо подходит для иконных изображений использующих палитру. Но оно не работает на сплошных тоновых изображениях, таких как фотографии, но JPEG использует его очень эффективно на коэффициентах, которые остаются после трансформации и квантизации блоков изображения.
Данные, которые имеют длинные последовательные серии байт (такие как низкокачественные звуковые сэмплы) могут быть сжаты с помощью RLE после того, как к ним будет применено Дельта-кодирование.
[править] См. также
- Последовательность Конуэя
