JavaのOSMジオコーダー

こんにちは、Habrの親愛なる読者。 この記事は話します

• ファジースキームを使用したアドレスとデータストアについて
• Javaでのジオデータ処理、つまりJavaトポロジスイートについて
• 開発者にとっての「シンプルさ」のコストについて
• Pure Java nosqlドキュメントデータベース/全文検索エンジンについて-Elasticsearch。

OSMに不慣れなJavaハブリーダー向け

OSMは、非常に詳細なグローバルカバレッジを持つオープンな地理空間データベースです。



ユーザーにとっては、オンラインで閲覧したり、ナビゲーターにダウンロードしたり、電話で編集したり、印刷したり、商業利益を受け取ることを含む他の考えられる方法で一般的に使用したりすることができます。



開発者の観点から見ると、これは非常に特殊なデータベースです。

• OSMには明確なデータスキームはなく、GISをレイヤーに分割する通常の方法はありません。 オブジェクトのタイプ、そのプロパティ、そしてある意味ではそのジオメトリは、タグ-テキストのキーと値のペアを介して設定されます。
• ジオメトリはポイントに対してのみ保存されます。 ラインは、id'shnikovポイントの配列です。 ポリゴン-ラインへのリンクのセットで、境界にラインが含まれているかどうかを示します-内部または外部。
• これにより、コミュニティは新しいデータ型を即座に作成できます。 歩道をマークしたい場合は、タグの組み合わせをネゴシエートして行きます。 理解できないモデレーターによって、「あなたはカードを乱雑にします、誰もあなたの仕事を必要としません」というコメントであなたの心に大切なデータを切り取って、ドラムなしで（まあ、ほとんど）。

当然、開発者にとってこのようなフリーシップは簡単に悪夢に変わります。

住所

私たちのほとんどは、1〜2都市を変えて生活していますが、さまざまな郵送スキームに注意を払う時間はありません。



それは小さなものから始まります-アドレスを書き留めることによって：大きいものから小さいものへ、または小さいものから大きいものへ。



次に、一部の都市では住所が住所で使用されていないことがわかります。

家521、コトル、モンテネグロまたはロシア連邦、エネルゲティクの家15。



その1つの家には複数の住所があります。

世界最高の都市、ダイレクトストリート、22、彼は世界最高の都市、垂直ストリート、12



その二重アドレス指定はコーナーハウスだけでなく、2つのアドレスは制限からはほど遠いものです。

タリンカシュタノバヤ通り13、15、17

タリンチェリーストリート1、3

*例は私の人生から非常に現実的であり、元のストリート名を忘れてしまいました。



家自体だけでなく、玄関、さらには家の外に現れる部分にも対処できること。 （これはタリンの例からのものです-同じ建物内の同じ通りの住所は、かつては異なる所有者に属していた内部セクションです）。



そして最後に、すべてのエキゾチックな

ナーベレジヌイェ・チェルニー、11/1

これは11の住宅団地、家1です。実際、低周波の家にはタイプHouse Streetの通常の住所もありますが、地元の人はそれらを使用しません。



これに次を掛けます：

OSMで場所を指定する4つの根本的に異なる方法

3-4マルチキャストを指定する方法

番地を指定する3つの方法



さらに、データを入力する場合は、この動物園のいくつかのスキームを使用するだけです。 適切なジオコーダーを作成する場合は、この動物園の存在を思い出すだけでは不十分です。「計算」する必要があります。



たとえば、家-都市と一致させるために何が必要かを見てみましょう。

プロジェクトの母国である英国から始めましょう。



たとえば、ウェストミンスターの家。 www.openstreetmap.org/way/46138969

addr:housenumber 1 addr:street Derby Gate building yes
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ウェストミンスター自体は次のようにマークされています。

 name Westminster name:ru  place town
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

覚えておくべきより重要なのは、アヒルがロンドンのほぼ中心であるということです。 ロンドンは基本的に数十の小さな町で構成されています。 家はどの都市に属しますか？ ロンドンへ、それともウェストミンスターへ？



実際、この質問に明確に答えることは不可能です。建物は正式にどの都市を指しているのかが示されていないためです。 しかし、例えば、私にとっては、「ロンドン、ダービーゲート、1」と「ウェストミンスター、ダービーゲート、1」および「ロンドン、ウェストミンスター、ダービーゲート、1」の両方の要求で、優れたジオコーダーがこの家を見つける必要があることは明らかです。



実装を見ると、各家（住所ポイント）に該当するすべての多角形の境界（ここで指定されている場合は都市の境界）と近隣の集落の配列にマッピングします。ここではロンドンが最も近い都市、ウェストミンスターが最も近い町です。まだ彼らの隣人。



elasticsearchのjsonデータスキーマでは次のようになります

 //     "nearby_places": { "properties": { "id": { "type": "string" }, "place": { "type": "string" }, "name": { "type": "string" }, "alt_names": { "type": "string" } } }, //         ,   ,     "locality_name": { "type": "string" }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

したがって、検索する場合、要求に応じてどの都市でも家を見つけることができますが、違いは正確に一致した都市と近隣の都市の関連性のみです。 各「必要」は、1つまたは2つの空間結合です。

ジオコーダー

有名なオスマーズヴェリクが言ったように

「最近、誰もが次のジオコーダーがしていることをしているだけです。」

私も例外ではありません：誰もがジオコーダーを書いていますが、なぜ私が悪いのですか？ ジオコーダーバイクも欲しいです。



住所に関してOSMに何を求めていますか？

1. csvまたはsqliteでアドレスをアップロードしてください
2. 100,500個の住所のリストをジオコーディングしてください
3. オンラインジオコーディングサービス（OSMにはオンラインジオコーダーがあるため、このアイテムはそもそもありません）
4. 家や組織の住所を入力しましたが、なぜオンラインジオコーダーで見つけられないのですか？
5. OSMデータを使用したローカル検索エンジンが欲しいのですが、何をお勧めしますか。

通常、答えは次のように始まります。

1. postgres、postgisが必要になります（通常、90％がクエストのこの部分を通過します）
2. osmosisまたはosm2pgsqlを使用してこのデータベースにOSMデータをロードする必要があります。突然惑星規模に焦点を合わせることを決めた場合、RAM（16-32ギガバイト）と忍耐（多くの作業員がいる場合は数日、 RAMは十分ではありません）。 また、国はあまり速くなく、鉄にあまり忠実ではありません。
3. post-sinスクリプトを使用してデータを処理します。 （希望する結果に応じて、OSM-stoicsのデータ処理に連絡したい10％-20％が残っています。）
4. アドレスを使用してデータベースに検索を追加するか、csv / jsonで必要な検索をアップロードします

ユニット全体がクエストを完了します。 ジオコーダーに各新機能を追加すると、ポストエラーで地理空間結合を処理するのに数時間または数日かかり、ポストエラーで必要な新しいデータをロードするのにギガバイトのRAMが必要です。



そして、ロシア連邦では都市の埋め立て地に入ることで家庭の都市を検討するのが慣習であり、英国では-集落のそれぞれの地点の近くで、ロシア連邦で採用された都市境界、英国のボロノイ埋め立て地+隣人の両方が必要であり、これはすべて混乱しています。 目は血で満たされており、次の対処方法は、たくさんの関係に基づいて、感情の突風を引き起こします。



ジオコーディングは、2つのほぼ独立したタスクと見なすことができます。

1. データを取得するためのすべてのオブジェクト（住所、通り、都市、関心のあるポイント）について：都市の境界、近隣の都市ポイント、周囲の道路。
2. このデータを使用して検索を整理します。 最も単純な場合、それは全文検索です。

問題1の解決に集中しました-検索インデックスに適した形式でデータを取得します。 原則として、Googleまたはyandexのインデックス作成用にこのデータを提供したので、ジオコーダーの2番目の部分を外部委託できます。

試行番号1

私の最初の試みはここにあります。 github.com/kiselev-dv/osm-addresses-pgsql

単純化されたデータをpostgresにロードし、その後、さまざまなトリックを使用して妥当な時間内に保持し、それらを処理します。



開発プロセス中に、Javaでジオメトリを処理し、完成したジオメトリをpostgresにロードする方が高速かつ柔軟であることが判明しました。

計算幾何学における計算の複雑さ

通常、誰も記事の途中を読みません;明らかなトートロジーが退屈な読者を元気づけることを願っています。



zip xmlにパッケージされた2ギガバイトのデータをダウンロードするのに6ギガバイト以上のRAMが必要なのはなぜですか？



OSMデータには完全なジオメトリが含まれておらず、地理参照を持つ唯一のOSMオブジェクトはポイントです。 （データの正規化だけで勝利）したがって、ジオメトリを取得するには、ラインからid'shnikovリストからポイントをロードする必要があります。 実際、メモリの主な量はポイントのインデックスを消費します。 もう一度ディスクに登らないように、通常はタグが保存されます。 現在、惑星のダンプには約30億ポイントが含まれており、ここにインデックスにポイントを保存するためのオーバーヘッドが追加され、通常のホームコンピューターではJavaHeapSpaceが失敗します。



これをすべて管理してデータベースにロードし、幾何学的なインデックスを収集したとします。 クエリの実行を高速化する方法は？

作業の大部分はポイントロケーションの問題です。 つまり、ロシア連邦の例を使用して、50万の境界ポリゴンで150万のポイントの発生を計算する必要があります。 たとえば、ロシア連邦の国境には40,000のセグメントが含まれていることを理解することも重要です。 境界線に入るためには、100万ポイント全体をチェックする必要があります。 インデックスの存在にもかかわらず、複雑さはO（N * M）です。 Postgisは、インデックスを使用して、100万のアドレスポイントのうちポイントnがロシア連邦の境界内にある可能性があることをすばやく判断し、その後、ポリゴン内のポイントが正確かどうかを判断して、M個のスカラー積を計算します（Mは境界ポリゴンのセグメントの数です）。



この事実が実現するまでに、私はすでにほぼすべての準備作業を行っていました。行政境界のポリゴンの解析、道路形状の取得と簡素化、Java Topology Suiteを使用したJavaの住所を持つ家の形状の取得です。 www.vividsolutions.com/jts/jtshome.htmつまり、私は基本的に空間結合をうまく計算するために、また一般的なIOフレームワークとして使用されていました。



postgisを使用する際のもう1つのボトルネックは、クエリ実行の並列化の難しさです。 この場合、1秒あたり数百のリクエストはありませんが、数時間にわたって1つのシックリクエストがあります。

最高の自転車、試行番​​号2

実際、データ処理の複雑さを描くとき、​​私は少し心を奪われます。 たとえば、OSMコミュニティは、マップをさまざまなナビゲーションプログラムの形式に変換することができます。 参加者の専用サーバーと通常のホームコンピューターの両方を使用して、これを毎日行います。

同時に、ロシアのコミュニティは、ローカルの詳細、ドイツのコミュニティを考慮に入れて、独自のOSMデータを処理します。



2回目の試みで、私は同様の道をたどることに決めました。 私は、ほとんどのOSMが自宅のPCで使用できるアプリケーションを作成することにしました。

これに必要なもの：

1. 最も重要なことは、インストールの容易さです。 誰もあなたのために環境を設定し始めたり、追加のライブラリやデータベースエンジンをインストールしたりしません。 （さようならpostgres）
2. カスタマイズする機能。 コミュニティに支援してもらいたい場合は、コミュニティに考慮して地元の伝統や慣行を実施する機会を与えてください。
3. さまざまなアプリケーション。 繰り返しになりますが、地元のコミュニティにあなたのツールで幅広いタスクを解決させてください。 ローカルコミュニティが必要とする形式でアドレスレジストリのアンロードを行う機会を与えます。

なぜなら No. 1を試した後、すでにある程度の経験がありました。javaのみを使用してpostgisに実装したプロセスを部分的に繰り返す必要がありました。 実際、JTSに実装されている空間インデックスRTreeとQuadTreeのみが必要です。 そして、ジオメトリとライン上のポイントを分離するなど、ジオメトリを操作するためのいくつかの実用的な方法。



そのため、OSMデータを2段階で処理します。

1 OSMファイルからジオメトリを取得し、断片にカットします-幅0.1度のストリップ。 これにより、タスクを自然にパーツに分割し、同時に境界のジオメトリを簡素化できます。 つまり、40,000のセグメントを持つロシア連邦の1つの境界の代わりに、1ダースのセグメントを持つ各1,500個のピース​​を取得します。 各ストリップの境界線ポリゴンの数も数十の領域になります。

2第2段階では、ポイントが境界のポリゴンに入ることを期待し、最も近い通り、最も近い都市を探します。 各「ストリップ」はそれぞれ個別に処理され、このステージはスレッド/ノード間で並列化されます。



その結果、興味のあるポイント、通り、都市、国境、家のJSON記述を取得します。











中間データのストレージ形式はjson（gzipで圧縮）です。 これにより、まず、デバッグが大幅に簡素化されます。 単純な（z）cat、（z）grepで中間結果を見ることができます。 第二に、もしあればサードパーティの開発者の生活を簡素化します。



出力では、postgis + sphynxバンドルのcsv（ここではpostgisは不要かもしれませんが、このバンドルでリバースジオコーダーを実行すると便利です）とelasticsearchのjsonを生成します（リバースジオコーディングはelasticsearch自体を使用して実行できます）。



6 GBのRAMと約5 GBのディスク容量で、RFの処理に約2時間かかります。 時間を犠牲にすることで、より少ないラムで収縮できます。 私に知られているアナログは2日間を過ごします。

多くのセクションは、私のクラス実装を使用してカスタマイズし（拡張する予定の拡張機能の数）、groovyの拡張機能を裏切ることができます。

データ処理アプリケーションは1つの実行可能jarであり、追加の依存関係をインストールする必要はありません。

現時点では、多くのコマンドラインパラメーターを使用して起動するためのかなり洗練された構文がありますが、将来は1行のjava -jar gazetteer.jar russia.configで起動し、クラスターの作業ノードとしてさらに改善する予定です。



自転車github.com/kiselev-dv/gazetteerへのリンク



私は検索技術が苦手なので、elasticsearchに読み込まれる検索自体はまだ不十分です。 この種のデータの操作と、ジオデータの検索エンジンの設定の実験に興味のある人がハブにいる場合-ようこそ。



プロジェクトは2つの部分で構成されています。

Gazetteer-データ処理。

GazetteerWeb-elasticsearchの上部にあるAPI（Tomcatでは現在-今後はnettyを使用する予定です）