2008/02/15
ロカポーターのしくみ（１）
これから、ロカポーターによる位置情報圧縮の基本的な仕組みを紹介していくことにします。
１．ロカポータ圧縮技術のもっとも基本的な考え方
まず、データはデータ種ごとに、すべて固定長の文字列データにします。
例：5桁（5文字）固定のデータにする場合
元データ ５桁固定
10030 10030
10028 10028
10022 10022
10019 10019
9998 09998
9997 09997
通常、このような数値のデータで、データ値が近いデータ群の圧縮には、差分形式がよく用いられます。
元データ ５桁固定 差分
10030 10030 N/A
10028 10028 -2
10022 10022 -6
10019 10019 -3
9998 09998 -19
9997 09997 -1
ロカポーターでは、差分ではなく、同じ桁を比較して、『文字列の違う箇所』を記述します。
ただし、比較は左側から行い、違う箇所より右は同じ値の場合すべて記述します。
元データ ５桁固定 ロカポータ方式
10030 10030 10030
10028 10028 28
10022 10022 2
10019 10019 19
9998 09998 09998
9997 09997 7
赤字の桁は直前のデータと同じなので、省略する
ちなみにデコードは、上から順に足りない桁を借りてきて埋めるだけ。
固定長と決まっているので、たとえば5桁固定長のところ3桁しかなければ、上位2桁が前のデータと同じ（冗長）と判断する。
ロカポータ
10030 10030
28 10028 ->10028
2 10022 ->10022
19 10019 ->10019
09998 09998 ->09998
7 09997
赤字の桁は、足りないので直前のデータから借りてきて補完した部分。復元したデータは、次のデータの補完の基準となる。
差分方式との違うは、
差分方式の符号処理の場合、2進数なら符号の為に1ビット確保する必要があります。
たとえば固定長データのとりうる値が０～２５５としましょう。２つのデータの差分のとりうる値は-255～+255ので、510種類の差分値を表す必要があり、9ビットの差分表現領域が必要です。これは元データの255=８ビットから符号の分の桁が増えるためです。
ただし、うまいやり方もあります。
現在の値が１００とすれば、次のデータの差分は-100～+155までに限定されます。これは幅が255なので、実質8ビットに抑えられるちう方法もあります。この場合、復号には差分値を足して、255をオーバーした分はマイナス扱いにするなど、一工夫必要です。
ロカポーターの場合は、何の符号制御も必要なく、ただ文字比較をするだけです！
最後の生データの挿入ですが、差分方式だろうとロカポータ方式だろうと、基準とする点に誤差があれば、その誤差は以後のデータに順に引き継がれてしまいます。ですので、時々生データを使い、その間を差分データ等で埋めることになります。ロカポータだと、任意の場所に生データを埋め込むことが出来、しかも生データと圧縮データの違いはデータ長がフルの固定長あるか、それより短いかという違いのみです。
それによって前後の処理が変わることは全く無く、全データを同じアルゴリズムで処理できます。差分方式では、生データか、差分データかという区別するための情報を各データ毎に付加する必要があり、ロカポータではその分、節約できます。
元データ ５桁固定 ロカポータ方式
10030 10030 10030 <-生データ（先頭は必ず生データ））
10028 10028 28 <-圧縮データ
10022 10022 10022 <-生データ（意図的に挿入）
10019 10019 19 <-圧縮データ
9998 09998 09998 <-圧縮データ（結果的に生データと同じ）
9997 09997 7 <-圧縮データ
この方式のデメリットは、たとえば9999と10000のような桁上がり付近のデータ同士の場合、差分なら１で済むところ10000と大きな表現になってしまうことです。
経路情報やエリア情報は、構成する各点の値が少しづつ変化すると考えられるため、単なる数値や数値を表すＮ進法文字列表現のような、左側に上位桁情報が、右側に下位桁情報がくるような（狭義の単調増加関数である）固定長データを利用すると、左側の桁が同じ値となって省略できる可能性が非常に高くなります。
反面、縦横の座標を基にしたような、メッシュコードなどの文字列では、必ずしも上位桁が左側一方（あるいは右側一方）に偏る可能性が少ないため、この方式による圧縮の効果は少なくなります。
ちなみに、現在N進法でM桁あるとすると、差分を使うと最大M桁の可能性があるのと、符号に１桁使うので、ひとつのデータ当たり最大 log2(Nの(M+1)乗)の情報量となります。ロカポーター方式では桁数は変わらない代わりに同じ場合は空白を使うのでN+1進法のM桁となり、最大 lon2((N+1)のM乗)の情報量となります。どちらがより有利かは N^(M+1) と (N+1)^M の大小関係によりますが、実際のデータによって結果は大きく変わります。
計算してみると、元が2進法の場合、ロカポータ方式のメリットのある可能性は非常に少ないです。ただ、元が10進法などNの値が大きい場合、ロカポータ方式が有効になる場合があります。
次回は、この圧縮したデータ群をどうやってまとめるかについてです。
続く
１．ロカポータ圧縮技術のもっとも基本的な考え方
まず、データはデータ種ごとに、すべて固定長の文字列データにします。
例：5桁（5文字）固定のデータにする場合
元データ ５桁固定
10030 10030
10028 10028
10022 10022
10019 10019
9998 09998
9997 09997
通常、このような数値のデータで、データ値が近いデータ群の圧縮には、差分形式がよく用いられます。
元データ ５桁固定 差分
10030 10030 N/A
10028 10028 -2
10022 10022 -6
10019 10019 -3
9998 09998 -19
9997 09997 -1
ロカポーターでは、差分ではなく、同じ桁を比較して、『文字列の違う箇所』を記述します。
ただし、比較は左側から行い、違う箇所より右は同じ値の場合すべて記述します。
元データ ５桁固定 ロカポータ方式
10030 10030 10030
10028 10028 28
10022 10022 2
10019 10019 19
9998 09998 09998
9997 09997 7
赤字の桁は直前のデータと同じなので、省略する
ちなみにデコードは、上から順に足りない桁を借りてきて埋めるだけ。
固定長と決まっているので、たとえば5桁固定長のところ3桁しかなければ、上位2桁が前のデータと同じ（冗長）と判断する。
ロカポータ
10030 10030
28 10028 ->10028
2 10022 ->10022
19 10019 ->10019
09998 09998 ->09998
7 09997
赤字の桁は、足りないので直前のデータから借りてきて補完した部分。復元したデータは、次のデータの補完の基準となる。
差分方式との違うは、
- 差分方式はプラスマイナスが発生するので、（マイナスの場合は）符号用に1文字必要となること。二進数ではデータごとに1ビットづつ余分に必要となることがあります。ロカポータ方式では、マイナス値は発生しないので、符号処理が不要です。
- 対象が数値ではなく文字列でも、数値演算の必要がなく、文字列の比較のみの簡単な処理で実現できます。
- 上記データの＃１、＃４のように、圧縮したデータの中に、生のデータを挿入してもまったく処理が破綻しません。
差分方式の符号処理の場合、2進数なら符号の為に1ビット確保する必要があります。
たとえば固定長データのとりうる値が０～２５５としましょう。２つのデータの差分のとりうる値は-255～+255ので、510種類の差分値を表す必要があり、9ビットの差分表現領域が必要です。これは元データの255=８ビットから符号の分の桁が増えるためです。
ただし、うまいやり方もあります。
現在の値が１００とすれば、次のデータの差分は-100～+155までに限定されます。これは幅が255なので、実質8ビットに抑えられるちう方法もあります。この場合、復号には差分値を足して、255をオーバーした分はマイナス扱いにするなど、一工夫必要です。
ロカポーターの場合は、何の符号制御も必要なく、ただ文字比較をするだけです！
最後の生データの挿入ですが、差分方式だろうとロカポータ方式だろうと、基準とする点に誤差があれば、その誤差は以後のデータに順に引き継がれてしまいます。ですので、時々生データを使い、その間を差分データ等で埋めることになります。ロカポータだと、任意の場所に生データを埋め込むことが出来、しかも生データと圧縮データの違いはデータ長がフルの固定長あるか、それより短いかという違いのみです。
それによって前後の処理が変わることは全く無く、全データを同じアルゴリズムで処理できます。差分方式では、生データか、差分データかという区別するための情報を各データ毎に付加する必要があり、ロカポータではその分、節約できます。
元データ ５桁固定 ロカポータ方式
10030 10030 10030 <-生データ（先頭は必ず生データ））
10028 10028 28 <-圧縮データ
10022 10022 10022 <-生データ（意図的に挿入）
10019 10019 19 <-圧縮データ
9998 09998 09998 <-圧縮データ（結果的に生データと同じ）
9997 09997 7 <-圧縮データ
この方式のデメリットは、たとえば9999と10000のような桁上がり付近のデータ同士の場合、差分なら１で済むところ10000と大きな表現になってしまうことです。
経路情報やエリア情報は、構成する各点の値が少しづつ変化すると考えられるため、単なる数値や数値を表すＮ進法文字列表現のような、左側に上位桁情報が、右側に下位桁情報がくるような（狭義の単調増加関数である）固定長データを利用すると、左側の桁が同じ値となって省略できる可能性が非常に高くなります。
反面、縦横の座標を基にしたような、メッシュコードなどの文字列では、必ずしも上位桁が左側一方（あるいは右側一方）に偏る可能性が少ないため、この方式による圧縮の効果は少なくなります。
ちなみに、現在N進法でM桁あるとすると、差分を使うと最大M桁の可能性があるのと、符号に１桁使うので、ひとつのデータ当たり最大 log2(Nの(M+1)乗)の情報量となります。ロカポーター方式では桁数は変わらない代わりに同じ場合は空白を使うのでN+1進法のM桁となり、最大 lon2((N+1)のM乗)の情報量となります。どちらがより有利かは N^(M+1) と (N+1)^M の大小関係によりますが、実際のデータによって結果は大きく変わります。
計算してみると、元が2進法の場合、ロカポータ方式のメリットのある可能性は非常に少ないです。ただ、元が10進法などNの値が大きい場合、ロカポータ方式が有効になる場合があります。
次回は、この圧縮したデータ群をどうやってまとめるかについてです。
続く
# posted by Nao : 10:26
