霍夫曼編碼文本文件

Question

這只是我使用ocaml生成的霍夫曼樹的一部分。該樹被表示爲（字符* INT列表）列表：

[(' ', [0]); ('e', [1; 0]); ('t', [1; 1; 0]); ('a', [1; 1; 1; 0]); 
('o', [1; 1; 1; 1; 0]); ('n', [1; 1; 1; 1; 1; 0]).....]. 

的(char*int list)是代碼和對應的編碼比特流。我想知道這是否是一棵正確的樹，或者我理解錯誤。這樣，最長的編碼ASC II代碼將是255位。原始文件爲213.3k，編碼後變成227k，而在說明中，我被告知應該在119k附近生成一個文件。我不知道我的問題在哪裏，因爲我按照說明做了所有事情。有人能告訴我這裏有什麼問題嗎？

我最大的問題是：如果我使用霍夫曼編碼，只有8個最頻繁的字符可以節省我的空間，而其他247個字符將花費額外的空間，這是真的嗎？如果不是，爲什麼？ http://www.cs.cornell.edu/Courses/cs3110/2012sp/hw/ps3/ps3.html

這是我的編碼功能的代碼：

我寫了下面這個鏈接指令的代碼

type huffmantree = Node of huffmantree*(int*int)*huffmantree 
| Leaf of char*int | Nil 
type encoding = char * (int list) 

let look_up (chr: char) (encl : encoding list) : int list = 
    let rec look_up_rec encl = 
    match encl with 
    | [] -> raise (Failure "Not found") 
    | (ch,theL)::tl -> if ch = chr then theL 
         else look_up_rec tl 
    in 
    look_up_rec encl 
;; 

let get_codes (hm : huffmantree): encoding list = 
    let rec get_codes_rec aTree word= 
    match aTree with 
    | Nil -> [] 
    | Node (Leaf(lKey,lFreq),value,Nil) -> [(lKey,[0])] 
    | Node (Leaf(lKey,lFreq),value,Leaf(rKey,rFreq)) -> 
    [(lKey,List.append word [0]);(rKey,List.append word [1])] 
    | Node (Leaf(lKey,lFreq),value,rNode) -> 
    (lKey,List.append word [0])::(get_codes_rec rNode (List.append  word [1])) 
    in 
    get_codes_rec hm [] 
;; 

let encode (text : char list) : huffmantree * int list = 
    let sortedT = List.fast_sort (fun ch1 ch2-> 
    if (int_of_char ch1)>=(int_of_char) ch2 then 1 else -1) text 
    in 
    let rec cre_freq_list aList m = 
    match aList with 
    | [] -> [] 
    | hd::[] -> [(hd,m+1)] 
    | hd1::hd2::tl -> if hd1=hd2 then cre_freq_list (hd2::tl) (m+1) 
         else (hd1,(m+1))::(cre_freq_list (hd2::tl) 0) 
    in 
    let sortedF = List.fast_sort (fun (ch1,fr1) (ch2,fr2) -> 
    if fr1>=fr2 then 1 else -1) (cre_freq_list sortedT 0) 
    in 
    let rec createHuff sortedF= 
    match sortedF with 
    | [] -> Nil 
    | (ch,va)::[] -> Node (Leaf (ch,va),(256,va),Nil) 
    | (ach,aval)::tl -> 
     let rec creH_rec the_tl sib n freq= 
     match the_tl with 
     | (bch,bval)::[] -> Node(Leaf (bch,bval),(n,bval+freq),sib) 
     | (bch,bval)::btl -> creH_rec btl 
      (Node (Leaf (bch,bval),(n,bval+freq),sib)) (n+1) 
      (freq+bval) 
    in creH_rec tl (Leaf(ach,aval)) 256 aval 
    in 
    let huff = createHuff sortedF 
    in 
    let rec make_codes text = 
    match text with 
    | [] -> [] 
    | hd::tl -> List.append (look_up hd (get_codes huff)) 
     (make_codes tl) 
    in 
    (huff,(make_codes text)) 

Answer 1

望着結果樹，看來你不實現霍夫曼算法。我懷疑你的文本中的'e'比任何其他信件更頻繁。如果沒有你的代碼，我只能猜測，但也許當合並兩棵最輕的樹時，你會在樹列表的末尾插入結果樹來合併，而不是根據其權重將它插入到正確的位置。

在您的代碼中createHuff被聲明爲遞歸，但沒有遞歸調用。 您的功能createHuff永遠不會比較sortedF列表中的值您不覺得這是個問題嗎？這意味着createHuff將始終產生相同的樹（具有不同的標籤但具有相同的結構）。