(ロカポ)開発などのブログ2008/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の値が大きい場合、ロカポータ方式が有効になる場合があります。次回は、この圧縮したデータ群をどうやってまとめるかについてです。Japanロカポ開発者です。