パスワードを忘れた? アカウント作成
この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。

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

  • ハフマン符号の圧縮処理では各バイト記号を可変長符号に変換し、連結すればよいだけなので並列化は容易です。

    符号の連結は、圧縮・伸長の双方で最も高速化が難しい処理なのに。

    • by Anonymous Coward on 2020年09月08日 0時04分 (#3884448)

      高速化ではなくて並列化ね。データを分割して並列化する場合、圧縮時は元データが固定bit長なのでデータをぶった切る位置が簡単。それに対して展開時の可変bit長のハフマン符号は先頭から順に追っていかないと、どのbit位置で区切られているのか分からない。そもそも先頭から追っていくのなら、並列化せずについでにデコードしてしまった方が速い可能性もある。

      だから圧縮時にキリトリ線を予め入れておけば、展開時にほとんど計算せずにデータをキリトリ線の位置でぶった切って並列処理に放り込むことができる。キリトリ線の位置の集合をギャップ配列というデータ構造に入れるということでしょう。

      適応型には向かない(キリトリ線だけでなくその位置での辞書がないといけない)ので圧縮率より展開速度の方を優先したい場合に有用なんでしょうね。

      ちょっとしたヒントを与えて並列化をし易くするという点がミソで、ギャップ配列を無視した場合は今まで通りの処理ができそう。だから既存データフォーマットをバージョンアップしてオプション仕様を拡張すればいいので採用し易いと思う。

      親コメント
      • by miyuri (33181) on 2020年09月08日 7時44分 (#3884524) 日記

        メモリには32bit単位で書き込みたいのに、伸長後の断片は8bit単位なので、連結する必要が有るが、その処理が重そう。
        そこを圧縮率を犠牲にして伸長後の断片を32bit単位にしていると思ったけど、そうでもなかったという。

        親コメント
        • by miyuri (33181) on 2020年09月08日 8時19分 (#3884542) 日記

          伝播とは言うものの、個別に足し込むだけだから問題無いのか。

          親コメント
          • by Anonymous Coward

            圧縮時に個々に並列処理されるデータの長さを32bitの倍数にしておけば伸長後もそうなるはずなのでビット単位の操作とか必要ないはず。むしろ圧縮時に並列処理されたデータが可変長ビットになるのでそれらを繋げるときにビット操作が必要になるかも知れないが、繋げる箇所の数はデータ量に対して少ないし、そもそも連結処理にはひたすらシフトする必要があるけどハッシュなんかに比べると重くはない(おそらくCPUよりメモリアクセスがボトルネックになる)。

            あるいはデータフォーマットを工夫することでそれも避けられる。というか並列処理単位ごとにヘッダとデータという構造にして、ヘッダにビット長を入れておいて末尾のキリの悪い半端bitを捨てることにすれば、ギャップ配列もいらなくなるかもね。この場合は既存のデータフォーマットの拡張ではできないけれども。

犯人は巨人ファンでA型で眼鏡をかけている -- あるハッカー

処理中...