LZH法における並列データ圧縮技法

概要

論文の詳細を見る
LZH法はLZ77法という,多くのデータ圧縮プログラムで使用されている基本アルゴリズムにハフマン符号化を組み合わせた,高圧縮率をほこるアルゴリズムである.ハフマン符号化は,単純で高速に実行できるため,圧縮プログラムの実行時間の80%以上がLZ77法において最長一致を探索するために費されている.LZ77法は,データ復元に比べ圧縮に時間がかかるという特徴をもっている.最長一致を探索する時間を短縮するため,KMPやBMなどのパターンマッチングアルゴリズムを使用する他に,圧縮アルゴリズムに適したデータ型とアルゴリズムがいろいろ考えられている.並列化パターンマッチングを用いて,圧縮アルゴリズムを並列化することは,構造的に容易である.しかし非常に多くのプロセッサが使用可能だとしても,パターンマッチを行なう最初の段階しか,多くのプロセッサを必要とせず,最終的には多くのプロセッサが***状態になる.また,並列化の単位が小さいため,プロセッサ間の通信コストが問題になる.以上のようなことを考慮して,考案したのが,今回,紹介するデータ圧縮アルゴリズムの並列化法である.実装はネットワーク環境において行っており,その時の,実験結果についても紹介する.
1996-03-06