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