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

胡 穎

（1.重慶市勘測(cè)院，重慶 400020）

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

胡 穎1

（1.重慶市勘測(cè)院，重慶 400020）

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

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

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

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

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

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

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

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

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

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

2 綜合索引框架

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

圖1 空間劃分平面圖

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

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

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

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

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

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

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

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

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

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

3 搜索算法的計(jì)算過程

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

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

其中，

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

其中，

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

空間關(guān)鍵詞查詢用q（q.loc，q.keyword）表示s，其中，q.loc表示發(fā)出查詢的位置坐標(biāo)；q.keyword表示關(guān)鍵詞。與此類似，P.loc和R.loc分別表示POI點(diǎn)位和結(jié)點(diǎn)R的位置；P.doc和R.doc分別表示POI點(diǎn)位對(duì)象和結(jié)點(diǎn)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é)點(diǎn)R、POI點(diǎn)P和搜索q點(diǎn)位之間的歐式距離，通過DISmax將歐式距離規(guī)范到區(qū)間DISmax表示空間數(shù)據(jù)庫中兩個(gè)POI對(duì)象之間的最大距離。

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

4 實(shí)驗(yàn)與分析

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

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

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

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

實(shí)驗(yàn)結(jié)果如下：

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

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

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

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

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

5 結(jié) 語

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

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

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

胡穎，碩士，工程師，研究方向?yàn)榈乩硇畔⒐こ獭?/p>

2016-01-15。

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