Come funziona il geocoder di Google?

Question

Sono curioso di sapere come funziona il geocoder di Google.

Ho studiato alcune implementazioni di geocoder open source come geocommons' geocoder o PostGIS's new Tiger Geocoder. Questo è più o meno quello che so finora (per sperare di dimostrare che ho fatto i compiti):

Mi rendo conto che al centro dei geocoder open source ci sono tre elementi principali.

1.- indirizzo normalizzatore che prende una stringa arbitraria e normalizza esso (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 | 

e:

2.- geocoder che fa un po 'di corrispondenza fuzzy magica per i nomi dove l'algoritmo principale è il Levenshtein Distance.

Un buon esempio è quello dall'articolo Wikipedia cui calcola la distanza Levenshtein tra parole gattino e seduta (la distanza è 3 dato che questo è il numero di modifiche necessarie per modificare una stringa nell'altra):

kitten → sitten (substitution of 's' for 'k') 
sitten → sittin (substitution of 'i' for 'e') 
sittin → sitting (insertion of 'g' at the end). 

3.- Qualche interpolazione dei segmenti stradali alla fine per indovinare dove si trova la casa. Ho scaricato un blocco del numero gratuito Census Tiger street dataset per creare questo esempio.

Nell'esempio precedente, il segmento strada di interesse (Schaeffer Hills Dr) presenta una dal nodo che inizia a 300 (così 300 Schaeffer Hills Dr) e un al nodo che termina sulla 400 (400 Schaeffer Hills Drv). Se corrispondevo a questo Schaeffer Hills Drv, e la richiesta era per la strada 310, allora l'algoritmo sarebbe solo interpolate ad esso (attraversa il 10% di esso) dove si trova la mia freccia verde.

Questo è ciò che fanno gli strumenti di geocoder Open Source. Tuttavia, Google è chiaramente più intelligente e utilizza tutti i tipi di suggerimenti non tradizionali.

Come mai?

Ad esempio, è possibile digitare 680 Mission st (nessuna città, stato, contea, niente). La maggior parte dei normalizzatori di indirizzi standard esploderebbero perché troverebbero troppe corrispondenze. Ma dal momento che sono in SF, sono indovinando google utilizza il mio ip per ottenere geoip-like information, fa some expanding bounding come suggerimento con una ricerca fuzzy, e subito trova il segmento più vicino che corrisponde e mi dice che è la mia risposta (che è corretta !).

Sto cercando risposte che possano far luce su come il geocoder di Google funziona oltre alle tecniche che ho descritto sopra.

Aggiornamento:

OK, finora abbiamo due tipi di suggerimenti elencati

• geoip come suggerimenti
• Area di interesse rettangolo di selezione (si veda l'esempio di Paolo).
• Altri?

Answer 1

Una delle cose che si possono trovare spaccando la scatola nera è che il geocoder di Google non è totalmente sensibile all'ordine dei token (non ci sono aspettative di strada/città/stato/paese forzate, anche se funziona meglio quando lo segui). Il che mi dice che potrebbero scaricare tutto in una sorta di ricerca a testo integrale e poi vedere cosa ritorna. O forse no. Prova a cercare "sault saint marie adams 200" e "sault saint marie 200 adams".

Per quanto riguarda il vostro esempio missione, che è un grande, come si può vedere la mappa suggerimento che entrano in gioco direttamente:

query con mappa finestra sull'Europa: Risultati europei

Query con finestra mappa il Nord America: i risultati americani

Answer 2

C'è un'altra fonte di dati: mappe di proprietà della contea. Questi non includono solo le strade, ma anche le linee di proprietà (e i loro indirizzi). Puoi spesso vederlo sulla mappa di Google, in realtà mostrerà deboli linee che separano le proprietà adiacenti. A volte hanno anche delineato edifici (le mappe di contea spesso includono anche questi).

Puoi anche eseguire la ricerca inversa, dato che le coordinate GPS per trovare il tuo indirizzo esatto possono essere semplici come una query 2D per trovare il poligono di proprietà in cui ti trovi. Ho visto questo funziona correttamente quando ero fisicamente lontano dalla strada ma ancora all'interno della proprietà e ha restituito l'indirizzo corretto, nonostante il portatile fosse più vicino a un'altra strada.

Si noti che queste mappe tendono ad essere pubbliche e alcune contee hanno persino una propria interfaccia online. Puoi anche cercare chi possiede una trama particolare.