Let's write β

趣味で書いたこととか、RustとLispが好き

続)続)CLでハフマン木

先ほどのグラフだけではハフマン符号を確認するのは大変です。ちょっと時間がそろそろ
なくなってきたので、本当は葉でなく節は二重線にするなど、ちょっと工夫をしたいのですが
今はとりあえず、木の左右に0,1をふるだけにしておきます。続きはのちほど

(defun to-dot (graph-name stream con-acc)
  (format stream "graph ~A {~%" graph-name)
  (loop for con in con-acc
       for idx from 0 upto (1- (length con-acc))
       do
       (format stream "   ~A -- ~A [label = \"~A\"];~%"
	       (node-name (car con))
	       (node-name (cadr con))
	       (if (oddp idx) 0 1)))
  (format stream "}~%"))

で、

CL-USER> (to-dot "hufmun"  t (caddr (hufmun '((:a 0.1) (:b 0.5) (:c 0.4) (:d 0.1)))))
graph hufmun {
   A_D_C_B -- B [label = "1"];
   A_D_C_B -- A_D_C [label = "0"];
   A_D_C -- C [label = "1"];
   A_D_C -- A_D [label = "0"];
   A_D -- D [label = "1"];
   A_D -- A [label = "0"];
}
NIL

これで、グラフ化して
f:id:Pocket7878_dev:20120507063442p:image
となります。

僕が働いているAzit.incでは一緒に働けるエンジニアを募集しています!
採用情報 — 株式会社アジット|Azit Inc.