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

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

1. Общая характеристика.

Диапазонное (range) кодирование, как известно, является разновидностью арифметического. Характерными признаками, отличающими данный метод от собственно арифметического кодирования являются: 1) выполнение вычислений над величиной диапазона (range) и нижней его границей, тогда как арифметический кодер оперирует значениями нижней и верхней границ; 2) выполнение многоразрядных арифметический операций и, соответственно, пословное, а не побитовое, как в арифметическом, формирование результата; 3) «раннее» вычисление отношения «диапазон»/«общий счётчик» и использование полученного в результате целого далее в качестве параметра операций вида «диапазон»*«счётчик»/«общий_счётчик». Последнее (п.3) снижает теоретическую «точность» диапазонного кодирования относительно частотной оценки энтропии кодируемой последовательности и приводит в целом к худшим результатам по избыточности диапазонного кодирования относительно стандартного арифметического метода.

Ниже представлена реализация прецизионного диапазонного кодирования, обеспечивающего пренебрежимо малую избыточность кодирования при использовании лишь целочисленных машинных операций. Для максимизации точности вычислений производится побитовое формирование результата. На 32-х разрядной машине избыточность кодирования представленным ниже алгоритмом над энтропийной оценкой источника по результатам испытаний имеет в абсолютном выражении величину порядка 10 байт (включая код завершающего символаEOFи с учётом 4-х байтовой кратности кода результата) на 30 мегабайт кодируемого текста. Время кодирования лишь незначительно (на 10-15%) превышает время простой перезаписи данных на жесткий диск без какой либо дополнительной обработки. Время, требуемое для декодирования, в данной реализации, превышает его примерно трёхкратно.

2.Алгоритмы кодирования и декодирования.

Алгоритмкодирования.

(*======================================================*)

Function MulDiv(Factor1 {eax}, Factor2 {edx} ,Divisor {ecx}:cardinal)

:cardinal;assembler;

(* Copyrights (C) Yuri A. Gadzhiev, 2004, all rights reserved.*)

asm

mul Factor2

div Divisor

end;

(*======================================================*)

Procedure Encode;

(* Copyrights (C) Yuri A. Gadzhiev, 2004, all rights reserved.*)

var ch,Low,NewLow,Delta,i,count:cardinal;

begin

with Fq do begin

StoreFreq;

Cmlt[0]:=0;

for i:=1 to ALPHASIZE-1 do Cmlt[i]:=Cmlt[i-1]+Freq[i-1];

count:=Cmlt[ALPHASIZE-1]+Freq[ALPHASIZE-1];

Delta:=cardinal(-1);

Low:=0;

RestartInput;

POut:=@OutStart;

while not EOI do begin

while Delta > 0 do begin

Delta:=Delta shl 1;

POut(Low <>

Low:= Low shl 1;

end;

ch:=get;

NewLow:= Low + MulDiv(Cmlt[ch],Delta,count);

if NewLow

Low:=NewLow;

Delta:= MulDiv(Freq[ch],Delta,count);

end;

while Low<>0 do begin

POut(Low <>

Low:= Low shl 1;

end;

OutClose;

end;

end;

Алгоритмдекодирования.

(*======================================================*)

Procedure Decode;

(* Copyrights (C) Yuri A. Gadzhiev, 2004, all rights reserved.*)

var count,Low,Delta,ch,r,i,NextChar:cardinal;

BitCounter:integer;

begin

with Fq do begin

GetFreq;

InitCmlt;

count:=Cmlt[1];

Delta:=cardinal(-1);

Low:=get shl 24 +get shl 16 + get shl 8 + get;

BitCounter:=-1;

NextChar:=0;

for i:=1 to SourceLength do begin

ch:=CmltSeek(Low,Delta,count,r);

put(ch);

Low:= Low - r;

Delta:=MulDiv(Freq[ch],Delta,count);

while Delta > 0 do begin

Delta:=Delta shl 1;

Low:= Low shl 1;

if BitCounter<0 then="">

BitCounter:=7;

if not EOI then NextChar:=Get else NextChar:=0;

end;

Low:=Low or ((NextChar shr BitCounter) and 1);

dec(BitCounter);

end;

end;

end;

end;