OSMパーサー

はじめに

プログラム作成ではなるべく標準APIを使いたい。しかし、地図システムのデジタルデータは膨大なため、 メモリ不足になったり、処理時間が長大になることがある。

また、OSM(OpenStreetMap)の xmlデータは規模は大きいが構造はシンプルであるという特徴がある。 このため、自前でのパースが比較的やりやすい。

色々と試行して、最終的には、分かりやすくて、パフォーマンスの良いプログラムとしたい。

２パス方式

OSM(OpenStreetMap)データ(xml形式)は、大きくは nodeセクション、wayセクション、relationセクションからなる。

日本地図データは xml ファイルでは 40GB 程度になる。xml には冗長性があるが、 8GB(ユーザ使用は５GB程度)レベルのパソコンには、全データをメモリに載せることはできない。

wayオブジェクトは必ず nodeオブジェクトに含まれる座標値データが必要になるため、 全ノードの座標値データはメモリに置くことにする。 同じように、全wayオブジェクトをメモリに置ければプログラムは楽であるが、5GB では難しい。

このため、第１パスでは、node と way のパースは行わず、先に relationをパースして、 relationの処理に必要な wayオブジェクトを見つけて置く。

第２パスでは、relation処理で使用する wayオブジェクトだけをメモリに置くようにする。 大抵の wayオブジェクトは単独でパースした結果を独立したレコードとしてファイル出力する。

主要クラスおよびデータ

Relation管理

public class Relation {
    static class Member {
        long ref_id;     // node, way, relation id
        String type;     // node, way, relation
        String role;     // inner, outer など
    }
    long id;
    String[] tags;
    Member[] members;
}

主要データ

HashMap<Long,long[]> mapWays

第１パスの relation のパースで、Member が way の場合、その id （ref_id）を mapWays に登録する。この段階では 値は null である。

第２パスの way のパースで、その way id が mapWays に登録されていた場合、 その way を構成する node id 列(long[]) を mapWays に登録する。これにより、 　　null だったものが long[] （long配列に変わる）

HashMap<Long,Relation> mapRelations

第１パスで relation のパース結果が格納される。キーは relation id である。

Memberが relation のケースを処理できるように HashMap に格納しているが、 当面、そのような relation (super relationと呼ぶ) はレンダリング対象でないため、 HashMap でなくて List でもよい。

HashMap<String,Integer> mapKeys

OSMタグのキー(natural、landuse、amenity、shop など)をコードに変換するとき使用する。

HashMap<String,Integer> mapVals

OSMタグのキー(water、forest、school、supermarket など)をコードに変換するとき使用する。

HashMap<String,Integer> mapWords

place、name、operator など値が任意の文字列となる OSMタグの値をコードに変換するとき使用する。

第１パスの空読み

SAXでは、日本地図データの場合、空読みに 8分ほどかかることが分かった。 現在使用中の自作OSMParserでは４分程度であるが、これを再確認しておく。

まず、次のプログラムを試した。japan.osm に対する実行時間は 3.5～3.7分となった。 line.indexOf("<r") や line.trim()、lines.toCharArray() なども試したが、速くはならなかった。

この後のパースを考えると、下のプログラムが一番いいであろう。 && line.charAt(ix+2)=='e' はなくてもいいが、分かりやすさのために加えた。 この場合、パフォーマンス上は変わらない。

public class MyParser  {

    // 第１パス： PreParser  relationセクションのみをパースする
    static class PreParser {
        void parse(String area) throws Exception {
            BufferedReader br = new BufferedReader(new FileReader("c:/osm/"+area+".osm"));
            String line;
            while ((line = br.readLine()) != null) {
                int ix = line.indexOf('<');
                if (line.charAt(ix+1)=='r' && line.charAt(ix+2)=='e') {   // relationオブジェクト
                    break;                          // relationセクションの始まり
                }
            }
            br.close();
        }
    }


    public static void main( String[] args ) throws Exception {
        long start = System.currentTimeMillis();
        String src = args.length >= 1 ? args[0] : "c:/osm/japan.osm";

        PreParser preparser = new PreParser();
        preparser.parse(src);

        System.out.printf("実行時間: %.2f分\n", (System.currentTimeMillis()-start)/60000.0);
    }
}

nodeタグのパース

まず、ノードのパース時間を調べた。kanto.osm で 0.7分、japan.osm で 3.5分となった。

    String getAttr(String name, String line) {
        int ixBgn = line.indexOf(name);
        if (ixBgn < 0) return null;
        ixBgn += name.length() + 1; // '"' の分
        int ixEnd = ixBgn;
        while (ixEnd < line.length() && 
                    line.charAt(ixEnd) != '"' && line.charAt(ixEnd) != '\'') {
            ixEnd++;
        }
        return line.substring(ixBgn, ixEnd);
    }

    void parse(String area) throws Exception {
        BufferedReader br = new BufferedReader(new FileReader("c:/osm/"+area+".osm"));
        String line;
        while ((line = br.readLine()) != null) {
            int ix = line.indexOf('<');
            if (line.charAt(ix+1)=='w' && line.charAt(ix+2)=='a') {   // wayオブジェクト開始
                break;  // nodeセクション終了
            }
            if (line.charAt(ix+1)=='n' && line.charAt(ix+2)=='o') {   // nodeオブジェクト開始
                if (cntNode++ == 0) {               // nodeセクションの始まり
                    System.out.printf("node section starts\n");
                }
                String sId = getAttr(" id=", line);
                String sLon = getAttr(" lon=", line);
                String sLat = getAttr(" lat=", line);
                long id = Long.parseLong(sId);
                int lon = (int)(Double.parseDouble(sLon)*E7);
                int lat = (int)(Double.parseDouble(sLat)*E7);
//System.out.printf("%d %d %d\n", id, lon, lat);
            }
        }
        br.close();
    }

    public static void main( String[] args ) throws Exception {
        long start = System.currentTimeMillis();
        String src = args.length >= 1 ? args[0] : "c:/osm/japan.osm";

        MyParser parser = new MyParser();
        parser.parse(src);

        //PreParser preparser = new PreParser();
        //preparser.parse(src);

        System.out.printf("実行時間: %.2f分\n", (System.currentTimeMillis()-start)/60000.0);
    }

実行時間は SAXを使った場合に比べて半分以下に短縮したが、メモリ使用量はほぼ同じ 3.5GB弱である。

Relationのパース

取りあえずは、以前のままとした。

プログラム ソースコード

地図アプリMap用OSMParser

おわりに

現時点で全プログラムとの大きな変更はノード座標値管理である。はるかにシンプルなものに変更した。 この効果が大きく、パース時間は約20分に半減した。

リファレンス