容量を著しく節約するデータの保存法
アドレス圧縮
0から順番に、自然数を可変長のストレージに保存する。
3つの段階と、1つの応用がある。
方法A
アドレスとデータの並びが一致する場所のアドレスのビットに、1を立てる。
どんなに大きなデータでも、1ビットで保存することができる。
方法B
複数のデータを保存する為、自然数をそれぞれのビットに保存する。自然数の順番にアドレスの数字を並べてデータを復元する。
ビットはそれ自体が可変長になっており、運が悪くて同じビットに沢山自然数を立てなければならない場合でも、容量に限界はなく、普段はある定数まで、必要があればその定数倍位まで保存できる。
アドレスの桁数が十分小さければ保存されるアドレスの番地はカオス理論に従い、アドレスの桁数がそれより大きければ、そもそも同じアドレスに多くのビットを立てる（複数の自然数を保存する）確率が低いので、心配は要らない。
方法C
保存する場所をただのストレージではなく、完全N分木のセグ木にする。
それ以外は方法Bと同じ。
当然データは扱いやすいが、Nのデータを扱うのに、完全2分木なら2N-1個のビットが必要になる。この場合本当のアドレスを用いなくてよいのも利点の1つ。SSD等で特にそうだが、同じ場所ばかりに書き込むとストレージが壊れることが多いので、書き込む場所を変える必要があることが多い。この方法Cなら、実装次第でランダムアクセスのメモリのようにストレージを扱うことができる。
ここまでが基本。
方法D
方法Bか方法Cで保存したデータを、更に同じ方法で圧縮して保存する。
ユークリッドの互除法圧縮
一定のビット数のデータを自然数として見た時に、その自然数をそれよりかなり小さいある自然数Nでユークリッドの互除法を用いて商のみを保存することで、Nと商の数列として保存する。
アドレス圧縮が優秀なので、本当に何か理由があって限界まで圧縮して容量を節約したい時にのみ使うとよい。
Zipで無限に圧縮
圧縮した後、01を11、10を00、00を01、11を10に変換する。
Zip等の圧縮は、0や1が沢山並んでいるデータほど高い圧縮率で処理できるので、これだけで少しファイルサイズが減る。大したことないし、時間も掛かる。その為過去の方法となった。
本当に何がなんでもファイルサイズを小さくしたい時は使えるかもしれない。
