OSMのデータ構造[1]は分かりやすい。しかし、lineデータや polygonデータのノード(頂点)データは ノード番号であって、座標値ではない。
５年ほど使ってきたプログラムでは、日本全体のノード座標値データを複数のブロックに分けて、 圧縮してメモリに載せている。一部のブロックだけをキャッシュとして、解凍している。
もっとシンプルな方法でノードの座標値を管理したい。最初にファイルにおいてスワップする方法を 試みたが、実行時間がかかりすぎることが分かった。
ファイル管理での高速化も可能であるが、メモリ管理には及ばないであろう。 二分探索でいけることが分かったので、現状では、データ圧縮は要らない。 数年後には 5GB では厳しくなるかも知れない。そのときは、なるべく簡単なデータ圧縮方法を考えたい。
現在の OSMのノード数は 10ギガ強である。４バイトは超えるが、５バイトあれば十分である。 ファイル管理では 下位の３バイトをサブID とした。 ブロック数(最大ブロック番号＋１)は 610 になった。
メモリ管理の場合には、もっと大きくなっても問題はない。
ブロックサイズが小さくなると、ブロック内の座標値を２バイトの差分コードで表現できる ブロックが出てくるかも知れない。
少なくとも、部分的には差分コード化が可能であるから、 ブロック内にいくつかの差分コードサブブロックと４バイトコードを共存させてもよい。
ファイル管理よりも行数はかなり少なくなる。 実行時間はファイル管理でもスワップが起きない状態と比較すれば１割ほど高速化した。
最大メモリ使用量は日本地図の場合で 3.5GB弱となった。
c:\gisa>java -Dfile.encoding=UTF-8 -Xmx5000m Parser c:/osm/kanto.osm 100万 189950106 1.62分 200万 385886896 1.75分 300万 558946275 1.85分 400万 725347405 1.95分 500万 849865383 2.05分 600万 1012313038 2.15分 実行時間: 2.24分 c:\gisa>java -Dfile.encoding=UTF-8 -Xmx5000m Parser 100万 109558932 7.58分 200万 118896760 7.77分 300万 129656349 7.96分 400万 151799302 8.17分 500万 176647489 8.33分 600万 199159815 8.48分 700万 237257311 8.62分 800万 297680074 8.74分 900万 361676392 8.87分 1000万 389144232 8.98分 1100万 420773372 9.09分 1200万 449643588 9.19分 1300万 483282560 9.29分 1400万 523962051 9.39分 1500万 554035212 9.50分 1600万 577758689 9.59分 1700万 603957342 9.69分 1800万 625593406 9.78分 1900万 665255659 9.88分 2000万 704605019 9.99分 2100万 733490874 10.08分 2200万 756457716 10.17分 2300万 790622198 10.28分 2400万 829932859 10.38分 2500万 881160441 10.48分 2600万 930982044 10.58分 2700万 974634995 10.68分 2800万 1006947494 10.77分 2900万 1041709924 10.87分 3000万 1081645714 10.97分 3100万 1117508196 11.07分 実行時間: 11.11分
// javac Parser.java OSMLib.java Tag.java
// java -Dfile.encoding=UTF-8 -Xmx5000m Parser c:/osm/japan.osm
import java.io.*;
import java.nio.file.*;
import java.util.*;
import javax.xml.parsers.*;
import org.xml.sax.*;
import org.xml.sax.helpers.DefaultHandler;
class NodeBlock {
final static int BlockBits = 24; // Block番号 id >> BlockBits
final static int BlockSize = 5000000;
static NodeBlock[] blocks = new NodeBlock[700];
int[] sids;
long[] lonlats;
int sidLast = -1, ixLast = -1, blkLast = -1;
public NodeBlock(int size) {
sids = new int[size];
lonlats = new long[size];
}
static int getBlockNumber(long id) { return (int)(id >> BlockBits); }
static int getSubId(long id) { return (int)(id & ((long)(1<<BlockBits) - 1)); }
static long getLonLat(long id) {
int blockNumber = getBlockNumber(id);
int sid = getSubId(id); // sub id
NodeBlock blk = blocks[blockNumber];
if (Math.abs(sid - blk.sidLast) < 10 && blk.blkLast == blockNumber) {
if (sid > blk.sidLast) {
for (int ix = blk.ixLast; blk.sids[ix] <= sid; ix++) {
if (blk.sids[ix] == sid) {
blk.sidLast = sid;
blk.ixLast = ix;
blk.blkLast = blockNumber;
return blk.lonlats[ix];
}
}
} else if (sid < blk.sidLast) {
for (int ix = blk.ixLast; blk.sids[ix] >= sid; ix--) {
if (blk.sids[ix] == sid) {
blk.sidLast = sid;
blk.ixLast = ix;
blk.blkLast = blockNumber;
return blk.lonlats[ix];
}
}
}
}
int ix = Arrays.binarySearch(blk.sids, sid);
if (ix >= 0) {
blk.sidLast = sid;
blk.ixLast = ix;
blk.blkLast = blockNumber;
} else {
System.out.printf("no! id=%x blk=%x sid=%x\n", id, blockNumber, sid);
}
return ix >= 0 ? blk.lonlats[ix] : Long.MIN_VALUE;
}
}
public class Parser extends DefaultHandler {
final double E7 = 10000000.0;
static long start = System.currentTimeMillis();
int currBlock=-1;
int cntNodes=0, maxNodes=0;
boolean fNodeSection = false;
boolean fWaySection = false;
int cntWay = 0;
int[] sids = new int[NodeBlock.BlockSize]; // ノード座標値のパースで使用
long[] lonlats = new long[NodeBlock.BlockSize];
public void startElement(String uri, String localName, String qName, Attributes atts) throws SAXException {
if (!fWaySection && "node".equals(qName)) {
if (!fNodeSection) fNodeSection = true;
procNode(atts); // nodeオブジェクトの処理
} else if ("way".equals(qName)) {
long id = Long.parseLong(atts.getValue("id"));
if (fNodeSection) {
fNodeSection = false; // nodeセクションは終わった
procNodeEnd(); // nodeセクションの後処理
}
if (!fWaySection) {
fWaySection = true;
}
if (++cntWay % 1000000 == 0) {
System.out.printf("%d万 %d %.2f分\n", cntWay/10000, id,
(System.currentTimeMillis() - start)/60000.0);
}
} else if (fWaySection && "nd".equals(qName)) {
long nid = Long.parseLong(atts.getValue("ref"));
long lonlat = NodeBlock.getLonLat(nid);
//System.out.printf("%d %d %d %d\n",
// NodeBlock.getBlockNumber(nid), nid, lonlat>>32, lonlat&0xffffffffL);
}
}
void putNodeBlock(int blk, int[] sids, long[] lonlats, int size) {
NodeBlock block = NodeBlock.blocks[blk] = new NodeBlock(size);
System.arraycopy(sids, 0, block.sids, 0, size);
System.arraycopy(lonlats, 0, block.lonlats, 0, size);
}
void procNode(Attributes atts) {
long id = Long.parseLong(atts.getValue("id"));
int blockNumber = NodeBlock.getBlockNumber(id);
if (blockNumber != currBlock) { // 新しいブロックが始まった
if (currBlock >= 0) { // 前のブロックをファイルに書き込む
putNodeBlock(currBlock, sids, lonlats, cntNodes);
if (cntNodes > maxNodes) maxNodes = cntNodes;
cntNodes = 0;
}
currBlock = blockNumber;
}
sids[cntNodes] = NodeBlock.getSubId(id);
int lon = (int)(Double.parseDouble(atts.getValue("lon")) * E7);
int lat = (int)(Double.parseDouble(atts.getValue("lat")) * E7);
lonlats[cntNodes++] = (((long)lon)<<32) + (lat&0xffffffffL);
}
void procNodeEnd() {
putNodeBlock(currBlock, sids, lonlats, cntNodes);
}
public static void main( String[] args ) throws Exception {
long start = System.currentTimeMillis();
String src = args.length >= 1 ? args[0] : "c:/osm/japan.osm";
SAXParserFactory factory = SAXParserFactory.newInstance();
SAXParser parser = factory.newSAXParser();
Parser handler = new Parser();
parser.parse(Paths.get(src).toFile(), handler);
System.out.printf("実行時間: %.2f分\n", (System.currentTimeMillis()-start)/60000.0);
}
}
wayオブジェクトでサイズが大きいのはノード番号列データである。 大半はwayオブジェクト単独で道路・鉄道や川などのラインデータであるから、 その都度、ラインレコードとしてファイル出力すればそれで終わりであるが、 一部の wayオブジェクトは relation オブジェクトのメンバーとなっており、 メンバーかどうかは relation をパースしなければ分からない。 nodeオブジェクトについても同じである。
wayデータを全てメモリ上に置くのであれば、１パスでよいが、 メモリ使用量から厳しい。nodeデータ、wayデータとも可変長バイトコード[4]で圧縮するのであれば 可能であろう。
もう一つの方法は２パス方式である。１パス目は nodeセクション、wayセクションは空読みして、 relationセクションのパースを先に実行する。これで、relationのメンバーとなっている node と way の情報を掴んでおく。２パス目の wayセクションでは、 relationメンバーのみメモリ上に残しておく。
１パス目の空読みのロスタイムはSAXパーサーでは、日本地図の場合で、10分前後になるであろう。
まずは、SAXでの２パスのロスタイムを調べる。7、8分で済むならば、 ２パス方式の方がプログラムが簡単であろう。
２パス方式の事前調査結果およびそのプログラムを下に示す。
現在のところ、１パス目が8分、２パス目が12分、全体で20分となった。
現在使用中の OSMParser は SAX を使わず、完全な自前プログラムである。 １パス目は４分強である。nodeのパース時間は５分弱である。 SAXでは 1.5～2 倍の時間がかかる。 しかし、パース以外の処理にかかる時間の方が大きいため、 SAXを使うことによる時間増加は２割前後であろう。
また、SAXでも時間短縮の余地はあるだろう。
現在のノード数は 約230M であるから、ノードのサブID、lon、lat に必要なメモリは 正味 230M * 12 ≒ 2.8GB である。実行中の最大メモリ使用量は 3.5GB であるから、 700MB 程度がどこかに使われていることになる。
c:\gisa>java -Dfile.encoding=UTF-8 -Xmx5000m Parser c:/osm/kanto.osm relation: 1.57分 ブロック数＝610 maxNodes＝888899 実行時間: 3.64分 c:\gisa>java -Dfile.encoding=UTF-8 -Xmx5000m Parser relation: 7.97分 ブロック数＝610 maxNodes＝4329823 totalNodes=227849492 実行時間: 20.05分
// 第１パス： PreParser relationセクションのみをパースする
static class PreParser extends DefaultHandler {
boolean fRelation = false;
public void startElement(String uri, String localName, String qName, Attributes atts) throws SAXException {
if (!fRelation && qName.equals("relation")) {
//System.out.println("relation");
// relationオブジェクトの開始処理
if (!fRelation) {
fRelation = true;
}
}
}
public void endElement(String namespaceURI, String localName, String qName) {
if (fRelation && qName.equals("relation")) {
// relationオブジェクトの終了処理
fRelation = false;
}
}
}
public static void main( String[] args ) throws Exception {
long start = System.currentTimeMillis();
String src = args.length >= 1 ? args[0] : "c:/osm/japan.osm";
SAXParserFactory factory = SAXParserFactory.newInstance();
SAXParser saxparser = factory.newSAXParser();
// 第１パス: relationパース
PreParser preparser = new PreParser();
saxparser.parse(Paths.get(src).toFile(), preparser);
System.out.printf("relation: %.2f分\n", (System.currentTimeMillis()-start)/60000.0);
// 第２パス: node/wayパース＆処理、relation処理
Parser parser = new Parser();
saxparser.parse(Paths.get(src).toFile(), parser);
System.out.printf("ブロック数＝%d maxNodes＝%d 実行時間: %.2f分\n",
parser.currBlock+1, parser.maxNodes, (System.currentTimeMillis()-start)/60000.0);
}