圧縮されたデータは偏っているので再圧縮できそう

# 圧縮されたデータの偏り

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

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

という規則に置き換えて、平面の左上(0,0) からの経路とします。経路を統計情報の図にすると
![サンプル](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/226677/889f785a-0679-890d-3151-623f5ef07520.png)
こんな感じになります。赤くなるほど高頻度で通過したことになります。緑の部分は通過しなかった、つまり、データとして出現しなかったことを意味します。

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

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


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

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

例: 4ビット中2ビットならば
1. 0011
2. 0101
3. 0110
4. 1001
5. 1010
6. 1100
$C(4,2)=6$ 通りです。

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

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

で、$B=4$ だと

```math:
\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ビット単位
![32ビット単位図](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/226677/75144d94-13d5-6216-ca9c-2c2f599c937c.png) 

64ビット単位
![64ビット単位図](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/226677/4feff31a-a3de-1e14-087d-e61054cc9b4a.png)

128ビット単位
![128ビット単位図](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/226677/298868a5-e4bc-fb3f-32d6-39777b391c4c.png)

256ビット単位
![256ビット単位図](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/226677/889f785a-0679-890d-3151-623f5ef07520.png)

512ビット単位
![512ビット単位図](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/226677/09549662-73f7-3f85-cecb-10b56a384f25.png)

1024ビット単位
![1024ビット単位図](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/226677/9a359ad3-01fd-6b71-ba4f-ad3716dbc1b4.png)

# 再圧縮するには？

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

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

```math:
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)$ は

```math:
 (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 ビットにする程度まではいけましたが、僅かなデータを処理するだけで、膨大な演算量になってしまい、とても実用的にはなりませんでした。

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