胡 穎

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

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

胡 穎1

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

針對智能移動終端的GPS定位位置和用戶在終端輸入的搜索關(guān)鍵詞，設(shè)計了一種綜合性的空間關(guān)鍵詞索引框架，該框架利用倒排索引進(jìn)行文本索引，利用四叉樹索引進(jìn)行空間索引?；谠摼C合索引框架設(shè)計和實現(xiàn)了一種高效準(zhǔn)確的POI搜索算法，該算法能夠根據(jù)移動終端的位置和用戶輸入的搜索關(guān)鍵詞，從數(shù)據(jù)庫中獲取到相關(guān)度盡量高的結(jié)果，從而提高地圖搜索的準(zhǔn)確度和效率。

空間索引；向量空間模型；空間關(guān)鍵詞搜索

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

1 文本相關(guān)度度量

在本文中，使用向量空間模型來計算搜索關(guān)鍵詞和POI數(shù)據(jù)文本的相關(guān)性，并應(yīng)用概率排序函數(shù)對搜索結(jié)果進(jìn)行排序。向量空間模型的基本思想是將文本中出現(xiàn)的所有特征詞構(gòu)成一個n維的向量空間，然后利用余弦定理計算文本相似度。

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

根據(jù)詞頻-逆向文件頻率模型，一個詞組在文件向量中權(quán)重就是局部參數(shù)和全局參數(shù)的乘積，經(jīng)過綜合考慮調(diào)整之后，特征詞權(quán)重的計算公式為：

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

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

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

2 綜合索引框架

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

圖1 空間劃分平面圖

圖2 四叉樹結(jié)構(gòu)示意圖

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

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

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

表1 四叉樹根結(jié)點和中間結(jié)點倒排文件

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

在四叉樹中，每個葉結(jié)點保存了該結(jié)點對應(yīng)的最小外包矩形區(qū)域內(nèi)所有POI對象的引用及其文本的標(biāo)識符。

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

如表2所示，葉節(jié)點的倒排文件主要由所有特征詞組成的詞匯表和特征詞對應(yīng)的倒排列表兩部分組成。每個倒排文件中的列表對應(yīng)一個特征詞t。列表中的內(nèi)容是結(jié)點文本和權(quán)重組成的序列，在本文中權(quán)重為特征詞在該文檔中出現(xiàn)的次數(shù)。

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

3 搜索算法的計算過程

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

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

其中，

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

其中，

表2 四叉樹部分葉結(jié)點倒排文件

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

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

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

4 實驗與分析

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

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

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

實驗環(huán)境：處理器為3.5GHz intel i7 CPU，內(nèi)存16 G；操作系統(tǒng)Windows Server 2008 R2。

實驗結(jié)果如下：

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

圖3 不同索引架構(gòu)的響應(yīng)時間

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

圖4 搜索結(jié)果滿意度評分

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

5 結(jié) 語

本文研究了基于四叉樹和倒排索引的空間關(guān)鍵詞查詢算法，提出了一種新型的索引結(jié)構(gòu)。這種索引結(jié)構(gòu)能同時根據(jù)文本和空間特性對空間數(shù)據(jù)庫中的POI數(shù)據(jù)集進(jìn)行有效的組織?；谠摼C合索引結(jié)構(gòu)，設(shè)計的高效的空間關(guān)鍵詞搜索算法，在POI空間關(guān)鍵詞搜索的準(zhǔn)確度和效率方面有了顯著的提升。

[1] 周巧臨.PMR四叉樹空間索引優(yōu)化的應(yīng)用研究[J].微計算機(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].計算機(jī)工程與應(yīng)用,2006,42(35)∶166-168

[4] 楊建武,陳曉鴻.基于倒排索引的文本相似搜索[J].計算機(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。

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