o5m形式のファイルサイズは pbf形式の２倍程度になるが、 pbf形式よりはシンプルなため、高速処理が可能である。
pbf形式ほど普及しておらず、サポートするソフトウェアが限られている。
低ズーム世界地図で必要なデータを現在、osmosis で抽出しているが、非常に時間がかかる。 osmconvert で o5m 形式に変換して、osmfilter で抽出すれば数倍速い。
データベースへのインポートに成功したこともあるが、osm2pgsql、imposm3 いずれでも、 データを読み込む段階で、Killed で止まってしまうことがある。 osmfilterによる抽出データに何らかの不具合が混入している可能性が高い。
o5m形式は無名ではないが、あまり普及していないことから、全幅の信頼は置けない。 しかし、そのパフォーマンスに惹かれる。 主流ソフト osm2pgsql ではサポートしていることから、 実用に耐えるファイル形式と思われるので、すこし、触れてみたい。
読み込みだけであるが、o5mreader という C言語ライブラリは500行ほどのコンパクトなものなので、中身も理解しやすい。
o5mは zipなどのような圧縮方法は採らない。 amenity=school といった、キー(amenity)、値(school)は同じ文字列が頻繁にでてくるため、 コード化により圧縮している。数値は可変長バイトで表す。 また、way の座標列は差分により、圧縮している。 これらを総合すると、osm(xml)プレーンテキストファイルのおよそ 1/10 のサイズとなる。
数値は可変長バイトで、各７ビットで表す、下位から順に。最上位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 とする。
以上のように、ファイルサイズを小さくするために、結構複雑な仕様になっている。 広く使われ、枯れたソフトでないと、バグが含まれていても不思議はない。
文字コードは osmと同じ UTF-8 である。
一般にはタグ(key)と値(val)をペアとする。user と uid はその値同士をペアとする。
始めて現れた文字列は 0x00 に続いて、文字列ペアをそのままコードとする。文字列の末尾は 0x00 である。
３行目の "oneway"/"yes" は二つ前にあるため 0x02 とする。６行目も "oneway"/"yes" であるが、 この間に新しい文字列 uid=1020,"John" があるため、ここでは 三つ前となるため、0x03 となる。
参照するのは最大 15,000 行で、登録は ペアで最大 250バイトである。
1020 が 0xfc 0x07 になるのはなぜか？ 124 + 128x7 = 0x7c 0x07 符号なし数値の 0以外の数値では、全バイトが 0 にはならない。
Each .o5m file starts with a byte 0xff and ends with byte 0xfe.
Every dataset starts with a specific byte:
0x10: node
0x11: way
0x12: relation
0xdb: bounding box
0xdc: file timestamp
0xe0: header, should follow the first 0xff in the file;
contents: 0x04 0x6f 0x35 0x6d 0x32 ("o5m2"),
or 0x04 0x6f 0x35 0x63 0x32 ("o5c2") for .o5m change files
0xee: Sync
0xef: Jump
0xff: (not a dataset) when somewhere in the file contents: Reset
１バイトの種別コードの次に符号なし整数によるデータセットの長さがある。 この長さには、最初の１バイトと長さを表す部分は含まない。 種別コードから処理が要らないときは、この長さを使って、このデータセットをスキップできる。
データセットの中身は種別により異なる。
tags までは以下の順で必ずあるのであろう。
・id (signed, delta-coded)
・either 0x00 or version information:
・version (unsigned)
・timestamp (seconds since 1970, signed, delta-coded)
・author information - only if timestamp is not 0:
・changeset (signed, delta-coded)
・uid, user (string pair)
・longitude (signed, delta-coded)
・latitude (signed, delta-coded)
・tags:
・key, val (string pair)
・key, val (string pair)
・...
tags の有無は先頭からパースしないと分からない。
o5mreader_iterateDataSet関数では１バイト目を type 、 データセットの長さを offset にセットして、 type により o5mreader_readNode、o5mreader_readWay、o5mreader_readRel関数を 実行している。
o5mreader_readNode関数では、まず、id をパース・セットしている。 そのあと、version、lon, lat をパース・セットしている。
tags 以外の処理は終わっている。
0x10 － node
0x21 － length of following data of this node: 33 bytes
0xce 0xad 0x0f － id: 0+125799=125799
0x05 － version: 5
0xe4 0x8e 0xa7 0xca 0x09 － timestamp: 2010-09-30T19:23:30Z
0x94 0xfe 0xd2 0x05 － changeset: 0+5922698=5922698
0x00 － string pair:
0x85 0xe3 0x02 0x00 － uid: 45445
0x55 0x53 0x63 0x68 0x61 0x00 － user: "UScha"
0x86 0x87 0xe6 0x53 － lon: 0+8.7867843=8.7867843
0xcc 0xe2 0x94 0xfa 0x03 － lat: 0+53.0749606=53.0749606
0x10 － node
0x0d － length of following data of this node: 13 bytes
0x02 － id: 125799+1=125800
0x0a － version: 10
0xd2 0x1f － timestamp: 2010-09-30T19:23:30Z+2025s=2010-09-30T19:57:15Z
0xe2 0x04 － changeset: 5922698+305=5923003
0x01 － string pair: reference 1
－ uid: 45445
－ user: "UScha"
0x89 0xae 0x03 － lon: 8.7867843-27525=8.7840318
0xe5 0xd8 0x03 － lat: 53.0749606-0.0030259=53.0719347
上の例では lon, lat が後ろの方にあるが、下の例のように、通常は id, lat, lon, ... の順である。 o5m の仕様は通常と異なるようだ。
<?xml version='1.0' encoding='UTF-8'?>
<osm version="0.6" generator="osmconvert 0.8.8" timestamp="2020-04-05T20:59:02Z">
<bounds minlat="32.229585" minlon="131.769819" maxlat="34.65151" maxlon="135.17938"/>
<node id="193247320" lat="34.3528966" lon="132.4400727" version="3" timestamp="2011-01-28T12:15:49Z" changeset="7112363" uid="32308" user="yamasan"/>
<node id="207689592" lat="33.8395188" lon="132.7653521" version="21" timestamp="2019-04-28T13:48:27Z" changeset="69664273" uid="255936" user="StenSoft">
<tag k="addr:postcode" v="790-8571"/>
...
string pair で uid や layer="-1" など数値は符号付き整数にするのか？ 文字か数値かはどうやって判断するのか？ 例では uid=1020 が 0xfc 0x07 0x00、45445 が 0x85 0xe3 0x02 0x00 となっている。uid のときだけ 数値で、タグでは文字列なのかも知れない。
o5m形式のファイルを osmconvert で osm 形式に変換すると下のようになる。
<xml version='1.0' encoding='UTF-8'> <osm version="0.6" generator="osmconvert 0.8.8" timestamp="2020-04-05T20:59:02Z"> <bounds minlat="32.229585" minlon="131.769819" maxlat="34.65151" maxlon="135.17938"/> <node id="193247320" lat="34.3528966" lon="132.4400727" version="3" timestamp="2011-01-28T12:15:49Z" changeset="7112363" uid="0" user=""/> <node id="195981411" lat="34.3609164" lon="132.5176466" version="6" timestamp="2012-09-02T17:05:01Z" changeset="12956769" uid="0" user=""/> // 省略 </osm>
o5mreader では、２行目の timestamp、３行目の各値はどうやって得られるのだろうか。
どうやら、0xdb～0xef に関連するコードはない。 osmタグの属性および３行目の境界座標はオプションのようなので、 なくてもデータベースへのインポートには支障がないかも知れない。
まず、o5mreaderのサンプルプログラムに時間計測を追加して、実行時間を計測する。
64ビットでコンパイルした方が32ビットより３割ほど速くなった。
time_t start_time = time(NULL);
FILE *f = fopen("e:/o5m/japan.o5m","rb");
fsize = _filelengthi64(_fileno(fp));
o5mreader_open(&reader,f);
int last_elapsed = 0;
while( (ret = o5mreader_iterateDataSet(reader, &ds)) == O5MREADER_ITERATE_RET_NEXT ) {
if (elapsed != last_elapsed) {
printf("time: %.2fm %llx[%.1f%%]\n",
(time(NULL) - start_time)/60.0, reader->current, reader->current*100.0/fsize);
last_elapsed = elapsed;
}
switch ( ds.type ) {
case O5MREADER_DS_NODE:
while ( (ret2 = o5mreader_iterateTags(reader,&key,&val)) == O5MREADER_ITERATE_RET_NEXT ) {
// Could do something with tag key and val
}
break;
case O5MREADER_DS_WAY:
while ( (ret2 = o5mreader_iterateNds(reader,&nodeId)) == O5MREADER_ITERATE_RET_NEXT ) {
// Could do something with nodeId
}
// Way taga iteration, can be omited
while ( (ret2 = o5mreader_iterateTags(reader,&key,&val)) == O5MREADER_ITERATE_RET_NEXT ) {
// Could do something with tag key and val
}
break;
case O5MREADER_DS_REL:
while ( (ret2 = o5mreader_iterateRefs(reader,&refId,&type,&role)) == O5MREADER_ITERATE_RET_NEXT ) {
// Could do something with refId (way or node or rel id depends on type), type and role
}
// Relation tags iteration, can be omited
while ( (ret2 = o5mreader_iterateTags(reader,&key,&val)) == O5MREADER_ITERATE_RET_NEXT ) {
// Could do something with tag key and val
}
break;
}
}
このプログラムではファイル(3.2GB)の途中(2GB)で表示がなくなり、 数分後に特にエラーメッセージはなく、終了する。 Windowsでのコンパイル方法に問題があるのかも知れない。 実際にはこのような使い方はしないので中断原因の究明はここではしない。
コンパイルが 64ビットに対応していなかった。
C:\gis>filter japan time: 1.00m 4175847[2.0%] time: 2.00m 88ee7c9[4.2%] [中略] time: 34.00m 7f5865ba[61.9%]
time_t start_time = time(NULL);
FILE *f = fopen("e:/o5m/japan.o5m","rb");
fsize = _filelengthi64(_fileno(fp));
o5mreader_open(&reader,f);
int last_elapsed = 0;
while( (ret = o5mreader_iterateDataSet(reader, &ds)) == O5MREADER_ITERATE_RET_NEXT ) {
if (elapsed != last_elapsed) {
printf("time: %.2fm %llx[%.1f%%] ds=%d\n", (time(NULL) - start_time)/60.0,
reader->current, reader->current*100.0/fsize, cntDataSet);
last_elapsed = elapsed;
}
}
fclose(fp);
printf("time: %.2f minutes, %d data_sets\n", (time(NULL) - start_time)/60.0, cntDataSet);
上のプログラムの実行結果は次のようになった。 データセット(node, way, relation)の数だけをカウントした。 これは速い。1.6分で 3.2GB の o5m ファイルをスキャンできた。
ここには、wayの構成要素(タグはない)およびrelの構成要素は含まれていない。 それらは way、rel のデータセットに属する。
C:\gis>filter time: 1.00m 4b87d04[54.9%] ds=5469080 time: 1.62 minutes, 9048539 data_setsjapan_osm_point テーブルのレコード数は 200万である。 残りの700万の大半は way の要素である。
タグのないデータセットに対して o5mreader_iterateTags(reader,&key,&val) を 実行すると、即座に O5MREADER_ITERATE_RET_DONE が戻るだろうか？
プログラムを追ってみると必ず
int o5mreader_thereAreNoMoreData(O5mreader *pReader) {
return (int)((pReader->current - ftell(pReader->f)) + pReader->offset) <= 0;
}
を実行するようだ。I/O関数 ftell のコールはそれなりのオーバヘッドになるだろう。
o5mreader_readNode関数でもこの関数をコールしている。 データセットの長さと、これまでにパースしたデータの長さを比べれば、 まだデータがあるかどうかは分かるはず。これまでにパースした長さを記録する代わりに、 現在位置から先頭位置の長さを引き算しているのであろう。
しかし、これだけが o5mreader_iterateTags 関数に時間がかかる理由ではないだろう。
要所にカウンタを入れたり、時間計測を入れてみよう。 どこで時間を食っているか、また、どこで 2GB 越えでエラーとなるかを探る。
改めて、shikoku で計測すると、o5mreader_iterateTags(reader,&key,&val)ではなく、 o5mreader_iterateDataSet(reader, &ds) で時間がかかっていた。
nodeの場合、通常は以下の処理となる。
fread(&(ds->type),1,1,pReader->f); o5mreader_readUInt(pReader,&pReader->offset); pReader->current = ftell(pReader->f); o5mreader_readNode(pReader, ds)
o5mreader_readNode(pReader, ds)の中心処理は以下の通り。
o5mreader_readVersion(pReader, ds);
o5mreader_thereAreNoMoreData(pReader);
o5mreader_readInt(pReader,&lon);
pReader->lon += (int32_t)lon;
o5mreader_readInt(pReader,&lat);
pReader->lat += (int32_t)lat;
ds->lon = pReader->lon;
ds->lat = pReader->lat;
fopen直後 で大きなバッファを設定すると、通常は速くなるが、この場合、遅くなった。 バイト単位の読み込みが多いのは非効率と思う。
osmfilter はここも凝っていて、ざっと見ではよく分からない。 低水準入力で自前でバッファを持っているようだ。
要するに、バイト単位でOSのI/O命令を発行しているわけではない。
o5mreader はプリミティブで分かりやすいが、これでは実行時間がかかりすぎて、 実用にはならないだろう。
osmfilterは正反対で、多機能でハイパフォーマンスを追求しているため、 簡単には理解できない。
自分に必要なのはシンプルでハイパフォーマンスである。 o5mreaderとosmfilterでは10倍以上の実行速度差がある。 おそらく、I/O以外でもどこかに大きな違いがあるだろう。
ノードのデータセットの先頭バイトの種別コードがタグのあるときとないときで異なるなど、 種別コードがもう少し詳しい方がスキップが簡単であるのに、なぜそうしていないのだろう。
osmfilterが高速なわけを探る必要がある。
下の処理を追加すると途端に時間がかかるようになる。 数値や文字列を得るのに時間がかかるのであろう。
実行は、2GB で終わってしまった。ポインタの 64ビット表現のどこかに 問題があるのだろう。
コンパイラの問題かと思ったが、 同じコンパイラでコンパイルした osmfilter は正常に動作する。 o5mreader に問題がある可能性が高い。
5488948282: city 岐阜市 岐阜市 Gifu time: 26.00m 7a8a4408[59.5%] ds=142411758 time: 27.00m 7e9a94fd[61.5%] ds=148014157
大抵は placeタグを含んでいないので、全タグを調べてそれが分かる。 つまり、ほぼ全ての文字列ペアを把握するという無駄がある。
osmfilterがどんな方法を採っているか探りたい。 文字列ペアの登録表が固定で、place=country,state,province,cityが 全て登録されているならば、どこにあるかを一度調べるだけでいい。
新たな文字列ペアにより位置が変わってゆくので、それをフォローする必要がある。
switch ( ds.type ) {
case O5MREADER_DS_NODE: // Data set is node
place = name = name_ja = name_en = NULL;
while ( (ret2 = o5mreader_iterateTags(reader,&key,&val)) == O5MREADER_ITERATE_RET_NEXT ) {
if (key[0] != 'p' && key[0] != 'n') {
;
} else if (strcmp(key,"place") == 0) {
place = val;
} else if (strcmp(key,"name") == 0) {
name = val;
} else if (strcmp(key,"name:ja") == 0) {
name_ja = val;
} else if (strcmp(key,"name:en") == 0) {
name_en = val;
}
}
if (place == NULL) break;
for (int i = 0; i < sizeof(places)/sizeof(char*); i++) {
if (strcmp(place,places[i]) == 0) {
printf("%lld: %s %s %s %s\n", reader->nodeId, place, name, name_ja, name_en);
break;
}
}
break;
} // switch
MinGW-W64 をインストールして gcc でコンパイルした。
gcc -O3 -o c:/gis/bin/filter.exe c:/gis/src/filter.c c:/gis/src/o5mreader.c
osmfilter.exe は MinGW-W64の gcc でコンパイルした。 下の実行時間は3分30秒であった。
osmfilter.exe --hash-memory=2000 e:/o5m/japan.o5m ^ --keep="place=country =state =province =city" ^ -o=d:/japan_out.o5m
Windows用バイナリをダウンロードしたものを osmfilter0 にリネームした。 実行時間は osmfilter.exe とほぼ同じだった。
osmfilter0 --hash-memory=2000 e:/o5m/japan.o5m ^ --keep="place=country =state =province =city" ^ -o=d:/japan_out.o5m
o5mreaderでは ftell のコールが多い。システムコールにならないとしても、 関数オーバヘッドはある。何バイト読み込んだかを記録するより確実なためこうしたのだろう。
osmfilter は (32+3)*5 MB の読み込みバッファを持っている。 o5mreaderの場合、
setvbuf(fp, NULL, _IOFBF, 128*1024*1024);を入れると極度に遅くなる。128KB でも遅くなる。
バッファへの読み込み回数が多いのだろうか？ fseek は1か所で不審はない。 ftellは多いが、これでは読み込みは発生しないはず。
文字列も freadで１バイトずつ読み込むのでオーバヘッドは大きいが、 バッファサイズが大きいとまずいとは思えない。
仕様でははっきりしなかったが、osmconvert のソースコードから、o5mファイル書き込み時のリセットでは 差分コードデータだけでなく、文字列テーブルもクリアしていることが分かった(o5__resetvars() → stw_reset())。
マルチスキャンの場合、最初のスキャンで、 node, way, relationセクションの始まりの直前の Reset位置を記憶しておけば、 ２回目以降は、必ずしも先頭からスキャンしなおす必要はない。
２回目は relation、３回目は way だけ、 ４回目で node, way, relation のセクションという風に処理範囲を絞り込むことにより、 全体の実行時間の短縮が図れる。
relationの member は node か way か relation である。 relation object自体の id と member の refId は共に差分コードの対象であるが、 この二つを一本化するのか、それとも別の系列とするのか、仕様[1] でははっきりしない。
o5mreader.c のソースは下の通りであり、relation object 自体の Id は relId で、 relation member の Id は relRefId であり、差分計算は分かれている。
o5m本家の osmfilter.c か osmconvert.c で確認した方がいいが、 両者のソース・コードは煩雑なので、まだ、確認していない。
日本全土のデータには relation member を持つような relation (super relation) は存在しないので、変換して確かめることはできない。
世界全体では存在することは確認済みである。 しかし、世界のデータについてはまだ十分なテストを終えていない。 いずれ、実データで動作確認する。
O5mreaderIterateRet o5mreader_readRel(O5mreader *pReader, O5mreaderDataset* ds) {
int64_t relId;
if ( o5mreader_readInt(pReader,&relId) == O5MREADER_RET_ERR )
return O5MREADER_ITERATE_RET_ERR;
pReader->relId += relId;
ds->id = pReader->relId;
if ( o5mreader_readVersion(pReader,ds) == O5MREADER_ITERATE_RET_DONE ) {
ds->isEmpty = 1;
return O5MREADER_ITERATE_RET_NEXT;
}
else
ds->isEmpty = 0;
o5mreader_readUInt(pReader,&pReader->offsetRf);
pReader->offsetRf += ftello(pReader->f);
pReader->canIterateRefs = 1;
pReader->canIterateNds = 0;
pReader->canIterateTags = 0;
return O5MREADER_ITERATE_RET_NEXT;
}
O5mreaderIterateRet o5mreader_iterateRefs(O5mreader *pReader, uint64_t *refId, uint8_t *type, char** pRole) {
int64_t relRefId;
if ( !pReader->canIterateRefs ) {
o5mreader_setError(pReader, O5MREADER_ERR_CODE_CAN_NOT_ITERATE_REFS_HERE,NULL);
return O5MREADER_ITERATE_RET_ERR;
}
if ( ftello(pReader->f) >= pReader->offsetRf ) {
pReader->canIterateNds = 0;
pReader->canIterateTags = 1;
pReader->canIterateRefs = 0;
return O5MREADER_ITERATE_RET_DONE;
}
if ( o5mreader_readInt(pReader, &relRefId) == O5MREADER_RET_ERR )
return O5MREADER_ITERATE_RET_ERR;
//fread(_,1,1,pReader->f);
if ( o5mreader_readStrPair(pReader, &pReader->tagPair,1) == O5MREADER_RET_ERR ) {
return O5MREADER_ITERATE_RET_ERR;
}
switch( pReader->tagPair[0] ) {
case '0':
if ( type )
*type = O5MREADER_DS_NODE;
pReader->nodeRefId += relRefId;
if ( refId )
*refId = pReader->nodeRefId;
break;
case '1':
if ( type )
*type = O5MREADER_DS_WAY;
pReader->wayRefId += relRefId;
if ( refId )
*refId = pReader->wayRefId;
break;
case '2':
if ( type )
*type = O5MREADER_DS_REL;
pReader->relRefId += relRefId;
if ( refId )
*refId = pReader->relRefId;
break;
}
if ( pRole ) {
*pRole = pReader->tagPair + 1;
}
return O5MREADER_ITERATE_RET_NEXT;
}
日本のデータにも super relation があることが分かった。 o5m ファイルを osmtool で osm 形式に戻したものを下に示す。 赤字の relation id と、青字の relation ref は別系列の差分コードデータとなっていたものを戻した値である。 osmtool では、上に示した osmreader と同じ方法を使っている。
<relation id="11503495" version="1" timestamp="2020-08-14T11:42:55Z" changeset="89408407" uid="10676345" user="red_mokuri"> <member type="relation" ref="11503494" role=""/> <member type="relation" ref="11503493" role=""/> <tag k="name" v="205系統"/> <tag k="network" v="横浜市営バス"/> <tag k="operator" v="横浜市交通局"/> <tag k="ref" v="205"/> <tag k="route_master" v="bus"/> <tag k="type" v="route_master"/> </relation>
前に(どこか別のページかも)述べたが、o5m ファイルの読み込みではペア文字列テーブルの参照は簡単であるが、 書き込みの方が面倒である。 直前の 15,000ペア文字列にあるか調べて、あれば何回前のペア文字列であるかを返す。 なければ、新規登録し、0 を返す。このとき、テーブルが満杯ならば、一番古く登録したものが上書きされる。
探すためにハッシュマップを使う。osmtool では、現在は unordered_set<string,string> を使っている。 ペア文字列は "#" でつないで一つの文字列としているが、これでよいか吟味する。
("***#", "123") と ("***", "#123") は共に "***##123" となる。
OSMタグの key と val および uid と user がそれぞれペア文字列となる。
uid は正の整数であるが、o5m ではこれを 符号なし可変長整数に変換する。 そうすると何バイトになっても、'\0' は含まないため、文字列とみなすことができる。
uid の最後の文字は "#" になることがあるかも知れないが、一つ前の文字は非ASCIIのため、 これが uid文字列の最後になることはない。よって問題は起きない。
一方、OSMタグのキーはどんな文字も許されるので、key の末尾が "#" ということも許される。 ただし、それだけでは問題は起きない。15,000組のペア文字列に、 ("abc#", "xyz") と ("abc", "#xyz") となったものがある。即ち、 key の末尾の"#" を除いたものが、一致し、val の先頭の "#" を除いたものが一致したときだけ、 両者が区別できない。そのようなケースは実際上は起きないだろう。
念のため、結合文字列を３文字 "#^_" にしておいた。 もし、出現したときは警告メッセージを出すようにしている。
他にも事情があり、自前のハッシュマップに変更した。
xml形式では changeset=0 で uid、user がないケースがある。 o5m では、文字列テーブルには登録せず、 ref=0の後に 0 が二つ(結局 0x00 が３バイト連続)続ける。