標簽
排序?鏈樹?GIS?POI?關(guān)鍵字?搜索算法
概念闡述
鏈樹及其相關(guān)概念
本來，數(shù)據(jù)結(jié)構(gòu)教科書中，不存在一種叫做“鏈樹”的數(shù)據(jù)結(jié)構(gòu)，用Goolge也搜索不到。這種數(shù)據(jù)結(jié)構(gòu)，是為了在GIS系統(tǒng)中進行POI關(guān)鍵字高速搜索，在n叉樹的基礎(chǔ)上，改進的一種數(shù)據(jù)結(jié)構(gòu)，為了論述方便，姑且稱之為鏈樹。
鏈樹，就是在n叉樹的基礎(chǔ)上，給每個樹節(jié)點(包括樹根和葉子)，都掛接上一個鏈表而形成的數(shù)據(jù)結(jié)構(gòu)。
下圖就表示一棵典型的鏈樹
圖1
鏈樹的2個顯著特點是：
???1.?某樹節(jié)點所掛接的鏈表元素，為該樹節(jié)點的所有子孫節(jié)點(如果有)所掛接的鏈表元素之集合(無重復節(jié)點)。
???2.?鏈樹的根結(jié)點，可以是一個虛擬節(jié)點，代表系統(tǒng)中所有實體節(jié)點的祖先。這樣，就不必要形成鏈樹森林了。圖1的根結(jié)點就是一個虛擬節(jié)點，其余節(jié)點都為實體節(jié)點。?
排序鏈樹搜索算法
該算法是指，根據(jù)關(guān)鍵字序列，從鏈樹根結(jié)點出發(fā)，在鏈樹中路由，最終找到一個鏈樹路徑和關(guān)鍵字序列最大匹配的樹節(jié)點，然后取其掛接鏈表的算法。
以圖1所示之排序鏈樹為例，假定每個樹節(jié)點的關(guān)鍵字即為其上的標簽字符，假如我們需要搜索的關(guān)鍵字序列為“ACI”,那么該算法的執(zhí)行順序為：
1.從根結(jié)點出發(fā)，查找關(guān)鍵字為‘A’的樹節(jié)點。
根節(jié)點Root下有2個孩子，分別為‘A’和‘X’，因為排序鏈樹節(jié)點的所有孩子都按一定規(guī)則排序，所以這一步可以使用二分查找來進行，假定Root有n個孩子，那么這一步所花時間為lgn.
2.在‘A’的所有孩子中查找關(guān)鍵字為‘C’的孩子。
同樣用二分查找，假定‘A’有m個孩子，那么這一步所花時間為lgm。
3.在‘C’的所有孩子中查找關(guān)鍵字為‘I’的孩子。
同樣使用二分查找，假定‘C’有p個孩子，那么這一步所花時間為lgp
綜上，關(guān)鍵字序列為“ACI”的搜索時間為lgn+lgm+lgp。
根據(jù)鏈樹的特點，有n>=k>=p，所以搜索長度為3的關(guān)鍵字序列的時間復雜度為O(3lgn)，推而廣之，我們得到更一般的排序鏈樹搜索算法復雜度:
假如關(guān)鍵字序列長度為k，系統(tǒng)中總的實體節(jié)點個數(shù)為n,那么在排序鏈樹搜索算法的時間復雜度為O(klgn)。
關(guān)于POI
在GIS系統(tǒng)中，對于地圖上的一個具有詳細信息的點，我們稱之為POI（Point?Of?Interest）。比如名稱為“北京西單圖書大廈”的POI,就包含了該地點的一系列詳細信息，這些信息通常有:
???1.該POI的名稱，這里是“西單圖書大廈”
???2.該POI的經(jīng)緯度
???3.該POI的地址
???4.該POI的類型
???5.該POI的描述信息
???6.該POI的電話號碼
???7.該POI的網(wǎng)址
???8.該POI的照片
???9.該POI的音頻，視頻
???…...
通常，一個城市中，就存在千百萬個這樣的POI。其數(shù)據(jù)量是相當?shù)木薮蟆?br />
關(guān)于POI的關(guān)鍵字搜索
在GIS相關(guān)應用中，都會提供一種最基本的功能，就是根據(jù)用戶輸入的關(guān)鍵字，搜索到和該關(guān)鍵字相關(guān)的一系列POI，按照和用戶輸入字串匹配度由高到底的順序，把這些POI呈現(xiàn)給用戶。因為用戶輸入的關(guān)鍵字，可能和該POI的名稱相關(guān)，也可能和該POI的地址，類型名稱，描述信息，網(wǎng)址等字段相關(guān)。理論上，只要POI的某個字段，或者某幾個字段的組合，和用戶輸入的關(guān)鍵字有關(guān)系，那么，這個POI就應該出現(xiàn)在搜索結(jié)果列表的合適位置上。
比如用戶輸入的關(guān)鍵字為“北大”，那么搜索出來的POI可能有:
??北大荒(名字中包含’北’，‘大’，且這2個字連在一起)
??北京大學(名字中包含’北’，‘大’，這2個關(guān)鍵字被隔開了，稱之為跳字)
??北京郵電大學(名字中包含’北’，‘大’，跳字)
??大北窯(名字中包含‘北’,‘大’，但這2個關(guān)鍵字被顛倒了，稱之為逆字)
??未名湖(地址中含有‘北‘，‘大’二字)
??……
當然按照我們一般的思路，北京大學應該排在第一位，因為一般來說，北大指的就是它。所以GIS系統(tǒng)要求在本次搜索中，北京大學應該排在第一位。
為了簡化問題，本文只限于對POI的名稱這一字段進行關(guān)鍵字搜索。也就是說，只把名稱字段和用戶輸入字串有關(guān)聯(lián)的POI搜索出來。
如何在POI關(guān)鍵字搜索中應用鏈樹搜索算法
如何在POI關(guān)鍵字搜索應用鏈樹呢，我們舉例來說。假定某城市中存在5個POI,其名稱分別是:
??北京大學
??北京郵電大學
??大北窯
??未名湖
??北大荒
那么我們首先要做的工作就是建立排序鏈樹，然后再依據(jù)排序鏈樹，進行關(guān)鍵字搜索。
建立排序鏈樹
建立排序鏈樹的工作分成以下幾步來做。
??1.分別給每個POI編號,指定其ID，如下
???????北京大學(1)
???????北京郵電大學(2)
???????大北窯(3)
???????未名湖(4)
???????北大荒(5)
每個POI的詳細信息，可以存在一個二進制文件(raw?data)中，然后再建立一個索引文件，該文件包括5個索引條目，每個條目為一個POI在raw?data文件中的偏移量(offset)與長度(size),該POI的索引條目序號(index)，即為該POI的ID，這樣，根據(jù)該POI的ID,查詢索引文件，可以得到其在raw?data中的offset和size,進而獲取其詳細信息。
??2.建立一個虛擬節(jié)點Root,作為排序鏈樹之根，把所有POI的ID鏈表掛接在Root上，這些ID按以空字符為關(guān)鍵字進行POI查詢的呈現(xiàn)結(jié)果為序。
圖2
可以看到，如果以空字符進行POI關(guān)鍵字查詢，輸出結(jié)果順序為
??????北大荒
??????北京大學
??????北京郵電大學
??????大北窯
??????未名湖
很明顯，這是按拼音排序的。
??3.找出該城市所有POI名稱中涉及到的字符集合。
在我們的例子中，這個集合包括為:{‘北’，‘大’，‘荒’，‘京’，‘學’，‘郵’，‘電’，‘窯’，‘未’，‘名’，‘湖’},共11個漢字。把該集合中的元素按字符的UNICODE編碼大小排序，我們姑且假定排序后的順序不變。
??4.把字符集合中的每一個字符都作為一個樹節(jié)點之關(guān)鍵字，并且讓該樹節(jié)點成為Root之子。如下圖
圖3
接下來，我們要以每個孩子為根，建立一顆子鏈樹，為了論述方便，本文只講述以‘北’字為樹根的這棵子鏈樹，其他子鏈樹，可以依此類推。
??5.對于圖3中每個子節(jié)點，掛接上一個ID鏈表，這些ID所代表的POI的名稱中，都包含了該樹節(jié)點所對應的字符。而且這些ID按照以該字符為關(guān)鍵字進行POI查詢的呈現(xiàn)結(jié)果順序為序。例如‘北’字形成的鏈表如下:
圖4
之所以掛接鏈表是5，1，2，3，是因為我們在以‘北’字進行POI關(guān)鍵字查詢時，GIS系統(tǒng)要求我們的輸出POI的列表順序必須是:北大荒，北京大學，北京郵電大學，大北窯這個順序。
??6.對于每一個根節(jié)點，構(gòu)建其子節(jié)點列表。構(gòu)建規(guī)則為
???a.子節(jié)點所代表字符，能和其父節(jié)點所代表字符，出現(xiàn)在同一個POI的名稱中。
???b.子節(jié)點列表，按其所代表字符的UNICODE大小排序。
比如‘北’字，其子節(jié)點列表為:
圖5
在這里，我們假定這幾個字的UNICODE排序結(jié)果如上圖所示。?
大家可以看到，11個字符中，基本上所有字符都能和‘北’字組合，除了‘未’，‘名’，‘湖’這3個字符和‘北’字本身，當然，如果有個POI叫“北北?”，那么‘北’字也會成為其本身的子節(jié)點。但是有一點是，父子節(jié)點的關(guān)鍵字可以相同，但是兄弟節(jié)點的關(guān)鍵字絕對不相同，他們是互斥的.
??7.結(jié)合父節(jié)點和每個子節(jié)點，形成每個子節(jié)點所掛接的ID鏈表。構(gòu)建規(guī)則為：
??該ID鏈表所代表的POI列表，即為用戶以鏈樹路徑作為關(guān)鍵字，查詢出來的POI結(jié)果列表。
比如對于根為‘北’字的鏈樹，到這一步的結(jié)果為:
圖6
大家可以看到，對于路徑“北大”，所掛接的ID鏈表為1，5，2，3，也就是
????????北京大學
????????北大荒
????????北京郵電大學
????????大北窯
這個順序，也就是GIS系統(tǒng)所要求的輸出順序。
??8.按照以上規(guī)律，繼續(xù)為第二層節(jié)點添加子節(jié)點。形成的高度為3的鏈樹如下圖所示
圖7
從上圖可以看到，顏色為紅色的鏈樹節(jié)點已經(jīng)到達葉子，無法再向下伸展了。?
??9.依此類推，還可以繼續(xù)向下擴展鏈樹。最終的鏈樹深度為6,對應著名稱最長的POI節(jié)點，也就是“北京郵電大學”，由于篇幅所限，就不再給出圖示了。
至此，我們的排序鏈樹已經(jīng)建好了。關(guān)于鏈樹的建立，還有幾個地方要說明一下:
????a.關(guān)于ID鏈表的排序
ID鏈表的順序，需要我們的POI數(shù)據(jù)處理程序按照一定的規(guī)則來實現(xiàn)，除了通用的一些規(guī)則外，還有些特定的簡稱數(shù)據(jù)要處理，比如“北大”所對應的POI列表，第一條通常應該是“北京大學”，而不是“北大荒”。??
????b.關(guān)于排序鏈樹的存儲
為了加快搜索速度，排序鏈樹森林中的冗余數(shù)據(jù)很多，所以實現(xiàn)者應該認真考慮文件存儲格式，以便節(jié)約存儲空間。?
根據(jù)排序鏈樹，按關(guān)鍵字搜索POI
建立了排序鏈樹之后，我們就可以按排序鏈樹搜索算法，來進行POI關(guān)鍵字查詢了。例如用戶如果輸入的關(guān)鍵字為“北大”2字，先從Root根節(jié)點出發(fā)，根據(jù)關(guān)鍵字序列，逐級向下路由，得到查詢結(jié)果1,5,2,3。然后根據(jù)這些POI?ID,從raw?data文件中檢索出詳細信息即可。因為采用了排序鏈樹搜索算法，對于長度為k的關(guān)鍵字，在POI總量為n的情況下，POI關(guān)鍵字查詢的時間復雜度為:
????????T?=?O(klgn)
比一般的時間復雜度為O(kn)的GIS?POI關(guān)鍵字搜索算法，搜索速度有了較大的提升。
算法優(yōu)劣分析
綜上分析可知，采用排序鏈樹搜索算法進行POI關(guān)鍵字查詢，其優(yōu)勢在于：
????*?搜索時間少，時間復雜度為O(klgn)
????*?可以讓用戶邊輸入，邊路由，邊搜索，實現(xiàn)實時搜索的功能，對于采用ajax效果的Web?GIS來說，猶為合適。
????*?此算法對通配符支持友好，比如用戶輸入的關(guān)鍵字串為“北大*”或者“北?荒”，此算法都能夠比較容易的適應。
其主要劣勢在于其ID鏈表的數(shù)據(jù)冗余度較大，而且建樹過程比較復雜，對POI數(shù)據(jù)處理程序的要求比較高。但是因為這些工作都在Server端完成，在目前多核，巨量內(nèi)存，集群的server端硬件條件下，應該都不是大問題。
作者信息
Jagie,軟件開發(fā)愛好者,可以通過chen_cwf@163.com與他聯(lián)系。本文來自于Jagie的google?page:http://chencwf.googlepages.com/linktree