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 ähnlich wie Nominatatim .
Also könnten die möglichen Ein- und Ausgänge sein: -
In 6 oben wurde New York zurückgegeben, da kein Ort mit der Adresse 103 Alkazam, New York, USA gefunden wurde, aber es konnte zumindest New York, USA finden.
Zuerst dachte ich daran, einen Baum zu erstellen, der die Hierarchiebeziehung darstellt, in der die Geschwister alphabetisch sortiert sind. Es hätte sein können wie: -
%Vor%Aber das Problem war, dass Benutzer unvollständige Adresse wie in 2, 4 und 5 bereitstellen kann.
Als nächstes dachte ich, einen Suchbaum zu verwenden und die voll qualifizierte Adresse in jedem Knoten zu speichern. Aber das ist auch ziemlich schlimm seit: -
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.
Update 1
Eine kleine 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 ein Gebäude finden können, wenn er die Adresse hat und unsere Daten so detailliert sind.
Update 2 (Abwesenheitsfall)
Wenn der Benutzer Pearl Street, USA abfragt, sollte unser Algo die Adresse finden können, da er weiß, dass Pearl Street New York als übergeordnetes Element hat und USA als übergeordnetes Element.
Update 3 (Überschüssiger Fall)
Angenommen, der Benutzer fragt nach 101 C, Alley A, Pearl Street, New York . Angenommen, unsere Daten kennen 101 C , nicht aber Alley A . Demnach ist 101 C ein unmittelbares Kind von Pearl Street . Auch in diesem Fall sollte es in der Lage sein, die Adresse zu lokalisieren.
Danke an alle für ihre Antworten, ihre Antworten waren hilfreich, aber nicht alles, was ich brauchte. Ich fand endlich einen Ansatz, der sich um alle meine Fälle kümmerte. Der Ansatz ist die modifizierte Version von dem, was ich in der Frage vorgeschlagen habe.
Hier werde ich auf etwas namens 'node' verweisen, es ist ein Klassenobjekt, das die Geo-Informationen wie den Breiten- und Längengrad einer geografischen Einheit, vielleicht auch die Dimension und ihre vollständige Adresse enthält.
Wenn die Adresse des Unternehmens "101 C, Pearl Street, New York, USA" lautet, bedeutet dies, dass unsere Datenstruktur mindestens vier Knoten für "101 C", "Pearl Street", "New York" aufweist "und" USA ". Jeder Knoten hat einen name und einen address Teil. Für '101 C' wird name '101 C' und die Adresse wird 'Pearl Street, New York, USA' sein.
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 address des Knotens mit dem abgefragten übereinstimmt.
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 verwendet. 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.
Um die Qualität des Ergebnisses zu bewerten, können wir Longest Common Subsequence verwenden. Die Fälle "Auslassung" und "Überschuss" werden in diesem Algo gut behandelt.
Es ist am besten, wenn ich den Code sprechen lasse. Unten ist eine Python-Implementierung für diesen Zweck zugeschnitten.
%Vor%Ich habe den obigen (grundlegenden) Ansatz ausgehebelt, da er Redundanz erzwang, und es konnte die Tatsache nicht aushebeln, dass, wenn der Benutzer 'USA' in seiner Abfrage angegeben hat, wir nicht in Knoten in 'INDIA' suchen müssen / p>
Dieser optimierte Ansatz spricht die oben genannten Probleme weitgehend an. 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 "Slicen".
Im unteren Diagramm - SearchSlice repräsentiert ein 'Segment' und SearchPool repräsentiert einen Suchbaum.
Einige wichtige Punkte, die Sie noch bemerken sollten ...
SearchSlice(USA) eine Schicht von Zuständen in 'USA' bei. So enthalten Knoten unter 'NEW YORK' in ihrem address nicht den Namen 'NEW YORK' oder 'USA'. Gleiches gilt auch für andere Regionen. Die Hierarchiebeziehung definiert implizit die vollständige Adresse. address enthält auch die name der Eltern, da sie nicht in Scheiben geschnitten sind. Wo es einen Bucket (Pool) gibt, gibt es eine implizite Skalierungsmöglichkeit. Wir teilen (sagen wir) Geodaten für "USA" in zwei Gruppen ein. Beide können auf verschiedenen Systemen sein. Also, es ist völlig in Ordnung, wenn 'NEW YORK' Pool auf System A ist, aber 'CALIFORNIA' Pool ist auf System B, da sie keine Daten teilen, außer für die Eltern natürlich.
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.
Bitte lesen Sie meinen GitHub für einen funktionierenden Demo-Python-Code .
Wie wäre es mit einer Schlüsselwert-Speicherzuordnung und einer Volltextsuche?
python.dict, memcached, mongodb .... werden Ihren Anforderungen entsprechen.
einige zu beachtende Fragen:
also, mehr verwendbarer Testfall für Benutzereingaben
%Vor%
für die Situation :
die beste Lösung :( auch komplexest)
Ihr Programm / Ihre Website kann vielleicht so schnell wie Google laufen.
Wenn Sie versuchen, eine Datenstruktur für dieses Problem zu erstellen, werden Sie eine Datenredundanz haben. Eher können Sie Baum / Grafik & amp; Versuchen Sie, einen Suchalgorithmus zu implementieren, der die Wörter aus der Eingabe des Benutzers anhand der Knotenwerte sucht. Das Fuzzy -Matching kann Ihnen dabei helfen, die wahrscheinlichsten Ergebnisse zu erzielen, und Sie können dem Benutzer einige Top-Keywords vorschlagen, je nach Konfidenzniveau des Ähnlichkeits-Zitats.
Dies kann auch für Fehlschreibfehler etc. sorgen.
Tags und Links python openstreetmap large-data geocoding large-data-volumes