読者です 読者をやめる 読者になる 読者になる

最適なハフマン符号化のために必要なビット長

common lisp algorithm

メモ2。
各コードを符号化するのに最適なビット長は、(- (log (/ コードの出現数 コード総数)) 2)、で求めることができる。
そのため次のような関数で、入力データの最適なハフマン符号化のために必要なビット長が得られる。

;; コードの出現頻度表を引数にし、最適なハフマン符号化を行うために必要な符号ビット長を返す
;; code-frequency-tableの添字がコード値で、値がその出現頻度(出現回数)
(defun optimal-bit-length (code-frequency-table) 
  (multiple-value-bind (min sum)
      (loop FOR cnt ACROSS code-frequency-table 
            SUMMING  cnt INTO sum                   ; 入力データ長を求める
            MINIMIZE cnt INTO min  WHEN (plusp cnt) ; 一番出現頻度が低いコードの出現数を求める
            FINALLY (return (values min sum)))
    (assert (plusp sum) () "入力データサイズが0です")
    ;; 必要なビット長を求める。
    ;; 小数点以下は繰り上げているため、実際に必要なビット長+1を返す場合がある
    (ceiling (- (log (/ min sum) 2)))))

符号ビットの長さ制限付きのハフマン符号を求めたい場合、まず上記関数を適用して、(最適な符号化に)必要なビット長を求め、もしそれが要求されたものより短いならば、普通のハフマン符号化アルゴリズムを用いて、符号化することが出来る。
(普通のハフマン符号化アルゴリズムの方が)処理速度、コンス量ともに多分一桁くらい効率的。
ただ、長さ制限付きのハフマン符号を求める箇所が、プログラム全体のボトルネックになることはまずないと思うので、このようにして処理を振り分ける意味はあまりないかも...。