來源：http://t.cn/EbMSD2A

geohash-feature

當(dāng)今年代，每個(gè)人都有智能手機(jī)，出門在外，自然離不開使用手機(jī)地圖了，查找附近的餐館，附近的地鐵站，非常方便，可是在這項(xiàng)技術(shù)背后又隱藏著什么算法呢？這篇博客將會(huì)講述這個(gè)技術(shù)背后的GeoHash算法以及基本的實(shí)現(xiàn)。

首先既然算法名字叫做GeoHash了那么對(duì)單詞比較敏感的人可能已經(jīng)猜出來了，差不多就是對(duì)當(dāng)前的位置生成一個(gè)Hash值，然后再比較相似吧，是的，大概就是這個(gè)樣子。

GeoHash的原理就是講一個(gè)地理位置的經(jīng)緯度，轉(zhuǎn)換成一個(gè)可以排序，可以比較的的Hash字符串。這個(gè)字符串。

GeoHash代表的不是一個(gè)精確地的標(biāo)，而是一個(gè)區(qū)域，當(dāng)Hash值越長(zhǎng)的時(shí)候，這個(gè)hash代表的區(qū)域越小，就越精確，比如 wtw3eegq 這個(gè)Hash就是上海南京西路周圍的的一塊，但是 只有前6位 wtw3ee 的話這個(gè)Hash代表的區(qū)域面積就比 wtw3eegq要大，但是 wtw3eegq 是包擴(kuò)在 wtw3ee 這個(gè)區(qū)域里面的，所以可以用這個(gè)特性來查找一個(gè)坐標(biāo)周圍的餐館之類的地方。

GeoHash就是這樣，他將地球首先分為四個(gè)象限，之后每一象限再平分為四個(gè)象限，就是這樣無限細(xì)分下去，這樣，地球就根據(jù)坐標(biāo)分為了若干區(qū)域，每個(gè)區(qū)域都會(huì)根據(jù)算法來生成一個(gè)Hash值，Hash值越相似就代表兩個(gè)區(qū)域的位置越近。

ProximityChat

?

接下來將會(huì)討論這個(gè)算法的具體細(xì)節(jié)：

• 計(jì)算緯度

比如我們需要計(jì)算 坐標(biāo) 121.443469, 31.22246 的GeoHash值

首先將緯度范圍(-90, 90)平分成兩個(gè)區(qū)間(-90,0)、(0, 90)，如果目標(biāo)緯度位于前一個(gè)區(qū)間，則編碼為0，否則編碼為1。

由于31.22246屬于(0, 90)，所以取編碼為1。

然后再將(0, 90)分成 (0, 45), (45, 90)兩個(gè)區(qū)間，而31.22246位于(0, 45)，所以編碼為0。

就和中學(xué)時(shí)代學(xué)過的二分法解方程一樣簡(jiǎn)單，對(duì)吧~

以此類推，直到精度符合要求為止，得到編碼為1010 1100 0110 0111 1100 ，下面的表只是計(jì)算了前8位，可以看出，二分次數(shù)越多，取得的值就越精確。

leftmidrightbit

-90	0	90	1
0	22.5	45	0
22.5	33.75	45	1
22.5	30	37.5	0
30	33.75	37.5	1
30	31.875	33.75	1
30	30.9375	31.875	0
30.9375	31.40625	31.875	0

接下來看經(jīng)度

• 計(jì)算經(jīng)度

首先將經(jīng)度范圍(-180, 180)平分成兩個(gè)區(qū)間(-180,0)、(0, 180)，如果目標(biāo)經(jīng)度位于前一個(gè)區(qū)間，則編碼為0，否則編碼為1。

由于121.443469屬于(0, 180)，所以取編碼為1。

然后再將(0, 180)分成 (0, 90), (90, 180)兩個(gè)區(qū)間，而121.443469位于(90, 180)，所以編碼為1。

以此類推，直到精度符合要求為止，得到經(jīng)度編碼為1101 0110 0101 1100 0001 ，下面的表只是計(jì)算了前8位。

leftmidrightbit

-180	0	180	1
0	90	180	1
90	135	180	0
90	112.5	135	1
112.5	123.75	135	0
112.5	118.125	123.75	1
118.125	120.9375	123.75	1
120.9575	122.35375	123.75	0

• 經(jīng)度緯度合并

接下來將經(jīng)度和緯度的編碼合并，奇數(shù)位是緯度，偶數(shù)位是經(jīng)度

10101100011001111100 和 11010110010111000001 合并為：
1110011001111000001101101011010101010010

• Base32編碼轉(zhuǎn)換

得到合并后的編碼之后，每5位一看，轉(zhuǎn)換為十進(jìn)制，之后按照Base32的編碼表來轉(zhuǎn)換為Base32編碼

Decimal01234567

Base32	0	1	2	3	4	5	6	7
Decimal	8	9	10	11	12	13	14	15
Base32	8	9	b	c	d	e	f	g
Decimal	16	17	18	19	20	21	22	23
Base32	h	j	k	m	n	p	q	r
Decimal	24	25	26	27	28	29	30	31
Base32	s	t	u	v	w	x	y	z

剛才合并的編碼為：1110011001111000001101101011010101010010

將他分為11100、11001、11100、00011、01101、01101、01010、10010

十進(jìn)制為：28, 25, 28, 3, 13, 13, 10, 18

根據(jù)編碼表轉(zhuǎn)換后的Base32編碼值為?wtw3eebk

這個(gè)值：wtw3eebk?就是坐標(biāo)121.443469, 31.22246?的GeoHash值

這樣的話只要在坐標(biāo)入庫(kù)的時(shí)候程序順便算出坐標(biāo)的GeoHash值一并入庫(kù)，就可以實(shí)現(xiàn)快速進(jìn)行周邊餐館查找之類的功能了。

• 測(cè)試

為了看一下這個(gè)算法的可行性，我寫了一個(gè)爬蟲來訪問高德地圖來不斷檢索地址并且算出Geohash（文章最后會(huì)給出整個(gè)爬蟲和算法的代碼）

posi

我生成的GeoHash是8位的，通過匹配前6位：wtw3ef，來進(jìn)行查找，匹配出了下面的餐館

熱辣壹號(hào)(淮海中路百盛店)
淮海中路918號(hào)百盛商場(chǎng)8層
121.459133,31.217455
wtw3efgy

伊秀壽司(淮海店)
淮海中路918號(hào)淮海百盛8層(久事復(fù)興大廈)
121.459291,31.217210
wtw3efgv

丸龜制面(淮海百盛店)
淮海中路918號(hào)百盛購(gòu)物中心B1樓13鋪(近陜西南路)
121.459274,31.217533
wtw3efgz

查厘士港式餐廳(淮海中路黃金店)
淮海中路988黃金世界3層
121.458316,31.216696
wtw3efg4

九久日本料理(淮海店)
淮海中路939號(hào)巴黎春天百貨5樓(地鐵1號(hào)線陜西南路站)
121.459520,31.216730
wtw3efu4

通過地址可以看出來這幾個(gè)餐館都是位于淮海中路上的。

和高德地圖檢索周邊出來的餐館差不多：

下面是GeoHash的精度表：

GeoHash長(zhǎng)度Lat位數(shù)Lng位數(shù)Lat誤差Lng誤差km誤差

1	2	3	±23	±23	±2500
2	5	5	± 2.8	±5.6	±630
3	7	8	± 0.70	± 0.7	±78
4	10	10	± 0.087	± 0.18	±20
5	12	13	± 0.022	± 0.022	±2.4
6	15	15	± 0.0027	± 0.0055	±0.61
7	17	18	±0.00068	±0.00068	±0.076
8	20	20	±0.000086	±0.000172	±0.01911
9	22	23	±0.000021	±0.000021	±0.00478
10	25	25	±0.00000268	±0.00000536	±0.0005971
11	27	28	±0.00000067	±0.00000067	±0.0001492
12	30	30	±0.00000008	±0.00000017	±0.0000186

Github鏈接

這個(gè)項(xiàng)目中有我寫的爬蟲，查詢類和Geohash，Base32相關(guān)類

爬蟲讀取后存為txt，之后查詢的時(shí)候讀取txt作為臨時(shí)數(shù)據(jù)庫(kù)

nearbyfinder

?

總結(jié)

以上是生活随笔為你收集整理的周围的餐馆有哪些？GeoHash算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。