ИННОВАЦИИ БИЗНЕСУ

Результат выполнения научно-исследовательской работы.

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

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

Анализ:Допустим в последовательности имеется строк повторов длины . Общая её длина . Длина строк повторов после кодирования составит , а общая длина: . Относительное сокращение длины последовательности:

,

где - вероятность цепочки повторов длины .

В большинстве случаев при кодировании обычных текстов и текстов после bw (burrows, wheeler) - преобразования наилучшие результаты наблюдались при и почти линейно ухудшались с его увеличением.

Реализация:

program rle; {postfixes rle algorithm. copyright (c) yuri a.gadzhiev, 2003.

all rights reserved.}

const k=2;

var stdin,stdout:text;

rep:longint;

c,l:char;

{================Кодирование================}

procedure encode;

begin

while not eof(stdin) do begin

read(stdin,c);

if (c=l) and (rep<256) then="">

inc(rep);

if rep < k="" then="">

write(stdout,c);

end

end

else begin

if rep > k-2 then begin

write(stdout,char(byte(rep+1-k)));

rep:=0;

end;

write(stdout,c);

l:=c;

end

end

end;

{============Декодирование=============}

procedure decode;

var check:boolean;

begin

check:=true;

while not eof(stdin) do begin

read(stdin,c);

write(stdout,c);

if check and (c=l) then inc(rep);

if rep=k-1 then begin

read(stdin,c); rep:=byte(c);

while rep>0 do begin

write(stdout,l);

dec(rep);

end;

check:=false;

end

else check:=true;

l:=c;

end;

end;

\