2008/02/16
ロカポーターのしくみ（２）
２．圧縮したデータ群の接続方法
ロカポータ圧縮で圧縮した各データは、可変長（というか不定長）のデータの羅列となります。
データが接頭符号であれば、そのまま接続できますし、接尾符号でデータの区切りが分かる場合もそのまま接続できます。
接頭符号など、情報圧縮全般についてはここが詳しい！
しかし、接頭符号でも接尾符号でもないデータをそのまま接続すると、今度分離しようとした時に、どこで分離したらよいか分からず、一意にデータを復元できなくなる恐れがあります。
そのばあい、区切り文字を使うこともできますが、仮にデータが１００個あれば区切り文字が1文字としても99文字余分に必要になってしまいます。なんだかもったいない。。。
二進数であれば、このようなデータを接続するには（各データの値が小さい場合は）ワイル(weyl)符号化、ガンマ(γ)符号化、(δ)デルタ符号化、などの方法が良く使われ、これらの符号化により接頭符号化するものです。よく考えられていますね！
ガンマ符号化
デルタ符号化
については、下記サイトの説明が良く分かります。
参考
http://codezine.jp/a/article/aid/475.aspx
CodeZine：δ符号によるデータ領域の節約（CODEC, δ符号, データ圧縮）
さて、ロカポーターでは二進数での処理はせず、文字列で圧縮しているので、文字列ベースでもう少し簡単なものは出来ないか、と考えたのが以下のロカポーターの方式です。
とても単純なアイデアですが、せっかくデータが緯度、経度、高度・・・とあるのでそれぞれを全く違う種類の文字で並べれば人間が目で見ても区切りがすぐわかる。
緯度 経度
５桁固定 ロカポータ ５桁固定 ロカポータ
10030 10030 20013 20012
10028 28 20035 35
10022 2 20135 135
10019 19 20135 (空)→必ず1文字は残すルールにして[5]とする
09998 09998 20029 29
09997 7 20025 5
とします。ここで緯度データの方を 0->A, 1->B, 2->C,,,9->J というように単純に文字を置換します。
緯度 経度
５桁固定 ロカポータ ５桁固定 ロカポータ
10030 BAADA 20013 20012
10028 CI 20035 35
10022 C 20135 135
10019 BJ 20135 5
09998 AJJJI 20029 29
09997 H 20025 5
で、緯度、経度、の順に並べる
BAADA 20012 CI 35 C 135 BJ 5 AJJJI 29 H 5
先ほど、全く同じデータの際でも必ず1文字は残すルールとしたので、このまま接続しても、文字種によってデータの境界が明白なので、区切り文字などを使用しなくても、そのまま接続してＯＫ
BAADA20012CI35C135BJ5AJJJI29H5
できあがり。
分離するときは、文字か数字かで単純に分ける。手作業でもできる！
BAADA 20012 CI 35 C 135 BJ 5 AJJJI 29 H 5
はい、もとどおりです。
なんと単純な仕組みですが、これでも「差分をとって、二進数にして、ガンマ符号にして、最後のホフマン符号で圧縮して、6ビットづつ64進法の文字に戻す」とやる場合と比べて、2倍も差はないです。2倍というのは適当な言い方ですが、仮に１００００文字の元データをギュウギュウに圧縮して１０００文字とすると、ロカポーター圧縮のような簡易形式でも、たいてい２０００文字以内には収まる、という意味です。
ちなみにこの例では、データの種類ごとに使う文字の種類を変えたが、要するにデータの最後の文字と、次のデータの（どこになるかわからない）先頭部分とが違う文字であればＯＫです。ですので、たとえば、各データを
ＡＡＡＡ０ （Ａのところは26進法、０のところは10進法、全部で０～４５６９７５９まで）
というロカポのような記述を使うと、最後が数字ひとつとわかっているので
ＡＡ０ＡＡ０ → （ＡＡ）ＡＡ０ と（ＡＡ）ＡＡ０
ＡＡＡ０００ → （Ａ）ＡＡＡ０ と （ＡＡＡＡ）０ と （ＡＡＡＡ）０
のように、問題なくデータを再分離可能です。
ロカポータでは、この両方の方式を組み合わせています。緯度経度には前者の方式をベースにしたもの、高度や日時などの付加データには後者の方式をベースにしたもの使用しています。
次回は、ロカポーターの目玉である、データ途中の精度変更です。
なお、ご質問等があれば、このブログに投稿頂くか、ロケージングまでお問い合わせください。
それとロカポーターのホームページ（突貫で作ったので、まだ１ページモノですが・・・）からロカポーターの仕様書をダウンロードできるようになっていますので、どうぞご利用ください。
ロカポータ圧縮で圧縮した各データは、可変長（というか不定長）のデータの羅列となります。
データが接頭符号であれば、そのまま接続できますし、接尾符号でデータの区切りが分かる場合もそのまま接続できます。
接頭符号など、情報圧縮全般についてはここが詳しい！
情報と通信のハイパーテキスト（詳しい！）
しかし、接頭符号でも接尾符号でもないデータをそのまま接続すると、今度分離しようとした時に、どこで分離したらよいか分からず、一意にデータを復元できなくなる恐れがあります。
そのばあい、区切り文字を使うこともできますが、仮にデータが１００個あれば区切り文字が1文字としても99文字余分に必要になってしまいます。なんだかもったいない。。。
二進数であれば、このようなデータを接続するには（各データの値が小さい場合は）ワイル(weyl)符号化、ガンマ(γ)符号化、(δ)デルタ符号化、などの方法が良く使われ、これらの符号化により接頭符号化するものです。よく考えられていますね！
ワイル符号化
０ 表現不可
１～４ 0xx
５～８ 10xxx
９～１６ 110xxxx
１７～３２ 1110xxxxx
３３～６４ 11110xxxxxx
６５～１２８ 111110xxxxxxx
１２９～２５６ 1111110xxxxxxxx
：
xxxの部分に数値を2進数で表現したものが入る
（出展：「圧縮アルゴリズム 符号化の原理とC言語による実装」昌達Ｋ’ｚ著 ソフトバンクパブリッシング）
ガンマ符号化
デルタ符号化
については、下記サイトの説明が良く分かります。
参考
http://codezine.jp/a/article/aid/475.aspx
CodeZine：δ符号によるデータ領域の節約（CODEC, δ符号, データ圧縮）
さて、ロカポーターでは二進数での処理はせず、文字列で圧縮しているので、文字列ベースでもう少し簡単なものは出来ないか、と考えたのが以下のロカポーターの方式です。
とても単純なアイデアですが、せっかくデータが緯度、経度、高度・・・とあるのでそれぞれを全く違う種類の文字で並べれば人間が目で見ても区切りがすぐわかる。
緯度 経度
５桁固定 ロカポータ ５桁固定 ロカポータ
10030 10030 20013 20012
10028 28 20035 35
10022 2 20135 135
10019 19 20135 (空)→必ず1文字は残すルールにして[5]とする
09998 09998 20029 29
09997 7 20025 5
とします。ここで緯度データの方を 0->A, 1->B, 2->C,,,9->J というように単純に文字を置換します。
緯度 経度
５桁固定 ロカポータ ５桁固定 ロカポータ
10030 BAADA 20013 20012
10028 CI 20035 35
10022 C 20135 135
10019 BJ 20135 5
09998 AJJJI 20029 29
09997 H 20025 5
で、緯度、経度、の順に並べる
BAADA 20012 CI 35 C 135 BJ 5 AJJJI 29 H 5
先ほど、全く同じデータの際でも必ず1文字は残すルールとしたので、このまま接続しても、文字種によってデータの境界が明白なので、区切り文字などを使用しなくても、そのまま接続してＯＫ
BAADA20012CI35C135BJ5AJJJI29H5
できあがり。
分離するときは、文字か数字かで単純に分ける。手作業でもできる！
BAADA 20012 CI 35 C 135 BJ 5 AJJJI 29 H 5
はい、もとどおりです。
なんと単純な仕組みですが、これでも「差分をとって、二進数にして、ガンマ符号にして、最後のホフマン符号で圧縮して、6ビットづつ64進法の文字に戻す」とやる場合と比べて、2倍も差はないです。2倍というのは適当な言い方ですが、仮に１００００文字の元データをギュウギュウに圧縮して１０００文字とすると、ロカポーター圧縮のような簡易形式でも、たいてい２０００文字以内には収まる、という意味です。
ちなみにこの例では、データの種類ごとに使う文字の種類を変えたが、要するにデータの最後の文字と、次のデータの（どこになるかわからない）先頭部分とが違う文字であればＯＫです。ですので、たとえば、各データを
ＡＡＡＡ０ （Ａのところは26進法、０のところは10進法、全部で０～４５６９７５９まで）
というロカポのような記述を使うと、最後が数字ひとつとわかっているので
ＡＡ０ＡＡ０ → （ＡＡ）ＡＡ０ と（ＡＡ）ＡＡ０
ＡＡＡ０００ → （Ａ）ＡＡＡ０ と （ＡＡＡＡ）０ と （ＡＡＡＡ）０
のように、問題なくデータを再分離可能です。
ロカポータでは、この両方の方式を組み合わせています。緯度経度には前者の方式をベースにしたもの、高度や日時などの付加データには後者の方式をベースにしたもの使用しています。
次回は、ロカポーターの目玉である、データ途中の精度変更です。
なお、ご質問等があれば、このブログに投稿頂くか、ロケージングまでお問い合わせください。
それとロカポーターのホームページ（突貫で作ったので、まだ１ページモノですが・・・）からロカポーターの仕様書をダウンロードできるようになっていますので、どうぞご利用ください。
# posted by Nao : 08:21
