python - ジオコーディングにはどのデータ構造を使用すればよいですか?

Question

Nominatimのように、住所を入力として受け取り、緯度と経度、または複数の一致の場合は緯度と経度を吐き出す Python スクリプトを作成しようとしています。

したがって、可能な入力と出力は次のようになります。

In:米国ニューヨーク=> Out:ニューヨーク (lat:x1 lon:y1)
In:ニューヨーク=> Out:ニューヨーク (lat:x1 lon:y1)
In:米国ニューヨーク州パールストリート=> Out:パールストリート (lat:x2 lon:y2)
In:パールストリート、アメリカ=> Out:パールストリート (lat:x2 lon:y2)、パールストリート (lat:x3 lon:y3)
イン:パールストリート=> アウト:パールストリート (lat:x2 lon:y2)、パールストリート (lat:x3 lon:y3)
In: 103 Alkazam, New York, USA => Out:ニューヨーク (lat:x1 lon:y1)

上記の 6 では、 address の場所が見つからなかったため New York が返されまし103 Alkazam, New York, USAたが、少なくともは見つかりNew York, USAました。

最初は、兄弟がアルファベット順にソートされる階層関係を表すツリーを構築することを考えました。それは次のようだったかもしれません:-

                                     GLOBAL
                                       |
                   ---------------------------------------------
                   |            | ...
                  USA
             ---------------
             |        | ...
         CALIFORNIA  NEW YORK 
            |         |
     -----------    -------------
     |        |..   |          |....
 PEARL STREET      PEARL STREET

しかし問題は、ユーザーが 2、4、5 のように不完全な住所を提供できることでした。

そこで、次に検索ツリーを使用して、各ノードに完全修飾アドレスを格納することを考えました。しかし、これもかなり悪いです:-

これにより、各ノードに冗長性の高いデータが保存されます。これは非常に大きなデータになるため、スペースの節約が重要です。
ユーザーが検索スペースを絞り込んだという事実を活用することはできません。

追加の要件が 1 つあります。スペルミスを検出する必要があります。これは別の問題として扱う必要があり、各ノードを一般的な文字列として扱うことができると思います。

更新 1

少し詳しく説明します。入力はリストで、低いインデックスの項目は高いインデックスの項目の親です。もちろん、それらは直接の親または子である場合もあれば、そうでない場合もあります。したがって、クエリ 1 の場合、入力はになります["USA", "NEW YORK"]。したがって、USA, New York結果が返されなくてもまったく問題ありません。

ユーザーが住所を知っていて、私たちのデータが非常に詳細であれば、ユーザーは建物を見つけることができるはずです。

更新 2 (省略ケース)

ユーザーがをクエリPearl Street, USAした場合、アルゴPearl StreetはNew Yorkを親として認識しておりUSA、その親であるため、アドレスを特定できるはずです。

更新 3 (サープラスケース)

ユーザーがを照会するとします101 C, Alley A, Pearl Street, New York。また、データがを知っているが101 C、については知らないとしAlley Aます。それによると101 C、の直接の子ですPearl Street。この場合でも、アドレスを特定できるはずです。

score 2 · Accepted Answer

彼らの答えに感謝します、彼らの答えは役に立ちましたが、私が必要とするすべてに対処しませんでした。私はついに私のすべてのケースを処理するアプローチを見つけました。このアプローチは、私が質問で提案したものの修正版です。

基本的なアプローチ

ここでは、「ノード」と呼ばれるものを参照します。これは、場所エンティティの緯度、経度、場合によっては寸法、およびその完全な住所などの地理情報を含むクラスオブジェクトです。

エンティティのアドレスが「101C、Pearl Street、New York、USA」の場合、これは、データ構造に「101 C」、「Pearl Street」、「New York」、および「」の少なくとも4つのノードがあることを意味します。アメリカ合衆国'。各ノードにはnameと1つaddressの部分があります。「101C」の場合、name「101 C」になり、住所は「Pearl Street、New York、USA」になります。

基本的な考え方は、これらのノードの検索ツリーを作成することです。ここで、ノードnameは検索のキーとして使用されます。address複数の一致が得られる可能性があるため、後で、ノードがクエリされたノードとどの程度一致しているかについて結果をランク付けする必要があります。

                                    EARTH
                                      |
                ---------------------------------------------
                |                                           |
               USA                                        INDIA
                |                                           |
        ---------------------------                     WEST BENGAL
        |                         |                         |
     NEW YORK                 CALIFORNIA                 KOLKATA
        |                         |                         |
   ---------------            PEARL STREET              BARA BAZAR
   |             |                                          |
PEARL STREET   TIME SQUARE                                 101 C
   |             |
  101 C         101 C

上記のような地理データがあるとします。したがって、「101 C、NEW YORK」を検索すると、「NEW YORK」の「101C」ノードだけでなく、「INDIA」のノードも返されます。これは、アルゴがnameノードの検索に「101C」のみを使用するためです。address後で、クエリされたアドレスからのノードの差を測定することにより、結果の品質を評価できます。この場合のように、ユーザーは不完全なアドレスを提供することが許可されているため、完全一致は使用していません。

グレーディング検索結果

結果の品質を評価するために、最長共通部分列を使用できます。このアルゴでは、「省略」と「余剰」のケースが適切に処理されます。

コードに話をさせるのが最善です。以下は、この目的のために調整されたPython実装です。

def _lcs_diff_cent(s1, s2):
    """
    Calculates Longest Common Subsequence Count Difference in percentage between two strings or lists.

    LCS reference: http://en.wikipedia.org/wiki/Longest_common_subsequence_problem.
    Returns an integer from 0-100. 0 means that `s1` and `s2` have 0% difference, i.e. they are same.
    """
    m = len(s1)
    n = len(s2)

    if s1 == s2:
        return 0
    if m == 0: # When user given query is empty then that is like '*'' (match all)
        return 0
    if n == 0:
        return 100

    matrix = [[0] * (n + 1)] * (m + 1)
    for i in range(1, m+1):
        for j in range(1, n+1):
            if s1[i-1] == s2[j-1]:
                matrix[i][j] = matrix[i-1][j-1] + 1
            else:
                matrix[i][j] = max(matrix[i][j-1], matrix[i-1][j])

    return int( ( 1 - float(matrix[m][n]) / m ) * 100 )

最適化されたアプローチ

冗長性を強制するため、上記の（基本的な）アプローチを採用しました。ユーザーがクエリで「USA」を指定した場合、「INDIA」のノードを調べる必要がないという事実を活用することはできませんでした。

この最適化されたアプローチは、上記の両方の問題にかなりの程度対処します。解決策は、1つの大きな検索ツリーを持たないことです。検索スペースを「USA」と「INDIA」に分割できます。後で、これらの検索スペースを州ごとにさらに再パーティション化できます。これは私が「スライス」と呼んでいるものです。

次の図では、-SearchSliceは「スライス」をSearchPool表し、検索ツリーを表します。

                            SearchSlice()
                                  |
            ---------------------------------------------
            |                                           |
        SearchSlice(USA)                           SearchSlice(INDIA)
            |                                           |
    ---------------------------                  SearchPool(WEST BENGAL)
    |                         |                   |
 SearchPool(NEW YORK)     SearchPool(CALIFORNIA)  |- KOLKATA
    |                         |                   |- BARA BAZAR, KOLKATA
    |- PEARL STREET           |- PEARL STREET     |- 101 C, BARA BAZAR, KOLKATA
    |- TIME SQUARE
    |- 101 C, PEARL STREET
    |- 101 C, TIME SQUARE

上記で注意すべきいくつかの重要なポイント...

各スライスの深さは1レベルのみです。さて、これは上では実際には明らかではありません。
スライスされたレベルの名前は、その子のアドレスには表示されません。たとえばSearchSlice(USA)、「USA」の州のスライスを維持します。したがって、「NEW YORK」の下のノードには、「NEWYORK」または「USA」という名前が含まれていませんaddress。他の地域でも同じことが言えます。階層関係は、完全なアドレスを暗黙的に定義します。
「101C」には、スライスされていないためaddress、親も含まれます。name

スケーリングの可能性

バケット（プール）がある場合、暗黙のスケーリングの可能性があります。私たちは（たとえば）「USA」の地理データを2つのグループに分けます。両方とも異なるシステム上にある可能性があります。したがって、「NEW YORk」プールがシステムAにあるが、「CALIFORNIA」プールがシステムBにある場合は、もちろん親を除いてデータを共有しないため、まったく問題ありません。

ここに警告があります。常にスライスとなる親を複製する必要があります。スライスの数は制限されているため、階層が深くなりすぎないため、冗長すぎて複製できないようにする必要があります。

ワーキングコード

動作するデモPythonコードについては、私のGitHubを参照してください。

score 1 · Accepted Answer

キー値ストレージマップと全文検索を使用するのはどうですか。

ロケーション文字列のキー
location_level および lat&lon データの値。
によって検索する：
- ユーザー入力文字列を単一の場所の単語に分割します（カンマだけではありません）
- マップ内の各単語を検索
- 最小位置レベルの緯度経度を返す(&L)

python.dict、memcached、mongodb .... あなたのニーズを満たします。

ロケーションワードが多すぎる場合は、location_level を新しいマップとして分割すると、2 つの検索が高速になります
位置レベルを忘れて、全文検索として扱います
膨大なデータ？短い文字列または数値へのハッシュキー

考慮すべきいくつかの質問:

データベースにデータを保存する方法
もしあれば、データから検索ツリーを初期化する方法
実行時に検索ツリーを拡張/編集する方法
入力/ストレージの耐障害性
ストレージスペース>速度？または速度>ストレージ？

そのため、ユーザー入力のためのより使いやすいテストケース

101 C, Time Square, New York, US
101 C, Pearl street, New York, US

101 C, Time Square, SomeCity, Mars
101 C
101 C, US
101 C, New York, US

101 C, New York, Time Square, US

North Door, 101 C, Time Square, New York, US
South Door, 101 C, Time Square, New York, US

状況の場合:

巨大なデータで高速。
完全な耐障害性;
ストレージとランタイムを簡単に調整

最良の解決策:(これも複雑です)

フラットキー値マップストレージ
全文検索
- またはBツリー検索によるハッシュキー

あなたのプログラム/ウェブサイトは、Google と同じくらい速く実行できるかもしれません。

score 0 · Accepted Answer

この問題に対してデータ構造を作成しようとすると、データの冗長性が得られると思います。むしろ、ツリー/グラフを使用して、ノード値に対してユーザーの入力から単語を検索する検索アルゴリズムを実装してみてください。あいまい一致は、最も可能性の高い結果を生成するのに役立ち、類似度の信頼度に応じて上位のいくつかをユーザーに提案/表示できます。

これにより、スペルミスなどにも対処できます。

python - ジオコーディングにはどのデータ構造を使用すればよいですか?

3 に答える 3

基本的なアプローチ

グレーディング検索結果

最適化されたアプローチ

スケーリングの可能性

ワーキングコード

Related

Reference