Welche Datenstruktur soll ich für die Geocodierung verwenden?

Question

Ich versuche, ein Python-Skript zu erstellen, das eine Adresse als Eingabe nimmt und seinen Breiten- und Längengrad oder Breiten- und Längengrade im Falle mehrerer Übereinstimmungen ausspuckt, ganz wie Nominatim.

also die möglichen Ein- und Ausgänge können sein: -

1. In: New York, USA => Out: New York (lat: x1 lon: y1)
2. In : in New York => Out: New York (lat: x1 lon: y1)
3. In: Pearl Street, New York, USA => Out: Pearl Street (lat: x2 lon: y2)
4. In: Pearl Street, USA => Out: Pearl Street (lat: x2 lon: y2), Pearl Street (lat: x3 lon: y3)
5. In: Pearl Street => Out: Pearl Street (lat: x2 lon: y2), Pearl Street (lat: x3 lon: y3)
6. In: 103 Alkazam, New York, USA => Heraus: New York (lat: x1 lon: y1)

In 6 oben wurde New York zurückgegeben, da kein Platz mit der Adresse 103 Alkazam, New York, USA gefunden wurde, aber es konnte zumindest New York, USA gefunden werden.

Ursprünglich dachte ich daran, einen Baum zu erstellen, der die Hierarchiebeziehung darstellt, in der die Geschwister alphabetisch sortiert sind. Es könnte wie gewesen: -

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

Aber das Problem war Benutzer unvollständige Adresse, wie in 2, 4 und 5

So bieten kann, ich als nächstes dachte einen Suchbaum zu verwenden und speichern Sie die vollqualifizierten Adresse in jedem Knoten. Aber das ist auch ziemlich schlecht seit:

• Dies wird hoch redundante Daten in jedem Knoten speichern. Da dies eine wirklich große Datenmenge ist, kommt es auf den Weltraumschutz an.
• Es kann nicht die Tatsache ausnutzen, dass der Benutzer den Suchraum eingegrenzt hat.

Ich habe eine zusätzliche Anforderung. Ich muss Rechtschreibfehler erkennen. Ich denke, das muss als ein separates Problem behandelt werden und kann jeden Knoten als generische Strings behandeln.

aktualisieren 1

Etwas Ausarbeitung. Die Eingabe wäre eine Liste, in der der Artikel auf dem niedrigeren Index dem übergeordneten Artikel übergeordnet ist. und sie können natürlich nicht unmittelbar Eltern oder Kind sein. Für Abfrage 1 wäre die Eingabe also ["USA", "NEW YORK"]. Es ist also völlig in Ordnung, dass USA, New York kein Ergebnis liefert.

Der Benutzer sollte in der Lage sein, ein Gebäude zu finden, wenn er die Adresse hat und unsere Daten so detailliert sind.

Update 2 (Weglassen Fall)

Wenn Benutzer Pearl Street, USA abfragt, so sollten unsere algo der Lage sein, um die Adresse zu finden, da es Pearl Street hat New York als Eltern wissen und USA ist seine Eltern.

Update 3 (Surplus Fall)

Angenommen, der Benutzer-Abfragen für 101 C, Alley A, Pearl Street, New York. Angenommen, unsere Daten kennen 101 C aber nicht über Alley A. Demnach ist 101 C ein unmittelbares Kind von Pearl Street. Auch in diesem Fall sollte es möglich sein, die Adresse zu finden.

Answer 1

Vielen Dank an alle für ihre Antworten, waren ihre Antworten hilfreich, aber ging nicht auf alles, was ich brauchte. Ich fand endlich einen Ansatz, der sich um alle meine Fälle kümmerte. Der Ansatz ist die modifizierte Version dessen, was ich in der Frage vorgeschlagen habe.

Der grundlegende Ansatz

Hier werde ich auf etwas beziehen ‚Knoten‘ genannt, es ist ein Klassenobjekt ist, das die Geoinformationen wie ein Ort Unternehmens Breite enthalten, Längengrad, Dimension vielleicht auch, und seine vollständige Anschrift.

Wenn die Adresse der Entität "101 C, Pearl Street, New York, USA" lautet, bedeutet dies, dass unsere Datenstruktur mindestens vier Knoten für - '101 C', 'Pearl Street', 'New hat York 'und' USA '. Jeder Knoten hat einen name und einen address Teil. Für "101 C" lautet name "101 C" und die Adresse lautet "Pearl Street, New York, USA".

Die Grundidee besteht darin, einen Suchbaum dieser Knoten zu haben, wobei der Knoten name als Schlüssel für die Suche verwendet wird. Wir können mehrere Übereinstimmungen erhalten, daher müssen wir später die Ergebnisse bewerten, wie gut der Knoten address mit dem abgefragten übereinstimmt.

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

Angenommen, wir haben geografische Daten wie oben.Eine Suche nach '101 C, NEW YORK' liefert also nicht nur die '101 C' Knoten in 'NEW YORK', sondern auch die in 'INDIA'. Dies liegt daran, dass der Algorithmus nur die name, d. H. "101 C", zum Durchsuchen der Knoten verwenden wird. Später können wir die Qualität des Ergebnisses bewerten, indem wir die Differenz des Knotens address von der abgefragten Adresse messen. Wir verwenden keine exakte Übereinstimmung, da der Benutzer wie in diesem Fall eine unvollständige Adresse angeben kann.

Grading Sucher

die Qualität des Ergebnisses zu Klasse wir Longest Common Subsequence verwenden können. Die Fälle "Auslassung" und "Überschuss" sind in diesem Algo gut aufgehoben.

Es ist am besten, wenn ich den Code sprechen lasse. Unten ist eine Python-Implementierung, die für diesen Zweck zugeschnitten ist.

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) 

Optimierte Ansatz

ich auf dem oben (unverwässert) Ansatz gerettet, da es Redundanz gezwungen, und es kann nicht die Tatsache nutzen, geschnitten, dass, wenn der Benutzer ‚USA‘ in seiner Anfrage zur Verfügung gestellt hat, dann müssen wir nicht in Knoten in 'INDIA' suchen.

Dieser optimierte Ansatz adressiert beide oben genannten Probleme zu einem beträchtlichen Teil. Die Lösung ist nicht, einen großen Suchbaum zu haben. Wir können den Suchraum in "USA" und "INDIEN" aufteilen. Später können wir diese Suchräume weiter statisch partitionieren. Das nenne ich "schneiden".

Im folgenden Diagramm - SearchSlice stellt eine 'Scheibe' dar und SearchPool stellt einen Suchbaum dar.

      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 

paar wichtige Punkte oben zu bemerken ...

• Jede Scheibe nur eine einzige Ebene tief ist. Nun, das oben nicht wirklich offensichtlich.
• Name der aufgeschnittenen Ebene wird nicht in der Adresse der untergeordneten Elemente angezeigt. Zum Beispiel behält SearchSlice(USA) eine Scheibe von Zuständen in 'USA' bei. Knoten unter 'NEW YORK' enthalten also nicht den Namen 'NEW YORK' oder 'USA' in ihrem address. Gleiches gilt auch für andere Regionen. Die Hierarchiebeziehung definiert implizit die vollständige Adresse.
• '101 C' address enthält die name seines Elternteils auch, da sie nicht geschnitten sind.

Skalierungsmöglichkeiten

Wo gibt es einen Eimer (Pool), gibt es eine implizite Skalierung Möglichkeit. Wir teilen (sagen wir) Geodaten für "USA" in zwei Gruppen ein. Beide können auf verschiedenen Systemen sein. Es ist also völlig in Ordnung, wenn sich der Pool 'NEW YORK' auf System A befindet, aber der Pool 'CALIFORNIA' auf System B ist, da sie keine Daten teilen, außer natürlich für die Eltern.

Hier ist der Vorbehalt. Wir müssen die Eltern kopieren, die immer eine Scheibe sein werden. Da Slices in der Anzahl begrenzt sein sollen, wird die Hierarchie nicht zu tief sein, daher sollte es nicht zu redundant sein, sie zu duplizieren.

Die Arbeits-Code

Bitte beachten Sie meine GitHub für eine working demo Python code.

Answer 2

Wie wäre es mit einer Schlüsselwertspeicherkarte und Volltextsuche?

• Schlüssel für Standort-String
• Wert für location_level und lat & lon Daten.
• Suche nach:
  • Split String Benutzereingaben zu einzelnen Standorten Worte (nicht nur durch Komma)
  • jeweils Worte in der Karte
  • Rückkehr des lat & lon kleinsten Standort Ebene suchen

python.dict, memcached, mongodb .... wird Ihren Bedarf erfüllen.

• wenn u zu viele Lage Worte haben, Split location_level als neue Karte werden zwei Suchanfragen beschleunigen
• vergessen Lage Ebenen, traet wie die Volltextsuche
• riesige Daten? kurze Zeichenfolge oder Zahlen Raute-Taste zu

einige questiongs zu berücksichtigen:

• , wie die Daten in der Datenbank speichern
• , wie Sie Ihren Suchbaum von Daten init, wenn überhaupt
• wie man den Suchbaum in Runtime erweitert/bearbeitet
• fehlertolerant für Eingang/Speicher
• Speicherplatz> Geschwindigkeit? oder Geschwindigkeit> Speicher?

so, mehr nutzbare Testfall für Benutzereingaben

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 

für die Situation:

• Schnellgeschwindigkeit mit riesigen Daten;
• vollständig fehlertolerant;
• einfach justiert mit Speicher- und Laufzeit

die beste Lösung: (komplex est)

• flacher Schlüssel-Wert-Kartenspeicher
• Volltextsuche
  • oder Raute-Taste mit B-Baum-Suche

Ihr Programm/Website kann vielleicht so schnell wie Google laufen.

Answer 3

Wenn Sie versuchen, eine Datenstruktur für dieses Problem zu erstellen, denke ich, dass Sie Datenredundanz haben werden. Stattdessen können Sie mit dem Baum/Graphen & versuchen, einen Suchalgorithmus zu implementieren, der die Wörter aus der Eingabe des Benutzers anhand der Knotenwerte sucht. Fuzzy Abgleich kann Ihnen helfen, die wahrscheinlichsten Ergebnisse zu generieren, und Sie können Benutzer eine Top-paar von ihnen vorschlagen/zeigen, je nach Konfidenzniveau ihrer Ähnlichkeit-zotieren.

Dies kann kümmern falsch geschrieben auch usw.