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

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

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

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

WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW

Если мы применим простое кодирование длин серий к этой строке, то получим следующее:

12W1B12W3B24W1B14W

Последняя запись интерпретируется как «двенадцать W», «одна B», «двенадцать W», «три B» и т. д. Таким образом, код представляет исходные 67 символов в виде всего лишь 18.

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

ABCABCABCABCDDEFFFFFFFF

1A1B1C1A1B1C1A1B1C1A1B1C2D1E8F

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

-12ABCABCABCABC2D1E8F

Так как численные типы данных на компьютере всегда имеют некоторый предел, возникает еще одна проблема. Предположим, мы используем signed char для записи длин серий. Тогда мы не можем записать серию длиннее 127 символов одной парой "длина-символ". Если подряд записано 256 символов A, их разделяют на минимальное количество групп:

127A127A2A

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

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

Применение

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

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

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

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

Имеется викиучебник по теме
«Кодирование длин серий»

Реализация алгоритма на языке php

<?php
$code = 'fafaaaaaaaaaaaaa';
$encode = '';
 
for ($i = 0; $i < strlen($code);$i++){
        $smb = $code[$i] ;
        $count = 1 ;
        for ($b = $i; $b < strlen($code);$b++){
                if ($code[$b + 1] != $smb) break ;
                $count++ ;
                $i++ ;
        }
        $encode .= $count . $smb ;
}
print 'Строку: ' . $code . ' удалось сжать до ' . $encode . '.<br> И мы сэкономили ' . (strlen($code) - strlen($encode)) . ' байт.' 
?>

Простой пример реализации алгоритма на Delphi/Pascal

function encode(s:string):string;
var i,j:integer;
    newS:string;
begin
  i:=1;
  while i <= length(s) do
  begin
    j:=i;
    while (s[i] = s[j+1]) do inc(j);
    if (j-i = 0) or (j-i = 1) or (j-i =2) then
    begin
      newS := newS + s[i];
      if (s[i]='0') then newS:=newS+'0';
      inc(i);
    end else
    begin
      newS := newS + inttostr(j-i+1) + s[i];
      inc(i,j-i+1);
    end;
  end;
  result:= newS;
end;
 
function decode(s:string):string;
var i,j,c:integer;
    newS:string;
    dp : string;
begin
i:=1;
while i <= length(s) do
  begin
    j:=i;
    while s[j] in ['0'..'9'] do inc(j);
    if j-i > 0 then
    begin
      dp := copy(s,i,j-i);
      for c:=1 to strtoint(dp) do newS := newS + s[j];
      delete(s,i,j-i+1);
    end else
    begin
      newS := newS + s[i];
      inc(i);
    end;
  end;
  result:= newS;
 
end;

См. также

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

Для улучшения этой статьи желательно?: Найти и оформить в виде сносок ссылки на авторитетные источники, подтверждающие написанное.