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

Пусть сообщение M составлено из символов ASCII. Эти символы могут быть представлены кодами фиксированной длины (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) бит (на самом деле меньше, т.к. вместе с сообщением надо передавать таблицу кодов). Проблем с декодированием не возникает - ни один из кодов не является префиксом другого. Декодер довольно прост, о нем чуть ниже.

Алгоритм Хаффмана основан на этой идее с той лишь разницей, что она применяется ко всем символам алфавита. Идея алгоритма - свести задачу к аналогичной с меньшим числом символов. Число символов уменьшается за счет объединения их в пары (C и D в приведенном примере). Легко установить, что начинать можно не с любых символов - для этого рассмотрим еще одно сообщение из трех символов A, B и C, повторяющихся 1, 2 и 3 раза соответственно. Вариантов объединения здесь всего три - (A и B), (A и C) и (B и C), их перебор показывает, что к наилучшему результату приводит объединение в пару символов A и B. Далее нужно попытаться доказать, что если объединять в пары самые редкие символы, то результат будет наилучшим. Но сначала детально рассмотрим алгоритм.

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

Рассмотрим еще один пример - сообщение составленное из шести символов 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. Так получим все биты кода. Реально приходится идти в обратном направлении - от листа к корню. Процедура получения кода похожа на преобразование числа в строку - последний символ строки получается первым. В этом примере коды следующие:

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

Нужно отметить, что длина кода символа может превзойти длину простой переменной (16 или 32 бит), но мы и не будем сохранять их в простых переменных.

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

Алгоритм Хаффмана дает самый короткий код среди всех кодов, представляющих каждый символ сообщения фиксированной последовательностью бит. Доказательства этого факта строится на следующем свойстве оптимального кода - этот код может быть преобразован так, что два наиболее редких символа 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. Если же Nc=Na и Lc>La, просто обменяем коды этих символов. Из предположения о том, что Lb меньше La следует, что есть символ D встречающийся Nd>=Nb раз, длина кода которого равна La. Предположение Nd>Nb противоречит оптимальности, поэтому Nd=Nb. Сделав одну замену можно получить оптимальный код код, в котором 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' может быть преобразовано в равное по весу дерево, в котором коды этих символов различаются лишь младшим битом. Заменим все символы A и B новым (отсутстующим в алфавите C) символом Z. В результате получим новый алфавит C'(N-1) и новое сообщение M'(C'). Число повторений символа Z в новом сообщении Nz=Na+Nb. Из деревьев T и T' исключим листья, соответствующие символам A и В, а их общий узел поставим в соответствие символу Z. Получим деревья T''(M') и T'''(M'), T'' - дерево Хаффмана для сообщения M'. Поскольку такие преобразования уменьшают веса обоих деревьев на одинаковую величину Nz (код символа Z на один бит короче кода символа A), дерево T'' также неоптимально:

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

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

Это не единственный способ посторения кода Хаффмана. Ниже рассмотрен совершенно иной алгоритм построения дерева Хаффмана, также неочевидный, но возможно более понятный.

Вот текст программы. Для доступа к файлам написаны функции побитовой записи/чтения (Save/Load). Информация о кодах символов в архиве представлена в виде таблицы чисел повторений - это не самый экономный способ, но зато самый простой. Содержательная часть начинается с первого define - на весь предшествующий текст можно не обращать внимания, в DOS-версии Context'а нет возможности сборки программы из модулей:

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 rewind(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 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 struct NODE int Code; // byte long N; int PP; int P0; int P1; end struct INFO int Code; // byte long N; int Node; end NODE Tree [515]; // 515=258+257 int nNode; int Root; int Indx [258]; // 256+2 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 long Init(long @Tabl) // Построение дерева Хаффмана INFO Info[256]; int nInfo; nInfo=0; while nInfo<256 do Info[nInfo].Code= nInfo; Info[nInfo].N = 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].N,Info[N1].N)<0 then N0=1; N1=0; end int 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 long N =lSum(Info[N0].N,Info[N1].N); int P0=Info[N0].Node; if P0<0 then Tree[nNode].Code = Info[N0].Code; 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].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].P0 = P0; Tree[nNode].P1 = P1; Info[nInfo].Code= 0; Info[nInfo].N = N; Info[nInfo].Node= nNode; inc nInfo; inc nNode; end Root=Info[0].Node; Tree[Root].PP =-1; return Info[0].N; 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); rewind(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); byte Txt[TXT_LEN]; int nArc=0; pArc=0; long nTxt=Init(@Tabl); 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

Рассмотренный алгоритм имеет два недостатка. Во-первых, он требует двух проходов по кодируемому тексту, во-вторых, в выходной файл должна быть записна информация о структуре дерева кодирования (что увеличивает размер файла).

Нужно отметить, что для хранения дерева кодирования используется массив Tree, состоящий из 515 элементов, но достаточно 511 элементов - на каждом шаге в дерево добавляется два, один или ни одного листа и один дополнительный узел, список узлов сокращается на единицу. Всего шагов 255, столько дополнительных узлов нужно, листов 256 - по одному на каждый символ. Дополнительные четыре элемента будут использованы в при рассмотрении адаптивной версии алгоритма.



Сайт создан в системе uCoz