Рассмотренный выше алгоритм Хаффмана можно изменить так,
чтобы он выполнялся за один проход и не требовал информации о структуре дерева
кодирования:
void Encode() // Кодирование
Инициализация дерева
while Не_конец_файла do
Считывание символа
Кодирование символа
Перестроение дерева
end
end
void Decode() // Декодирование
Инициализация дерева;
while Условие do
Декодирование символа
Перестроение дерева
end
end
Декодирование возможно, поскольку обе функции обновляют дерево кодирования одинаковым
образом. Псевдокод не вполне точен - в нем не указано условие прекращения декодирования
и некоторые другие детали.
Инициализировать дерево кодирования можно исходя из некоторого предположения о частотах
повторений различных символов. Можно добавить к 256 символам еще два - EOF (код 256) и
CHR (код 257) и включить в дерево только их. Другие символы будут включены в дерево
после их первого появления в кодируемом файле. Соответственно, при первом появлении
символа в выходной файл записывается код CHR и сам символ (восемь бит), при последующих
появлениях этого символа в выходной файл записывается его код (символ уже включен в дерево
и может быть закодирован). Выходной файл завершается кодом EOF. При декодировании появлене
кода EOF является условием завершения. Получаемый таким образом код не будет кодом Хаффмана,
поскольку коды символов могут меняться по ходу кодирования.
В принципе можно после считывания каждого символа строить дерево Хаффмана заново,
это потребует весьма значительных затрат времени, но работать будет. Для начала так и
сделаем, в программе статического кодирования заменим
функции Init, Encode и Decode, добавим Insert и Update. Теперь построение дерева
рассредоточено по трем функциям - Init (инициализация дерева), Insert (регистрация
нового символа) и Update (перестроение дерева). Далее функция Update будет заменена
гораздо более быстродействующей.
define EOF 256
define CHR 257
define nCHR 258
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
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
Не пытайтесь кодировать с помощью этой программы большие файлы и не думайте что она
зависла - просто она медленно работает.
Более внимательное рассмотрение свойств опимального дерева кодирования приводит
к существенно лучшим алгоритмам. В дереве Хаффмана более часто встречающимся символам
соответствуют более короткие коды. Для любых двух узлов 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 приведет к следующему измененению
веса дерева:
вес дерева уменьшится лишь при равенстве весов A и B и при меньшей длине кода B.
Этой перестановки недостаточно для восстановления оптимальноти дерева, но она дает
ключ к построению алгоритма.
Заметим, что перестановка двух равных по весу поддеревьев не меняет веса дерева и,
следовательно, не нарушает указанного выше соотношения весов и длин кодов (обратное
противоречит оптимальности дерева). Сделаем следующее:
Найдем узел B с весом Na и с самым коротким кодом Lb<=La
Выполним перестановку поддеревьев с корнями в узлах A и B
Перейдем от узла A (стоящего на месте B) к вышестоящему узлу C
Если не достигнут корень, повторим действия 1-3 для узла C
Все эти перестановки не нарушают оптимальности дерева. Затем увеличим на единицу
веса всех узлов на пути от корня до A. Такое увеличение не нарушит соотношение между
весами узлов и длинами кодов, поскольку после сделанных перестановок всем узлам на этом
пути соответствуют коды минимальной возможной для их весов длины. Следовательно,
полученное дерево будет оптимальным.
Для начала реализуем все это в виде двух рекурсивных процедур Locate и Update.
Первая из них обходит дерево и находит узел с заданным весом и самым коротким кодом,
вторая реализует привденный алгоритм. Процедура Insert стала более сложной - если старая
процедура только регистрировала новый символ, то новая вставляет в дерево узел с нулевым
весом (поскольку длина его кода максимальна, это не нарушает соотношение весов и
длин кодов):
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
Программа стала работать быстрее, но все равно не быстро. Поскольку выполнено
соотношение весов и длин кодов, узлы дерева кодирования могут быть одновременно
упорядочены по уменьшению веса и увеличению длины кода. Действительно, ничто не
мешает упорядочить узлы с одинаковыми весами по увеличению длины кода, коды узлов
с меньшими весами как минимум не короче кодов узлов с большими весами. Используя
упорядоченный массив поиск узла с заданным весом и самым коротким кодом можно
выполнять значительно быстрее:
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
И наконец, рекурсивную процедуру обновления можно заменить циклической:
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 различных символов, за которыми следую следуют символы с
максимально длинными кодами:
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%.