Wie funktioniert der Google Geocoder?

Question

Ich bin neugierig, wie der Google Geocoder funktioniert.

Ich habe einige Implementierungen von Open-Source-Geocoder wie geocommons' geocoder oder PostGIS's new Tiger Geocoder untersucht. Das ist ungefähr das, was ich bisher weiß (um zu beweisen, dass ich meine Hausaufgaben gemacht habe):

Ich weiß, dass im Kern der Open-Source-Geocoder drei Hauptelemente existieren.

1.- Ein Adresse Normalisierer, die eine beliebige Zeichenkette nimmt und normalisiert sie (taking the example from here):

normalize_address('address string'); 

e.g.: SELECT naddy.* FROM normalize_address('29645 7th Street SW Federal Way 98023') AS naddy; 

address | predirabbrev |  streetname  | streettypeabbrev | postdirabbrev | internal | location | stateabbrev | zip | parsed 
---------+-------------+-----------------------+------------------+---------------+----------+----------+-------------+-------+-------- 
29645 |    | 7th Street SW Federal | Way    |    |   |   |    | 98023 | 

und:

2.- Ein geocoder, die für Namen einige magische Fuzzy Matching tut wo der Kernalgorithmus der Levenshtein Distance ist.

Ein gutes Beispiel dafür ist der von dem Wikipedia-Artikel, in dem es den Levenshtein Abstand zwischen den Worten Kätzchen berechnet und sitzt (der Abstand ist 3, da die Anzahl der Änderungen erforderlich ist eine Zeichenkette in die andere zu wechseln):

3.- Einige Interpolation der Straßensegmente am Ende zu raten, wo das Haus ist. Ich habe einen Teil der kostenlosen Census Tiger street dataset heruntergeladen, um dieses Beispiel zu erstellen.

In dem obigen Beispiel weist das Straßensegment von Interesse (Schaeffer Hills Dr) ein von Knoten, die (so 300 Schaeffer Hills Dr) und ein bei 300 beginnen Knoten, der endet am 400 (400 Schaeffer Hills Drv). Wenn ich diesen Schaeffer Hills Drv anpasse, und die Anfrage für die Straße 310 wäre, dann würde der Algorithmus nur interpolate (10% davon überschreiten) dorthin, wo mein grüner Pfeil ist.

Dies ist, was die Open Source Geocoder-Tools tun. Nichtsdestoweniger ist Google deutlich schlauer und verwendet alle Arten von nicht-traditionellen Hinweisen.

Wie so?

Zum Beispiel kann ich 680 Mission st eingeben (keine Stadt, Bundesland, Landkreis, irgendetwas überhaupt). Die meisten Standardadressnormalisierer würden in die Luft gehen, weil sie zu viele Übereinstimmungen finden würden. Aber da ich in SF bin, bin ich Erraten google verwendet meine IP, um einige geoip-like information zu bekommen, tut some expanding bounding als Hinweis mit einer unscharfen Suche, und findet sofort das nächste Segment, das übereinstimmt und sagt mir, das ist meine Antwort (das ist richtig !).

Ich bin auf der Suche nach Antworten, die mehr Licht in die Funktionsweise des Google Geocoders neben den oben beschriebenen Techniken bringen.

Update:

OK, so weit haben wir zwei Arten von Hinweisen

aufgeführt

• Geoip als Hinweise
• Area of ​​Interest Bounding Box (Paul siehe Beispiel).
• Andere?

Answer 1

Eines der Dinge, die Sie durch Stochern in der Black Box finden können, ist, dass der Google Geocoder nicht völlig empfindlich auf die Reihenfolge der Token reagiert (es gibt keine erzwungene Straße/Stadt/Staat/Land Erwartung, obwohl es besser geht wenn du dem folgst). Was mir sagt, dass sie alles in eine Art Volltextsuche stecken und dann sehen, was zurückkommt. Oder vielleicht nicht. Versuchen Sie "sault saint marie adams 200" und "sault saint marie 200 adams" zu suchen.

Im Hinblick auf Ihre Mission Beispiel, das ist ein großer, wie Sie die Karte Hinweis direkt ins Spiel kommen sehen:

Abfrage mit Kartenfenster über Europa: Europäische Ergebnisse

Abfrage mit Kartenfenster über Nordamerika: amerikanische Ergebnisse

Answer 2

Es gibt eine weitere Datenquelle: Landkarten. Dazu gehören nicht nur Straßen, sondern auch Grundstücksgrenzen (und ihre Straßenadressen). Sie können dies oft auf der Google-Karte sehen, es werden tatsächlich schwache Linien angezeigt, die angrenzende Eigenschaften trennen. Manchmal skizzieren sie sogar Gebäude (Landkarten enthalten diese oft auch).

Sie können auch die umgekehrte Suche durchführen, vorausgesetzt, Ihre GPS-Koordinaten finden Ihre genaue Adresse kann so einfach wie eine 2D-Abfrage zu finden, welche Eigenschaft Polygon Sie sind. Ich habe gesehen, funktioniert das richtig, wenn ich körperlich weit war von der Straße, aber immer noch innerhalb des Grundstücks und es gab die richtige Adresse, obwohl das Mobilteil näher an einer anderen Straße.

Beachten Sie, dass diese Karten öffentlich sind und einige Grafschaften sogar ihre eigene Online-Schnittstelle haben. Sie können sogar nachschauen, wem ein bestimmtes Grundstück gehört.