кодировка huffman для текстового файла

Question

Это только часть дерева huffman, сгенерированного с использованием 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. Я не знаю, где моя проблема, потому что я сделал все, что было в соответствии с инструкциями. Может ли кто-нибудь сказать мне, что здесь не так?

Моя самая большая проблема в том, что: если я использую кодирование huffman, только 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 всегда будет давать одно и то же дерево (с разными метками, но с той же структурой).