Алгоритм Хаффмана

Алгоритм Хаффмана также прост и красив, но если при рассмотрении алгоритма LZSS можно ограничиться интуитивными соображениями, то здесь требуется более строгое изложение.

Пусть сообщение M составлено из символов алфавита C. Эти символы могут быть представлены кодами некоторой фиксированной длины (для определенности 8 бит). Допустим, числа повторений символов A, B, C и D (Na, Nb, Nc и Nd соответственно) удовлетворяют неравенству

Na>Nc+Nd

Число повторений символа B произвольно. Назначим этим символам следующие коды:

A: 00000000
B: 00000001
C: 00000010
D: 00000011

Оставшиеся 252 кода произвольно распределим между оставшимися символами алфавита. Далее сделаем следующую замену кодов:

A: 0000000
B: 00000010
C: 000000110
D: 000000111

В результате получим экономию в Na-(Nc+Nd) бит (на самом деле меньше, т.к. вместе с сообщением надо передавать таблицу кодов). Также важно отметить, что проблем с декодированием не возникает - ни один из кодов не является префиксом другого. Декодер довольно прост, о нем чуть ниже.

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

В качестве примера рассмотрим сообщение, составленное из шести символов A, B, C, D, E и F. Числа повторений следующие:

A B C D E F
60 25 30 5 10 20

Возьмем два узла с самыми маленькими весами (D и E), образуем из них новый узел с весом 15 и добавим его в список. Узлы D и E исключим:

A B C F
60 25 30 20 15
/ \
E D
10 5

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

A B C
60 25 30 35
/ \
| 15
| / \
F E D
20 10 5

Возьмем два узла с наименьшими весами (B и C), образуем из них новый узел с весом 55 и добавим его в список. Взятые узлы исключим:

A
60 35 55
/ \ / \
| 15 | |
| / \ | |
F E D C B
20 10 5 30 25

Возьмем два узла с наименьшими весами (35 и 55), образуем из них новый узел с весом 90 и добавим его в список. Взятые узлы исключим:

A
60 – 90 –
/ \
55 35
/ \ / \
| | | 15
| | | / \
C B F E D
30 25 20 10 5

Возьмем два узла с наименьшими весами (A и 90) и образуем из них новый узел с весом 150 и добавим его в список. Взятые узлы исключим. В списке остался один узел - дерево построено:

– – 150 – –
/ \
– 90 – |
/ \ |
55 35 |
/ \ / \ |
| | | 15 |
| | | / \ |
C B F E D A
30 25 20 10 5     60

Чтобы получить код Хаффмана для любого из символов нужно пройти от корня дерева к соответствующему этому символу листу, каждый переход влево - 0, вправо - 1. Так получим все биты кода. Реально приходится двигаться в обратном направлении - от листа к корню. Процедура получения кода похожа на преобразование числа в строку - последний символ строки получается первым. Следует заметить, что длина кода может превосходить длину простой переменной (16 или 32 бит). В данном примере коды следующие:

A: 1
B: 001
C: 000
D: 0111
E: 0110
F: 010

Декодирование символа начинается с корня дерева. Сообщение читается по одному биту, если прочитан 0 - переход по дереву влево, если 1 - вправо. По достижению листа определяется конец кода символа (и сам этот символ).

Алгоритм Хаффмана дает самый короткий код среди всех кодов, представляющих каждый символ сообщения фиксированной последовательностью бит. Доказательства этого факта строится на следующем свойстве оптимального кода - два наиболее редких символа A и B представляются кодами максимальной длины, т.е. коды всех прочих символов заведомо не длиннее кода A (B). Без ограничения общности Na - число повторений символа A не больше Nb - числа поторений символа B. Допустим, что код символа С встречающегося Nc>Na раз имеет длину Lc>La. Тогда после обмена кодов A и C получим более короткий код:

(Na*La+Nc*Lc)-(Na*Lc+Nc*La)=Nc*(Lc-La)-Na*(Lc-La)=(Nc-Na)*(Lc-La)>0

Это противоречит оптимальности кода и, следовательно, Lc не может превосходить La. Предположение Lb меньше La также неверно - в этом случае либо есть символ D встречающийся Nd>Nb раз, длина кода которого равна La, либо код символа A содержит лишние биты. Сделав одну замену можно получить оптимальный код код, в котором A и B различаются лишь последним битом. Таким образом, существует оптимальное дерево кодирования, в котором коды двух самых редких символов отличаются лишь последним битом.

Обозначим C(N) алфавит из N символов, M(C) - сообщение, образованное из символов этого алфавита, T(M) -дерево кодирования и W(T) - вес дерева T, т.е. сумму по всем символам произведений чисел повторений символа на длину кода этого символа.

Допустим, что дерево Хаффмана T(M) неоптимально, т.е. существует некоторое дерево T'(M), вес которого меньше веса дерева Хаффмана:

W(T')<W(T)

Пусть A и В - два наиболее редких символа сообщения M, их числа повторений Na и Nb соответственно. И в дереве T и в дереве T' их коды различаются лишь младшим битом (в дереве Хаффмана - по построению, дерево T' может быть преобразовано к такому виду). Заменим все символы A и B новым (отсутстующим в алфавите C) символом Z. Число повторений этого символа в сообщении Nz=Na+Nb. В результате получим новый алфавит C'(N-1) и новое сообщение M'(C'). Из деревьев T и T' исключим листья, соответствующие символам A и В, а их общий узел поставим в соответствие символу Z. Получим деревья T''(M') и T'''(M'), T'' - дерево Хаффмана для сообщения M'. Поскольку такие преобразования уменьшают веса обоих деревьев на одинаковую величину Nz (код символа Z на один бит короче кода символа A) верно неравенство:

W(T''')=W(T')-Nz<W(T)-Nz=W(T'')

Это означает, что дерево Хаффмана для сообщения из алфавита C'(N-1) также неоптимально. Продолжая процесс слияния самых редких символов придем к тому, что дерево Хаффмана для сообщения из алфавита C(2) неоптимально. Но это не так - каждый символ сообщения представляется одним битом. Противоречие доказывает оптимальность кода Хаффмана. Но это совсем не означает, что алгоритм Хаффмана - лучший алгоритм сжатия.

Ниже приведен текст программы. Как и в программе LZSS здесь есть функции побитового чтения/записи, но здесь они проще, т.к. читать и писать нужно только по одному биту. Информация о кодах символов в архиве представлена в виде таблицы чисел повторений - это не самый экономный способ, но зато самый простой. Содержательная часть начинается с первого define - я понимаю, что возможность вынести общие функции (ввод/вывод и т.п.) в отдельные файлы была бы полезна, но пока ее нет.

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 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 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 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 void lDec(long @l) if l.lo>0 then dec l.lo; else dec l.hi; l.lo=65535; 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 struct SNode byte Code; long Cnt; int PP; int P0; int P1; end struct SInfo byte Code; long Cnt; int Node; end SNode Tree [1024]; int Root; int nNode; int Indx [256]; void Init(long @Tabl) // построение дерева Хаффмана SInfo Info[256]; int nInfo; nInfo=0; while nInfo<256 do Info[nInfo].Code= nInfo; Info[nInfo].Cnt = Tabl[nInfo]; Info[nInfo].Node=-1; inc nInfo; end nNode=0; while nInfo>1 do int N0=0; int N1=1; if lCmp(Info[N0].Cnt,Info[N1].Cnt)<0 then N0=1; N1=0; end int I=2; while I<nInfo do if lCmp(Info[I].Cnt,Info[N0].Cnt)<0 then if lCmp(Info[I].Cnt,Info[N1].Cnt)<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].Cnt = Info[N0].Cnt; 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].Cnt = Info[N1].Cnt; 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].Cnt =Info[nInfo].Cnt; Info[N0].Node=Info[nInfo].Node; if N1=nInfo then N1=N0; end dec nInfo; Info[N1].Code=Info[nInfo].Code; Info[N1].Cnt =Info[nInfo].Cnt; Info[N1].Node=Info[nInfo].Node; Tree[P0] .PP = nNode; Tree[P1] .PP = nNode; Tree[nNode].Code= 0; Tree[nNode].Cnt = lSum(Tree[P0].Cnt,Tree[P1].Cnt); Tree[nNode].P0 = P0; Tree[nNode].P1 = P1; Info[nInfo].Code= 0; Info[nInfo].Cnt = Tree[nNode].Cnt; 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]; // Текст long Tabl [256]; // Таблица чисел повторений int I=0; while I<256 do Tabl[I].lo=0; Tabl[I].hi=0; inc I; end int nTxt=0; int pTxt=0; while TRUE do if pTxt>=nTxt then nTxt=read(hTxt,@Txt,BLK_LEN); if nTxt=0 then exit end pTxt=0; end lInc(@Tabl[Txt[pTxt]]); inc pTxt; end write(hArc,@Tabl,1024); Init(@Tabl); reset(hTxt); nTxt=0; 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 Code(Indx[Txt[pTxt]]); inc pTxt; end while pBit>0 do Save(0); end Save(0); if pArc>0 then write(hArc,@Arc,pArc); end end void Decode(word hArc, hTxt) long Tabl [256]; read(hArc,@Tabl,1024); Init(@Tabl); byte Txt[TXT_LEN]; int nArc=0; pArc=0; long nTxt=Tree[Root].Cnt; int pTxt=0; while nTxt.hi>0 | nTxt.lo>0 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 Txt[pTxt]=Tree[P].Code; inc pTxt; lDec(@nTxt); 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
Сайт создан в системе uCoz