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

Кодирование длин серий (англ. run-length encoding, RLE) или кодирование повторов — алгоритм сжатия данных, заменяющий повторяющиеся символы (серии) на один символ и число его повторов. Серией называется последовательность, состоящая из нескольких одинаковых символов. При кодировании (упаковке, сжатии) строка одинаковых символов, составляющих серию, заменяется строкой, содержащей сам повторяющийся символ и количество его повторов.

Пример использования

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

WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW

Посчитаем количество повторяющихся символов:

1. 12 символов «W»;
2. 1 символ «B»;
3. 12 символов «W»;
4. 3 символа «B»;
5. 24 символа «W»;
6. 1 символ «B»;
7. 14 символов «W».

Итого найдено 7 серий. Заменим серии на число повторов и сам повторяющийся символ:

12W1B12W3B24W1B14W

Получилась последовательность из 18 символов. Исходная последовательность состояла из 67 символов. Данные были сжаты в 67/18≈3.72 раза.

Возъмём строку, состоящую из большого количества неповторяющихся символов:

ABCABCABCDDDFFFFFF

После сжатия методом RLE такая строка будет выглядеть так:

1A1B1C1A1B1C1A1B1C3D6F

Исходная строка состоит из 18 символов, а сжатая — из 22. Размер данных увеличился в 22/18≈1.22 раза.

Чтобы после сжатия размер данных не увеличивался, алфавит, в котором записаны длины серий, делят на две части (обычно равные). Например, алфавит целых чисел можно разделить на две части: положительные и отрицательные числа. Положительные числа используют для записи количества повторов одного символа, а отрицательные — для записи количества неодинаковых символов, следующих друг за другом.

Посчитаем символы с учётом вышесказанного:

• сначала друг за другом следуют 9 не одинаковых символов: «ABCABCABC»;
• затем записаны 3 символа «D»;
• наконец записаны 6 символов «F».

Сжатая строка запишется в виде:

-9ABCABCABC3D6F

Исходная строка состоит из 18 символов, а сжатая — из 15. Размер данных уменьшился в 18/15=1.2 раза.

Допустим, реализация метода RLE для записи длин серий (для подсчёта количества символов) использует переменную целочисленного типа со знаком «signed char». В такую переменную можно записать числа от -128 до 127 включительно. Как же быть, если длина серии равна 128 символам и более? В этом случае серию разделяют на части так, чтобы длина части не превышала 127 символов. Например, серия, состоящая из 256 символов «A», будет закодирована следующей строкой (256=127+127+2):

127A127A2A

Запись на некотором языке программирования алгоритма RLE с учётом этих ограничений нетривиальна.

Конечно, кодирование, которое используется для хранения изображений, оперирует с двоичными данными, а не с символами ASCII, как в рассмотренных примерах, однако принцип остаётся тем же.

Применение

Очевидно, что такое кодирование эффективно для данных, содержащих большое количество серий, например, для простых графических изображений, таких как иконки и графические рисунки. Однако это кодирование плохо подходит для изображений с плавным переходом тонов, таких как фотографии.

Распространённые форматы для упаковки данных с помощью RLE включают в себя PackBits, PCX и ILBM.

Методом кодирования длин серий могут быть сжаты произвольные файлы с двоичными данными, поскольку спецификации на форматы файлов часто включают в себя повторяющиеся байты в области выравнивания данных. Тем не менее, современные системы сжатия (например, DEFLATE) чаще используют алгоритмы на основе LZ77, которые являются обобщением метода кодирования длин серий и оперируют с последовательностями символов вида «BWWBWWBWWBWW».

Звуковые данные, которые имеют длинные последовательные серии байт (такие как низкокачественные звуковые семплы) могут быть сжаты с помощью RLE после того, как к ним будет применено Дельта-кодирование.

Полезные ссылки

• [rle.codeplex.com/ RLE утилита по кодированию/декодированию на CodePlex, видоизмененный алгоритм RLE на языке C#, GNU GPL v2 лицензия]

См. также

• Последовательность Конуэя

Отрывок, характеризующий Кодирование длин серий

– Ваше превосходительство, вот два трофея, – сказал Долохов, указывая на французскую шпагу и сумку. – Мною взят в плен офицер. Я остановил роту. – Долохов тяжело дышал от усталости; он говорил с остановками. – Вся рота может свидетельствовать. Прошу запомнить, ваше превосходительство!
– Хорошо, хорошо, – сказал полковой командир и обратился к майору Экономову.
Но Долохов не отошел; он развязал платок, дернул его и показал запекшуюся в волосах кровь.
– Рана штыком, я остался во фронте. Попомните, ваше превосходительство.

Про батарею Тушина было забыто, и только в самом конце дела, продолжая слышать канонаду в центре, князь Багратион послал туда дежурного штаб офицера и потом князя Андрея, чтобы велеть батарее отступать как можно скорее. Прикрытие, стоявшее подле пушек Тушина, ушло, по чьему то приказанию, в середине дела; но батарея продолжала стрелять и не была взята французами только потому, что неприятель не мог предполагать дерзости стрельбы четырех никем не защищенных пушек. Напротив, по энергичному действию этой батареи он предполагал, что здесь, в центре, сосредоточены главные силы русских, и два раза пытался атаковать этот пункт и оба раза был прогоняем картечными выстрелами одиноко стоявших на этом возвышении четырех пушек.
Скоро после отъезда князя Багратиона Тушину удалось зажечь Шенграбен.
– Вишь, засумятились! Горит! Вишь, дым то! Ловко! Важно! Дым то, дым то! – заговорила прислуга, оживляясь.
Все орудия без приказания били в направлении пожара. Как будто подгоняя, подкрикивали солдаты к каждому выстрелу: «Ловко! Вот так так! Ишь, ты… Важно!» Пожар, разносимый ветром, быстро распространялся. Французские колонны, выступившие за деревню, ушли назад, но, как бы в наказание за эту неудачу, неприятель выставил правее деревни десять орудий и стал бить из них по Тушину.
Из за детской радости, возбужденной пожаром, и азарта удачной стрельбы по французам, наши артиллеристы заметили эту батарею только тогда, когда два ядра и вслед за ними еще четыре ударили между орудиями и одно повалило двух лошадей, а другое оторвало ногу ящичному вожатому. Оживление, раз установившееся, однако, не ослабело, а только переменило настроение. Лошади были заменены другими из запасного лафета, раненые убраны, и четыре орудия повернуты против десятипушечной батареи. Офицер, товарищ Тушина, был убит в начале дела, и в продолжение часа из сорока человек прислуги выбыли семнадцать, но артиллеристы всё так же были веселы и оживлены. Два раза они замечали, что внизу, близко от них, показывались французы, и тогда они били по них картечью.
Маленький человек, с слабыми, неловкими движениями, требовал себе беспрестанно у денщика еще трубочку за это , как он говорил, и, рассыпая из нее огонь, выбегал вперед и из под маленькой ручки смотрел на французов.
– Круши, ребята! – приговаривал он и сам подхватывал орудия за колеса и вывинчивал винты.
В дыму, оглушаемый беспрерывными выстрелами, заставлявшими его каждый раз вздрагивать, Тушин, не выпуская своей носогрелки, бегал от одного орудия к другому, то прицеливаясь, то считая заряды, то распоряжаясь переменой и перепряжкой убитых и раненых лошадей, и покрикивал своим слабым тоненьким, нерешительным голоском. Лицо его всё более и более оживлялось. Только когда убивали или ранили людей, он морщился и, отворачиваясь от убитого, сердито кричал на людей, как всегда, мешкавших поднять раненого или тело. Солдаты, большею частью красивые молодцы (как и всегда в батарейной роте, на две головы выше своего офицера и вдвое шире его), все, как дети в затруднительном положении, смотрели на своего командира, и то выражение, которое было на его лице, неизменно отражалось на их лицах.
Вследствие этого страшного гула, шума, потребности внимания и деятельности Тушин не испытывал ни малейшего неприятного чувства страха, и мысль, что его могут убить или больно ранить, не приходила ему в голову. Напротив, ему становилось всё веселее и веселее. Ему казалось, что уже очень давно, едва ли не вчера, была та минута, когда он увидел неприятеля и сделал первый выстрел, и что клочок поля, на котором он стоял, был ему давно знакомым, родственным местом. Несмотря на то, что он всё помнил, всё соображал, всё делал, что мог делать самый лучший офицер в его положении, он находился в состоянии, похожем на лихорадочный бред или на состояние пьяного человека.