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

Тема в разделе "WASM.A&O", создана пользователем MAPTbIH, 29 янв 2007.

  1. MAPTbIH

    MAPTbIH Member

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

    Booster New Member

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

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

    Cyber_Mozg Andrey

    Публикаций:
    0
    Регистрация:
    4 апр 2005
    Сообщения:
    196
    Адрес:
    Russia
    вот посмотри
     
  4. Cyber_Mozg

    Cyber_Mozg Andrey

    Публикаций:
    0
    Регистрация:
    4 апр 2005
    Сообщения:
    196
    Адрес:
    Russia
    и ещё
     
  5. Cyber_Mozg

    Cyber_Mozg Andrey

    Публикаций:
    0
    Регистрация:
    4 апр 2005
    Сообщения:
    196
    Адрес:
    Russia
    и вот
    не влезает в яндексе напиши хафман в плане минимализации программ
     
  6. MAPTbIH

    MAPTbIH Member

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

    MAPTbIH Member

    Публикаций:
    0
    Регистрация:
    3 янв 2006
    Сообщения:
    83
    Да, Booster, дерево - это жесть! Да и вообще, всё это жесть. Теория понятна, а вот практика. Ума не приложу!
     
  8. Y_Mur

    Y_Mur Active Member

    Публикаций:
    0
    Регистрация:
    6 сен 2006
    Сообщения:
    2.494
    MAPTbIH
    Дык там где яндекс находит такой вагон статей по сабжу, нечто ничего не порадовало?
     
  9. IceFire

    IceFire New Member

    Публикаций:
    0
    Регистрация:
    30 окт 2006
    Сообщения:
    244
    Когда-то давно написал хорошую реализацию этого алгоритма на...(не пинайте)... на дельфе. Но идея одна. Моя реализация бегает быстро. Если надо - скажи, я выложу.
     
  10. MAPTbIH

    MAPTbIH Member

    Публикаций:
    0
    Регистрация:
    3 янв 2006
    Сообщения:
    83
    IceFire, выкладывай, но без exe-файла, т.к. он тяжело весит, а откимпилировать я и сам смогу! На сайте www.compression.ru хорошо объясняется теория, а вот кода на асме я не видел!
     
  11. MAPTbIH

    MAPTbIH Member

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

    IceFire New Member

    Публикаций:
    0
    Регистрация:
    30 окт 2006
    Сообщения:
    244
    MAPTbIH

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

    IceFire New Member

    Публикаций:
    0
    Регистрация:
    30 окт 2006
    Сообщения:
    244
    Код (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----
    Алгоритм не дописан и расчитан на работу с ОДНИМ символом. Надо еще сделать непосредственную замену символов битовыми последовательностями. Чуть-чуть подумай - и все напишешь, там не сложно. Будут вопросы - говори.

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

    W4FhLF New Member

    Публикаций:
    0
    Регистрация:
    3 дек 2006
    Сообщения:
    1.050
    У меня методичка есть, 50 листов, специально для студентов написана, сам по ней реализовывал. Примеры на С++.
     
  15. MAPTbIH

    MAPTbIH Member

    Публикаций:
    0
    Регистрация:
    3 янв 2006
    Сообщения:
    83
    А кто из вас знает ответ на вопрос: "Как, зная длину всех битовых цепочек, записать их одна за другой?"
     
  16. Booster

    Booster New Member

    Публикаций:
    0
    Регистрация:
    26 ноя 2004
    Сообщения:
    4.860
    MAPTbIH
    Так тебя интересует как создать дерево имея битовые цепочки? Да это небольшой подводный камень. Надо будет посмотреть как я делал, а то забыл уже -).
     
  17. Proteus

    Proteus Member

    Публикаций:
    0
    Регистрация:
    19 июн 2004
    Сообщения:
    344
    Адрес:
    Russia
    MAPTbIH
    Вот так и записать. Вывалить подряд и молча в файл и всё.

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

    Booster New Member

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

    MAPTbIH Member

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

    Proteus Member

    Публикаций:
    0
    Регистрация:
    19 июн 2004
    Сообщения:
    344
    Адрес:
    Russia
    Дык дерево и строят в тот момент когда вычисляются битовые цепочки.