位置情報移動ログ圧縮

## 概要
GPSログ等の移動ログをそのまま、文字列で残すと膨大なログとなります。
いくつかの点を犠牲にしつつ、トレードオフで圧縮できる仕様を比較紹介します。

### いくつかの基本戦略

* 単純にバイナリ、浮動小数点数で保存する。文字列よりはデータ量小さくなる。
* 位置情報データの圧縮仕様を利用する。
 * LocaPorter
 * GeoHex + 移動方向

### いくつかのトレードオフ視点

* データ圧縮効率
* データの精度
* 即時検索性（圧縮することで、デコードしないと検索できなくなる）
* 時刻情報の保存可否（一点ごとに全時刻を残すか、まとまった移動ログ情報に一つだけ時刻情報を残すか）

## 位置情報圧縮仕様の紹介

* LocaPorter ( http://www.locaporter.com/jp/ )
 * 分解能数m～50cm程度の位置コードを、差分を繋いで圧縮する方式
 * コード方式の圧縮のため、間引き効果もあり。
 * 実装は無い（仕様は公開されている、仕様書：http://www.locaporter.com/jp/locaporter_spec_v1b.pdf ）
 * 利用は無料（ただしサポートもなし）
 * 連続文字列連結した場合でも、点毎の時刻情報も埋め込める
* GeoHex ( http://geogames.net/geohex/v3 )+移動方向
 * 分解能数m程度の位置コードからスタートして、移動方向（6方向）の連結で位置を記録する。
 * コード方式の圧縮のため、間引き効果もあり。
 * 実装はあり。
 * ライセンス料必要（1案件月3000円程度） => 最近無料になった
 * 連続文字連結した場合は、時刻情報は捨てられる
![image](https://qiita-image-store.s3.amazonaws.com/0/10108/3f871a75-0414-4f54-8d43-45f2ce74b3c8.png)  
この図の移動の場合、  
*XM5340821314,5,4,5*  
と言った感じで現せる。

## 位置ログ蓄積手法の比較
### 比較した蓄積手法一覧
下記のやり方について、実際にネット上で拾ったGPSログを蓄積し、比較を行った。

* lat,lngを普通のfloat(4バイト)カラムで、1点1点別レコードで蓄積

```sql
CREATE TABLE IF NOT EXISTS `pure_latlng_flt` (
  `date` datetime NOT NULL,
  `lat` float NOT NULL,
  `lng` float NOT NULL
) ENGINE=InnoDB DEFAULT CHARSET=utf8;
```
* lat,lngを普通のdouble(8バイト)カラムで、1点1点別レコードで蓄積

```sql
CREATE TABLE IF NOT EXISTS `pure_latlng_dbl` (
  `date` datetime NOT NULL,
  `lat` double NOT NULL,
  `lng` double NOT NULL
) ENGINE=InnoDB DEFAULT CHARSET=utf8;
```
* lat,lngをまとめてgeometryカラムで、1点1点別レコードで蓄積

```sql
CREATE TABLE IF NOT EXISTS `pure_latlng_geo` (
  `date` datetime NOT NULL,
  `latlng` geometry NOT NULL
) ENGINE=InnoDB DEFAULT CHARSET=utf8;
```
* 全移動をまとめて線オブジェクトにして、1レコードのgeometryカラムに全て蓄積

```sql
CREATE TABLE IF NOT EXISTS `all_latlng_geo` (
  `date` datetime NOT NULL,
  `latlng` geometry NOT NULL
) ENGINE=InnoDB DEFAULT CHARSET=utf8;
```
* 11レベル(最高精度のGeoHex)カラムで、1点1点別レコードで蓄積

```sql
CREATE TABLE IF NOT EXISTS `pure_geohex` (
  `date` datetime NOT NULL,
  `geohex` varchar(13) CHARACTER SET utf8 COLLATE utf8_bin NOT NULL
) ENGINE=InnoDB DEFAULT CHARSET=utf8;
```
* 10レベル(2番目精度のGeoHex)カラムで、1点1点別レコードで蓄積

```sql
CREATE TABLE IF NOT EXISTS `pure_geohex10` (
  `date` datetime NOT NULL,
  `geohex` varchar(12) CHARACTER SET utf8 COLLATE utf8_bin NOT NULL
) ENGINE=InnoDB DEFAULT CHARSET=utf8;
```
* 11レベル(最高精度のGeoHex)カラムで、差分連接で1文字列にしたものを1レコードで蓄積

```sql
CREATE TABLE IF NOT EXISTS `all_geohex` (
  `date` datetime NOT NULL,
  `geohex` text CHARACTER SET utf8 COLLATE utf8_bin NOT NULL
) ENGINE=InnoDB DEFAULT CHARSET=utf8;
```
* 10レベル(2番目精度のGeoHex)カラムで、差分連接で1文字列にしたものを1レコードで蓄積

```sql
CREATE TABLE IF NOT EXISTS `all_geohex10` (
  `date` datetime NOT NULL,
  `geohex` text CHARACTER SET utf8 COLLATE utf8_bin NOT NULL
) ENGINE=InnoDB DEFAULT CHARSET=utf8;
```
LocaPorterについては、実装が無いためテストできなかった。圧縮効率はGeoHexと同程度か若干よいと思われる。

## テストデータ：GPSログ

中に801点の経緯度データを含む、名古屋付近のGPSログデータをテストに使用。

データkml: http://t.tilemap.jp.s3.amazonaws.com/OriginalRoute.kml

## 蓄積データ容量結果：

|方式|データ件数|データ容量(bytes)|
|:--|:--|:--|
|lat,lng、一般カラム、float、個別蓄積|801|65536|
|lat,lng、一般カラム、double、個別蓄積|801|81920|
|geometryカラム、個別蓄積|801|81920|
|geometryカラム、一斉蓄積|1|32768|
|GeoHexレベル11、個別蓄積|749|65536|
|GeoHexレベル10、個別蓄積|634|49152|
|GeoHexレベル11、一斉蓄積|1|16384|
|GeoHexレベル10、一斉蓄積|1|16384|

* 1カラム蓄積方式で大幅に減るのは、各点に紐づく時刻データがなくなるためである。このため、容量は減るが移動ログ全体で単独の時刻情報しかつけられなくなる。
* 全件記録方式でも圧縮するとデータ件数が変わるのは、近い点の間引き効果が出るため。
* 一斉蓄積のGeoHexでレベル10と11に差が無いのは、Textカラムを使っているためと思われる。

## 圧縮による精度悪化比較

* オリジナルデータ（Double保存）：緑
* オリジナルデータをfloatで保存　：薄紫
* GeoHex Level11からのデコード　：青
* GeoHex Level10からのデコード　：赤紫

## 結果

![image](https://qiita-image-store.s3.amazonaws.com/0/10108/e28c2f21-5e25-5251-c633-68c40a47d24d.png)

* GeoHexレベル11からのデコードは、生データとほぼ遜色ない。
* GeoHexレベル10からのデコードも、若干ばたつくが異なる道に落ちるといった事はほぼない。
* floatでの保存はかなり精度が落ちる。

## まとめ

* LocaPorterはテストできなかったが、GeoHexとほぼ同程度とみなす

|手法|ログ圧縮効率|位置精度|復号なしで検索可能|全点時刻保持|ライセンス費用等|備考|
|:---|:--|:--|:--|:--|:--|:--|
|lat,lng、一般カラム、float、個別蓄積|×|◎|○|◎|◎|検索はインデックスは張れない（空間情報検索のため）|
|lat,lng、一般カラム、double、個別蓄積|△|×|○|◎|◎|検索はインデックスは張れない（空間情報検索のため）|
|geometryカラム、個別蓄積|×|◎|◎|◎|◎|検索インデックスを張るにはMyISAM必要|
|geometryカラム、一斉蓄積|○|◎|△|×|◎|MySQL5.6以上ならば復号なしで検索可能。MyISAM必要|
|GeoHexレベル11、個別蓄積|△|◎|×|◎	|△→◎||	
|GeoHexレベル10、個別蓄積|○|○|×|◎|△→◎||	
|GeoHexレベル11、一斉蓄積|◎|◎|×|×|△→◎||	
|GeoHexレベル10、一斉蓄積|◎|○|×|×|△→◎||	
|LocaPorter（想定）、個別蓄積|△|◎|×|◎|◎||	
|LocaPorter（想定）、一斉蓄積|◎|◎|×|○|◎|LocaPorterは時刻情報も圧縮蓄積可能なので、情報は残せる。ただし復号前に時刻検索は不可能。|