OSM(OpenStreetMap)で広く使われている圧縮ファイル(拡張子pbf)では、 整数データは４バイト、８バイトといった固定サイズではなく、その値によって、1バイト、2バイト、3バイトというように、 サイズが異なるバイトコードで表されている。 このような符号化方式の詳細は別のページに記す。
ここでは、自作地図アプリに適用した場合の効果を事前に調べたい。
現在は全ての座標差分値が２バイトで表現できる場合のみ、差分を２バイトで表す差分コードを使用している。 差分を使わなかった場合に比べて30～40％程度のファイルサイズ縮小効果が得られている。
可変長バイトコードの効果を明らかにするために、現状のファイルサイズを示す。
japan-high12 2.01GB japan-high7 157MB japan-mid7 214MB japan-low3 10.2MB
現状のバイナリレコードの形式を下に示す。
head(4), [num_nds(4)], {lon,lat}*, {key,val}* ... point/line/polygon
head(4), {num_nds(4)}*, {lon,lat}*, {key,val}* ... multipolygon
head:
第0,1bit(0x03) 0: point、 1: line、 2: polygon、 3: multipolygon
第2bit(0x04) 0: 差分座標、1: 絶対座標
下位３バイト レコード長
num_nodes:
multipolygonの場合、最終要素(最終inner polygonノード数)の最上位ビットは 1 とする。
head(1), length, [bbox,] [len_nds], {lon,lat}*, {key,val}* ... point/line/polygon
head(1), length, bbox, num_polys, {len_nds}*, {lon,lat}*, {key,val}* ... multipolygon
head:
第0,1bit(0x03) 0: point、 1: line、 2: polygon、 3: multipolygon
境界ボックス bbox は地図アプリ Map4 の負担を軽減するため。Pointレコードでは省略する。 境界ボックスは lon(4), lat(4), width, height の４値からなる。lon、lat は４バイト固定整数ペア、 width、height は可変長バイトコード(符号なし)とする。
{lon,lat} は Pointレコードに限り、４バイト固定整数ペアとする。 line、polygon、multipolygon では可変長バイトコード(符号あり)とする。 先頭の lon、lat は境界ボックスの lon、lat からの差分値とする。
multipolygon の inner polygon については、 先頭ノードの lon、lat は４バイト固定整数ペアで、次のノードから 可変長バイトコード(符号あり)とする。 先頭のouter polygonとは仕様が異なる。
境界ボックスの lon、lat からの差分値をやめる方が、仕様としてはきれいになる。 しかし、そうした場合、平均レコードサイズは４バイト程増加する。
タグ highway=motorway、amenity=police などは符号なし整数のため、 可変長バイトコード(符号なし)とする。文字列の長さも符号なしのため、 可変長バイトコード(符号なし)とする。 整数値を値とするタグ(layer、admin_level、populatiionなど)については、 符号ありと符号なしに分けると紛らわしいため、全て符号ありとする。
以上のようにした方が平均レコードサイズは小さくなるが、バグが入り込みやすい。 まずは、座標値列データ {lon,lat}* のみ差分コードとしてみる。 先頭ノードは境界ボックスのlon、latからの差分ではなく、 先頭 lon、lat は４バイト固定整数ペアとして、次のノードから可変長バイトコードとする。
その後、効果を調べながら、可変長バイトコードの適用範囲を広げていく。
relation処理によるレコードでは差分コードを使用していない。 このため、このレコードの比率が高い中ズーム、低ズームでは差分コードの効果は低い。
差分コード 固定整数
japan-low.dat 22.3MB(97%) 22.9MB
japan-mid.dat 227MB(81%) 280MB
japan-high.dat 1.72GB(69%) 2.51GB
可変長バイトコード化は新たな ByteCoder.java で行う。
少なくとも当面は ByteCoder.java の入力レコード形式は現状通りとする。
head(4), [num_nds(4)], {lon,lat}*, {key,val}* ... point/line/polygon
head(4), {num_nds(4)}*, {lon,lat}*, {key,val}* ... multipolygon
head:
第0,1bit(0x03) 0: point、 1: line、 2: polygon、 3: multipolygon
下位３バイト レコード長
num_nodes:
multipolygonの場合、最終要素(最終inner polygonノード数)の最上位ビットは 1 とする。
境界バックスは後程検討する。取りあえずの形式は以下の通りとする。
head(1), length, [num_nds], {lon,lat}*, {key,val}* ... point/line/polygon
head(1), length, num_polys, {num_nds}*, {lon,lat}*, {key,val}* ... multipolygon
head:
第0,1bit(0x03) 0: point、 1: line、 2: polygon、 3: multipolygon
まず、座標値列データだけを可変長バイトコード化した。
固定整数 可変長バイト
japan-low3 10.8MB 8.9MB
japan-mid7 266MB 164MB
japan-high12 2.84GB 1.93GB
japan-high7 165MB 53.5MB
lowズームの精度は小数点以下4桁、midズームの精度は小数点以下5桁とした。 期待したほどはサイズが縮小しなかった。
固定整数 可変長バイト
japan-low3 10.8MB 7.9MB
japan-mid7 266MB 152MB
japan-high12 2.84GB 1.93GB
japan-high7 165MB 53.5MB
length、num_polys、num_nds を符号なし可変長バイトコードとする。 japan-high7 はノード数が多いレコードが中心のため、これらの数値が占める比重は小さい。 ほぼ 1/3 になっていることから、４バイトが平均的に 1.3バイトになっている。 １バイトコードが７割、２バイトコードが３割程度と推測される。
固定整数 可変長バイト
japan-low3 10.8MB 6.5MB
japan-mid7 266MB 136MB
japan-high12 2.84GB 1.75GB
japan-high7 165MB 53.4MB
中低ズームではタグは少ないため、可変長バイトコード化しても縮小効果はあまり期待できない。 その割にプログラム上手数がかかるため、まずは、見送る。
低ズームについては現状でもファイルサイズは十分に小さいため、可変長バイトコード導入の必要性は低い。 中ズームでは大きな効果が期待できる。 高ズームでは high12 のファイルサイズは現状よりわずかに小さい程度に過ぎないが、 high7 が大幅に(約1/3）小さくなるため、その効果が期待される。
現在、境界ボックスは地図アプリで算出しているが、 バイナリレコードとは別に管理データをパソコンで準備したほうがよいかもしれない。
現在、メモリ上ではレコード当たり24バイトの大きさである。 ファイルに含めると当然読み込み時間が増える。この読み込み時間の増加分より、 バイトレコードからの算出時間の方が短いと判断して、現在はバイナリレコードファイルに含めていない。
可変長バイトコードでもこの判断が正しい可能性があるため、十分に検討したい。
管理データも可変長バイトコード化すれば、平均的に12か13バイトに収まるであろう。 境界ボックスは大きい分には問題ないので、単位を座標値の 10～100倍でもよいので、 １バイトで表せるケースを増やすことができる。 工夫により、管理データの平均サイズを 10バイト程度に縮小できるであろう。
また、メモリ上のサイズを工夫により小さくできればより多くのブロックファイルをメモリに 置くことができるため、ファイルの入れ替えを減らすことにより、パフォーマンスが向上する。
タイルのレンダリングではブロックの全レコードをスキャンして、レンダリングの対象かどうかを調べている。 管理データなしの場合、ブロックレコードに境界ボックスデータを含める必要がある。byte配列データから、 全レコードの境界ボックスデータを取り出すのは時間的に無理である。
byte[] ba;
int off;
int getSInt() { // lon, lat 順の差分データ
int v, w, x, y, z;
int flag = (v=ba[off++]) & 0x0001;
if ((v&0x8000) == 0) { // 1バイトコード
v >>= 1;
} else if (((w=ba[off++])&0x8000) == 0) { // 2バイトコード
v = ((v & 0x7fff)>>1) | (w<<6);
} else if (((x=ba[off++])&0x8000) == 0) { // 3バイトコード
v = ((v & 0x7fff)>>1) | ((w&0x7fff)<<6) | (x<<13);
} else if (((y=ba[off++])&0x8000) == 0) { // 4バイトコード
v = ((v & 0x7fff)>>1) | ((w&0x7fff)<<6) | ((x&0x7fff)<<13) | (y<<20);
} else { // 5バイトコード
z = ba[off++];
v = ((v & 0x7fff)>>1) | ((w&0x7fff)<<6) | ((x&0x7fff)<<13) | ((y&0x7fff)<<20) | (z<<27);
}
if (flag != 0) v = - v;
return v;
}
境界ボックスは空間検索に使うだけであるから、ブロックと交差する範囲で十分である。 レンダリングするタイルの最小サイズ(最大zoom)に応じた精度があればよい。 ８～１０ビットあれば十分であろう。４値では ４バイトか５バイトでよいはず。８バイトあれば十分であろう。 管理データは type + length に４バイト、空間検索に４～８バイト、合計で８～１２バイトとしたい。 type + length は殆どのレコードは２バイトあれば十分である。可変長バイトコードほど複雑なものではなく、 ２バイトか４バイトの簡単な可変長を管理データに採用することも考えられる。
japan-**** の場合、境界ボックスの基準をそのブロックの西北端とする案もあるが、マージンが必要なため、 それを考慮すると、少し分かりずらくなる。中ズーム用ファイルは zoom 8～zoom 12 のレンダリングに使うため、 境界ボックス値は１バイト(8ビット)で表せるが、高ズームは現在 zoom 13～zoom 21 としているため、 少なくとも 9ビットは必要となるため、１バイトでは表現できない。 陸地ポリゴンデータも適用ズーム幅が広い。
管理データでは粗い空間検索で1.2～2倍程度が抽出する。 実際の座標値データから正確な境界ボックスを算出し、余分なレコードを排除する。
陸地ポリゴンも高中低の３段階として、zoom 範囲を調整し直せば、 管理データにおける境界ボックスの精度は１バイトでも良いかもしれない。
ブロック内の一つタイルのレンダリングにしか使われないレコード(w=1,h=1)が多くある。 この場合必要なのは、x、y の値だけである。しかし、二つ以上のタイルにまたがることがあるため、 (x,y,w.h)で管理する。
精度は高ズームでは zoom 21、中ズームでは zoom 12、低ズームでは zoom 7 のタイル座標とする。
場内によっては、ブロックファイルの前部に (x,y)レコード、後部に (x,y,w,h) レコードとしてもよい。
このように考えてゆくと、現在２４バイトの管理データは平均的には５、６バイトまで縮小できる。 マージンを考えると、精度は16ビットにした方が楽である。この場合、殆どのレコードが６バイト、 タイルをまたがるレコードは主に10バイト、ノード数が多いと12バイト、全体平均は７、８バイトとなるであろう。
以上から、まずは、次の仕様とする。 管理データは２バイト配列とする。先頭の２バイトの上位２ビットはフラグ、 フラグの一つはレコード長が 14ビットですむ(bit=0)か、次の２バイトがレコード長上位か(bit=1)を表す。 もう一つのフラグは境界ボックスが (x,y)(bit=0) か (x,y,w,h)(bit=1) かを表す。
レコード長が14ビットで表せないレコードはごくわずかである。タイルをまたがるものはかなり存在する。
この仕様であれば、空間検索の負担は少ないであろう。