Как работает геокодер Google?

Мне любопытно, как работает геокодер Google.

Я изучал некоторые реализации геокодеров с открытым исходным кодом, таких как геокодер geocommonsили новый Tiger Geocoder PostGIS. Вот примерно то, что я знаю на данный момент (чтобы доказать, что я выполнял свою домашнюю работу):

Я понимаю, что в основе геокодировщиков с открытым исходным кодом лежат три основных элемента.

1.- нормализатор адресов, который берет произвольную строку и нормализует ее (на примере отсюда):

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 | 

и:

2.- геокодер это делает какое-то волшебное нечеткое сопоставление для имен, где основным алгоритмом является Расстояние Левенштейна.

Хорошим примером является статья из Википедии, где вычисляется расстояние Левенштейна между словами котенок и сидит (расстояние равно 3, поскольку это количество правок, необходимых для замены одной строки на другую):

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

3.- Некоторая интерполяция сегментов улиц в конце, чтобы угадать, где находится дом. Я скачал фрагмент бесплатного набора данных Census Tiger street, чтобы создать этот пример.

В приведенном выше примере интересующий сегмент улицы (Schaeffer Hills Dr) имеет от узла, который начинается с 300 (то есть 300 Schaeffer Hills Dr), и к узлу, который заканчивается на 400 (400 Schaeffer Hills Drv). Если бы я сопоставил этот Schaeffer Hills Drv, а запрос был для улицы 310, то алгоритм просто интерполировал бы его (прошел бы 10% от него) до того места, где находится моя зеленая стрелка.

Это то, что делают инструменты геокодирования с открытым исходным кодом. Тем не менее, Google явно умнее этого и использует всевозможные нетрадиционные подсказки.

Как так?

Например, я могу ввести 680 Mission st(без города, штата, округа, вообще ничего). Большинство стандартных нормализаторов адресов взорвутся, потому что они найдут слишком много совпадений. Но так как я нахожусь в Сан-Франциско, я предполагаю, чтоgoogle использует мой ip, чтобы получить некоторую информацию, похожую на geoip, делает некоторые расширяющиеся границыв качестве подсказки с некоторыми нечеткими поиск, и сразу же находит ближайший соответствующий сегмент и говорит мне, что это мой ответ (что правильно!).

Я ищу ответы, которые могли бы пролить больше света на то, как работает геокодер Google, помимо методов, описанных выше.

Обновление:

Хорошо, на данный момент у нас есть два типа подсказок

• GeoIP в качестве подсказок
• Ограничивающая рамка области интереса (см. пример Пола).
• Другие?