圧縮されたデータを観察するとき、私はほぼ均一に分散されたバイトストリームを期待します。分布を測定するためにカイ二乗検定を使用すると、たとえばZIPファイルやその他の圧縮データではこの結果が得られますが、JPGファイルでは得られません。昨日、この理由を見つけることに費やしましたが、何も見つかりません。
JPGのエントロピーを計算すると、高い結果が得られます（たとえば、7,95ビット/バイト）。エントロピーと分布の間には関係があるに違いないと思いました。すべてのバイトがほぼ同じ確率で現れる場合、エントロピーは高くなります。しかし、カイ2乗を使用する場合、約4,5e-5のp値を取得します。
異なる分布がテスト結果にどのように影響するかを理解したいだけです...両方のテストで同じプロパティを測定できると思いましたが、明らかにできません。
ヒントありがとうございます！トム
メタ情報と jpeg ヘッダー データを無視すると、jpeg のペイロードは、ハフマン テーブルまたはエンコードされた MCU (Minimum-Coded-Units、サイズ 16x16 の正方形のブロック) を記述するブロックで構成されます。他にもあるかもしれませんが、これは最も頻繁なものです。
これらのブロックは で区切られています。0xFF 0xSSここ0xSSで、 は特定の開始コードです。これが最初の問題です。コメントでtwalbergが言及したように、0xFFもう少し頻繁です。
0xFFエンコードされた MCUで発生する可能性があります。この通常のペイロードと新しいブロックの開始を区別するために、0xFF 0x00が挿入されます。スタッフィングされていないペイロードの分布が完全に均一である0x00場合、スタッフィングされたデータでは 2 倍の頻度になります。さらに悪いことに、すべての MCU はバイトアライメント (より大きな値へのわずかな偏り) を得るためにバイナリ 1 で満たされ、再度スタッフィングが必要になる場合があります。
私が気づいていない他の要因もあるかもしれません。さらに詳しい情報が必要な場合は、jpeg ファイルを提供する必要があります。
rand_data の場合:
dd if=/dev/urandom of=rand_data count=4096 bs=256
rand_pseudo (python) の場合:
s = "".join(chr(i) for i in range(256))
with file("rand_pseudo", "wb") as f:
for i in range(4096):
f.write(s)
どちらもバイト値に関しては統一されているはずですよね? ;)
$ ll rand_*
-rw-r--r-- 1 apuch apuch 1048576 2012-12-04 20:11 rand_data
-rw-r--r-- 1 apuch apuch 1048967 2012-12-04 20:13 rand_data.tar.gz
-rw-r--r-- 1 apuch apuch 1048576 2012-12-04 20:14 rand_pseudo
-rw-r--r-- 1 apuch apuch 4538 2012-12-04 20:15 rand_pseudo.tar.gz
均一な分布はエントロピーが高いことを示している可能性がありますが、それを保証するものではありません。また、rand_data は 1MB から構成される場合があり0x00ます。その可能性は非常に低いですが、可能です。
これが私のJavaコードです
public static double getShannonEntropy_Image(BufferedImage actualImage){
List<String> values= new ArrayList<String>();
int n = 0;
Map<Integer, Integer> occ = new HashMap<>();
for(int i=0;i<actualImage.getHeight();i++){
for(int j=0;j<actualImage.getWidth();j++){
int pixel = actualImage.getRGB(j, i);
int alpha = (pixel >> 24) & 0xff;
int red = (pixel >> 16) & 0xff;
int green = (pixel >> 8) & 0xff;
int blue = (pixel) & 0xff;
//0.2989 * R + 0.5870 * G + 0.1140 * B greyscale conversion
//System.out.println("i="+i+" j="+j+" argb: " + alpha + ", " + red + ", " + green + ", " + blue);
int d= (int)Math.round(0.2989 * red + 0.5870 * green + 0.1140 * blue);
if(!values.contains(String.valueOf(d)))
values.add(String.valueOf(d));
if (occ.containsKey(d)) {
occ.put(d, occ.get(d) + 1);
} else {
occ.put(d, 1);
}
++n;
}
}
double e = 0.0;
for (Map.Entry<Integer, Integer> entry : occ.entrySet()) {
int cx = entry.getKey();
double p = (double) entry.getValue() / n;
e += p * log2(p);
}
return -e;
}
ここには 2 つのファイルがあります。1 つ目は dev/unrandom で生成されたランダム データ (約 46MB)、2 つ目は通常の JPG ファイル (約 9MB) です。JPG ファイルのシンボルが dev/urandom ほど均等に分散されていないことは明らかです。
両方のファイルを比較すると:
エントロピー: JPG: 7,969247 ビット/バイト RND: 7,999996 ビット/バイト
カイ二乗検定の P 値: JPG: 0 RND: 0,3621
エントロピーがどうしてこんなに高い結果につながるの?!?
