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

動的ハフマンコード

[Anonymous Coward]

入力列に応じて辞書を更新するタイプの動的ハフマン符号でもうまく動くのかな？
そもそもこの場合並列処理が無理な気がするけど、今の圧縮処理のトレンドでは使われてないのかな？

Re:動的ハフマンコード

[Anonymous Coward]

先行するデコード結果を参照することになるのでむりぽ。
この発表、将来の展望でzipとかも入れてんだけど、そいつらのスライド辞書とかも同じく無理。
並列化の分割点での辞書内容を独立に復元するないしはリセットする事ができればいいけど、
数百バイト程度毎にそんなのやったら圧縮率が壊滅するので多分意味はない。

これが成立するのは、
入力の符号境界と出力のオフセットくらいしかシークで欠落する情報がないハフマン符号化で、
出力のオフセットを後で適当にマージすることで省略し符号境界のビット表現を短縮できたから。
より大量のデータを抱えた辞書が相手ではシークに必要なヒントが大きくなりすぎる。

素直にGPGPUで扱うデータをハフマンのみで圧縮してオンメモリないしオンノードで扱うって方向のほうが使い勝手良いと思う。