データをなるべく小さくする : プログラミング指南

データを無圧縮でなるべく小さくするには、まるごと保存を極力無くす事ですね。それは例えば一つ前のデータからの差分にするとか、データがある場所だけ位置情報と共に覚えるようにするだとか、そのデータの特性を利用して無駄を見つけて潰していきます。まあ、これは広義の圧縮にはなりますが。

例えばこんなタイリングデータを考えてみましょう。


    0101010101010101010101
    1010101010101010101010
    0101010101010101010101
    1010101010101010101010
    0101010101010101010101
    1010101010101010101010
    0101010101010101010101
    1010101010101010101010

これをこのまま記録しようとすると、割と大きなデータになりますが、この場合は自分の一つ上の行と XOR すると…


    0101010101010101010101
    1111111111111111111111
    1111111111111111111111
    1111111111111111111111
    1111111111111111111111
    1111111111111111111111
    1111111111111111111111
    1111111111111111111111

なんと、最初の行以外は全部 1 だけになってしまいます。そこでデータの持ち方を…


    0101010101010101010101, 7

こうすると、最初の行はそのまま覚えていますが、残りの 7行は全て 1 と XOR するだけで再現してしまいます。最初の行も繰り返しのデータなので、


    11, 7

このようなデータとすれば、01 を 11 回切り返して 1行を作成して、その行を 7 回 1 と XOR するだけで再現します。たった 2バイトまで小さくなってしまいました。普通にlz4とかの圧縮をかけるより小さいですよね。これはとても極端な例ですが、データの特性を利用する考え方はとても大事だという例です。

では、今度は以下のデータではどうでしょうか。


    2000, 1997, 1986, 1966, 1938, 1907, 1870, 1816, 
    1765, 1709, 1638, 1572, 1504, 1421, 1338, 1257, 
    1173, 1086,  996,  916,  828,  740,  663,  576, 
     500,  431,  356,  291,  233,  180,  138,   96, 
      62,   35,   11,    6,    4,    0,   20,   39, 
      65,   97,  132,  182,  230,  292,  353,  431, 
     501,  580,  657,  744,  829,  908,  997, 1086, 
    1172, 1255, 1338, 1425, 1500, 1577, 1643, 1704, 
    1764, 1817, 1866, 1905, 1935, 1968, 1984, 1999,

一見、普通にデータを保存するしかないように見えますが、このデータの規則性に気がつくと小さく出来ます。それが差分です。今回は直前のデータとの差分を取ってみましょう。すると…


    2000,
      -3, -11, -20, -28, -31, -37, -54, -51
     -56, -71, -66, -68, -83, -83, -81, -84
     -87, -90, -80, -88, -88, -77, -87, -76
     -69, -75, -65, -58, -53, -42, -42, -34
     -27, -24,  -5,  -2,  -4,  20,  19,  26
      32,  35,  50,  48,  62,  61,  78,  70
      79,  77,  87,  85,  79,  89,  89,  86
      83,  83,  87,  75,  77,  66,  61,  60
      53,  49,  39,  30,  33,  16,  15,

こんなデータに変わります。気か付きました？最初のデータのままだと全て 16bit でデータを保存する必要がありましたが、差分に変更する事で最初の基数だけ 16bit で残りは 8bit データで保存する事ができるように変わっているのです。データ総数は 72個ですから、最初は 144バイトだったのが、差分にする事で 73バイトに半減しました。

都合が良い？そうですね、今回は検証用のデータなので簡単に縮みました。でも、元データを作った本人なら、そのデータの傾向は知っているはずなので、より効率的なデータ構造を思い至る事が出来ると思っています。ちなみにこのサンプルデータですが、実はノイズ付きのコサインデータなので、それを知っているのなら…


    72, 2000, 5

円周を72分割、最大値2000、ノイズ±5 というデータに置き換える事が出来ます。但し、完全に同一のデータでは無く、ノイズの誤差が出ます。それすらも完全に同一にするのであれば、


    72, 2000, 5, 1234

こんな感じで最後に乱数のタネをデータとして保持する事で、完全に同じデータを再現する事が出来ます。これでデータは 1 + 2 + 1 + 4 = 8バイトまで縮む事になります。このような考察をデータ構造を考える際には常に意識する事が大事です。例え、データが思うように縮まらなかったとしても、そのように考えるクセを付ける事で、次にはデータを小さく効率的に用意する事が出来るようになると私は信じています。