sileのブログスマートフォン用の表示で見るsileのブログこの広告は、90日以上更新していないブログに表示しています。algorithm冬休みの取り組みとして、ZIP*1圧縮/解凍器を作ってみることにした。ZIPで使われている圧縮アルゴリズム(圧縮フォーマット?)は、DEFLATEアルゴリズムと云って、簡単に云えばLZ77とハフマン符号化を組み合わせたもののようだ。日本語版仕様(RFC1951)ハフマン符号化は、以前に簡単なものを実装したことがあるが、DEFLATEアルゴリズムで使用するハフマン符号化では、一般的なそれとは異なり、(符号化される)各コードを表現するビット列の長さに制限(15ビットまで)を付けられる必要があるらしい。今回はまず、その長さ制限付きのハフマン符号化アルゴリズムの実装を試してみることにする。Problem参考にしたのは、以下のWikipediaの記事。UTC詳しくはリンク先を読んでもらえれば分かると思うが、長さ制限付きハフマン符号化には、package-mergeアルゴリズムというものを使えば良いらしい。Problem」という問題を解くことから始めているので、僕もそれに習うことにする。額面上の価値の値は、二の乗数であるとする。1ドル、1/2ドル、1/4ドル、1/8ドル、など。lispで書いたのが以下のコード。denomは二の乗数とする。最大のdenomと最小のdenomの間に、抜けている二の乗数値はないとものとする。o)))))基本的には、以下の二つを繰り返しているだけ。額面金額の合計)が1になるまで繰り返す額面金額の一番小さいコイン群を、古銭的な価値が小さい順に二つずつまとめる。まとめられたコインの額面金額(の合計)は、二番目に小さい額面金額と等しくなる。1/8+1/8=1/4上でまとめたコイン群を、二番目に額面価値が小さいコイン群とマージする。次は、長さ制限付きのハフマン符号化。package-mergeアルゴリズムは使えるようになったので、後はこれをハフマン符号化に応用するだけ。後で使うので保存しておくこれで、符号化対象データ(入力ストリーム)から各コードの符号ビット長を(長さ制限付きで)計算することができるようになった。上の関数で取得できるのは各コードの符号ビット長だけで、実際の符号化で用いるビット列は不明なままだが、これはビット長さえ分かれば、(例えば)以下のようなコードで簡単に求めることができる(詳しくはRFC1951を参照)。修正版length-limited-huffman上で作成したlength-limited-huffmanパッケージは対象がバイト列(値が0~255の列)に固定されていたので、その制限をなくした版を載せておく。(コードに対応する)符号ビット長の列からハフマン符号表およびハフマン符号木を作成する関数も追加した。符号化の対象となるコードの出現数を保持する配列を受けとるように変更。trie))*1:gzipに変更。長さ制限付きのハフマン符号化のソースコードは、以前にも載せ...2010-01-14最適なハフマン符号化のために必要なビット長メモ2。読者になる検索リンクgithub最新記事RustでMD5ハッシュを計算するRustとSBCLでのDAWG構築性能の比較メモEmacsのファイル保存時に自動的にrustfmtが適用されるようにする現在時刻をUNIXタイムスタンプ形式で取得するloglevelとseverityの使い分けメモ月別アーカイブ最新記事RustでMD5ハッシュを計算するRustとSBCLでのDAWG構築性能の比較メモEmacsのファイル保存時に自動的にrustfmtが適用されるようにする現在時刻をUNIXタイムスタンプ形式で取得するloglevelとseverityの使い分けメモ注目記事ブクログqiitasileのtips人気エントリーはてなブログをはじめよう!sileさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。