OSM(OpenStreetMap)で広く使われている圧縮ファイル(拡張子pbf)では、 整数データは４バイト、８バイトといった固定サイズではなく、その値によって、1バイト、2バイト、3バイトというように、 サイズが異なるバイトコードで表されている。
符号付き整数の場合、符号に１ビット、後続バイトがあるかどうかに１ビット使われる。 １バイトの場合、数値に使われるのは６ビットである。２バイトでは１３ビットが数値の表現に使われる。 ４バイトで表される数値は ６＋７*３＝２７ビットである。このため、28～32ビットを占める４バイト整数の表現には ５バイトが使われる。
OSM地図データでは隣り合う数値の差は小さいことが多いため、 ４バイト、８バイト整数の差を１、２バイトで表現できることが多いため、このような符号化方式をつかうことにより、 ファイルサイズの縮小を図っている。
通常の数列データでは効果はないが、隣り合うデータの差が小さいことが多い場合にはデータ圧縮効果がある。
このような可変長バイトコードを固定長の整数配列データに戻す(復号化)には時間がかかるが、 殆どが１バイトであれば、平均的な符号化時間は短い。
１バイトで表せることが少なく、２、３バイトになることが多い場合、ファイルサイズの圧縮効果はあるが、 実時間で繰り返し復号化をする場合、処理時間上不利になる。
このため、自作地図アプリでは全ての差分を２バイトで表現できる場合に限り、差分を２バイトで表している。 ファイルサイズ上は可変長バイトコードほどの圧縮効果はないが、復号化が極めて単純であり、可変長バイトコードより有利である。
数値は可変長バイトで、各７ビットで表す、下位から順に。最上位bitは、 最下位桁のとき 0、そうでないときは 1 となる。323 = 67(0x43) + 128x2 であるが、最初の 0x43 は末尾ではないので 0x80 が加わり、0xc3 となる。
符号を含めるときは、１ビットが必要になる。 最下位桁の最下位ビットが 0 のとき ＋、1 のとき － とする。最下位桁の数値は 0～63 となる。
例えば、３バイトで表される数値は以下の通りである。符号ありの 0 は二通りある。
lon(経度), lat(緯度) は 10,000,000倍した整数で表す。この lon, lat, id には差分が使われる。 例えば、123000, 123050, 123055 は符号付き数値で +123000, +50, +5 とする。
以上のように、ファイルサイズを小さくするために、結構複雑な仕様になっている。
地図アプリでは符号化はパソコンで一度行うだけであるから、符号化時間は問題ない。 復号化は何度も何度も繰り返し実行するため、高速処理が必須となる。
１バイトの場合、関数コールとはせず、例外処理で極力シンプルな処理で復号化することが望ましい。 ２バイトの場合も例外処理が望ましい。平均的に３バイトを超えるケースが多い場合は、そもそも、 このような符号化方式を採用すべきではない。
// 復号化
inline uint64_t ParseUInt64(byte **pp) {
uint8_t b, i = 0;
uint64_t v = 0;
do {
b = *(*pp);
(*pp)++;
v |= (uint64_t)(b & 0x7f) << (i++ * 7);
} while (b & 0x80);
return v;
}
inline int64_t ParseSInt64(byte **pp) {
int64_t v = ParseUInt64(pp);
v = (v & 1) ? -(int64_t)(v >> 1) - 1 : (int64_t)(v >> 1);
return v;
}
// 符号化
inline void ConvertUVar64(byte** p, uint64_t v) {
uint32_t frac = v & 0x7f;
while (frac != v) {
*(*p)++ = frac | 0x80;
v >>= 7;
frac = v & 0x7f;
}
*(*p)++ = frac;
}
inline void ConvertSVar64(byte **pp, int64_t v) {
uint64_t u = v<0 ? ((-v)<<1) - 1 : v<<1;
ConvertUVar64(pp, u);
}
// ByteBuffer
static void ConvertULong(ByteBuffer buf, long v) {
byte frac = (byte)(v & 0x7f);
while (frac != v) {
buf.put((byte)(frac | 0x80));
v >>= 7;
frac = (byte)(v & 0x7f);
}
buf.put(frac);
}
static void ConvertSLong(ByteBuffer buf, long v) {
long u = v<0 ? ((-v)<<1) - 1 : v<<1;
ConvertULong(buf, u);
}
// byte[]
final static int ConvertULong(long v, byte[] buf, int ix) {
byte frac = (byte)(v & 0x7f);
while (frac != v) {
buf[ix++] = (byte)(frac | 0x80);
v >>= 7;
frac = (byte)(v & 0x7f);
}
buf[ix++] = frac;
return ix;
}
final static int ConvertSLong(long v, byte[] buf, int ix) {
long u = v<0 ? ((-v)<<1) - 1 : v<<1;
return ConvertULong(u, buf, ix);
}
Javaには unsigned がないため、分かりにくい。 下のプログラムは C/C++プログラムを Java に置き換えただけであり、 テストはしていない。 実際に使う際には、Long.MIN_VALUEの符号化・復号化などで十分にテストする必要がある。
byte[] ba;
int off;
long getULong() {
byte b, i = 0;
long v = 0;
do {
b = ba[off++];
v |= (long)(b & 0x7f) << (i++ * 7);
} while ((b & 0x80) != 0);
return v;
}
long getSLong() {
long v = getULong();
v = ((v & 1) != 0) ? -(v >> 1) - 1 : (v >> 1);
return v;
}
ラインやポリゴンなどの座標値列データに対して可変長バイトコードの適用について考えてみる。
レコード数としては戸建て住宅ポリゴンデータが全体の過半数を占める。 戸建て住宅ポリゴンレコードの境界ボックスのサイズは極座標に 107 を乗じて整数化したデータでは 縦横とも 500～1000 程度となる。ノードとノード間の極座標の差は１バイトで表現できることもあるが、大抵は ２バイトになるであろう。
一律２バイトの差分コードでのデータ圧縮を 30％程度とすれば、 可変長バイトコードのデータ圧縮は 40％程度になるものと推測される。
中ズームの極座標の精度は 105 を乗じて整数化、 中ズームの極座標の精度は 104 を乗じて整数化でもいいであろう。 そうすれば、ノード間の極座標の差は小さくなる。だが、ノードを間引いていることにより、 ノード間の極座標の差は大きくなっている。したがって、１バイトで表現できる比率がどの程度かは実測しないと分からない。 しかし、一律２バイトの差分コードに比べれば、高ズーム以上に有利であろう。
以上を総合すると、可変長バイトコードの平均的な復号化時間を差分コードの復号化時間に遜色のないものとできるならば、 差分コードより、可変長バイトコードがやや有利と言えるであろう。
C/C++言語の場合、バイト配列データから、short や int データを読み込むことは簡単であるが、 Java の場合には下に示すような手間がかかる。可変長バイトコードの復号化は一般的にはこれよりも複雑であるが、 １バイトコードに限れば、以下の処理に比べて、それほど手間のかかるものではない。
符号なし数値のコード化がベースとなっているが、地図アプリの座標値列データのコード化では、 ４バイトの符号あり数値のコード化のみのため、省略する。
最上位ビットで１バイトコードかどうかが判定でき、最下位ビットで符号が判定できる。 １ビット右にシフトしたものが数値である。getShortよりは少し時間がかかるかも知れないが、getIntよりは速い。
static int getShort(byte[] ba, int off) {
return (ba[off] << 8) | (ba[off+1] & 0x00ff);
}
static int getInt(byte[] ba, int off) {
return (ba[off] << 24) | (ba[off+1] & 0xff) << 16 | (ba[off+2] & 0xff) << 8 | (ba[off+3] & 0xff);
}
２バイトコードの場合も while文を使わず、ダイレクトに求める方法を考えてみよう。
最初のバイトの最上位ビットが 1、次バイトの最上位ビットが 0 で２バイトコードと判定できる。 次に & と右シフトにより、xxxxxx を取り出す。******* は最上位ビットが 0 であるから、何の操作もいらない。int変数に移す。
先頭の方が下位バイトであるため、xxxxxx をセットした変数に ******* を６ビット左シフトした値を加算または | すると、 それが復号化した数値(絶対値)となる。符号ビットが１であれば、負の値に変える。
ParseSInt をコール、内部で ParseUInt をコールして、戻った値を少し加工して、戻り値とするよりは処理時間は短いであろう。 上記の getInt と同程度の処理時間はかかるであろう。
例外処理を１バイトと２バイトに限定する場合
int v = ba[off];
int flag = v & 0x01;
if ((v&0x80) == 0) { // 1バイトコード
v >>= 1;
if (flag != 0) v = - v;
off++;
} else {
int w = ba[off+1]
if ((w&0x80) == 0) { // 2バイトコード
v = ((v & 0x7f)>>1) | (w<<6);
if (flag != 0) v = - v;
off += 2;
} else {
// 関数コール
}
}
となる。４バイト整数はコード化した場合、最長では５バイトとなる。
１～５バイトの処理を全て書き下すと次のようになる。
int v = ba[off++];
int flag = v & 0x01;
if ((v&0x80) == 0) { // 1バイトコード
v >>= 1;
} else {
int w = ba[off++];
if ((w&0x80) == 0) { // 2バイトコード
v = ((v & 0x7f)>>1) | (w<<6);
} else {
int x = ba[off++];
if ((x&0x80) == 0) { // 3バイトコード
v = ((v & 0x7f)>>1) | ((w&0x7f<<6) | (x<<13);
} else {
int y = ba[off++];
if ((y&0x80) == 0) { // 4バイトコード
v = ((v & 0x7f)>>1) | ((w&0x7f<<6) | ((x&0x7f)<<13) | (y<<20);
} else { // 5バイトコード
int z = ba[off++];
v = ((v & 0x7f)>>1) | ((w&0x7f<<6) | ((x&0x7f)<<13) | ((y&0x7f)<<20) | (z<<27);
}
}
}
}
if (flag != 0) v = - v;
バイトデータの取り込みを if文に含めれば if else 文は簡素になる。 パフォーマンスは while文よりもよい。
先頭は int型の整数化した経度、緯度とする。 その後に、経度、緯度順に前経度、緯度との差分の可変長バイトコードが続くものとする。 この可変長バイトコードを int整数に戻すプログラムを以下に示す。
実際上は１、２バイトのケースが殆どであることから、処理時間は短い見込みである。
OSMのpbfファイルでは、符号なし整数や８バイト整数も含まれるが、 下のプログラムは４バイトの符号あり整数限定である。
while文の方が見やすくなり、処理時間も大差がないかも知れない。
地図アプリでこの可変長バイトコードをどう扱うかの詳細は別途、地図アプリのページで述べる。
１、２バイトの復号化の高速化に力を注ぐ。３、４バイトが多いような場合、可変長バイトコードは適さない。
byte[] ba;
int off;
int getUInt() { // 符号なし整数
int v, w, x, y, z;
if ((v=ba[off++]) >= 0) { // 1バイトコード
return v;
} else if ((w=ba[off++]) >= 0) { // 2バイトコード
return (v & 0x7f) | (w<<7);
} else if ((x=ba[off++]) >= 0) { // 3バイトコード
return (v & 0x7f) | ((w&0x7f)<<7) | (x<<14);
} else if ((y=ba[off++]) >= 0) { // 4バイトコード
return (v & 0x7f) | ((w&0x7f)<<7) | ((x&0x7f)<<14) | (y<<21);
} else { // 5バイトコード
z = ba[off++];
return (v & 0x7f) | ((w&0x7f)<<7) | ((x&0x7f)<<14) | ((y&0x7f)<<21) | ((z&0x7f)<<28);
}
}
int getSInt() { // 符号あり
int v, w, x, y, z;
int flag = (v=ba[off++]) & 0x01;
if (v >= 0) { // 1バイトコード
v >>= 1;
} else if ((w=ba[off++]) >= 0) { // 2バイトコード
v = ((v & 0x7f)>>1) | (w<<6);
} else if ((x=ba[off++]) >= 0) { // 3バイトコード
v = ((v & 0x7f)>>1) | ((w&0x7f)<<6) | (x<<13);
} else if (((y=ba[off++]) >= 0) { // 4バイトコード
v = ((v & 0x7f)>>1) | ((w&0x7f)<<6) | ((x&0x7f)<<13) | (y<<20);
} else { // 5バイトコード
z = ba[off++];
v = ((v & 0x7f)>>1) | ((w&0x7f)<<6) | ((x&0x7f)<<13) | ((y&0x7f)<<20) | (z&0x7f)<<27);
}
return flag == 0 ? v : - v;
}
まず、レコード先頭の type と length だけを読み込んで全レコードをスキャンした。 実行毎に時間は変わるが、一例を下に示す。ファイルは japan-mid7/112/50.dat である。
ByteCodeTest: size=24MB time=52mS ByteCodeTest end: 561718レコード time=67mS
タグ部のパースは行っていないが、座標値関連の数値は全て復号化した結果の実行時間の測定結果を下に示す。
低価格なAndroidタブレットでの結果であり、スマホの方が高速であるが、ファイル読み込み時間に比べて、 バイトコードの復号化には時間がかかると言える。
Map３では管理データをAndroid機で作成しているが、パソコンで作成して、 バイナリレコードファイルの上部に置く方が実行時間は短くなるであろう。 その場合も byte配列上部を short配列(またはint配列)に変換する操作は必要になる。
ByteCodeTest: size=24MB time=38mS ByteCodeTest end: 561718レコード time=453mS ByteCodeTest: size=24MB time=25mS ByteCodeTest end: 561718レコード time=417mS
24MBは大きなファイルである。平均的なファイルでの結果を下に示す。サイズ、レコード数とも１/５の大きさである。 ファイル読み込み時間は1/5にならないが、復号化時間は 1/8 くらいになっている。 この程度の数字であれば、管理データを Android機で作成しても負担にならないであろう。
ByteCodeTest: size=5MB time=10mS ByteCodeTest end: 110603レコード time=58mS
これまで復号化時間がネックで、可変長バイトコードの採用を見送ってきたが、 １、２バイトの時の復号化を効率よく行えるようになったので、Map４ではこれを採用する。
ファイルサイズ（メモリ使用量）を極力小さくすれば、中ズームでは殆どのバイナリレコードファイル を同時にメモリに置くことができる。高zoom から低zoom に切り替わったら、 画面範囲のバイナリレコードファイルだけでなく、 周辺のファイルも先行してバックグラウンドで読み込むことが可能となる。 これによりパフォーマンスを向上させることができる。