Адаптивный алгоритм Хаффмана
Рассмотренный выше алгоритм Хаффмана имеет два недостатка. Во-первых, он требует
двух проходов по кодируемому тексту, во-вторых, в выходной файл должна быть записна
информация о структуре дерева кодирования (что увеличивает размер файла).
Можно изменить алгоритм кодирования так, чтобы он выполнялся за один проход и не
требовал информации о структуре дерева:
<![CDATA[
void Encode() // Кодирование
Инициализация дерева
while Не_конец_файла do
Считывание символа
Кодирование символа
Перестроение дерева
end
end
void Decode() // Декодирование
Инициализация дерева;
while Условие do
Декодирование символа
Перестроение дерева
end
end
]]>
Псевдокод не вполне точен. В частности, в нем не указано условие прекращения декодирования.
Инициализировать дерево кодирования можно исходя из некоторого предположения о частотах
повторений различных символов. Можно добавить к 256 символам еще два - EOF (код 256) и
CHR (код 257) и включить в дерево только их. Другие символы будут включены в дерево
после их первого появления в кодируемом файле. Соответственно, при первом появлении
символа в выходной файл записывается код CHR и сам символ (восемь бит), при последующих
появлениях этого символа в выходной файл записывается его код (символ уже включен в дерево
и может быть закодирован). Выходной файл завершается кодом EOF. При декодировании появлене
кода EOF является условием завершения.
Разумеется, при кодировании и декодировании должны использоваться одни и те же функции
инициализации и перестроения дерева. Получаемый код не будет кодом Хаффмана, поскольку
коды символов могут меняться по ходу кодирования. Вопрос о том, лучше он или хуже чем
код Хаффмана будет рассмотрем ниже. Очевидно, для коротких сообщений
он лучше, для длинных - не обязательно.
В принципе можно после считывания каждого символа строить дерево Хаффмана заново, это
потребует весьма значительных затрат времени, но работать будет. Для начала так и
сделаем, затем заменим процедуры Insert и Update более быстродействующими. Весь прочий
код изменяться не будет. Вот полный текст программы, он получен путем незначительной правки
статического алгоритма. Собственно алгоритм начинается с первого
define - возможности выполнять сборку программы из нескольких файлов в DOS-версии компилятора
не будет, в Windows-версии она есть, но нет некоторых других возможностей, так что пока следует
использовать DOS-компилятор версии 1.1 или 1.2:
<![CDATA[
struct Addr
word Ofs;
word Seg;
section
void @Ptr;
end
void @Ptr(word Seg,Ofs)
Addr P;
P.Seg=Seg;
P.Ofs=Ofs;
return @P.Ptr;
end
word GetPSP()
asm mov AH,62H
asm int 21H
asm mov AX,BX
end
word create(char @Name)
asm push DS
asm mov AH,3CH
asm mov CX,00H
asm mov DX,SS:[BP+6]
asm mov DS,DX
asm mov DX,SS:[BP+4]
asm int 21H
asm pop DS
end
word open(char @Name)
asm push DS
asm mov AH,3DH
asm mov AL,00H
asm mov DX,SS:[BP+6]
asm mov DS,DX
asm mov DX,SS:[BP+4]
asm int 21H
asm pop DS
end
word reset(word F)
asm push DS
asm mov AX,4200H
asm mov BX,SS:[BP+4]
asm mov CX,0
asm mov DX,0
asm int 21H
asm pop DS
end
word read(word F; void @Buff; word N)
asm push DS
asm mov AH,3FH
asm mov BX,SS:[BP+10]
asm mov CX,SS:[BP+4]
asm mov DX,SS:[BP+8]
asm mov DS,DX
asm mov DX,SS:[BP+6]
asm int 21H
asm pop DS
end
word write(word F; void @Buff; word N)
asm push DS
asm mov AH,40H
asm mov BX,SS:[BP+10]
asm mov CX,SS:[BP+4]
asm mov DX,SS:[BP+8]
asm mov DS,DX
asm mov DX,SS:[BP+6]
asm int 21H
asm pop DS
end
void close(word F)
asm mov AH,3EH
asm mov BX,SS:[BP+4]
asm int 21H
end
void putc(char Ch)
asm mov AH,2
asm mov DL,SS:[BP+4]
asm int 21H
end
void puts(char @St)
word P=0;
while St[P]!=#0 do
putc(St[P]);
inc P;
end
end
int strcmp(char @S1, @S2)
int P=0;
while TRUE do
if S1[P]<S2[P] then
return -1;
end
if S1[P]>S2[P] then
return 1;
end
if S1[P]=#0 then
return 0;
end
inc P;
end
end
struct long
word lo;
word hi;
end
void lInc(long @l)
if l.lo<65535 then
inc l.lo;
else
inc l.hi;
l.lo=0;
end
end
long lSum(long a, b)
asm mov AX,SS:[BP+ 4]
asm mov DX,SS:[BP+ 6]
asm mov BX,SS:[BP+ 8]
asm mov CX,SS:[BP+10]
asm add AX,BX
asm db 013H ; adc DX,CX
asm db 0D1H
end
int lCmp(long a, b)
if a.hi<b.hi then
return -1;
end
if a.hi>b.hi then
return 1;
end
if a.lo<b.lo then
return -1;
end
if a.lo>b.lo then
return 1;
end
return 0;
end
define TXT_LEN 16384
define ARC_LEN 16384
define BLK_LEN 4096
define ARC_FWD 128
define EOF 256
define CHR 257
define nCHR 258
struct NODE
int Code; // byte
long N;
int PP;
int P0;
int P1;
end
struct INFO
int Code; // byte
long N;
int Node;
end
int Indx [nCHR];
NODE Tree [1024];
int Root;
int nNode;
void Init() // инициализация дерева Хаффмана
int I=0;
while I<nCHR do
Indx[I]=-1;
inc I;
end
Tree[0].N.hi = 0;
Tree[0].N.lo = 1; // 2
Tree[0].Code =-1;
Tree[0].PP =-1;
Tree[0].P0 = 1;
Tree[0].P1 = 2;
Tree[1].N.hi = 0;
Tree[1].N.lo = 1;
Tree[1].Code = EOF;
Tree[1].PP = 0;
Tree[1].P0 =-1;
Tree[1].P1 =-1;
Indx[EOF] = 1;
Tree[2].N.hi = 0;
Tree[2].N.lo = 0; // 1
Tree[2].Code = CHR;
Tree[2].PP = 0;
Tree[2].P0 =-1;
Tree[2].P1 =-1;
Indx[CHR] = 2;
Root = 0;
nNode = 3;
end
void Insert(int B)
Tree[nNode].N.hi = 0;
Tree[nNode].N.lo = 0;
Tree[nNode].Code = B;
Indx[B] =nNode;
inc nNode;
end
void Update(int P) // построение дерева Хаффмана
lInc (@Tree[P].N);
INFO Info[nCHR];
int nInfo=0;
int I=0;
while I<nCHR do
if Indx[I]>=0 then
Info[nInfo].N = Tree[Indx[I]].N;
Info[nInfo].Code= I;
Info[nInfo].Node=-1;
inc nInfo;
end
inc I;
end
nNode=0;
while nInfo>1 do
int N0=0;
int N1=1;
if lCmp(Info[N0].N,Info[N1].N)<0 then
N0=1;
N1=0;
end
I=2;
while I<nInfo do
if lCmp(Info[I].N,Info[N0].N)<0 then
if lCmp(Info[I].N,Info[N1].N)<0 then
N0=N1;
N1=I;
else
N0=I;
end
end
inc I;
end
int P0=Info[N0].Node;
if P0<0 then
Tree[nNode].Code = Info[N0].Code;
Tree[nNode].N = Info[N0].N;
Tree[nNode].P0 =-1;
Tree[nNode].P1 =-1;
Indx[Info[N0].Code]= nNode;
P0 = nNode;
inc nNode;
end
int P1=Info[N1].Node;
if P1<0 then
Tree[nNode].Code = Info[N1].Code;
Tree[nNode].N = Info[N1].N;
Tree[nNode].P0 =-1;
Tree[nNode].P1 =-1;
Indx[Info[N1].Code]= nNode;
P1 = nNode;
inc nNode;
end
dec nInfo;
Info[N0].Code=Info[nInfo].Code;
Info[N0].N =Info[nInfo].N;
Info[N0].Node=Info[nInfo].Node;
if N1=nInfo then
N1=N0;
end
dec nInfo;
Info[N1].Code=Info[nInfo].Code;
Info[N1].N =Info[nInfo].N;
Info[N1].Node=Info[nInfo].Node;
Tree[P0] .PP = nNode;
Tree[P1] .PP = nNode;
Tree[nNode].Code= 0;
Tree[nNode].N = lSum(Tree[P0].N,Tree[P1].N);
Tree[nNode].P0 = P0;
Tree[nNode].P1 = P1;
Info[nInfo].Code= 0;
Info[nInfo].N = Tree[nNode].N;
Info[nInfo].Node= nNode;
inc nInfo;
inc nNode;
end
Root=Info[0].Node;
Tree[Root].PP =-1;
end
byte Arc [ARC_LEN];
int pArc;
byte Tmp;
byte pBit;
void Save(word B)
if pBit=0 then
Arc[pArc]=Tmp;
inc pArc;
Tmp = 0;
pBit=128;
end
Tmp =Tmp+pBit*B;
pBit=pBit/2;
end
word Load()
if pBit=0 then
pBit=128;
inc pArc;
end
word C=Arc[pArc]&pBit;
pBit=pBit/2;
return C;
end
void Code(int P)
if Tree[P].PP>=0 then
Code(Tree[P].PP);
if Tree[Tree[P].PP].P0=P then
Save(0);
else
Save(1);
end
end
end
void Encode(word hArc, hTxt)
byte Txt [TXT_LEN]; // Текст
Init();
int nTxt=0;
int pTxt=0;
pArc=0;
while TRUE do
if pTxt>=nTxt then
nTxt=read(hTxt,@Txt,BLK_LEN);
if nTxt=0 then
exit
end
pTxt=0;
end
if pArc>=BLK_LEN then
write(hArc,@Arc,pArc);
pArc=0;
end
if Indx[Txt[pTxt]]<0 then
Code(Indx[CHR]);
byte B=Txt[pTxt];
int I=0;
while I<8 do
Save(B&1);
B=B/2;
inc I;
end
Update(Indx[CHR]);
Insert(Txt[pTxt]);
else
Code (Indx[Txt[pTxt]]);
end
Update(Indx[Txt[pTxt]]);
inc pTxt;
end
Code(Indx[EOF]);
while pBit>0 do
Save(0);
end
Save(0);
if pArc>0 then
write(hArc,@Arc,pArc);
end
end
void Decode(word hArc, hTxt)
byte Txt[TXT_LEN];
Init();
int nArc=0;
pArc=0;
int pTxt=0;
while TRUE do
if pTxt>=BLK_LEN then
write(hTxt,@Txt,pTxt);
pTxt=0;
end
if pArc+ARC_FWD>=nArc then
word I=pArc;
word J=0;
while I<nArc do
Arc[J]=Arc[I];
inc J;
inc I;
end
nArc=J+read(hArc,@Arc[J],BLK_LEN);
pArc=0;
end
int P=Root;
while Tree[P].P0>=0 do
if Load()=0 then
P=Tree[P].P0;
else
P=Tree[P].P1;
end
end
byte B=0;
select
case Tree[P].Code=EOF:
exit
case Tree[P].Code=CHR:
word I=0;
word J=1;
while I<8 do
if Load()!=0 then
B=B+J;
end
J=2*J;
inc I;
end
Update(Indx[CHR]);
Insert(B);
default:
B=Tree[P].Code;
end
Txt[pTxt]=B;
inc pTxt;
Update(Indx[B]);
end
if pTxt>0 then
write(hTxt,@Txt,pTxt);
end
end
begin
char @Line=@Ptr(GetPSP(),129); // Командная строка
byte @Size=@Ptr(GetPSP(),128); // Длина строки
char Parm [3][128]; // Параметры
int F=1;
int I=0;
int J=0;
while I<3 do
while J<Size & Line[J] =' ' do
inc J;
end
int K=0;
while J<Size & Line[J]!=' ' do
Parm[I][K]=Line[J];
inc K;
inc J;
end
Parm[I][K]=#0;
if K<1 then
F=0;
end
inc I;
end
word hArc;
word hTxt;
int C=0;
if F!=0 then
select
case strcmp(@Parm[0][0],"e")=0 | strcmp(@Parm[0][0],"E")=0:
hArc=create(@Parm[1][0]);
hTxt=open (@Parm[2][0]);
C=1;
case strcmp(@Parm[0][0],"d")=0 | strcmp(@Parm[0][0],"D")=0:
hArc=open (@Parm[1][0]);
hTxt=create(@Parm[2][0]);
C=2;
end
end
if C=0 then
puts("huffman.com e(ncode)|d(ecode) arc-file txt-file");
return
end
Tmp = 0;
pBit=128;
select
case C=1:
Encode(hArc,hTxt);
case C=2:
Decode(hArc,hTxt);
end
close(hTxt);
close(hArc);
end
]]>
В приведенной программе дерево кодирования строится заново после обработки
каждого символа и это занимает очень много времени. Более внимательное
рассмотрение свойств опимального дерева кодирования приводит к существенно
лучшим алгоритмам. В дереве Хаффмана более часто встречающимся символам
соответствуют более короткие коды. Для любых двух узлов A и B верно следующее:
Na>Nb => La<=Lb
Na и Nb - веса узлов, La и Lb - длины кодов. Из предположения обратного следует
уменьшение веса дерева при перестановке A и B, что противоречит оптимальности:
Na*Lb+Nb*La-Na*La-Nb*Lb=(Na-Nb)*(Lb-La)<0
Таким образом, соотношение между весами и длинами кодав является необходимым условием
оптимальности. Но также оно является достаточным условием, т.е. из его истинности
следует оптимальность дерева. Доказательство аналогично доказательству оптимальности
дерева Хаффмана. Пусть A - самый редкий символ сообщения. Из соотношения весов и длин
следует, что либо длина La его кода максимальна, либо существует символ C с весом Nc=Na
и длиной Lc>La. В последнем случае переставим узлы A и С. Действительно, для любого
символа C c весом Nc>Na длина кода Lc<=La (соотношение весов и длин кодов).
Символ B - следующий после A по весу, Nb>=Na. Если допустить, что Lb<La, то
существует символ D c весом Nd>=Nb и длиной Ld=La>Lb. Если Nd>Nb, приходим
к противоречию, остается вариант Nd=Nb и после перестановки B и D придем к Lb=La и
кодам A и B отличающимся только последним битом.
Предположим, дерево T, для которого выполнено соотношение весов и длин кодов
неоптимально. Т.е. существует дерево T' с весом W(T')<W(T).
В обоих деревьях коды символов A и B имеют максилальную длину и различаются последним
битом. Заменим алфавит A, B -> Z, Nz=Na+Nb. Веса обоих деревьев кодирования
уменьшатся на одинаковую величину Na+Nb бит, соотношение весов и длин кодов не
нарушится. Продолжая процесс слияния самых редких символов придем к тому, что дерево
кодирования для алфавита из двух символов неоптимально. Противоречие доказывает
оптимальность дерева T.
Пусть имеется уже построенное оптимальное дерево и вес одного из символов (A) нужно
увеличить на единицу. Простое увеличение веса соответствующего символу узла и всех
лежащих выше узлов может нарушить оптимальность. Пусть Na - вес символа
(до увеличения), La - длина кода. Nb и Lb - вес и длина некоторого другого узла
(не обязательно символа). Перестановка узлов A и B приведет к следующему измененению
веса дерева:
(Na+1)*Lb+Nb*La-(Na+1)*La-Nb*Lb=((Na-Nb)+1)*(Lb-La)
вес дерева уменьшится лишь при равенстве весов A и B и при меньшей длине кода B.
Этой перестановки недостаточно для восстановления оптимальноти дерева, но она дает
ключ к построению алгоритма.
Также заметим, что перестановка двух равных по весу поддеревьев оптимального дерева
не меняет его веса и, следовательно, не нарушает указанного выше соотношения весов
и длин кодов (обратное противоречит оптимальности дерева). Сделаем следующее:
- Найдем узел B с весом Na и с самым коротким кодом Lb<=La
- Выполним перестановку поддеревьев с корнями в узлах A и B
- Перейдем от узла A к вышележащему узлу C
- Если не достигнут корень, повторим действия 1-3 для узла C
Все эти перестановки не нарушают оптимальности дерева. Затем увеличим на единицу
веса всех узлов на пути от корня до A. Такое увеличение не нарушит соотношение между
весами узлов и длинами кодов, поскольку всем узлам соответствуют коды минимальной
возможной для их весов длины. Следовательно, полученное дерево будет оптимальным.
Для начала реализуем все это в виде двух рекурсивных процедур Locate и Update.
Первая из них обходит дерево и находит узел с заданным весом и самым коротким кодом,
вторая реализует привденный алгоритм. Процедура Insert стала более сложной - если старая
процедура только регистрировала новый символ, то новая вставляет в дерево узел с нулевым
весом (поскольку длина его кода максимальна, это не нарушает соотношение весов и
длин кодов):
<![CDATA[
void Insert(int B) // byte
int L=0; // длина кода
int J;
int I=0;
while I<nCHR do
int P=Indx[I];
if P>=0 then
if Tree[P].N.hi=0 & Tree[P].N.lo=1 then
int H=0;
while P>=0 do
inc H;
P=Tree[P].PP;
end
if L<=H then
L=H;
J=I;
end
end
end
inc I;
end
int P0=Indx[J];
Tree[P0] .P0 =nNode;
Tree[P0] .P1 =nNode+1;
Tree[nNode].N = Tree[P0].N;
Tree[nNode].Code = Tree[P0].Code;
Tree[nNode].PP = P0;
Tree[nNode].P0 =-1;
Tree[nNode].P1 =-1;
Indx[Tree[P0].Code]=nNode;
inc nNode;
Tree[nNode].N.hi = 0;
Tree[nNode].N.lo = 0;
Tree[nNode].Code = B;
Tree[nNode].PP = P0;
Tree[nNode].P0 =-1;
Tree[nNode].P1 =-1;
Indx[B] =nNode;
inc nNode;
Tree[P0] .Code =-1;
end
void Locate(int P; int L; int @P1; int @L1)
if P<0 then
return
end
if L>=L1 & L1>=0 then
return
end
if Tree[P].N.hi<Tree[P1].N.hi then
return
end
if Tree[P].N.hi=Tree[P1].N.hi & Tree[P].N.lo<Tree[P1].N.lo then
return
end
if Tree[P].N.hi=Tree[P1].N.hi & Tree[P].N.lo=Tree[P1].N.lo then
P1=P;
L1=L;
return
end
Locate(Tree[P].P0,L+1,@P1,@L1);
Locate(Tree[P].P1,L+1,@P1,@L1);
end
void Update(int P) // обновление дерева кодирования
if P<0 then
return
end
int P1= P;
int L1=-1;
Locate(0,0,@P1,@L1);
if P1!=P then
int PP =Tree[P] .PP;
int PP1=Tree[P1].PP;
if PP1!=PP then
if Tree[PP] .P0=P then
Tree[PP] .P0=P1;
else
Tree[PP] .P1=P1;
end
if Tree[PP1].P0=P1 then
Tree[PP1] .P0=P;
else
Tree[PP1] .P1=P;
end
Tree[P] .PP=PP1;
Tree[P1].PP=PP;
end
end
Update(Tree[P].PP);
lInc (@Tree[P].N);
end
]]>
Можно сделать еще лучше. Поскольку выполнено соотношение весов и длин кодов,
узлы дерева кодирования могут быть одновременно упорядочены по уменьшению
веса и увеличению длины кода. Действительно, ничто не мешает упорядочить
узлы с одинаковыми весами по увеличению длины кода, коды узлов с меньшими
весами как минимум не короче кодов узлов с большими весами. Используя
упорядоченный массив поиск узла с заданным весом и самым коротким кодом можно
выполнять быстрее:
<![CDATA[
void Insert(int B) // byte
int P0=nNode-1;
Tree[P0] .P0 =nNode;
Tree[P0] .P1 =nNode+1;
Tree[nNode].N = Tree[P0].N;
Tree[nNode].Code = Tree[P0].Code;
Tree[nNode].PP = P0;
Tree[nNode].P0 =-1;
Tree[nNode].P1 =-1;
Indx[Tree[P0].Code]=nNode;
inc nNode;
Tree[nNode].N.hi = 0;
Tree[nNode].N.lo = 0;
Tree[nNode].Code = B;
Tree[nNode].PP = P0;
Tree[nNode].P0 =-1;
Tree[nNode].P1 =-1;
Indx[B] =nNode;
inc nNode;
Tree[P0] .Code =-1;
end
void Update(int P) // обновление дерева кодирования
if P<0 then
return
end
int P1=P;
while P1>0 do
if Tree[P1-1].N.lo!=Tree[P].N.lo | Tree[P1-1].N.hi!=Tree[P].N.hi then
exit
end
dec P1;
end
if P1!=P then
int P00=Tree[P] .P0;
int P01=Tree[P] .P1;
int C =Tree[P] .Code;
int P10=Tree[P1].P0;
int P11=Tree[P1].P1;
int C1 =Tree[P1].Code;
if C<0 then
Tree[P00].PP=P1;
Tree[P01].PP=P1;
else
Indx[C] =P1;
end
if C1<0 then
Tree[P10].PP=P;
Tree[P11].PP=P;
else
Indx[C1] =P;
end
Tree[P] .P0 =P10;
Tree[P] .P1 =P11;
Tree[P] .Code =C1;
Tree[P1].P0 =P00;
Tree[P1].P1 =P01;
Tree[P1].Code =C;
end
Update(Tree[P1].PP);
lInc (@Tree[P1].N);
end
]]>
И наконец, рекурсивную процедуру обновления можено заменить циклической:
<![CDATA[
void Update(int P) // обновление дерева кодирования
while P>=0 do
int P1=P;
while P1>0 do
if Tree[P1-1].N.lo!=Tree[P].N.lo | Tree[P1-1].N.hi!=Tree[P].N.hi then
exit
end
dec P1;
end
if P1!=P then
int P00=Tree[P] .P0;
int P01=Tree[P] .P1;
int C =Tree[P] .Code;
int P10=Tree[P1].P0;
int P11=Tree[P1].P1;
int C1 =Tree[P1].Code;
if C<0 then
Tree[P00].PP=P1;
Tree[P01].PP=P1;
else
Indx[C] =P1;
end
if C1<0 then
Tree[P10].PP=P;
Tree[P11].PP=P;
else
Indx[C1] =P;
end
Tree[P] .P0 =P10;
Tree[P] .P1 =P11;
Tree[P] .Code =C1;
Tree[P1].P0 =P00;
Tree[P1].P1 =P01;
Tree[P1].Code =C;
end
lInc (@Tree[P1].N);
P=Tree[P1].PP;
end
end
]]>
Такой способ обновления дерева кодирования был предложен Робертом Галлагером
в 1978 году. Стоит отметить, что все три способа перестроения дерева приводят
к немного разным результатам. Общее лишь то, что на каждом шаге колирования
деревья оптимальны.
Теперь о длине кода. Можно создать такое сообщение, каждый байт
которого будет закодирован не менее чем девятью битами. Поскольку всего кодов 258,
в дереве всегда есть коды длиной более 8 бит. Следующая процедура создает сообщение,
начинющееся с 256 различных символов, за которыми следую следуют символы с максимально
длинными кодами:
<![CDATA[
void Create(word hTxt)
byte Txt[TXT_LEN];
Init();
int pChr=0;
int pTxt=0;
while pTxt<TXT_LEN do
byte B=0;
if pChr<=255 then
B=pChr;
Update(Indx[CHR]);
Insert(B);
inc pChr;
else
int L =0;
int J =0;
int I =0;
while I<=255 do
int P=Indx[I];
int N=0;
while P>=0 do
inc N;
P=Tree[P].PP;
end
if L<N then
L=N;
J=I;
end
inc I;
end
B=Tree[Indx[J]].Code;
end
Txt[pTxt]=B;
inc pTxt;
Update(Indx[B]);
end
write(hTxt,@Txt,pTxt);
end
]]>
Таким образом, адаптивное кодирование может быть хуже статического - в худшем
случае статический код длиннее исходного сообщения на длину таблицы частот,
адаптивный код - как минимум, на 12.5%.
Сайт создан в системе
uCoz