如何設計實現一個地址反解析服務？

http://www.cnblogs.com/LBSer/p/4507829.html

一、什么是地址反解析

? ? ? ?我們都知道手機定位服務，其本質是匯總各種信號得出一個經緯度坐標（x,y）（具體定位原理可以參考：LBS定位技術、基于樸素貝葉斯的定位算法），然而定位服務并未提供該坐標對應的實體地理信息，比如街道、POI等，要知道這些信息就需要使用地址反解析服務，該服務就是由經緯度信息得到結構化地址信息（圖1）。

圖1 地址反解析

? ? ? 例如lat:30.252188,?lng:120.120427，地址反解析得到的結果如表1所示。

?

表1 地址反解析得到的結果

{data: {province: "杭州市",city: "杭州",district: "西湖區",detail: "靈隱路-靈溪南路",lat: 30.252188,lng: 120.120427}
}

?　　

二、基本思路

? ? ? 一般現有的地圖服務公司如高德、google、百度等都會提供地址反解析服務，當大家業務規模較小時可以選擇調用他們提供的接口，但是如果業務規模較大時，再去直接調用顯然不太合適。大家需要有自己的實現能力！

　　實現地址反解析服務有矢量和柵格兩種思路。

1）矢量思路

? ? ? 高德、google、百度等地圖服務公司有自己的地圖數據，包括矢量數據（比如點、線、面等幾何數據）以及矢量對應的屬性信息（比如某線對應的屬性是“北京朝陽望京東路”），因此他們的地址反解析思路很直接，直接根據經緯度查找附近的矢量數據（POI、道路等數據），比如查找到一條道路，然后返回道路對應的屬性信息即可（圖2）。具體實現思路與地理圍欄算法解析（Geo-fencing）一文相似。

圖2 矢量思路示意圖

?? ? ?

　　這種方式的優點是數據存儲量較小。缺點是要求有詳細的地圖矢量數據以及對應的屬性數據，而對一般公司來說很難獲得。

? ? ? 盡管我們可以通過開源的openstreetmap拿到中國的矢量地圖數據（如何獲取、存儲、管理、使用osm數據呢？可以參考：利用OpenStreetMap（OSM）數據搭建一個地圖服務），但是openstreetmap中國地區的矢量地圖數據很不詳細，精度也較低，完全依賴于openstreetmap的地圖數據來進行地址反解析還不太靠譜。

?2）柵格思路

? ? ? ?什么是柵格思路？如圖3a所示，比如將北京劃分成很多柵格（也稱之為瓦片），當柵格比較精細時，比如為10米*10米時，我們可以假設一個柵格內部的地址是相同的。這種假設是合理的，如圖3b虛線框柵格內的兩點所示，盡管該兩點經緯度坐標不同，但是其地址均為“中國北京市朝陽區北苑路”。基于上述假設，我們可以事先存儲各個柵格對應的地址信息。每當一個用戶請求過來，首先判斷該用戶經緯度所對應的柵格，然后將此柵格對應的地址信息返回即可。 ? ??

? ? ?柵格思路的優點是很簡單很直觀，缺點是數據量大。以北京為例，北京全市面積為?16,410.54平方千米，如果柵格大小為10米*10米，那么需要存儲1.6億個柵格對應的地址信息，如果放大到全國（約960萬平方千米），數據量將更大。

?圖3 柵格思路示意圖

三、方案設計

? ? ? ?在沒有矢量數據的情況下一般應用可以采用柵格思路，因為簡單直觀易于上手，后期如果找到完備的矢量數據則可以借鑒矢量思路。

1）如何降低柵格方案的數據存儲量？

? ? ? ?柵格方案最大的缺點是存儲量巨大，如何降低柵格方案的數據存儲量呢？我們有兩種思路。

? ? ? ?a）有效柵格方案。前面講到如果柵格為10米*10米時，僅北京就會有1.6億個柵格。但是我們知道一般應用的用戶基本是在城區進行訪問，鮮有用戶會在山溝溝里使用大家的服務，因此這1.6億個柵格有大部分是不會有被訪問到的（某柵格被訪問到是指用戶請求的經緯度落在該柵格范圍內），我們將被用戶訪問到的柵格稱之為有效柵格。事實上我們無需存儲所有柵格對應的地址信息，而僅需存儲有效柵格對應的地址信息即可實現我們的地址反解析服務，從而大大降低數據存儲量。如圖4所示，黃色柵格代表是有用戶訪問到的柵格，即有效柵格，有效柵格數目<<全部柵格數目。

圖4 有效柵格方案（紅點代表用戶請求的經緯度，黃色柵格代表有效柵格）

?

? ? ? ?b）自適應粒度柵格方案。之前柵格粒度是不變的，比如都是10米*10米，由于大部分柵格用戶不會訪問到，這樣較為浪費存儲空間。我們可以采用四叉樹對地理空間進行劃分（圖5），每次劃分都對空間進行四等分，直到劃分出的柵格內沒有用戶請求點或者柵格的粒度<=10米*10米為止。在用戶訪問密集區域，柵格的粒度較為精細，精度較高，在鮮有用戶訪問區域，柵格粒度較粗，地址反解析的結果也較粗，可以發現：自適應粒度柵格數目<<均等粒度柵格數目。

圖5 自適應粒度柵格方案

?

? ? ? ? ?從本質上講有效柵格方案是key-value的存儲結構，存儲簡單方便，并且更新也很簡便，非常適合大數據環境。而自適應粒度柵格方案本質上是樹存儲結構（四叉樹），涉及到樹結構的節點分裂等操作，在大數據環境下實現邏輯較為復雜。簡便起見我們采用有效柵格方案。

2）數據存儲方式？

? ? ? ?有效柵格方案本質是key-value的存儲方式。1）這里的key指的是柵格的編號，一個用戶請求過來，首先根據用戶請求的經緯度判斷其所在的柵格編號（key），然后查找該編號（key）對應的地址信息。柵格的編號方式有很多，可以采用geohash編碼來進行編號（關于geohash可以查看GeoHash核心原理解析、Geohash距離估算），一般來講，geohash編碼長度為8位時，其代表著20米*20米的柵格。2）value值指的是該柵格的中心點對應的地址信息。

? ? ?此外還需存儲該記錄的時間戳，以便我們知道數據的新舊，方便更新（表2）。

?

? ? 表2 數據存儲結構

3）實現流程?

? ? ? ?地址反解析服務實現流程分為預處理以及線上服務兩個步驟（參見圖6）。

a）預處理

? ? ? 1）利用已有用戶的定位/地址反解析請求日志來確定有效柵格

? ? ? ? ? ? 用戶定位/地址反解析請求會攜帶有經緯度信息，可以計算該經緯度對應的geohash編碼（key），并查詢數據庫，如果沒有該key則進行插入，數據量較大時可以使用mapreduce進行處理，最后將數據寫入Hbase以便線上實時查詢；

? ? ? 2）獲取各個有效柵格對應的地址信息

? ? ? ? ? ? 獲取每個有效柵格對應的經緯度，去請求地圖服務商google、baidu、高德、搜狗等的地址反解析服務接口，獲得相應結構化地址信息并進行插入。

? ? ? ?上述兩個步驟也可以合二為一，確定了有效柵格后即可請求地圖服務商接口，并將geohash編碼、結構化地址信息和時間戳信息插入到數據庫中。

b）線上服務

? ? ? 對一個用戶請求，首先得到經緯度，通過geohash對該經緯度編碼，從而查找數據庫，如果找到便直接返回，如果沒找到或離上次更新時間與現在間隔超過一個月（具體時間可以動態設置）之內，則請求第三方地址反解析接口，并將更新任務放在任務隊列里實現異步更新。

圖6 柵格思路的地址反解析方案?