前回のデータの途中部分、電車の駅の部分は、駅であることが分かれば良いので200mほどの精度でも十分でしょう。この例では手を抜いて本当に駅だけですが、途中経路の形をもう少しこまかく(たとえば高速道路のカタチで)取りたいというような場合、重要度の低い部分を非可逆圧縮にして精度を落とすことで、もう少し圧縮できるようになります。駅の部分だけ200mの精度(4桁にコード化したもの)にしてみましょう。ここで、青字にしたところが、精度を下げたところと、元に戻した(上げた)ところです。ともに「_」(アンダースコア)が精度変更のサインになります。コードがアンダースコアで終わる場合は精度を下げる(桁を減らす)記号、反対にアンダースコアのあとコードが続く場合は、これまでの桁数にプラスしてアンダースコア以下の桁数を増やすという記号となります。ここで、アンダースコア直前の文字は、全データと同じであっても省略しないことに注意してください。bbbb)に分離します。なりません)詳細はロカポーターのサイトからダウンロードできる仕様書ご覧ください。これによって、データがさらに圧縮できる場合があります。この元データの例では、対象となるデータ数が少ないので、ほとんど変わりませんが、少しだけ短くなってきます。可変精度前(データ部分のみ)RZHBZwuimjCAjBZmAKnKrGZWqSrRtIoSABWSeyuYCjzELOkfDIBAxcdzuJEAhpNiyGCjqITluWwWxUmaTlz可変精度適用後(データ部分のみ)RZHBZwuimjCAjBZmAKnKrGZWqSrRtZ_m_SABWeyYjELkDIBxcdzJEhE_Ni_yGCjqITluWwWxUmaTlz以上がロカポーターの基本的な仕組みになります。次回から、ロカポーターがどのような用途に使えるのか、いろいろ検討していきたいと思います。例として、奈良県香芝市にあるロケージング本社から渋谷にあるゴーガさんへのルートを圧縮してみます。元データ緯度経度をそれぞれコード化すると、次のようになります。コード化の詳細は、別に機会に解説しますが、ここではとりあえず6文字の固定長文字列になることだけ頭においてください。このコードの精度はおよそ1mです。(コード化の手順はロカポーターの仕様書に記述してあります。)圧縮して、接続する工程は次のようになります。赤字で示してあるのは圧縮される部分です。右端の合成値をそのまま接続し、以下のようになります。これが圧縮したデータの部分です。RZHBZCwuimjfCAEhBZJmaAKIndDreGZWHqcSJriRFtaIDodSABWSDeyuiYCBjzcELOAkfgDIBAJxcdzugJEAHhpdNCiybGCEjqdITAlufWBwgCxiUImadTDlzhロカポーターのフォーマット規格は以下のようになっており、圧縮したデータ以外にも、ヘッダ、データセットのデータ種情報とターミネータを付けることが必要です。ヘッダの作成ロカポーターのバージョンは「1.0」なので、整数部分は「1」です。小数点以下の部分は、下記表にしたがって数字を英文字に置換します。少数以下は「0」なので「A」となります。この両方をつなげて「1A」となります。この変換は次の対応表を使います。カスタムコードは使用しないので省略します。したがって、ヘッダは「1A」となります。[g]2進数6ビットから文字への変換は以下の表を使います。よって、データ種類は「g」となります。データセットのターミネータ最後のデータの省略しない表記は「SDJITDxcdlzh」となるので、これをターミネータとします。これらをまとめると[ヘッダ][ピリオド][データ種類][データ][ターミネータ]となるので「1A.gRZHBZCwuimjfCAEhBZJmaAKIndDreGZWHqcSJriRFtaIDodSABWSDeyuiYCBjzcELOAkfgDIBAJxcdzugJEAHhpdNCiybGCEjqdITAlufWBwgCxiUImadTDlzhSDJITDxcdlzh」がロカポーターとなります。QRコードにするとこうです。道案内などの目的で、精度が8m程度でよければ、コード化の際に5桁の固定長文字列になり、次のようになります。データの圧縮工程は以下のようになります。右端の列を連結すると圧縮データになります。左の緯度の表で「K」と「W」が強調されている箇所があります。これは、データが前のデータと全く同じ場合ですが、空文字列にしてしまうとデータの再分離ができなくなるので、緯度経度データの場合、全く前のデータと値が同じ場合でも1文字残す仕様になっています。「1A.gRZHBZwuimjCAjBZmAKnKrGZWqSrRtIoSABWSeyuYCjzELOkfDIBAxcdzuJEhpNiyGCjqITluWwWxUmaTlzSDJITxcdlz」QRコードにするとこうなります。次回は、このデータの途中部分、電車の駅は200mほどの精度でもいいや、という場合の例です。重要度の低い部分を非可逆圧縮にして精度を落とすことで、もう少し圧縮できるようになります。高度を考えて見てください。仮にデータが1メートル単位として、地上付近では1メートル精度のデータが欲しい。飛行機で上空へ行けば10m単位や100m単位でも問題ない。このデータをどうやって混在させればよいのか。1000mロカポーターには答えがあります。ロカポータ圧縮の前提は、「固定長文字列であること」ですので、その「固定長」の長さを途中で変えてしまえばいいのです。1000mの3つのセットに分けます。括弧の中は精度を落とせば不要となるデータです。ところが、単に括弧の中を省略すれだけでは、不十分です。1000m精度のつもりの「01」が5桁の固定長と思われて「***01」と解釈されてしまいます。そこで、精度を落とす記号を導入します。5仮にこれらのデータをカンマ区切りでつなげてみるとこうなります。(実際はカンマの部分には緯度経度など他のデータが入り込むことになります。)00001,2,3,1_,2,3,1__,2,5ちなみに可変精度を使わないと00001,2,3,10,20,30,100,200,300となります。逆に精度を高めていくには、固定長の長さを増やします。これにもアンダースコアを使いますが、現データの後に、アンダースコア+増加するデータを加えます。1m上記のデータは精度を変更すると、次のようになる。1m圧縮すると次のようになる。1カンマ区切りでつなげてみるとこうなります。(実際はカンマの部分には緯度経度など他のデータが入り込むことになります。)05,2,1,0_10,02,1,0_3,2,1ちなみに可変精度を使わないと05000,2000,1000,0100,020,10,03,2,1となります。圧縮のアイデアは、このように高度のデータについて考えている時に出てきました。当初は対数を使って、地上付近を密に、上空を粗くするコード体系を用意していたのですが、精度を可変にすることで、1番目のデータのみフル精度が必要であり、あとは好きな桁に落とせば良いことから、もっとも扱いやすい10進法のまま高度を扱うことにしました。・精度記号によるデータの接続が基本的なロカポーターの実装に必要なロジックとなります。post2008/02/16ロカポーターのしくみ(2)2.圧縮したデータ群の接続方法ロカポータ圧縮で圧縮した各データは、可変長(というか不定長)のデータの羅列となります。データが接頭符号であれば、そのまま接続できますし、接尾符号でデータの区切りが分かる場合もそのまま接続できます。接頭符号など、情報圧縮全般についてはここが詳しい!情報と通信のハイパーテキスト(詳しい!)しかし、接頭符号でも接尾符号でもないデータをそのまま接続すると、今度分離しようとした時に、どこで分離したらよいか分からず、一意にデータを復元できなくなる恐れがあります。そのばあい、区切り文字を使うこともできますが、仮にデータが100個あれば区切り文字が1文字としても99文字余分に必要になってしまいます。なんだかもったいない。二進数であれば、このようなデータを接続するには(各データの値が小さい場合は)ワイル(weyl)符号化、ガンマ(γ)符号化、(δ)デルタ符号化、などの方法が良く使われ、これらの符号化により接頭符号化するものです。ソフトバンクパブリッシング)ガンマ符号化デルタ符号化については、下記サイトの説明が良く分かります。データ圧縮)さて、ロカポーターでは二進数での処理はせず、文字列で圧縮しているので、文字列ベースでもう少し簡単なものは出来ないか、と考えたのが以下のロカポーターの方式です。あるのでそれぞれを全く違う種類の文字で並べれば人間が目で見ても区切りがすぐわかる。いうように単純に文字を置換します。5先ほど、全く同じデータの際でも必ず1文字は残すルールとしたので、このまま接続しても、文字種によってデータの境界が明白なので、区切り文字などを使用しなくても、そのまま接続してOKBAADA20012CI35C135BJ5AJJJI29H5できあがり。分離するときは、文字か数字かで単純に分ける。5はい、もとどおりです。なんと単純な仕組みですが、これでも「差分をとって、二進数にして、ガンマ符号にして、最後のホフマン符号で圧縮して、6ビットづつ64進法の文字に戻す」とやる場合と比べて、2倍も差はないです。2倍というのは適当な言い方ですが、仮に10000文字の元データをギュウギュウに圧縮して1000文字とすると、ロカポーター圧縮のような簡易形式でも、たいてい2000文字以内には収まる、という意味です。ちなみにこの例では、データの種類ごとに使う文字の種類を変えたが、要するにデータの最後の文字と、次のデータの(どこになるかわからない)先頭部分とが違う文字であればOKです。(AAAA)0のように、問題なくデータを再分離可能です。ロカポータでは、この両方の方式を組み合わせています。緯度経度には前者の方式をベースにしたもの、高度や日時などの付加データには後者の方式をベースにしたもの使用しています。次回は、ロカポーターの目玉である、データ途中の精度変更です。ご質問等があれば、このブログに投稿頂くか、ロケージングまでお問い合わせください。それとロカポーターのホームページ(突貫で作ったので、まだ1ページモノですが・・・)からロカポーターの仕様書をダウンロードできるようになっていますので、どうぞご利用ください。post2008/02/15ロカポーターのしくみ(1)これから、ロカポーターによる位置情報圧縮の基本的な仕組みを紹介していくことにします。1.ロカポータ圧縮技術のもっとも基本的な考え方まず、データはデータ種ごとに、すべて固定長の文字列データにします。09997通常、このような数値のデータで、データ値が近いデータ群の圧縮には、差分形式がよく用いられます。-1ロカポーターでは、差分ではなく、同じ桁を比較して、『文字列の違う箇所』を記述します。比較は左側から行い、違う箇所より右は同じ値の場合すべて記述します。7赤字の桁は直前のデータと同じなので、省略するちなみにデコードは、上から順に足りない桁を借りてきて埋めるだけ。固定長と決まっているので、たとえば5桁固定長のところ3桁しかなければ、上位2桁が前のデータと同じ(冗長)と判断する。09997赤字の桁は、足りないので直前のデータから借りてきて補完した部分。復元したデータは、次のデータの補完の基準となる。差分方式はプラスマイナスが発生するので、(マイナスの場合は)符号用に1文字必要となること。二進数ではデータごとに1ビットづつ余分に必要となることがあります。ロカポータ方式では、マイナス値は発生しないので、符号処理が不要です。対象が数値ではなく文字列でも、数値演算の必要がなく、文字列の比較のみの簡単な処理で実現できます。上記データの#1、#4のように、圧縮したデータの中に、生のデータを挿入してもまったく処理が破綻しません。差分方式の符号処理の場合、2進数なら符号の為に1ビット確保する必要があります。固定長データのとりうる値が0~255としましょう。2つのデータの差分のとりうる値は-255~+255ので、510種類の差分値を表す必要があり、9ビットの差分表現領域が必要です。これは元データの255=8ビットから符号の分の桁が増えるためです。うまいやり方もあります。現在の値が100とすれば、次のデータの差分は-100~+155までに限定されます。これは幅が255なので、実質8ビットに抑えられるちう方法もあります。この場合、復号には差分値を足して、255をオーバーした分はマイナス扱いにするなど、一工夫必要です。ロカポーターの場合は、何の符号制御も必要なく、ただ文字比較をするだけです!最後の生データの挿入ですが、差分方式だろうとロカポータ方式だろうと、基準とする点に誤差があれば、その誤差は以後のデータに順に引き継がれてしまいます。時々生データを使い、その間を差分データ等で埋めることになります。ロカポータだと、任意の場所に生データを埋め込むことが出来、しかも生データと圧縮データの違いはデータ長がフルの固定長あるか、それより短いかという違いのみです。それによって前後の処理が変わることは全く無く、全データを同じアルゴリズムで処理できます。差分方式では、生データか、差分データかという区別するための情報を各データ毎に付加する必要があり、ロカポータではその分、節約できます。<-圧縮データこの方式のデメリットは、たとえば9999と10000のような桁上がり付近のデータ同士の場合、差分なら1で済むところ10000と大きな表現になってしまうことです。経路情報やエリア情報は、構成する各点の値が少しづつ変化すると考えられるため、単なる数値や数値を表すN進法文字列表現のような、左側に上位桁情報が、右側に下位桁情報がくるような(狭義の単調増加関数である)固定長データを利用すると、左側の桁が同じ値となって省略できる可能性が非常に高くなります。反面、縦横の座標を基にしたような、メッシュコードなどの文字列では、必ずしも上位桁が左側一方(あるいは右側一方)に偏る可能性が少ないため、この方式による圧縮の効果は少なくなります。log2(Nの(M+1)乗)の情報量となります。lon2((N+1)のM乗)の情報量となります。大小関係によりますが、実際のデータによって結果は大きく変わります。計算してみると、元が2進法の場合、ロカポータ方式のメリットのある可能性は非常に少ないです。元が10進法などNの値が大きい場合、ロカポータ方式が有効になる場合があります。次回は、この圧縮したデータ群をどうやってまとめるかについてです。LocaPorter(ロカポーター)』発売開始しました大変お待たせいたしました。スケジュールが延び延びになっていました『ロカポーター』の発売を、バレンタインデー前日の本日2008年2月13日に開始いたしました。仕様バージョン1.1ですが、皆さんのご意見を取り入れて、どんどん使いやすいものに変えていきたいと思っています。よろしければロカポーターのサイトから「ロカポーター仕様書」をご請求ください。これから、ロカポーターのアルゴリズムを、このブログでも分かり易く解説していきたいと思います。今後は「位置情報ロカポ」と共に「ロカポーター」も、どうぞよろしくお願いいたします。開発の経緯の記録の最後に、ロカポーターの名前の由来を残しておきたいと思います。最初、「ロカポ圧縮」というベタな名前だったこの技術、位置情報系サービス間のパラメータとして使ってほしい、ということでジオメディア2008新年会では「LocaParam」という名前でご紹介させて頂きました。Locazing(位置情報ロカポで知られてますが、実は「ロケージング」という会社名なんです。Tickins氏に聞いてみたところ、Paramというのがいまいちしっくりこないとのこと。Parameterの後半のmeterをとって「Locameter」とか「Geometer」にしてはどうかとアドバイスをもらいました。geometerってそのまんま「幾何学の数学者」だし、meterというとメートルと思ってしまいます。インチ・ヤード法の国の方はあまりイメージしないんでしょうかねぇ。マッシュアップアワードでご一緒させて頂いた、ここギコ!さん!からもロカプレスという名前候補をもらったり、同じくご一緒させて頂いたAN-NAIさんからも「ロカポ」という音がいいので残した法がいい、などいろんな方にアドバイスもらいました。