この記事は、Go Parallel に公開されている「Improving Data Compression: a Parallel Algorithm for “Shannon Entropy”」 (https://goparallel.sourceforge.net/improving-data-compression-parallel-algorithm-shannon-entropy/) の日本語参考訳です。
この記事の PDF 版はこちらからご利用になれます。
私の個人的な研究のほとんどはデータ圧縮分野に関するもので、これまで 20 年間にわたって研究に取り組んでいます。データ圧縮は、データ・エントロピーと密接な関係にあります。データ・エントロピーは、多くの人が考える熱力学的エントロピーに似ています。データ・エントロピーが高いと、データセットは雑然とし予測不可能になります。データ・エントロピーが低いと、データセットは整然とし予測可能になります。
ご想像のとおり、データ・エントロピーが低いデータセットのほうが、高いデータセットよりもうまく圧縮できます。これは、経験的なデータの照合により得られた仮説です。現在の研究は、データ・エントロピーとデータ圧縮率には関係があることを示しています。
私の研究のほとんどでは、数万の大きなファイルのエントロピー計算が必要になります。これらの計算には非常に時間がかかります。処理を高速化できれば、研究をより短期間で完了することができます。この記事は、データセットのシャノン・エントロピーを並列に計算するアプローチを紹介します。(著者注 – 1948 年に発表された Claude E. Shannon の「A Mathematical Theory of Communication (計算の数学理論)」で登場したシャノン・エントロピーは、情報源の可逆符号化またはロスレス圧縮の最高平均長の絶対限界を提供します。)
通常のシャノン・エントロピー計算
データセットのシャノン・エントロピーの計算には、2 つの反復プロセスがあります。1 つは各データ値の頻度を計算し、もう 1 つは頻度分布を基にエントロピーを計算します。どちらのプロセスにも時間がかかりますが、特に大きなデータセットでは頻度分布の計算に時間がかかります。リスト 1 の疑似コードはプロセス全体を示します。C++ コードはリスト 2 に示します。
array freqencyTable function countFrequencies array dataSet count i from 0 to dataSet.Length - 1 thisByte = dataSet[i] frequencyTable[thisByte] = frequencyTable[thisByte] + 1 function calculateShannonEntropy array dataSet countFrequencies dataSet entropyMeasurement = 0 -- count i from 0 to frequencyTable.Length - 1 H = frequencyTable [i] / dataSet.Length; entropyMeasurement = entropyMeasurement - ( H * log2( H ) ) -- return entropyMeasurement
リスト 1: シャノン・エントロピー計算の疑似コード
void countFrequencies(unsigned char *dataSet, int length)
{
int i;
/* 頻度バッファーをゼロにする */
for (i = 0; i < 256; i++)
{
frequencies[i] = 0;
}
/* データセットの各データ要素をループする */
for (i = 0; i < length; i++)
{
/* このデータ値の頻度をインクリメントする */
frequencies[dataSet[i]]++;
}
}
double calculateShannonEntropy(unsigned char *dataSet,
int length)
{
int i;
double entropy = 0, H;
/* 頻度をカウントする関数を呼びだす */
countFrequencies(dataSet, length);
for (i = 0; i < 256; i++)
{
if (frequencies[i] == 0)
{
continue;
}
H = (double)frequencies[i] / (double)length;
entropy -= (H * log2(H));
}
return(entropy);
}
リスト 2: シャノン・エントロピー計算の C++ コード
OpenMP* を使用した並列化
このアルゴリズムを並列化する最も簡単な方法は、countFrequencies 関数から着手することです。頻度をカウントするループを次のプラグマで修飾するだけで並列化できます。
#pragma omp parallel for
このプラグマを追加することで、複数のスレッドを生成し、高速に処理するようにコンパイラーに指示します。内部では、いくつかのスレッドがスポーンされ、各スレッドがそれぞれに割り当てられた計算の部分を実行します。
このアプローチには、1 つ問題があります。複数のスレッドが同時に同じデータの場所にアクセスする可能性があります。その場合、予測できない結果をもたらします。これは、データ競合と呼ばれます。この問題を排除するため、OpenMP* のリダクションを使用します。リダクションを使用すると、複数のスレッドがメモリー位置に安全にアクセスできるようになります。リスト 3 のコードは、OpenMP* プラグマを使用して countFrequencies コードを並列化したものです。
#pragma omp parallel for reduction(+:frequencies)
void countFrequencies(unsigned char *dataSet, int length)
{
int i;
/* 頻度バッファーをゼロにする */
for (i = 0; i < 256; i++)
{
frequencies[i] = 0;
}
/* データセットの各データ要素をループする */
for (i = 0; i < length; i++)
{
/* このデータ値の頻度をインクリメントする */
frequencies[dataSet[i]]++;
}
}
リスト 3: シャノン・エントロピー計算の並列化された C++ コード
まとめ
並列化によりアプリケーションの生産性を向上できます。研究者の時間を考慮すれば、スピードアップは実際の費用の節約につながります。OpenMP* を利用することで、簡単なコンパイラー・プラグマを追加するだけで簡単にループを並列化できます。
