ocaml - 文本文件的霍夫曼编码

Question

这只是我使用 ocaml 生成的哈夫曼树的一部分。树表示为 (char*int list) 列表:

[(' ', [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 中的值 list 你不觉得这是个问题吗？这意味着 createHuff将始终产生相同的树(具有不同的标签但具有相同的结构)。