Лучшее описание алгоритма Хаффмана

Здравствуйте! Предлагаю обсудить источники лучших описаний алгоритма Хаффмана, т.к. я хочу понять как это можно реализовать на ассемблере и не могу организовать правильно структуры данных для кодирования/декодирования при сжатии данных. Помогите мне и тем кто ищет информацию по методу Хаффмана. Заранее благодарен!

 

MAPTbIH
Не можешь закодировать что? Бинарное дерево на асме? Пожалуй IMHO это наибольшая трудность. Так как даже на С++ в Хаффмане приходится своё дерево писать, врядли устроит механизм работы например STL. Но вот и начни с создания дерева.
Я его реализовывал только на C++, и конечно дерево писал сам. А вообще алгоритм интересный, и не такой простой как о нём отзываются.

P.S. Пара статей у меня есть в электронном виде, но они древние и вроде всем давно известные. Есть ещё статейка про арифметическое кодирование, неплохая. Правда арифм., я не делал так как тут нужна мощьная оптимизация, и скандачка нормальную реализацию не сделаешь.

 

вот посмотри

 

и ещё

 

и вот
не влезает в яндексе напиши хафман в плане минимализации программ

 

Нашел статью "Хаффман в плане минимализации программ", сложная для понимания статья да еще и на ассемблере под DOS пишет. Кто-нибудь еще знает что-нибудь наипростейшее? Выкладывайте!

 

Да, Booster, дерево - это жесть! Да и вообще, всё это жесть. Теория понятна, а вот практика. Ума не приложу!

 

MAPTbIH

Дык там где яндекс находит такой вагон статей по сабжу, нечто ничего не порадовало?

 

Когда-то давно написал хорошую реализацию этого алгоритма на...(не пинайте)... на дельфе. Но идея одна. Моя реализация бегает быстро. Если надо - скажи, я выложу.

 

IceFire, выкладывай, но без exe-файла, т.к. он тяжело весит, а откимпилировать я и сам смогу! На сайте www.compression.ru хорошо объясняется теория, а вот кода на асме я не видел!

 

Короче, дело к ночи, видимо тут тоже все супер-ассемблерщики как и я. Поэтому наверное тему можно прикрывать. Пусть зарубежные прыщавые студенты пишут программы-архиваторы и видео-кодеки, а я лучше пойду водки попью! СССР - Рулит!

 

MAPTbIH

Ну чего разнервничался? Люди, может, работают, может им код нада выдрать... (мой случай). Как только - так сразу.

 

Код (Text):

1. const
2. SizeOfBuf = 65536*16;
3. SizeOfDic = 65536*16;
4.  
5.  
6. //----For Huffman----
7. type
8.    SizeOfArrays = 0..SizeOfDic;
9.  
10.    PTree = ^TTree;
11.    TTree = record
12.         Str: string;
13.         Next: PTree;
14.         Left: PTree;
15.         Right: PTree;
16.         Freq: DWORD;
17.    end;
18.  
19.    Codes = record
20.         number_of_bits: byte;
21.         code: byte;
22.    end;
23.  
24. //----For Huffman----
25.  
26. var
27. Freq: array [byte] of DWORD;
28. E1, E2: BYTE;
29. Root, T1, T2: PTree;
30. Tree: array [byte] of PTree;
31. Huff_Codes: array [byte] of Codes;
32.  
33. Huff: array [0..SizeOfBuf{*100}] of Char; //
34. Huff_Size: Longint; //
35.  
36.  
37. k: SizeOfArrays;
38. Exists: boolean;
39.  
40. Freq: array [0..255] of DWORD;    
41.  
42. buffer: array [1..SizeOfBuf] of char;  //===Main Array===
43.  
44.  
45. function Is_Contains(const sample: char; Str: String): boolean;
46. var
47. i: integer;
48. begin
49. result:= false;
50.         For i:=1 to Length(Str) do
51.                 If Str[i] = Sample then
52.                         begin
53.                                 Result:=true;
54.                                 Break;
55.                         end;
56. end;
57.  
58.  
59. //----Huffman----
60. For i:=0 to $FF do
61.         begin
62.                 New(T1);
63.                 T1^.Str:=Chr(i);
64.                 T1^.Next:=nil;
65.                 T1^.Left:=nil;
66.                 T1^.Right:=nil;
67.                 T1^.Freq:=Freq[i];
68.  
69.                 If Freq[i]=0 then Dispose(T1) else Tree[i]:=T1;
70.         end;
71.  
72. Exists:=true;
73.  
74. while (Exists) do
75.         begin
76.                 For i:=0 to $FF do
77.                      If (NOT (Tree[i]=nil)) then
78.                                 begin
79.                                      E1:=i;
80.                                      Break;
81.                                 end;
82.  
83.                 For i:=0 to $FF do
84.                         If (NOT (Tree[i]=nil)) then
85.                           If  (NOT (i=E1)) then
86.                                  begin
87.                                      E2:=i;
88.                                      Break;
89.                                  end;
90.  
91.                 If Tree[E2]^.Freq < Tree[E1]^.Freq then
92.                        begin
93.                         i:=E1;
94.                         E1:=E2;
95.                         E2:=i;
96.                        end;
97.  
98.                 For i:=0 to $FF do
99.                         If (NOT (Tree[i]=nil)) then
100.                           If (Tree[i]^.Freq < Tree[E1]^.Freq)  then  
101.                                 E1:=i;
102.  
103.                 For i:=0 to $FF do
104.                         If (NOT (Tree[i]=nil)) then
105.                           If (Tree[i]^.Freq < Tree[E2]^.Freq) AND (NOT (i=E1)) then
106.                                 E2:=i;
107.  
108.                 New(T1);
109.                 T1^.Str:=Tree[E1]^.Str+Tree[E2]^.Str;
110.                 T1^.Next:=nil;
111.                 T1^.Left:=Tree[E1];
112.                 T1^.Right:=Tree[E2];
113.                 T1^.Freq:=Tree[E1]^.Freq+Tree[E2]^.Freq;
114.  
115.                 Tree[E1]:=T1;
116.                 Tree[E2]:=nil;
117.  
118.                 Exists:=false;
119.                 For i:=0 to $FF do
120.                      begin
121.                                 If NOT (Tree[i] = nil) then
122.                                                 For j:=i+1 to $FF do
123.                                                         If NOT (Tree[j] = nil) then
124.                                                                 begin
125.                                                                         Exists:=true;
126.                                                                         Break;
127.                                                                 end;
128.                                 If (Exists) then Break;
129.                      end;
130.  
131.         end;
132.  
133.     i:=0;
134.     while (Tree[i]=nil) do inc(i);
135.  
136.         Root:=Tree[i];
137.  
138.         For j:=0 to $FF do
139.                 Freq[j]:=0;
140.  
141.             For i:=0 to $FF do
142.                 begin
143.                         T1:=Root;
144.                         while NOT ((T1^.Left = nil) AND (T1^.Right = nil)) do
145.                                 begin
146.                                         T2:=T1^.Left;
147.  
148.                                         inc(Huff_Codes[i].number_of_bits);
149.                                         Huff_Codes[i].code:=Huff_Codes[i].code shl 1;
150.  
151.                                         If Is_Contains(Chr(i), T2^.Str) then
152.                                                     T1:=T1^.Left
153.                                         else
154.                                                 begin
155.                                                     inc(Huff_Codes[i].code);
156.                                                     T1:=T1^.Right;
157.                                                 end;
158.                                 end;
159.  
160.                 end;
161.  
162.         //=====Temp code for Huffman======
163.         AssignFile(SrcFile,NameCrypt);
164.         Reset(SrcFile,1);
165.         BlockRead(SrcFile, Huff, FileSize(SrcFile), TransBytes);
166.  
167.         Huff_Size:=0;
168.  
169.         For i:=0 to TransBytes do
170.                  Huff_Size:=Huff_Size+Huff_Codes[Ord(buffer[i])].number_of_bits;
171.  
172.         Huff_Size:=Huff_Size div 8;
173.  
174.         Application.MessageBox(PChar('Предполагаемый размер по Хаффману: '+IntToStr(Huff_Size)),PChar('Коэффициент сжатия по Хаффману'), MB_OK);  //
175.  
176.         //=====End temp code for Huffman=====
177.  
178. //----Huffman----

Алгоритм не дописан и расчитан на работу с ОДНИМ символом. Надо еще сделать непосредственную замену символов битовыми последовательностями. Чуть-чуть подумай - и все напишешь, там не сложно. Будут вопросы - говори.

З.Ы. Водка мозгов не прибавляет....

 

У меня методичка есть, 50 листов, специально для студентов написана, сам по ней реализовывал. Примеры на С++.

 

А кто из вас знает ответ на вопрос: "Как, зная длину всех битовых цепочек, записать их одна за другой?"

 

MAPTbIH

Так тебя интересует как создать дерево имея битовые цепочки? Да это небольшой подводный камень. Надо будет посмотреть как я делал, а то забыл уже -).

 

MAPTbIH

Вот так и записать. Вывалить подряд и молча в файл и всё.

Формулировка такая, что непонятно о чём вопрос.

 

Proteus
Он наверно имел ввиду как построить дерево, исходя из того, что просчитаны все битовые цепочки. Проблема в том что они разной длины. Просто когда я делал алгоритм дерева, децел пришлось подумать над этим, вот и решил что вопрос об этом, может я и неверно понял. А создать дерево для 8 бит можно так: создаёшь 256 массивов, каждый размерностью 256. Записываешь в них цепочки. Потом сортирушь всё это дело, так чтобы у тебя первые элементы массивов шли 0, 0, 0...1, 1, затем сортировка по следующим элементам массивов в подчастях 0 и 1. И потом остаётся только перенести всё это в дерево.

 

Проблему с записью и чтением битовых цепочек я уже решил, спасибо. Уже даже написал весь алгоритм, сжимаю NOTEPAD.EXE, весом в 69 Кбайт, а в итоге получаю сжатый фал размером в 53 Кбайт. Вот это сжатие! Плоховат немного алгоритм-то! Буду изучать арифметическое сжатие! А вообще какой алгоритм подходит для сжатия кодовой секции exe-фалов? Ето мне для вируса надо!

 

Дык дерево и строят в тот момент когда вычисляются битовые цепочки.