2009-12-29から1日間の記事一覧

長さ制限つきのハフマン符号化(The Coin Collector's Problem)

冬休みの取り組みとして、ZIP*1圧縮/解凍器を作ってみることにした。 ZIPで使われている圧縮アルゴリズム(圧縮フォーマット?)は、DEFLATEアルゴリズムと云って、簡単に云えばLZ77とハフマン符号化を組み合わせたもののようだ。日本語版仕様(RFC1951) ハフマ…

find-min/find-max

列の要素にキー関数を適用して、その結果が最大(or 最小)となる要素を返す、という関数。 loopマクロのmin/max辺りでやってくれるかなと思ったが、無理そうなので自作した。 マクロをふんだんに使用。 (defmacro find-xxx-helper (empty? first loop compare…