基于四叉樹的移動終端地圖搜索算法研究與實現

胡 穎

（1.重慶市勘測院，重慶 400020）

基于四叉樹的移動終端地圖搜索算法研究與實現

胡 穎1

（1.重慶市勘測院，重慶 400020）

針對智能移動終端的GPS定位位置和用戶在終端輸入的搜索關鍵詞，設計了一種綜合性的空間關鍵詞索引框架，該框架利用倒排索引進行文本索引，利用四叉樹索引進行空間索引。基于該綜合索引框架設計和實現了一種高效準確的POI搜索算法，該算法能夠根據移動終端的位置和用戶輸入的搜索關鍵詞，從數據庫中獲取到相關度盡量高的結果，從而提高地圖搜索的準確度和效率。

空間索引；向量空間模型；空間關鍵詞搜索

近幾年來，移動終端的GPS功能迅速普及，在移動互聯網爆發式增長的驅動下，互聯網增加了空間的維度，研究顯示，大約20%的網絡搜索是和地理位置相關的。位置服務搜索采用關鍵詞結合地理坐標的方式，幫助用戶從空間數據庫中找到相關的結果。空間數據中存儲了許多具有坐標位置的POI，如商場、景點、賓館、車站、餐館等，同時還存儲了一定描述性的文本信息。因此，空間搜索必須同時考慮搜索對象的空間坐標和文本信息，返回兩個方面都符合用戶查詢要求的POI[1-2]。本文提出一種全新的索引框架，這種索引框架綜合了文本檢索的倒排索引和四叉樹索引，并基于這個綜合索引框架，設計了一種高效和準確地檢索空間數據庫中POI對象的算法。

1 文本相關度度量

在本文中，使用向量空間模型來計算搜索關鍵詞和POI數據文本的相關性，并應用概率排序函數對搜索結果進行排序。向量空間模型的基本思想是將文本中出現的所有特征詞構成一個n維的向量空間，然后利用余弦定理計算文本相似度。

本文使用中科院計算所的ICTCLAS分詞工具將POI的文本內容進行分詞，分詞完成后，把文本表示為特征詞權重的一個向量：

根據詞頻-逆向文件頻率模型，一個詞組在文件向量中權重就是局部參數和全局參數的乘積，經過綜合考慮調整之后，特征詞權重的計算公式為：

式中，tft,d為特征詞t在文檔d中出現的頻率；是逆向文本頻率為文本集合中的文件總數；是含有特征詞t的文本數。

文本di和查詢q之間通過余弦定理計算相似度。計算兩個文檔向量之間的夾角，通過余弦定理可知，夾角越小，余弦值越大，則文本向量之間的相關度越大。

下文中，利用式（1）計算搜索q和POI對象之間的文本相關度。

2 綜合索引框架

四叉樹是空間搜索的重要索引方法。其基本思想是將地理空間遞歸劃分為不同層次的樹結構。首先將已知范圍的空間等分為4個相等子空間，如此遞歸下去，直至四叉樹的層次滿足要求后停止分割（圖1、圖2）。四叉樹結構簡單，并且當空間數據POI對象分布比較均勻時，具有較高的空間數據插入和查詢效率[1,3]。

圖1 空間劃分平面圖

圖2 四叉樹結構示意圖

倒排索引是一種高效的文本索引方法。通過倒排索引，可以根據特征詞快速獲取包含這個特征詞的文檔列表。一個典型的倒排索引主要由詞匯表和倒排列表兩部分組成。詞匯表是用來存放分詞詞典的，通常稱存放詞匯表的文件為索引文件；倒排列表是用來存放這個文件中對應詞匯表中詞匯出現的位置和次數的，存放分詞位置的文件稱為位置文件[4]。

在必須兼顧空間和文本索引的位置服務搜索領域，需要綜合使用四叉樹索引和倒排索引，本文據此提出一種新型的索引框架。

首先在空間數據庫POI對象集合P上建立一顆四叉樹，從根結點開始，將空間4等分，對于每個子空間，建立四叉樹的第1層，接著繼續4等分，這4個子空間得到更多更小的空間，直到劃分達到一定的深度時停止；并為每一層的各個結點分別創建倒排文件，如表1所示。

表1 四叉樹根結點和中間結點倒排文件

由于結點并沒有對應一個具體的文檔文件，結點文檔是一個復合的概念，它覆蓋結點在空間劃分對應的矩形區域包含的所有POI對象中的文本文檔，可以應用結點文檔來評估以該結點包含的POI對象中所有文本和搜索關鍵詞之間的文本相關度。每個特征詞t在結點文檔中的權重表示特征詞t對于子樹結點文檔的最大權重。

在四叉樹中，每個葉結點保存了該結點對應的最小外包矩形區域內所有POI對象的引用及其文本的標識符。

POI對象的訪問入口包含指向空間數據庫中某個POI點對象的指針，POI點所在的外包矩形以及對象文本文檔的標識符。葉結點中還包含了指向POI對象文本的倒排文件的指針。

如表2所示，葉節點的倒排文件主要由所有特征詞組成的詞匯表和特征詞對應的倒排列表兩部分組成。每個倒排文件中的列表對應一個特征詞t。列表中的內容是結點文本和權重組成的序列，在本文中權重為特征詞在該文檔中出現的次數。

在四叉樹的每個結點建立對應的倒排索引文件之后，調用索引合并程序，將索引合并成一顆完整的四叉樹，最終得到綜合索引框架[5]。

3 搜索算法的計算過程

在綜合索引框架下，采用最佳優先搜索策略遍歷四叉樹結點，搜索k個符合程度最高的搜索結果。

在搜索過程中，引入M（R，q）來表示搜索q到結點R之間的最小編輯距離，定義為：

其中，

當搜索算法訪問到POI對象時，引入D（P，q）來評估搜索q和POI對象之間的編輯距離。

其中，

表2 四叉樹部分葉結點倒排文件

空間關鍵詞查詢用q（q.loc，q.keyword）表示s，其中，q.loc表示發出查詢的位置坐標；q.keyword表示關鍵詞。與此類似，P.loc和R.loc分別表示POI點位和結點R的位置；P.doc和R.doc分別表示POI點位對象和結點R的文本文檔。

式（2）、（3）中的參數α，取值在0～1之間，用于平衡空間距離和文本相關度。通過調整α參數，用戶能夠設置文本相關度和位置距離的偏好程度。DIS（R.loc，q.loc）和DIS（P.loc，q.loc）分別表示結點R、POI點P和搜索q點位之間的歐式距離，通過DISmax將歐式距離規范到區間DISmax表示空間數據庫中兩個POI對象之間的最大距離。

算法從四叉樹根結點開始逐層訪問四叉樹，對于訪問的每一個結點，算法根據其位置信息和文本相關度通過式（2）計算出綜合的編輯距離值，插入優先隊列，然后將編輯距離最小的結點作為下個將要訪問的結點。直到訪問葉結點內包含POI對象，通過D（P，q）算出POI點的編輯距離值，同樣插入優先隊列，逐次迭代，最終根據需要，從優先隊列中取出前K個結果，便是最佳相關度的搜索結果[6]。

4 實驗與分析

為了評價綜合索引框架和算法的性能，通過實驗對比了多種索引下查詢的響應時間。

實驗使用的空間數據庫包含大約80萬條POI數據，每條POI記錄包含位置坐標和文本信息，對文本進行分詞，建立詞匯表大約包含特征詞25萬個。

四叉樹空間劃分最大深度取3，參數α取值0.5，也就是距離和文本相關度以各50%的權重進行對比，接著測試從0.1～0.9變化的情況。

實驗環境：處理器為3.5GHz intel i7 CPU，內存16 G；操作系統Windows Server 2008 R2。

實驗結果如下：

1）文本和空間權重相同，對于式（2）、（3），α取值0.5，測試結果如圖3所示，通過使用綜合索引前后對比，可以看出搜索效率有了很大的提升。在3種空間索引的結構上進行空間關鍵詞查詢，實驗頻率為每組數據100次。在這種方式下，能客觀地獲取3種索引結構的平均響應時間。通過響應時間的對比來評價索引效率。當空間數據集增大，綜合索引的響應時間明顯優于其他空間索引，通過對其進行剪枝操作，效率能夠得到進一步提升。

圖3 不同索引架構的響應時間

2）為了驗證本文搜索算法的有效性，使用2種搜索方法對搜索結果進行排序，記錄前5條查詢結果，對用戶群體進行了問卷調查，調查結果如圖4，用戶滿意度達到了較高水平。

圖4 搜索結果滿意度評分

由以上實驗可知，基于綜合索引框架的算法提高了POI搜索的準確性和效率。

5 結 語

本文研究了基于四叉樹和倒排索引的空間關鍵詞查詢算法，提出了一種新型的索引結構。這種索引結構能同時根據文本和空間特性對空間數據庫中的POI數據集進行有效的組織。基于該綜合索引結構，設計的高效的空間關鍵詞搜索算法，在POI空間關鍵詞搜索的準確度和效率方面有了顯著的提升。

[1] 周巧臨.PMR四叉樹空間索引優化的應用研究[J].微計算機信息,2008,24(3)∶175-177

[2] ZHOU Y,XIE X,WANG C,et al.Hybrid Index Structures for Location-based Web Search [C].ACM International Conference on Information & Knowledge Management,New York,2005

[3] 蔣華.一種PMR四叉樹空間索引效率分析模型的研究[J].計算機工程與應用,2006,42(35)∶166-168

[4] 楊建武,陳曉鴻.基于倒排索引的文本相似搜索[J].計算機工程,2005,31(5)∶1-3

[5] XIN C,GAO C,Jensen C S,et al.Collective Spatial Keyword Querying[C].ACM Sigmod International Conference on Management of Data, New York,2011

[6] XIAO C,WANG W,LIN X,et al.Top-k Set Similarity Joins[C]. IEEE International Conference on Data Engineering, Shanghai,2009

[7] Zobel J,Moffat A.Inverted Files for Text Search Engines[J]. ACM Computing Surveys,2006,38(4)∶38-56

P208

B

1672-4623（2016）05-0089-03

10.3969/j.issn.1672-4623.2016.05.028

胡穎，碩士，工程師，研究方向為地理信息工程。

2016-01-15。

項目來源：重慶市社會民生科技創新資助項目（CSTC2015shmszx40007）。