アカウント名:
パスワード:
ハフマン符号の圧縮処理では各バイト記号を可変長符号に変換し、連結すればよいだけなので並列化は容易です。
符号の連結は、圧縮・伸長の双方で最も高速化が難しい処理なのに。
高速化ではなくて並列化ね。データを分割して並列化する場合、圧縮時は元データが固定bit長なのでデータをぶった切る位置が簡単。それに対して展開時の可変bit長のハフマン符号は先頭から順に追っていかないと、どのbit位置で区切られているのか分からない。そもそも先頭から追っていくのなら、並列化せずについでにデコードしてしまった方が速い可能性もある。
だから圧縮時にキリトリ線を予め入れておけば、展開時にほとんど計算せずにデータをキリトリ線の位置でぶった切って並列処理に放り込むことができる。キリトリ線の位置の集合をギャップ配列というデータ構造に入れるということでしょう。
適応型には向かない（キリトリ線だけでなくその位置での辞書がないといけない）ので圧縮率より展開速度の方を優先したい場合に有用なんでしょうね。
ちょっとしたヒントを与えて並列化をし易くするという点がミソで、ギャップ配列を無視した場合は今まで通りの処理ができそう。だから既存データフォーマットをバージョンアップしてオプション仕様を拡張すればいいので採用し易いと思う。
メモリには32bit単位で書き込みたいのに、伸長後の断片は8bit単位なので、連結する必要が有るが、その処理が重そう。そこを圧縮率を犠牲にして伸長後の断片を32bit単位にしていると思ったけど、そうでもなかったという。
伝播とは言うものの、個別に足し込むだけだから問題無いのか。
圧縮時に個々に並列処理されるデータの長さを32bitの倍数にしておけば伸長後もそうなるはずなのでビット単位の操作とか必要ないはず。むしろ圧縮時に並列処理されたデータが可変長ビットになるのでそれらを繋げるときにビット操作が必要になるかも知れないが、繋げる箇所の数はデータ量に対して少ないし、そもそも連結処理にはひたすらシフトする必要があるけどハッシュなんかに比べると重くはない（おそらくCPUよりメモリアクセスがボトルネックになる）。
あるいはデータフォーマットを工夫することでそれも避けられる。というか並列処理単位ごとにヘッダとデータという構造にして、ヘッダにビット長を入れておいて末尾のキリの悪い半端bitを捨てることにすれば、ギャップ配列もいらなくなるかもね。この場合は既存のデータフォーマットの拡張ではできないけれども。
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
物事のやり方は一つではない -- Perlな人
なにかがおかしい (スコア:2)
符号の連結は、圧縮・伸長の双方で最も高速化が難しい処理なのに。
Re: (スコア:1)
高速化ではなくて並列化ね。データを分割して並列化する場合、圧縮時は元データが固定bit長なのでデータをぶった切る位置が簡単。それに対して展開時の可変bit長のハフマン符号は先頭から順に追っていかないと、どのbit位置で区切られているのか分からない。そもそも先頭から追っていくのなら、並列化せずについでにデコードしてしまった方が速い可能性もある。
だから圧縮時にキリトリ線を予め入れておけば、展開時にほとんど計算せずにデータをキリトリ線の位置でぶった切って並列処理に放り込むことができる。キリトリ線の位置の集合をギャップ配列というデータ構造に入れるということでしょう。
適応型には向かない（キリトリ線だけでなくその位置での辞書がないといけない）ので圧縮率より展開速度の方を優先したい場合に有用なんでしょうね。
ちょっとしたヒントを与えて並列化をし易くするという点がミソで、ギャップ配列を無視した場合は今まで通りの処理ができそう。だから既存データフォーマットをバージョンアップしてオプション仕様を拡張すればいいので採用し易いと思う。
Re:なにかがおかしい (スコア:2)
メモリには32bit単位で書き込みたいのに、伸長後の断片は8bit単位なので、連結する必要が有るが、その処理が重そう。
そこを圧縮率を犠牲にして伸長後の断片を32bit単位にしていると思ったけど、そうでもなかったという。
Re:なにかがおかしい (スコア:2)
伝播とは言うものの、個別に足し込むだけだから問題無いのか。
Re: (スコア:0)
圧縮時に個々に並列処理されるデータの長さを32bitの倍数にしておけば伸長後もそうなるはずなのでビット単位の操作とか必要ないはず。むしろ圧縮時に並列処理されたデータが可変長ビットになるのでそれらを繋げるときにビット操作が必要になるかも知れないが、繋げる箇所の数はデータ量に対して少ないし、そもそも連結処理にはひたすらシフトする必要があるけどハッシュなんかに比べると重くはない（おそらくCPUよりメモリアクセスがボトルネックになる）。
あるいはデータフォーマットを工夫することでそれも避けられる。というか並列処理単位ごとにヘッダとデータという構造にして、ヘッダにビット長を入れておいて末尾のキリの悪い半端bitを捨てることにすれば、ギャップ配列もいらなくなるかもね。この場合は既存のデータフォーマットの拡張ではできないけれども。