「ハフマンコード」:関数型プログラミングの初級問題 -43問目- （1時間）

　符号についての練習問題と答案です。問題は、OCaml公式ページのものを使いました。答案の作成時間は、約1時間でした。

問題43.

出現表からハフマン符号表を生成する関数huffmanを書け。（ハフマン符号については、そのアルゴリズムについて詳述した書籍等を調べよ）

※出現表は、文字と出現回数とからなるタプルのリストとして表されます。
[("a", 45); ("b", 13); ("c", 12); ("d", 16); ("e", 9); ("f", 5)]
ハフマン符号表は、文字と符号とからなるタプルのリストとして表されます。
[("a", "0"); ("c", "100"); ("b", "101"); ("f", "1100"); ("e", "1101");
("d", "111")]

答案

本問の解き方

　まずは、ハフマン符号についての情報を集めます。私は、金銭的な余裕がないので、ネットで情報を集めました。
　後は、それに従って実装するだけです。

コード

type 'a binary_tree = Nil | Node of 'a*'a binary_tree*'a binary_tree

let rec sort comp =
 let rec divide pivot l = match l with [] -> (l, [])
  | head::tail ->
   let (lower, upper) = divide pivot tail in
   if comp head pivot then (head::lower, upper) else (lower, head::upper ) in

 function [] -> []
  | head::tail ->
   let (lower, upper) = divide head tail in
 sort comp lower@(head::(sort comp upper))

let feq_of = function Nil -> raise (Failure "feq_of") 
 | Node ((_, feq), _, _) -> feq

let order = sort (fun x y -> feq_of x < feq_of y)

let rec to_tree = function [] -> raise (Failure "to_tree")
 | head::[] -> head
 | ultima::penult::tail ->
 let br = Node (("", feq_of ultima+feq_of penult), ultima, penult) in
 to_tree (order (br::tail))

let rec trace c = function Nil -> "\\0"
 | Node ((x, _), left, right) ->
  if x = c then ""
  else let code = trace c left in if not (code = "\\0") then "0"^code
  else let code = trace c right in if not (code = "\\0") then "1"^code
  else "\\0"

let huffman lst =
 let rec symbol_of = function [] -> [] | (x, _)::tail -> x::(symbol_of tail) in

 let rec list_of_leaf = function [] -> []
  | head::tail -> Node (head, Nil, Nil)::list_of_leaf tail in

 let tr = to_tree (order (list_of_leaf lst)) in

 let rec table = function [] -> [] | head::tail -> (head, trace head tr)::table tail in

 table (symbol_of lst)

　型binary_treeは、二分木です。
　関数sortは、クイックソートを実装した関数です。
　関数to_treeは、葉のリストから二分木を生成する関数です。
　関数traceは、二分木の根から文字までの経路に沿って符号を生成する関数です。
　関数list_of_leafは、出現表から葉のリストを生成する内部関数です。
　残りは、タプルの要素を取り出すなどの細々とした関数です。

感想

　今回の問題は、アルゴリズムを考えないという点では簡単でした。
　アルゴリズムをOCamlのコードに書き換えるだけなのでアホでもできます。実際に私でもできました。

　一方、アルゴリズムについては難しくてよく理解できませんでした。ハフマン符号が、最短の平均符号長を有する瞬時復号可能な符号であることの証明ができません。

　次回は、第44問です。
　県の最低賃金額改定に伴い、アルバイト情報サイトに掲載される賃金も上昇しています。眺めるだけでも妄想が捗り愉快な毎日です。