OSM(OpenStreetMap)で広く使われている圧縮ファイル(拡張子pbf)では、 整数データは４バイト、８バイトといった固定サイズではなく、その値によって、1バイト、2バイト、3バイトというように、 サイズが異なるバイトコードで表されている。 このような符号化方式の詳細は別のページに記す。
ここでは、自作地図アプリに適用した場合の効果を事前に調べたい。
現在は全ての座標差分値が２バイトで表現できる場合のみ、差分を２バイトで表す差分コードを使用している。 差分を使わなかった場合に比べて30％程度のファイルサイズ縮小効果が得られている。
可変長バイトコードの効果を明らかにするために、現状のファイルサイズを示す。
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 とする。
c:\map>java -Dfile.encoding=UTF-8 -Xmx5g -classpath ./class OSMUtil -devide 12 7 japan-high レコード数=34256431, 最大レコード長=4539942, 平均レコード長=55.7, 平均タグ数=1.3, 平均タグ長=7.6B 実行時間: 1.85分
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
先頭の lon、lat は４バイト固定整数ペアで、次のノードから 可変長バイトコード(符号あり)とする。
ただし、multipolygonの場合、各polygon毎に先頭は４バイト固定整数ペアとする。
高ズームでは平均タグ数は1.3、長さは7.6バイトである。 highway=motorway、amenity=police など基本タグは４バイトであるため、この 1.3倍は 5.2バイトであるが、 概ね文字列タグにより、平均値が 7.6バイトになっている。
タグの数値も可変長バイトコードとした場合、基本タグは大体が２バイトとなり、 平均タグ長は現在の値より、2.5～3バイト縮小する見込みである。
タグにはいくつかの種類があるため、可変長バイトコードにすると更に煩雑になる。 レコード当たり２，３バイトの縮小ではコスパが良くないので、少なくとも当面は現状の固定幅数値とする。
relation処理によるレコードでは差分コードを使用していない。 このため、このレコードの比率が高い中ズーム、低ズームでは差分コードの効果は低い。
差分コードのファイルサイズ縮小効果は高ズームで30％強であった。中ズームで20％弱、低ズームでは３％であった。
差分コード 固定整数
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 とする。
まず、座標値列データだけを可変長バイトコード化した。極座標の精度は一律、小数点以下７桁である。
固定整数 可変長バイト
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（68%）
japan-high7 165MB 53.5MB
length、num_polys、num_nds を符号なし可変長バイトコードとする。 japan-high7 はノード数が多いレコードが中心のため、これらの数値が占める比重は小さい。 ほぼ 1/3 になっていることから、４バイトが平均的に 1.3バイトになっている。 １バイトコードが７割、２バイトコードが３割程度と推測される。
japan-high12 は過半数のレコードが住宅など小さい建物である。平均ノード数は６程度で、 差分コードは殆どが２バイトとなる。 ４バイト整数では６x８＝48バイトが可変長バイトコードでは８＋５x４＝28バイト(58%)となる。
下の結果(62%)はこれよりも悪い。平均7.6バイトのタグを圧縮していないことが最大の要因であろう。
固定整数 可変長バイト 最大zoom
japan-low3 10.8MB 6.5MB 7
japan-mid7 266MB 136MB 12
japan-high12 2.84GB 1.75GB(62%) 21
japan-high7 165MB 53.4MB 21
上記のjapan-high12、japan-high7にはレコードの重複があるため、合計レコード数は 34,256,431 よりは多い。重複を無視した場合、52.5バイト/レコードとなる。
現在の管理データは 24バイト/レコードである。重複を考えると、バイナリレコードの半分になる。 これではあまりにも大きすぎる。8～12バイト/レコードに縮小したい。
type＋length は殆どのレコードは ２バイトでよい。２バイトで表せない大きなレコードのみ４バイトで表す。
境界ボックスの単位は最大zoom のタイル座標とする。
zoom 1 では縦横２枚のタイルであるから縦横１ビットで表せる。 low、mid、high の最大zoom は 7、12、21 であるから、タイル座標は 1、2、3バイトで表現できる。
mid7 は zoom 8からzoom 12のレンダリングで使う。 zoom 12での西北端および東南端の座標を(minlot, minlat)、(maxlon, maxlat)とすると、 この矩形範囲の外に当たる数値は空間検索では意味を持たない。 minlonより小さい時は minlonに切り上げ、maxlonより大きい時は maxlon に切り下げてよい。 lat についても同様である。この結果から (minlon, minlat) を引けば、その値は１バイトで表現できる。
high12、high7 については、２バイトが必要となる。
大抵のレコードの境界ボックスはそれぞれの最大zoom における一つのタイルに包含される。 width=1、height=1 である。この場合は管理データを (x, y)のみとする。 二つ以上のタイルにまたがる場合のみ (x, y, width, height)とする。 low、midファイルでは width、height は１バイトで表せるが、high では１バイトでは表せないことがありうる。
分かりやすさを採れば、高ズームでは (x, y)、(x, y, width, height) は２バイト整数となる。 (x, y) で済むレコードが多いことから、管理レコードの平均サイズは 8～12バイトと推測される。
可変長バイトコードについては、パフォーマンスが気になるところである。
管理データについては、現状のままではメモリ使用量が大きすぎる。 上記のような複雑な仕様は避けて、単純な仕様で半減させることを更に検討したい。
zoom 21 では、ほとんどの建物がタイルをまたぐ。したがって、(x, y) で済むレコードは少ない。
単位を最高zoomのタイル座標とする場合、レンダリング対象のタイル矩形にマージンを加えるのが難しい。
極座標のままで、精度を落としても、可変長バイトコードではそれほど効果はなかった。
差分を２バイトか４バイトの二択にする程度で我慢すべきかもしれない。 ２バイトのケースが多いと思われるので、平均サイズは12バイト程度に収まる可能性がある。 プログラムで実測してみよう。
まずは、可変長バイトコードを試した。結果を下に示す。
c:\map>java -Dfile.encoding=UTF-8 -Xmx5g -classpath ./class OSMUtil -bytecode japan low 3 6621KB/11091KB (59%) Idx合計＝3076KB レコード数＝256906 圧縮なし＝44B 可変長＝26B 管理＝12B 実行時間: 0.01分 c:\map>java -Dfile.encoding=UTF-8 -Xmx5g -classpath ./class OSMUtil -bytecode japan mid 7 139854KB/273112KB (51%) Idx合計＝39629KB レコード数＝2840899 圧縮なし＝98B 可変長＝50B 管理＝14B 実行時間: 0.10分 c:\map>java -Dfile.encoding=UTF-8 -Xmx5g -classpath ./class OSMUtil -bytecode japan high 7 54689KB/169539KB (32%) Idx合計＝488KB レコード数＝27584 圧縮なし＝6293B 可変長＝2030B 管理＝18B 実行時間: 0.06分 c:\map>java -Dfile.encoding=UTF-8 -Xmx5g -classpath ./class OSMUtil -bytecode japan high 12 1837962KB/2984356KB (61%) Idx合計＝534754KB レコード数＝34687558 圧縮なし＝88B 可変長＝54B 管理＝15B 実行時間: 2.02分
予想したより、管理データサイズは大きくなった。 平均的には、15～16バイト/レコードであり、バイナリレコードの平均値が 55～60バイト/レコードであることから その 1/4～1/3 程度である。現状の24バイトに比べて十分に小さいとは言えないが、どうにか我慢できる数値であろう。
可変長バイトコードの場合、空間検索の度に瞬時に復号化するのは難しいため、 復号化が簡単なものに変える必要がある。
管理データをやめて、境界ボックスをバイナリレコードに含める案もある。 境界ボックスの原点(西北端)座標は、そのまま４バイト整数ｘ２とする。座標値列データの先頭はこの原点座標からの差分とする。
境界ボックスの幅と高さは復号化の速さを考え、２バイトか４バイトの二者択一にするのがいいであろう。
typeに続くレコードサイズも可変長バイトコードではなく、 typeを含めて２バイトか４バイトの二者択一にすべきであろう。
この場合、平均レコードサイズの増加は 10 バイト程度になるであろう。C/C++言語であればバイト配列から ４バイト整数を取り出すのは簡単であるが、Javaでは４バイトを取り出してシフト演算と加算演算を行う必要があるため、 空間検索時間は現在よりも何割か増える。
空間検索時間が最も速いのは管理データがint配列の場合である。 現在の24バイトを 20バイトにするのは簡単である。大抵のレコードでは width と height は２バイトに収まる。 合わせて４バイトとそれぞれ４バイトの二者択一にすれば、平均的には 16バイト強になる。
管理データを short配列にする案もある。大抵のレコードは 二つのフラグとtype とレコード長を 最初の２バイトに収容できる。長いレコードのみ、次の２バイトもレコード長に使う。 ４バイトの経度、緯度の取り出しではシフト演算と加算がいるが、widthとheightが2バイトの場合、 ４バイトからの分割は要らなくなるので、処理時間の差は僅かであり、 レコード当たりの管理データを 14バイト強に減らすことができる。
ここ数日あれこれ検討したが、これまででは、この方法が一番良いと思われる。
プログラムで試した結果を下に示す。japan-high7 のみ管理データの平均サイズは少し大きくなったが、 レコード数が少ないため、全体与える影響は微々たるものである。 平均的には予想通り14バイト強になった。
高ズームではタイル当たりのレコード数が少ないので、レンダリングの負担は軽い。 低ズームはファイルサイズが小さいので、全体をメモリに常駐できる。
中ズームが最もファイルの入れ替えが激しく、描画に時間がかかる。ファイルサイズ(メモリ使用量)が 現在の半分近くになるため、大幅なパフォーマンス向上が見込める。
ただし、空間検索で抽出されたレコードについて可変長バイトコードを 復号化する時間は現在よりも少し増えるマイナス効果もある。
空間検索で全レコードをスキャンする時間はフラグ判定で２バイトか４バイトに分かれる判定処理 が加わるが、サイズが４割以上小さくなっているため、全体の時間は同程度か少し短縮するであろう。
パソコンでは、全ファイルをメモリに読込める大きさであるが、 Androidスマホ/タブレットではひとつのアプリで使えるメモリが限られており、 現在は 512MB である。 他に、陸地ポリゴンレコードやタイル画像キャッシュ、空間検索結果の格納エリア が必要となるため、中ズーム全データを同時にメモリに読込むのは難しい。 たとえ可能であっても、一度は読み込む必要がある。 メモリに余裕があれば、先行読み込みも検討する価値があるであろう。
flags;type;length(2/4), minlon(4), minlat(4), width;height(4/8)
c:\map>java -Dfile.encoding=UTF-8 -Xmx5g -classpath ./class OSMUtil -bytecode japan low 3 6621KB/11091KB (59%) Idx合計＝3513KB レコード数＝256906 圧縮なし＝44B 可変長＝26B 管理＝14B 実行時間: 0.01分 c:\map>java -Dfile.encoding=UTF-8 -Xmx5g -classpath ./class OSMUtil -bytecode japan mid 7 139854KB/273112KB (51%) Idx合計＝38875KB レコード数＝2840899 圧縮なし＝98B 可変長＝50B 管理＝14B 実行時間: 0.10分 c:\map>java -Dfile.encoding=UTF-8 -Xmx5g -classpath ./class OSMUtil -bytecode japan high 7 54689KB/169539KB (32%) Idx合計＝473KB レコード数＝27584 圧縮なし＝6293B 可変長＝2030B 管理＝17B 実行時間: 0.08分 c:\map>java -Dfile.encoding=UTF-8 -Xmx5g -classpath ./class OSMUtil -bytecode japan high 12 1837962KB/2984356KB (61%) Idx合計＝477074KB レコード数＝34687558 圧縮なし＝88B 可変長＝54B 管理＝14B 実行時間: 1.97分
復号化時間が短ければ、管理データはバイナリレコードに含めず、Androidスマホ/タブレットで作り出す方がよい。
そこで、可変長バイトコードの復号化時間を計測する。