標(biāo)簽
排序?鏈樹(shù)?GIS?POI?關(guān)鍵字?搜索算法
概念闡述
鏈樹(shù)及其相關(guān)概念
本來(lái),數(shù)據(jù)結(jié)構(gòu)教科書(shū)中,不存在一種叫做“鏈樹(shù)”的數(shù)據(jù)結(jié)構(gòu),用Goolge也搜索不到。這種數(shù)據(jù)結(jié)構(gòu),是為了在GIS系統(tǒng)中進(jìn)行POI關(guān)鍵字高速搜索,在n叉樹(shù)的基礎(chǔ)上,改進(jìn)的一種數(shù)據(jù)結(jié)構(gòu),為了論述方便,姑且稱之為鏈樹(shù)。
鏈樹(shù),就是在n叉樹(shù)的基礎(chǔ)上,給每個(gè)樹(shù)節(jié)點(diǎn)(包括樹(shù)根和葉子),都掛接上一個(gè)鏈表而形成的數(shù)據(jù)結(jié)構(gòu)。
下圖就表示一棵典型的鏈樹(shù)

圖1
鏈樹(shù)的2個(gè)顯著特點(diǎn)是:
???1.?某樹(shù)節(jié)點(diǎn)所掛接的鏈表元素,為該樹(shù)節(jié)點(diǎn)的所有子孫節(jié)點(diǎn)(如果有)所掛接的鏈表元素之集合(無(wú)重復(fù)節(jié)點(diǎn))。
???2.?鏈樹(shù)的根結(jié)點(diǎn),可以是一個(gè)虛擬節(jié)點(diǎn),代表系統(tǒng)中所有實(shí)體節(jié)點(diǎn)的祖先。這樣,就不必要形成鏈樹(shù)森林了。圖1的根結(jié)點(diǎn)就是一個(gè)虛擬節(jié)點(diǎn),其余節(jié)點(diǎn)都為實(shí)體節(jié)點(diǎn)。?
排序鏈樹(shù)搜索算法
該算法是指,根據(jù)關(guān)鍵字序列,從鏈樹(shù)根結(jié)點(diǎn)出發(fā),在鏈樹(shù)中路由,最終找到一個(gè)鏈樹(shù)路徑和關(guān)鍵字序列最大匹配的樹(shù)節(jié)點(diǎn),然后取其掛接鏈表的算法。
以圖1所示之排序鏈樹(shù)為例,假定每個(gè)樹(shù)節(jié)點(diǎn)的關(guān)鍵字即為其上的標(biāo)簽字符,假如我們需要搜索的關(guān)鍵字序列為“ACI”,那么該算法的執(zhí)行順序?yàn)椋?br />1.從根結(jié)點(diǎn)出發(fā),查找關(guān)鍵字為‘A’的樹(shù)節(jié)點(diǎn)。
根節(jié)點(diǎn)Root下有2個(gè)孩子,分別為‘A’和‘X’,因?yàn)榕判蜴湗?shù)節(jié)點(diǎn)的所有孩子都按一定規(guī)則排序,所以這一步可以使用二分查找來(lái)進(jìn)行,假定Root有n個(gè)孩子,那么這一步所花時(shí)間為lgn.
2.在‘A’的所有孩子中查找關(guān)鍵字為‘C’的孩子。
同樣用二分查找,假定‘A’有m個(gè)孩子,那么這一步所花時(shí)間為lgm。
3.在‘C’的所有孩子中查找關(guān)鍵字為‘I’的孩子。
同樣使用二分查找,假定‘C’有p個(gè)孩子,那么這一步所花時(shí)間為lgp
綜上,關(guān)鍵字序列為“ACI”的搜索時(shí)間為lgn+lgm+lgp。
根據(jù)鏈樹(shù)的特點(diǎn),有n>=k>=p,所以搜索長(zhǎng)度為3的關(guān)鍵字序列的時(shí)間復(fù)雜度為O(3lgn),推而廣之,我們得到更一般的排序鏈樹(shù)搜索算法復(fù)雜度:
假如關(guān)鍵字序列長(zhǎng)度為k,系統(tǒng)中總的實(shí)體節(jié)點(diǎn)個(gè)數(shù)為n,那么在排序鏈樹(shù)搜索算法的時(shí)間復(fù)雜度為O(klgn)。
關(guān)于POI
在GIS系統(tǒng)中,對(duì)于地圖上的一個(gè)具有詳細(xì)信息的點(diǎn),我們稱之為POI(Point?Of?Interest)。比如名稱為“北京西單圖書(shū)大廈”的POI,就包含了該地點(diǎn)的一系列詳細(xì)信息,這些信息通常有:
???1.該P(yáng)OI的名稱,這里是“西單圖書(shū)大廈”
???2.該P(yáng)OI的經(jīng)緯度
???3.該P(yáng)OI的地址
???4.該P(yáng)OI的類型
???5.該P(yáng)OI的描述信息
???6.該P(yáng)OI的電話號(hào)碼
???7.該P(yáng)OI的網(wǎng)址
???8.該P(yáng)OI的照片
???9.該P(yáng)OI的音頻,視頻
???…...
通常,一個(gè)城市中,就存在千百萬(wàn)個(gè)這樣的POI。其數(shù)據(jù)量是相當(dāng)?shù)木薮蟆?br />
關(guān)于POI的關(guān)鍵字搜索
在GIS相關(guān)應(yīng)用中,都會(huì)提供一種最基本的功能,就是根據(jù)用戶輸入的關(guān)鍵字,搜索到和該關(guān)鍵字相關(guān)的一系列POI,按照和用戶輸入字串匹配度由高到底的順序,把這些POI呈現(xiàn)給用戶。因?yàn)橛脩糨斎氲年P(guān)鍵字,可能和該P(yáng)OI的名稱相關(guān),也可能和該P(yáng)OI的地址,類型名稱,描述信息,網(wǎng)址等字段相關(guān)。理論上,只要POI的某個(gè)字段,或者某幾個(gè)字段的組合,和用戶輸入的關(guān)鍵字有關(guān)系,那么,這個(gè)POI就應(yīng)該出現(xiàn)在搜索結(jié)果列表的合適位置上。
比如用戶輸入的關(guān)鍵字為“北大”,那么搜索出來(lái)的POI可能有:
??北大荒(名字中包含’北’,‘大’,且這2個(gè)字連在一起)
??北京大學(xué)(名字中包含’北’,‘大’,這2個(gè)關(guān)鍵字被隔開(kāi)了,稱之為跳字)
??北京郵電大學(xué)(名字中包含’北’,‘大’,跳字)
??大北窯(名字中包含‘北’,‘大’,但這2個(gè)關(guān)鍵字被顛倒了,稱之為逆字)
??未名湖(地址中含有‘北‘,‘大’二字)
??……
當(dāng)然按照我們一般的思路,北京大學(xué)應(yīng)該排在第一位,因?yàn)橐话銇?lái)說(shuō),北大指的就是它。所以GIS系統(tǒng)要求在本次搜索中,北京大學(xué)應(yīng)該排在第一位。
為了簡(jiǎn)化問(wèn)題,本文只限于對(duì)POI的名稱這一字段進(jìn)行關(guān)鍵字搜索。也就是說(shuō),只把名稱字段和用戶輸入字串有關(guān)聯(lián)的POI搜索出來(lái)。
如何在POI關(guān)鍵字搜索中應(yīng)用鏈樹(shù)搜索算法
如何在POI關(guān)鍵字搜索應(yīng)用鏈樹(shù)呢,我們舉例來(lái)說(shuō)。假定某城市中存在5個(gè)POI,其名稱分別是:
??北京大學(xué)
??北京郵電大學(xué)
??大北窯
??未名湖
??北大荒
那么我們首先要做的工作就是建立排序鏈樹(shù),然后再依據(jù)排序鏈樹(shù),進(jìn)行關(guān)鍵字搜索。
建立排序鏈樹(shù)
建立排序鏈樹(shù)的工作分成以下幾步來(lái)做。
??1.分別給每個(gè)POI編號(hào),指定其ID,如下
???????北京大學(xué)(1)
???????北京郵電大學(xué)(2)
???????大北窯(3)
???????未名湖(4)
???????北大荒(5)
每個(gè)POI的詳細(xì)信息,可以存在一個(gè)二進(jìn)制文件(raw?data)中,然后再建立一個(gè)索引文件,該文件包括5個(gè)索引條目,每個(gè)條目為一個(gè)POI在raw?data文件中的偏移量(offset)與長(zhǎng)度(size),該P(yáng)OI的索引條目序號(hào)(index),即為該P(yáng)OI的ID,這樣,根據(jù)該P(yáng)OI的ID,查詢索引文件,可以得到其在raw?data中的offset和size,進(jìn)而獲取其詳細(xì)信息。
??2.建立一個(gè)虛擬節(jié)點(diǎn)Root,作為排序鏈樹(shù)之根,把所有POI的ID鏈表掛接在Root上,這些ID按以空字符為關(guān)鍵字進(jìn)行POI查詢的呈現(xiàn)結(jié)果為序。

圖2
可以看到,如果以空字符進(jìn)行POI關(guān)鍵字查詢,輸出結(jié)果順序?yàn)?br />??????北大荒
??????北京大學(xué)
??????北京郵電大學(xué)
??????大北窯
??????未名湖
很明顯,這是按拼音排序的。
??3.找出該城市所有POI名稱中涉及到的字符集合。
在我們的例子中,這個(gè)集合包括為:{‘北’,‘大’,‘荒’,‘京’,‘學(xué)’,‘郵’,‘電’,‘窯’,‘未’,‘名’,‘湖’},共11個(gè)漢字。把該集合中的元素按字符的UNICODE編碼大小排序,我們姑且假定排序后的順序不變。
??4.把字符集合中的每一個(gè)字符都作為一個(gè)樹(shù)節(jié)點(diǎn)之關(guān)鍵字,并且讓該樹(shù)節(jié)點(diǎn)成為Root之子。如下圖

圖3
接下來(lái),我們要以每個(gè)孩子為根,建立一顆子鏈樹(shù),為了論述方便,本文只講述以‘北’字為樹(shù)根的這棵子鏈樹(shù),其他子鏈樹(shù),可以依此類推。
??5.對(duì)于圖3中每個(gè)子節(jié)點(diǎn),掛接上一個(gè)ID鏈表,這些ID所代表的POI的名稱中,都包含了該樹(shù)節(jié)點(diǎn)所對(duì)應(yīng)的字符。而且這些ID按照以該字符為關(guān)鍵字進(jìn)行POI查詢的呈現(xiàn)結(jié)果順序?yàn)樾颉@纭薄中纬傻逆湵砣缦?

圖4
之所以掛接鏈表是5,1,2,3,是因?yàn)槲覀冊(cè)谝浴薄诌M(jìn)行POI關(guān)鍵字查詢時(shí),GIS系統(tǒng)要求我們的輸出POI的列表順序必須是:北大荒,北京大學(xué),北京郵電大學(xué),大北窯這個(gè)順序。
??6.對(duì)于每一個(gè)根節(jié)點(diǎn),構(gòu)建其子節(jié)點(diǎn)列表。構(gòu)建規(guī)則為
???a.子節(jié)點(diǎn)所代表字符,能和其父節(jié)點(diǎn)所代表字符,出現(xiàn)在同一個(gè)POI的名稱中。
???b.子節(jié)點(diǎn)列表,按其所代表字符的UNICODE大小排序。
比如‘北’字,其子節(jié)點(diǎn)列表為:

圖5
在這里,我們假定這幾個(gè)字的UNICODE排序結(jié)果如上圖所示。?
大家可以看到,11個(gè)字符中,基本上所有字符都能和‘北’字組合,除了‘未’,‘名’,‘湖’這3個(gè)字符和‘北’字本身,當(dāng)然,如果有個(gè)POI叫“北北?”,那么‘北’字也會(huì)成為其本身的子節(jié)點(diǎn)。但是有一點(diǎn)是,父子節(jié)點(diǎn)的關(guān)鍵字可以相同,但是兄弟節(jié)點(diǎn)的關(guān)鍵字絕對(duì)不相同,他們是互斥的.
??7.結(jié)合父節(jié)點(diǎn)和每個(gè)子節(jié)點(diǎn),形成每個(gè)子節(jié)點(diǎn)所掛接的ID鏈表。構(gòu)建規(guī)則為:
??該ID鏈表所代表的POI列表,即為用戶以鏈樹(shù)路徑作為關(guān)鍵字,查詢出來(lái)的POI結(jié)果列表。
比如對(duì)于根為‘北’字的鏈樹(shù),到這一步的結(jié)果為:

圖6
大家可以看到,對(duì)于路徑“北大”,所掛接的ID鏈表為1,5,2,3,也就是
????????北京大學(xué)
????????北大荒
????????北京郵電大學(xué)
????????大北窯
這個(gè)順序,也就是GIS系統(tǒng)所要求的輸出順序。
??8.按照以上規(guī)律,繼續(xù)為第二層節(jié)點(diǎn)添加子節(jié)點(diǎn)。形成的高度為3的鏈樹(shù)如下圖所示

圖7
從上圖可以看到,顏色為紅色的鏈樹(shù)節(jié)點(diǎn)已經(jīng)到達(dá)葉子,無(wú)法再向下伸展了。?
??9.依此類推,還可以繼續(xù)向下擴(kuò)展鏈樹(shù)。最終的鏈樹(shù)深度為6,對(duì)應(yīng)著名稱最長(zhǎng)的POI節(jié)點(diǎn),也就是“北京郵電大學(xué)”,由于篇幅所限,就不再給出圖示了。
至此,我們的排序鏈樹(shù)已經(jīng)建好了。關(guān)于鏈樹(shù)的建立,還有幾個(gè)地方要說(shuō)明一下:
????a.關(guān)于ID鏈表的排序
ID鏈表的順序,需要我們的POI數(shù)據(jù)處理程序按照一定的規(guī)則來(lái)實(shí)現(xiàn),除了通用的一些規(guī)則外,還有些特定的簡(jiǎn)稱數(shù)據(jù)要處理,比如“北大”所對(duì)應(yīng)的POI列表,第一條通常應(yīng)該是“北京大學(xué)”,而不是“北大荒”。??
????b.關(guān)于排序鏈樹(shù)的存儲(chǔ)
為了加快搜索速度,排序鏈樹(shù)森林中的冗余數(shù)據(jù)很多,所以實(shí)現(xiàn)者應(yīng)該認(rèn)真考慮文件存儲(chǔ)格式,以便節(jié)約存儲(chǔ)空間。?
根據(jù)排序鏈樹(shù),按關(guān)鍵字搜索POI
建立了排序鏈樹(shù)之后,我們就可以按排序鏈樹(shù)搜索算法,來(lái)進(jìn)行POI關(guān)鍵字查詢了。例如用戶如果輸入的關(guān)鍵字為“北大”2字,先從Root根節(jié)點(diǎn)出發(fā),根據(jù)關(guān)鍵字序列,逐級(jí)向下路由,得到查詢結(jié)果1,5,2,3。然后根據(jù)這些POI?ID,從raw?data文件中檢索出詳細(xì)信息即可。因?yàn)椴捎昧伺判蜴湗?shù)搜索算法,對(duì)于長(zhǎng)度為k的關(guān)鍵字,在POI總量為n的情況下,POI關(guān)鍵字查詢的時(shí)間復(fù)雜度為:
????????T?=?O(klgn)
比一般的時(shí)間復(fù)雜度為O(kn)的GIS?POI關(guān)鍵字搜索算法,搜索速度有了較大的提升。
算法優(yōu)劣分析
綜上分析可知,采用排序鏈樹(shù)搜索算法進(jìn)行POI關(guān)鍵字查詢,其優(yōu)勢(shì)在于:
????*?搜索時(shí)間少,時(shí)間復(fù)雜度為O(klgn)
????*?可以讓用戶邊輸入,邊路由,邊搜索,實(shí)現(xiàn)實(shí)時(shí)搜索的功能,對(duì)于采用ajax效果的Web?GIS來(lái)說(shuō),猶為合適。
????*?此算法對(duì)通配符支持友好,比如用戶輸入的關(guān)鍵字串為“北大*”或者“北?荒”,此算法都能夠比較容易的適應(yīng)。
其主要劣勢(shì)在于其ID鏈表的數(shù)據(jù)冗余度較大,而且建樹(shù)過(guò)程比較復(fù)雜,對(duì)POI數(shù)據(jù)處理程序的要求比較高。但是因?yàn)檫@些工作都在Server端完成,在目前多核,巨量?jī)?nèi)存,集群的server端硬件條件下,應(yīng)該都不是大問(wèn)題。
作者信息
Jagie,軟件開(kāi)發(fā)愛(ài)好者,可以通過(guò)chen_cwf@163.com與他聯(lián)系。本文來(lái)自于Jagie的google?page:http://chencwf.googlepages.com/linktree