「広島大学、ハフマン符号の処理を高速化するデータ構造「ギャップ配列」を考案」記事へのコメント

ワーストケース

[Anonymous Coward]

リリースを読んだ感じでは、最大符号長によってギャップ配列のビット数が変わるよね。
ハフマン木のバランスが悪い場合、ギャップ配列が相当おデブになるんじゃ……。
まあ、「バランスが悪い＝データが偏っている」ということなので、圧縮前のサイズを基準にすれば比較的軽微、ということかもしれないけど。
ワーストケースを示してほしいところ。

Re:

[Anonymous Coward]

ハフマン辞書のサイズなんてたかが知れているので、ワーストケースでもGPUの手に余るようなものになるとは思えないなぁ

Re:

[Anonymous Coward]

いや、処理速度とかではなく、圧縮率の方です。

例えば、8ビットのデータをハフマン符号化したとき、ワーストケースでの最大符号長って256ビットになるんじゃなかったっけ。
だとすると、1セグメントにつき8ビットのギャップ値が必要になるはずなので、そこそこ容量を取りそう。

Re:ワーストケース

[Anonymous Coward]

そこそこ大きなセグメントで使うだろうし、8ビットくらい誤差みたいなもんでは。