2006年9月15日

ルートデルタ

 きのうの続き。

 数字を単に10進数で表現するのは勿体無い。かといってバイナリの表現はURLパラメータにできない。%xxで表現できるが、余計に伸びてしまう。

 BASE64のように、使えるキャラクタだけ用いて64進数で表現したらどうだろうか。BASE64にはURLパラメータとして使えない文字があるからそれは別の文字に置き換えよう。

 これで、5桁+5桁ぐらいで表現できるかな。しかし、これでも大きい。

 緯度経度は、前回の地点からの差分を取ると、小さい数字になるだろう。それを可変長フォーマットでつなげていくとかなり圧縮できるのではないだろうか。

 可変長だと、データ長を示すヘッダが必要になる。ヘッダには緯度経度それぞれのデータ長が必要だ。それに2ビットずつ使おう。2ビットなので0〜3になる。3桁だとオーバーフローしそうなので、3のときは4桁と定義しよう。0桁は意味無いからな。0は1桁だ。さらに、符号も必要だ。初めは補数で表現しようかと思ったが、可変長データの補数は面倒だ。符号用のビットもちょうど余っているので使おう。

 ということで、ヘッダは 緯度符号(1bit)・緯度データ長(2bit)・経度符号(1bit)・経度データ長(2bit) の計6ビット。ちょうど64進数の一桁を使うことになる。

 そのあと、緯度経度の差分値を並べる。

 これで1つの点の表現が完成。ヘッダ1文字+緯度1〜4文字+経度1〜4文字=3〜9文字で1つの点。

 最初の点だけ困るな。4桁だと全世界を網羅できない。日本のどこか適当な場所を基準点として、そこからの差分にしようか。

 などなど考えて作ったのがコレ。

 ルート (ルートデルタ)
 ルート 説明書

Posted by rukihena at 23:09:18
トラックバックURL

このエントリーのトラックバックURL:
http://weblog.rukihena.com/mt/mt-tb.cgi/562

コメント