HaskellでHuffmanコードベースの圧縮ユーティリティを作る
(lazamar.github.io)- 約150行のHaskellでHuffman coding圧縮器を実装し、任意のバイナリファイルのエンコード・デコードを定数メモリで処理する構造を示す
- Huffmanコードは頻出する値に短いビット列を割り当て、prefix-free code条件によってデコーダがビット列を曖昧さなく解釈できるようにする
- 実装では
FreqMap、HTree、CodeMapを使って頻度表から木を作り、concatMapと再帰デコーダの遅延評価で結果を段階的に生成する - バイナリファイルは
Data.ByteString.Char8でバイトをCharのように扱い、圧縮結果の先頭に頻度表をシリアライズし、ビット列はバイト単位でパディングして保存する - テストではWar and Peaceが3.2Mから1.9Mに、106Mの
ghcupバイナリは84Mに縮小し、最大resident set sizeは300KB未満と観測された
Huffmanコード圧縮の基本アイデア
- 目的はHuffman codingを使い、約150行のHaskellでデータ圧縮ユーティリティを実装すること
- 全コードはGitHubリポジトリで公開されている
- Huffmanコードは各文字や値に固有のビット列を割り当てる
- 頻繁に出現する値には短いビット列を使う
- まれに出現する値には長いビット列を使う
- よく出る値が元の表現より少ないビットで表されることで圧縮効果が生まれる
- 例
aaabでa = 1、b = 0とすると結果は1110になる- UTF-8では4バイトが必要な文字列を半バイトで表現する例である
Prefix-free codeとHuffman木
- デコードが曖昧にならないためには、どのコードワードも他のコードワードの接頭辞になってはならない
- 例えば
aaabcでa = 1、b = 10、c = 01と割り当てると、101がacなのかbaなのか曖昧になり得る
- 例えば
- prefix-free codeは完全二分木として作れる
- すべての値を葉に配置する
- 左の辺に
1、右の辺に0とラベル付けする - 根から葉までの経路がその値のコードワードになる
- Huffman木は頻度の低い値から下側でまとめて上に上がっていく方式で生成する
- 各文字を出現回数であるweightとともにノードにする
- 最小のweightを持つ2つのノードを木にまとめる
- 新しい木のweightは2つのノードのweightの合計である
- 1つの木だけが残るまで繰り返す
- この過程を経ると、より頻繁に出現する値が根に近くなり、より短いコードワードを持つようになる
Haskellエンコーダの構造
- 実装の主要な型は
Bit、Code、FreqMap、CodeMap、Weight、HTreeであるBitはOneまたはZeroCodeは[Bit]FreqMapはMap Char Intで文字ごとの出現回数を保存するCodeMapはMap Char Codeで文字ごとのコードワードを保存するHTreeはLeaf Weight CharまたはFork Weight HTree HTreeである
HTreeはweight基準で比較できるようにし、木の生成過程でのソートと挿入を単純化しているcountFrequencyは文字列内の各文字の出現回数を計算するbuildTreeはFreqMapを葉のリストに変換してソートし、最小の2ノードを繰り返し結合してHuffman木を作るbuildCodesは木をたどりながら左にOne、右にZeroを付けて各文字のコードワードを生成するencode :: FreqMap -> String -> [Bit]はFreqMapから木とコードマップを作り、入力文字列の各文字をコードワードに置き換えてビットリストを作る
遅延評価で段階的に処理する
- エンコードの中心となる変換は
concatMap codeFor strである- 概念的には
[Char]を[[Bit]]に変換したあと、再び[Bit]へ平坦化する過程である - Haskellの遅延評価のおかげで、入力全体を先にすべてエンコードしてから結合する方式では動作しない
- 概念的には
- 小さなリストは左から右へ進みながら大きな結果リストに平坦化される
- 結果リストのtailはまだ評価されていないthunkとして残る
- 必要な値が要求されたときに次の部分が計算される
- デコーダも同じ方式で結果を段階的に生成する
decode :: FreqMap -> [Bit] -> Stringはビットに応じて木の左または右へ移動する- 葉に到達すると文字を出力し、根から再び開始する
- デコード済みの総文字数がHuffman木のweightと同じになるまで繰り返す
- デコーダは入力ビットリストの終端ではなく文字数を基準に停止する
- シリアライズ段階でバイトアラインメントのため最後にパディングビットを追加するためである
go関数は葉に到達すると、headが分かっているリストとtailの再帰呼び出しを返すため、再帰全体が終わる前に結果を評価できる
バイナリファイル処理とシリアライズ
- バイナリデータは、256種類の可能なバイトのいずれかが繰り返される形と見なせる
Data.ByteString.Char8はByteStringをChar演算で扱えるようにし、すべてのCharは8ビットに切り詰められる- この特性のおかげで、テキスト用コーダを大きく変えずにバイナリデータにも適用できる
- 圧縮ファイルにはデコードに必要な
FreqMapが先に入り、その後にエンコード済みのビット列が続く serializeFreqMapは頻度表を次の形式で記録する- マップ長は
Word8で保存するが、表現範囲の補正のため1を引いて保存する - 各項目はキーを
Word8、頻度値を64ビットbig-endian整数として保存する
- マップ長は
serializeはbinaryパッケージのPutモナドでByteStringを生成する- ビットを1つずつ読み、1バイトを埋める
- 8ビットが埋まると
putWord8で記録する - 最後のバイトは残りの空間を
Zeroでパディングする
デシリアライズと定数メモリ戦略
deserializeFreqMapはData.Binary.Getでシリアライズされた頻度表を読む- まず長さを読み、1を足して実際の項目数を計算する
- 各項目から
Word8キーと64ビット頻度値を読み、FreqMapを復元する
- 残りの入力全体は
Getで処理せず、ByteStringからoffset以降を取り出してビットリストに変換する deserializeは(FreqMap, [Bit])を返し、[Bit]は即座に全体計算されない遅延リストである- このリストの長さを要求するとリスト全体を評価する必要があるため避けるべきである
- 入力全体に
Getを使わない理由は、モナドのbindが順序を強制するためである- 入力全体の処理が終わって初めてリストを返せる構造になる
- 定数メモリ戦略は、出力ビットを書き込むたびに入力の次の小さな部分だけを評価する方式である
- 一部の
ByteStringが評価され、そのファイル片が読み込まれる - 処理された出力はファイルに記録される
- 参照されなくなった入力片とビットリストはガベージコレクタが回収できる
- 一部の
FreqMapはバイト基準で最大256項目なので、定数サイズのオーバーヘッドに収まる
ファイル圧縮・展開CLI
compressは入力ファイルを2回読む- 1回目のパスで
FreqMapを作る - 2回目のパスでその
FreqMapを使ってデータをエンコードする
- 1回目のパスで
- ファイルを1回だけ読み、同じ参照を
encodeに渡すと、頻度表生成後も入力ファイル全体への参照を保持する必要があるため、ファイル全体をメモリ上に持つ必要がある - 2回読む方式により、頻度表生成とエンコードの両方で処理済みメモリを進行中に解放できる
decompressは圧縮ファイルを読み、deserializeでFreqMapとビットリストを得たあと、decode結果をファイルに保存する- CLIは次の引数を受け取る
compress FILE FILEdecompress FILE FILE
- GHCに含まれるパッケージだけを使うため、
cabalなしでghc -O2 Main.hs -o mainとしてコンパイルできる
実行結果とメモリ使用量
- TolstoyのWar and Peaceテキストファイルのテストでは、圧縮と展開後の
diff結果が同一である- 元の
WarAndPeace.txt: 3.2M - 圧縮ファイル: 1.9M
- 展開ファイル: 3.2M
- サイズが約40%減少
- 元の
- より大きなバイナリファイル
ghcupでも圧縮と展開が動作する- 元の
ghcup: 106M - 圧縮ファイル: 84M
- 展開ファイル: 106M
- 圧縮時間は約15.173秒、展開時間は約14.555秒
- 元の
+RTS -s基準で、ghcup処理中の最大resident set sizeは300KB未満である- 2つのプロセスは実行に10MB未満のメモリを使用する
- 時間の使われ方は別途プロファイルで確認できる
さらに改善できる点
- 実装の目標は、できるだけ単純で明確な圧縮ユーティリティであり、効率を高めるにはより複雑な実装が必要である
- 考えられる改善案は次のとおり
- マルチスレッディング: ファイル区間を並列にデコードする。ただし任意位置でコードワード境界が分からないため、圧縮ファイルの先頭に区間境界と予想デコードサイズのテーブルを追加する
- 単一パスエンコード: すべてのバイトが頻度1を持つ初期頻度表から開始し、バイトを見るたびにまずエンコードしてから頻度表を更新する
- Canonical Huffman codes: デコードで木を
O(log n)で探索する代わりに、コードをベクターインデックスとして使ってO(1)アクセスを狙える。関連内容はCanonical Huffman codeにある - より高速なコード生成: 単一パスエンコードでは
CodeMap生成をはるかに高速化する必要があり、木を作らずにコードワードを生成するより速い方法がある
- 将来的に適応型辞書方式であるLZ77を使えば、Huffmanコードと組み合わせてgzipを実装できる
1件のコメント
Hacker News のコメント
この作業には、ツリーを割り当ててポインタをたどる処理を減らす 配列ベースのインプレースアルゴリズムがあります
大学でツリーベースのアプローチを学んだときは、別の方法があるとは知りませんでしたし、ほかの人もそうだったのか気になります
ツリー方式は直感的で理解の助けになりますが、圧縮が最も重要になる場面はたいていデータ量が多く、高速に実行したいときなので、インプレース配列として扱うほうが理にかなっている場合があります
In-Place Calculation of Minimum-Redundancy Codes, Moffat, Katajainen, 1995
http://hjemmesider.diku.dk/~jyrki/Paper/WADS95.pdf
Charles Bloom が強く推薦しており、後に解説も付け加えています
https://cbloomrants.blogspot.com/2010/08/08-12-10-lost-huffm...
「どのコード語も別のコード語の接頭辞にならないようにしなければ曖昧でなくならない」という説明は、厳密には正確ではありません
いわゆる 一意復号可能コード は曖昧でなく、接頭辞コードの上位集合です
簡単な例は、接頭辞コードを反転したコードです。記事の例なら
a 1,b 00,c 10になりますaのコードはcのコードの接頭辞ですが、コード列を逆順に処理すれば、なお曖昧なく復号できます。接頭辞コードでもその逆向きでもない一意復号可能コードを見ると面白そうですA 0,B 01,C 11とし、さらにa A 0,b BA 010,c BB 0101,d BC 0111,e C 11とすれば{a=0,b=010,c=0101,d=0111,e=11}になります0->Aのように後ろから一意に復号したあと、A->aのように前からもう一度一意に復号すればよいので、明らかに一意復号可能です長さの点では最適な接頭辞コード
{a=0,b=110,c=1110,d=1111,e=10}と同じなので、同じ確率分布に対する複数の最適コードの1つです同時に、
a=0,b=010のため接頭辞コードでも接尾辞コードでもありません。実際、一般にはどちらの方向にも逐次復号できず、cee...ee?とbee...ee?、?cc...ccaと?cc...ccbを区別するには、1つの記号を判別するだけでも無限に先読みが必要になることがあります独立に最適な接頭辞コードと独立に最適な接尾辞コードを合成すると常に最適性が保たれるのかは分かりませんが、退化的な 1:1 コードを除いて思いついた最も単純なケースではうまく機能しました
a 101,b 1のような例が可能ですただし、これは悪いコードです。常に
a=1,b=0とするほうがよいからですKraft の不等式 は一意復号可能にできるコード長の集合を教えてくれ、Huffman 符号化によってそのような集合をすべて実現できます。したがって記号符号化をするなら、ANS や算術符号化のような別方式に切り替える場合を除き、非接頭辞コードを使う理由はありません
ただし、最適な Huffman コードと同じ長さ集合を持ちながら、接頭辞コードでも、その逆である接尾辞コードでもない一意復号可能コードが存在するかは分かりません
時間をかけるなら https://en.wikipedia.org/wiki/Sardinas-Patterson_algorithm を見て、反例を総当たりで探すか、アルゴリズムの動作から証明を思いつく気がします
a 1,b 101はどうでしょうか接頭辞自由でも接尾辞自由でもありませんが、
0が現れるたびにbが現れたことに対応しますもちろん明らかに非効率なので、結局気になるのは、接頭辞自由でも接尾辞自由でもない 最適コード があるのかという点です
検索してみると https://blog.plover.com/CS/udcodes.html で、
a 0011,b 011,c 11,d 1110という一意復号可能コードの例が挙げられています唯一の接頭辞関係が
cがdの接頭辞である場合だけなので、「ほぼ」接頭辞自由に近いです。メッセージが1で始まるなら最初の0を探し、その前の1の個数が奇数か偶数かを見ればよさそうなので、一意復号可能性は理解できますただ、これがどの確率分布に対して最適なのかを示す方法は、暗号学の知識があまりに錆びついていて思い出せません
例えば
100000000000000001のような場合、最初のコードがaなのかcなのかを知るには、0 の並びが終わる地点まで全部読まなければなりませんこの記事のように Haskell プログラムを書き進めていく似たチュートリアルで、モナド変換子 や レンズ のようなより高度な機能を扱う資料があるのか気になります
Template Haskell、並行性のようなほかの高度な機能も扱っており、Haskell で SQL データベースを扱う章もあります
FRP ライブラリ Rhine のチュートリアルで、コメントとテストがよく整備されています
Coursera の Scala ベースの関数型プログラミング講座にもかなり似た Huffman コーディング課題があり、自動採点器もあるので、自分で解いてみたい人に向いている
https://www.coursera.org/learn/scala-functional-programming?...
最後に Huffman 符号を使ったのは、MICMAC プロセッサのマクロプログラム、つまりアセンブリテキストを最小のマイクロサイクル数と最小のマイクロ命令数で実行するためだった
実行されたマクロ命令のヒストグラムから始め、記憶ではまず C でインタプリタを書いて、各命令が何回実行されるかを数えた
その後、必要な ISA マクロ演算をすべて実装する漸進的な復号マイクロコードプログラムを作った。作成したマクロ命令 ISA は、バイト指向ではなくビット単位だったように思う
現実には遅くて不便だっただろうが、Huffman 符号の利点は、値の分布に応じて接頭辞の深さを調整できるため、1 ビット接頭辞のせいで片側に偏ったコードにする必要がない点にある
また、マイクロプログラムは非スーパースカラのパイプラインプロセッサモデルだったので、分岐予測も扱う必要があった。分岐予測を誤ると、正しい分岐が前方へ伝播する間、パイプライン停止でサイクルを浪費することになる
https://rosettacode.org/wiki/Huffman_coding
Haskellプログラマーが集まりそうなので聞きたいのですが、最近のHaskellは、最適化に気を使うプログラマーが使うとどれくらい速いのでしょうか？
特に行列演算のような数値計算やSIMDの恩恵を受ける処理の性能が気になります
複数の部分を、一貫性があり整理されたプログラムとして組み立てやすいことが本質です。これは単にタイトなループだけでなく、プログラム全体にとって重要です
HaskellはFFIが優れているので、本質的に命令型の最適化が必要な部分は、ガベージコレクションのない言語へ下りることができます。そうした部分を良い型を持つライブラリで包めば、型が合うHaskellコードのどこからでも、そのネイティブ性能を活用できます
Metaで高性能なHaskellアプリケーションを作るときはそうしていました。美しく、大きく、速いHaskellプログラムを書きつつ、一部の特化した部分にはC++コンポーネントを入れていました。時間の99%は、Haskell側でそれをより有用なアプリケーションへ組み合わせることに使っていました
それでもHaskellが遅い部類というわけではありません。ファイル内の1ビットの数を数える小さなプログラムを例にできます
-msse4.2でコンパイルすると、ハードウェアのpopcount命令をきちんと使い、1GBの入力ファイルを0m0,090sで処理します。MB単位で丸めるとヒープ使用量は0です-msse4.2なしでコンパイルすると0m0,293sかかります行列計算は自分では試していませんが、出発点としては
repa、accelerate、massivを確認すると思いますhttps://hackage.haskell.org/package/repa
https://hackage.haskell.org/package/accelerate
https://hackage.haskell.org/package/massiv
https://gitlab.haskell.org/ghc/ghc/-/issues/7741
GHC 9.12に入る可能性もあります。ただし対象は128ビットベクタのみで、他の人が貢献しない限り、主に浮動小数点演算中心になりそうです
パッチはこちらにあります
https://gitlab.haskell.org/ghc/ghc/-/merge_requests/12860
あるレベルでは、ホスト言語の選択は大きな意味を持ちません。本当に速度を真剣に考えるなら、計算はどうせ外部に任せることになるからです
世界中で計算資源を最も多く使う部類である可能性が高いAIコードが、低レベル計算ライブラリを除けばPythonで書かれていても問題ない理由も同じです
直接答えるなら、GHCコンパイラは非常に優秀です。高水準コードはかなりうまく動きますし、現実的なアプリケーションの大半で性能ボトルネックになるのは、単一幅演算対SIMDのような問題ではなく、アーキテクチャ上の問題です。Haskellの「アーキテクチャ的な漸近性」はかなり有利です
GHCはSIMDサポートを備えている、または備えつつあると思いますが、性能を評価するときにそこへ焦点を当てるつもりはありません
Haskellで行列乗算アルゴリズムを自分で書くことはしませんが、速度を真剣に考えるならRustやCでも自分では書かないでしょう
数値計算を性能指標として見ることは多いですが、実際にそこがボトルネックになる人はほとんどおらず、もしボトルネックなら、どの高水準言語を使っているかはあまり重要ではありません
このスタイルの性能は、普通はCLIやWebバックエンドの作業には十分です。かなり速い低レベルコードを書くための道具もありますが、やや武骨なので、それだけを使いたいなら最良の道具ではない可能性が高いです
ただし、最適化すべき集中的なホットスポットがいくつかある場合には、かなり良い選択です
CPUプロファイリングツールが優れているので、CPUホットスポットを見つけて最適化する作業は比較的快適です。一方で、遅延評価のせいで起こりやすい妙なメモリリークを追跡するのは、非常にもどかしいことがあります
benchmarks gameの結果を見ると、最速のHaskell実装はおおむね最速のC版より2〜5倍遅く、非常に命令型のスタイルで書かれています
https://benchmarksgame-team.pages.debian.net/benchmarksgame/...
“Creating prefix-free codes”セクションの表に誤字があるようです。**Dは
0110ではなく0010**のはずです0110がどうして曖昧でないと言えるのか、しばらく頭を抱えていたのですが、今は理解できました画像の中の女性のシャツに描かれているものが何なのか気になります
直接リンク: https://lazamar.github.io/images/data-compressor.svg