小嘰導(dǎo)讀：閑魚是一款閑置物品的交易平臺(tái)APP,。通過這個(gè)平臺(tái),，全國各地“無處安放”的物品能夠輕松實(shí)現(xiàn)流動(dòng)。這種分享經(jīng)濟(jì)業(yè)務(wù)形態(tài)被越來越多的人所接受,，也進(jìn)一步實(shí)現(xiàn)了低碳生活的目標(biāo),。

今天，閑魚團(tuán)隊(duì)就商品與商圈的匹配算法為我們展開詳細(xì)解讀,。

摘要

閑魚app根據(jù)交通條件,、商場分布情況、住宅區(qū)分布情況綜合考慮,，將城市劃分為一個(gè)個(gè)商圈,。杭州部分區(qū)域商圈劃分如下圖所示。

閑魚的商品是由用戶發(fā)布的GPS隨機(jī)分布在地圖上的點(diǎn)數(shù)據(jù)。當(dāng)用戶處于某個(gè)商圈范圍內(nèi)時(shí),，app會(huì)向用戶推薦GPS位于此商圈中的商品,。要實(shí)現(xiàn)精準(zhǔn)推薦服務(wù)，就需要計(jì)算出哪些商品是歸屬于你所處的商圈,。

在數(shù)據(jù)庫中,，商圈是由多個(gè)點(diǎn)圍成的面數(shù)據(jù)，這些面數(shù)據(jù)形狀,、大小各異,，且互不重疊。商品是以GPS標(biāo)記的點(diǎn)數(shù)據(jù),，如何能夠快速高效地確定海量商品與商圈的歸屬關(guān)系呢,？傳統(tǒng)而直接的方法是，利用幾何學(xué)的空間關(guān)系計(jì)算公式對海量數(shù)據(jù)實(shí)施直接的“點(diǎn)—面”關(guān)系計(jì)算,，來確定每一個(gè)商品是否位于每一個(gè)商圈內(nèi)部,。

閑魚目前有10億商品數(shù)據(jù)，且每天還在快速增加,。全國所有城市的商圈數(shù)量總和大約為1萬,，每個(gè)商圈的大小不一，邊數(shù)從10到80不等,。如果直接使用幾何學(xué)點(diǎn)面關(guān)系運(yùn)算,，需要的計(jì)算量級約為2億億次基本運(yùn)算。按照這個(gè)思路,，我們嘗試過使用阿里巴巴集團(tuán)內(nèi)部的離線計(jì)算集群來執(zhí)行計(jì)算,，結(jié)果集群在運(yùn)行了超過2天之后也未能給出結(jié)果,。

經(jīng)過算法改進(jìn)，我們采用了一種基于GeoHash精確匹配,，結(jié)合GeoHash非精確匹配并配合小范圍幾何學(xué)關(guān)系運(yùn)算精匹配的算法,，大大降低了計(jì)算量，高效地實(shí)現(xiàn)了離線環(huán)境下海量點(diǎn)-面數(shù)據(jù)的包含關(guān)系計(jì)算,。同樣是對10億條商品和1萬條商圈數(shù)據(jù)做匹配，可以在1天內(nèi)得到結(jié)果,。

▌點(diǎn)數(shù)據(jù)GeoHash原理與算法

GeoHash是一種對地理坐標(biāo)進(jìn)行編碼的方法,，它將二維坐標(biāo)映射為一個(gè)字符串。每個(gè)字符串代表一個(gè)特定的矩形,，在該矩形范圍內(nèi)的所有坐標(biāo)都共用這個(gè)字符串,。字符串越長精度越高，對應(yīng)的矩形范圍越小,。

對一個(gè)地理坐標(biāo)編碼時(shí),，按照初始區(qū)間范圍緯度[-90,90]和經(jīng)度[-180,180]，計(jì)算目標(biāo)經(jīng)度和緯度分別落在左區(qū)間還是右區(qū)間,。落在左區(qū)間則取0,，右區(qū)間則取1。然后,，對上一步得到的區(qū)間繼續(xù)按照此方法對半查找,，得到下一位二進(jìn)制編碼。當(dāng)編碼長度達(dá)到業(yè)務(wù)的進(jìn)度需求后,，根據(jù)“偶數(shù)位放經(jīng)度,，奇數(shù)位放緯度”的規(guī)則，將得到的二進(jìn)制編碼穿插組合,，得到一個(gè)新的二進(jìn)制串,。最后，根據(jù)base32的對照表,，將二進(jìn)制串翻譯成字符串,，即得到地理坐標(biāo)對應(yīng)的目標(biāo)GeoHash字符串。

以坐標(biāo)“30.280245, 120.027162”為例,，計(jì)算其GeoHash字符串,。首先對緯度做二進(jìn)制編碼：

將[-90,90]平分為2部分，“30.280245”落在右區(qū)間(0,90],，則第一位取1,。

將(0,90]平分為2分，“30.280245”落在左區(qū)間(0,45],，則第二位取0,。

不斷重復(fù)以上步驟,，得到的目標(biāo)區(qū)間會(huì)越來越小，區(qū)間的兩個(gè)端點(diǎn)也越來越逼近“30.280245”,。

下圖的流程詳細(xì)地描述了前幾次迭代的過程：

按照上面的流程,，繼續(xù)往下迭代,，直到編碼位數(shù)達(dá)到我們業(yè)務(wù)對精度的需求為止。完整的15位二進(jìn)制編碼迭代表格如下：

得到的緯度二進(jìn)制編碼為10101 01100 01000。

按照同樣的流程,，對經(jīng)度做二進(jìn)制編碼,，具體迭代詳情如下：

得到的經(jīng)度二進(jìn)制編碼為11010 10101 01101,。

按照“偶數(shù)位放經(jīng)度，奇數(shù)位放緯度”的規(guī)則,，將經(jīng)緯度的二進(jìn)制編碼穿插,，得到完成的二進(jìn)制編碼為：11100 11001 10011 10010 00111 00010。由于后續(xù)要使用的是base32編碼,，每5個(gè)二進(jìn)制數(shù)對應(yīng)一個(gè)32進(jìn)制數(shù),，所以這里將每5個(gè)二進(jìn)制位轉(zhuǎn)換成十進(jìn)制位，得到28,25,19,18,7,2,。 對照base32編碼表,，得到對應(yīng)的編碼為：wtmk72。

可以在geohash.org/網(wǎng)站對上述結(jié)果進(jìn)行驗(yàn)證，驗(yàn)證結(jié)果如下：

驗(yàn)證結(jié)果的前幾位與我們的計(jì)算結(jié)果一致。如果我們利用二分法獲取二進(jìn)制編碼時(shí)迭代更多次,，就會(huì)得到驗(yàn)證網(wǎng)站中這樣的位數(shù)更多的更精確結(jié)果,。

GeoHash字符串的長度與精度的對應(yīng)關(guān)系如下：

**▌面數(shù)據(jù)GeoHash編碼實(shí)現(xiàn)

**

上一節(jié)介紹的標(biāo)準(zhǔn)GeoHash算法只能用來計(jì)算二維點(diǎn)坐標(biāo)對應(yīng)的GeoHash編碼,，我們的場景中還需要計(jì)算面數(shù)據(jù)（即GIS中的POLYGON多邊形對象）對應(yīng)的GeoHash編碼，需要擴(kuò)展算法來實(shí)現(xiàn),。

算法思路是,，先找到目標(biāo)Polygon的最小外接矩形MBR,，計(jì)算此MBR西南角坐標(biāo)對應(yīng)的GeoHash編碼。然后用GeoHash編碼的逆算法,，反解出此編碼對應(yīng)的矩形GeoHash塊,。以此GeoHash塊為起點(diǎn)，循環(huán)往東,、往北找相鄰的同等大小的GeoHash塊,，直到找到的GeoHash塊完全超出MBR的范圍才停止。如此找到的多個(gè)GeoHash塊,，邊緣上的部分可能與目標(biāo)Polygon完全不相交,，這部分塊需要通過計(jì)算剔除掉，如此一來可以減少后續(xù)不必要的計(jì)算量,。

上面的例子中最終得到的結(jié)果高清大圖如下,，其中藍(lán)色的GeoHash塊是與原始Polygon部分相交的，橘黃色的GeoHash塊是完全被包含在原始Polygon內(nèi)部的,。

上述算法總結(jié)成流程圖如下：

▌求臨近GeoHash塊的快速算法

上一節(jié)對面數(shù)據(jù)進(jìn)行GeoHash編碼的流程圖中標(biāo)記為綠色和橘黃色的兩步，分別是要尋找相鄰的東邊或北邊的GeoHash字符串,。

傳統(tǒng)的做法是,，根據(jù)當(dāng)前GeoHash塊的反解信息，求出相鄰塊內(nèi)部的一點(diǎn),，在對這個(gè)點(diǎn)做GeoHash編碼,，即為相鄰塊的GeoHash編碼。如下圖,，我們要計(jì)算"wtmk72"周圍的8個(gè)相鄰塊的編碼,，就要先利用GeoHash逆算法將"wtmk72"反解出4個(gè)頂點(diǎn)的坐標(biāo)N1、N2,、N3,、N4,，然后由這4個(gè)坐標(biāo)計(jì)算出右側(cè)鄰接塊內(nèi)部的任意一點(diǎn)坐標(biāo)N5,，再對N5做GeoHash編碼，得到的“wtmk78”就是我們要求的右邊鄰接塊的編碼,。按照同樣的方法,，求可以求出"wtmk72"周圍總共8個(gè)鄰接塊的編碼,。

這種方法需要先解碼一次再編碼一次,，比較耗時(shí),，尤其是在指定的GeoHash字符串長度較長需要循環(huán)較多次的情況下。

通過觀察GeoHash編碼表的規(guī)律,，結(jié)合GeoHash編碼使用的Z階曲線的特性,，驗(yàn)證了一種通過查表來快速求相鄰GeoHash字符串的方法。

還是以“wtmk72”這個(gè)GeoHash字符串為例,，對應(yīng)的10進(jìn)制數(shù)是“28,，25，19,，18,，7，2”,，轉(zhuǎn)換成二進(jìn)制就是11100 11001 10011 10010 00111 00010,。其中，w對應(yīng)11100,，這5個(gè)二進(jìn)制位分別代表“經(jīng) 緯 經(jīng) 緯 經(jīng)”,；t對應(yīng)11001，這5個(gè)二進(jìn)制位分別代表“緯 經(jīng) 緯 經(jīng) 緯”,。由此推廣開來可知,，GeoHash中的奇數(shù)位字符（本例中的'w'、'm',、'7'）代表的二進(jìn)制位分別對應(yīng)“經(jīng) 緯 經(jīng) 緯 經(jīng)”,，偶數(shù)位字符（本例中的't'、'k',、'2'）代表的二進(jìn)制位分別對應(yīng)“緯 經(jīng) 緯 經(jīng) 緯”,。

'w'的二進(jìn)制11100，轉(zhuǎn)換成方位含義就是“右 上 右 下 左”,。't'的二進(jìn)制11001,，轉(zhuǎn)換成方位含義就是“上 右 下 左 上”。

根據(jù)這個(gè)字符與方位的轉(zhuǎn)換關(guān)系,，我們可以知道,，奇數(shù)位上的字符與位置對照表如下：

偶數(shù)位上的字符與位置對照表如下：

這里可以看到一個(gè)很有意思的現(xiàn)象，奇數(shù)位的對照表和偶數(shù)位對照表存在一種轉(zhuǎn)置和翻轉(zhuǎn)的關(guān)系,。

有了以上兩份字符與位置對照表,，就可以快速得出每個(gè)字符周圍的8個(gè)字符分別是什么。而要計(jì)算一個(gè)給定GeoHash字符串周圍8個(gè)GeoHash值,，如果字符串最后一位字符在該方向上未超出邊界,，則前面幾位保持不變，最后一位取此方向上的相鄰字符即可,；如果最后一位在此方向上超出了對照表邊界,，則先求倒數(shù)第二個(gè)字符在此方向上的相鄰字符，再求最后一個(gè)字符在此方向上相鄰字符（對照表環(huán)狀相鄰字符）,；如果倒數(shù)第二位在此方向上的相鄰字符也超出了對照表邊界,，則先求倒數(shù)第三位在此方向上的相鄰字符。以此類推,。

以上面的“wtmk72”舉例,，要求這個(gè)GeoHash字符串的8個(gè)相鄰字符串，實(shí)際就是求尾部字符‘2’的相鄰字符,?！?’適用偶數(shù)對照表，它的8個(gè)相鄰字符分別是‘1’,、‘3’,、‘9’,、‘0’,、‘8’、‘p’,、‘r’,、‘x’，其中‘p’,、‘r’,、‘x’已經(jīng)超出了對照表的下邊界，是將偶數(shù)位對照表上下相接組成環(huán)狀得到的相鄰關(guān)系,。所以,，對于這3個(gè)超出邊界的“下方”相鄰字符，需要求倒數(shù)第二位的下方相鄰字符,，即‘7’的下方相鄰字符,。‘7’是奇數(shù)位,，適用奇數(shù)位對照表,，‘7’在對照表中的“下方”相鄰字符是‘5’，所以“wtmk72”的8個(gè)相鄰GeoHash字符串分別是“wtmk71”,、“wtmk73”,、“wtmk79”,、“wtmk70”、“wtmk78”,、“wtmk5p”,、“wtmk5r”、“wtmk5x”,。利用此相鄰字符串快速算法,，可以大大提高上一節(jié)流程圖中面數(shù)據(jù)GeoHash編碼算法的效率。

▌高效建立海量點(diǎn)數(shù)據(jù)與面數(shù)據(jù)的關(guān)系

建立海量點(diǎn)數(shù)據(jù)與面數(shù)據(jù)的關(guān)系的思路是,，先將需要匹配的商品GPS數(shù)據(jù)（點(diǎn)數(shù)據(jù)）,、商圈AOI數(shù)據(jù)（面數(shù)據(jù)）按照前面所述的算法，分別計(jì)算同等長度的GeoHash編碼,。每個(gè)點(diǎn)數(shù)據(jù)都對應(yīng)唯一一個(gè)GeoHash字符串,；每個(gè)面數(shù)據(jù)都對應(yīng)一個(gè)或多個(gè)GeoHash編碼，這些編碼要么是“完全包含字符串”,，要么是“部分包含字符串”,。

a)將每個(gè)商品的GeoHash字符串與商圈的“完全包含字符串”進(jìn)行join操作。join得到的結(jié)果中出現(xiàn)的<商品,商圈>數(shù)據(jù)就是能夠確定的“某個(gè)商品屬于某個(gè)商圈”的關(guān)系,。

b)對于剩下的還未被確定關(guān)系的商品,，將這些商品的GeoHash字符串與商圈的“部分包含字符串”進(jìn)行join操作。join得到的結(jié)果中出現(xiàn)的<商品,商圈>數(shù)據(jù)是有可能存在的“商品屬于某個(gè)商圈”的關(guān)系,，接下來對這批數(shù)據(jù)中的商品gps和商圈AOI數(shù)據(jù)進(jìn)行幾何學(xué)關(guān)系運(yùn)算,，進(jìn)而從中篩選出確定的“商品屬于某個(gè)商圈”的關(guān)系。

如圖,，商品1的點(diǎn)數(shù)據(jù)GeoHash編碼為"wtmk70j",，與面數(shù)據(jù)的“完全包含字符串wtmk70j”join成功，所以可以直接確定商品1屬于此面數(shù)據(jù),。

商品2的點(diǎn)數(shù)據(jù)GeoHash編碼為“wtmk70r”,，與面數(shù)據(jù)的“部分包含字符串wtmk70r”join成功，所以商品2疑似屬于面數(shù)據(jù),，具體是否存在包含關(guān)系,，還需要后續(xù)的點(diǎn)面幾何學(xué)計(jì)算來確定。 商品3的點(diǎn)數(shù)據(jù)GeoHash編碼與面數(shù)據(jù)的任何GeoHash塊編碼都匹配不上,，所以可以快速確定商品3不屬于此面數(shù)據(jù),。

實(shí)際應(yīng)用中,，原始的海量商品GPS范圍散布在全國各地，海量商圈數(shù)據(jù)也散布在全國各個(gè)不同的城市。經(jīng)過a)步驟的操作后,，大部分的商品數(shù)據(jù)已經(jīng)確定了與商圈的從屬關(guān)系,。剩下的未能匹配上的商品數(shù)據(jù)，經(jīng)過b)步驟的GeoHash匹配后,，可以將后續(xù)“商品-商圈幾何學(xué)計(jì)算”的運(yùn)算量從“1個(gè)商品 x 全國所有商圈”笛卡爾積的量級,，降低為“1個(gè)商品 x 1個(gè)（或幾個(gè)）商圈”笛卡爾積的量級，減少了絕大部分不必要的幾何學(xué)運(yùn)算,，而這部分運(yùn)算是非常耗時(shí)的,。

在閑魚的實(shí)際應(yīng)用中，10億商品和1萬商圈數(shù)據(jù),，使用本文的快速算法,，只需要 10億次GeoHash點(diǎn)編碼 + 1萬次GeoHash面編碼 + 500萬次“點(diǎn)是否在面內(nèi)部”幾何學(xué)運(yùn)算，粗略換算為基本運(yùn)算需要的次數(shù)約為1800億次,，運(yùn)算量遠(yuǎn)小于傳統(tǒng)方法的2億億次基本運(yùn)算,。使用阿里巴巴的離線計(jì)算平臺(tái)，本文的算法在不到一天的時(shí)間內(nèi)就完成了全部計(jì)算工作,。

另外,，對于給定的點(diǎn)和多邊形，通過幾何學(xué)計(jì)算包含關(guān)系的算法不止一種,，最常用的算法是射線法,。簡單來說，就是從這個(gè)點(diǎn)出發(fā)做一條射線,，判斷該射線與多邊形的交點(diǎn)個(gè)數(shù)是奇數(shù)還是偶數(shù),。如果是奇數(shù)，說明點(diǎn)在多邊形內(nèi),；否則,，點(diǎn)在多邊形外,。

▌延伸

面對海量點(diǎn)面數(shù)據(jù)的空間關(guān)系劃分,，本文采用是的通過GeoHash來降低計(jì)算量的思路，本質(zhì)上來說是利用了空間索引的思想,。事實(shí)上,，在GIS領(lǐng)域有多種實(shí)用的空間索引，常見的如R樹系列（R樹,、R+樹,、R*樹）、四叉樹,、K-D樹,、網(wǎng)格索引等，這些索引算法各有特點(diǎn)。本文的思路不僅能用來處理點(diǎn)—面關(guān)系的相關(guān)問題,，還可以用來快速處理點(diǎn)—點(diǎn)關(guān)系,、面—面關(guān)系、點(diǎn)—線關(guān)系,、線—線關(guān)系等問題,，比如快速確定大范圍類的海量公交站臺(tái)與道路的從屬關(guān)系、多條道路或鐵路是否存在交點(diǎn)等問題,。

本文作者：峰明