圧縮されたデータの偏り

zlib で圧縮したものを、あるビット幅の単位でデータを取り出して、各ビットを

0 ならば、座標(X) の右方向へ、１つ進む
1 ならば、座標(Y) の下方向へ、１つ進む

という規則に置き換えて、平面の左上(0,0) からの経路とします。経路を統計情報の図にすると

こんな感じになります。赤くなるほど高頻度で通過したことになります。緑の部分は通過しなかった、つまり、データとして出現しなかったことを意味します。

座標は、横が 0 の数、縦が 1 の数になります。全てのビットが 0 なら横一直線で、1 なら縦一直線です。左上からの横と縦の合計は、データの取り出し単位 $(B = X + Y)$ なので、画像の灰色部分は使いません。

図から、圧縮したデータの偏りが一目瞭然です。

二項係数に沿った分布になる(?)

始点 (0,0) から終点 (x,y) までの経路は、二項係数 $C\left(B,y\right)$ 通りになります。これは、$B$ ビット中に 1 が $y$ 個入っているときに出てくる値の個数です。

例: 4ビット中2ビットならば

0011
0101
0110
1001
1010
1100
$C(4,2)=6$ 通りです。

二項係数の $C\left(B,0\right)$ から $C\left(B,B\right)$ の総和

\sum_{n=0}^B{C \left( B,n \right)} = 2^B

で、$B=4$ だと

\sum_{n=0}^4{C \left( 4,n \right)} = 16 \\
C \left( 4,0 \right) = 1 \\
C \left( 4,1 \right) = 4 \\
C \left( 4,2 \right) = 6 \\
C \left( 4,3 \right) = 4 \\
C \left( 4,4 \right) = 1 \\

になります。

出てくる値が一様なら、二項係数に沿った分布になりそうですが、B が大きくなると $X=Y$ 付近に集中してきます。少ないビット数で取り出すと、出現する値が一様になりますが、長いビット列では「0と1」の頻度が「1:1」に近くなるので、ビット数の増加とともに、図にすると細くなっていきます。

同じデータで、取り出すビット幅を変えた図

32ビット単位

64ビット単位

128ビット単位

256ビット単位

512ビット単位

1024ビット単位

再圧縮するには？

図から分かることは、使われないビット並びの存在です。簡単な方法は、表現可能な $2^B$ 個の値から、使われない値を排除することでしょう。

例えば、$\left(2^B-1\right)$ が出てこないのであれば、$\left(2^B-1\right)$進数で表現できます。次の式

n \log_2{ \left( 2^B-1 \right) } \le \left( B n - 1 \right) \\
\begin{eqnarray}
B = 8\ &,& n = 178 \\
B = 16 &,& n = 45,426 \\
B = 32 &,& n = 2,977,044,472 \\
\end{eqnarray}

を満たす最小の整数 $n$ (データ個数)で 1 ビット削減できます。 1個ではなく、$m$ 個の値を排除できれば、$\left(2^B-m\right)$ 進数にできるので、n も小さくできます。

パスカルの三角形の変形

パスカルの三角形の、右辺を横軸、左辺を縦軸にすると

| | -1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|--:|--:|--:|--:|--:|--:|--:|--:|--:|--:|
| -1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 2 | 0 | 1 | 3 | 6 | 10 | 15 | 21 | 28 |
| 3 | 0 | 1 | 4 | 10 | 20 | 35 | 56 | 84 |
| 4 | 0 | 1 | 5 | 15 | 35 | 70 | 126 | 210 |
| 5 | 0 | 1 | 6 | 21 | 56 | 126 | 252 | 462 |
| 6 | 0 | 1 | 7 | 28 | 84 | 210 | 464 | 924 |

となって、各枡 $(x,y)$ は

 (x, y) = 左(x-1, y) + 上(x, y-1)

で埋め尽くすことになります。$(0,0)=1$ は始点なので例外です。これが二項係数になり、図と対応します。ここから図の緑の部分を排除します。排除方法は単純で、緑の部分を「0」として、表を作り直します。

例えば

| | -1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|--:|--:|--:|--:|--:|--:|--:|--:|--:|--:|
| -1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 1 | 1 | 1 | 0 | 0 |
| 1 | 0 | 1 | 2 | 3 | 4 | 5 | 5 | 0 |
| 2 | 0 | 1 | 3 | 6 | 10 | 15 | 20 | 20 |
| 3 | 0 | 1 | 4 | 10 | 20 | 35 | 55 | 75 |
| 4 | 0 | 1 | 5 | 15 | 35 | 70 | 125 | 200 |
| 5 | 0 | 0 | 5 | 20 | 55 | 125 | 250 | 450 |
| 6 | 0 | 0 | 0 | 20 | 75 | 200 | 450 | 900 |

とします。図と照らし合わせると、長いビット列では、$m$ を大きくできることがわかります。

ある程度の大きさの圧縮データならば、再圧縮可能であることは示せたと思います。

課題は効率的な方法

$m$ を増やして、4096 ビットのデータを 4095 ビットにする程度まではいけましたが、僅かなデータを処理するだけで、膨大な演算量になってしまい、とても実用的にはなりませんでした。

私の能力＆歳では、これ以上の効率化は厳しいようです。他の方法もあるでしょう。記事にして他力本願にしたいと思います。