支持多子串近似匹配的空間關(guān)鍵詞查詢算法

張素智，丁溫雪，徐家興

(鄭州輕工業(yè)學院 計算機與通信工程學院，河南 鄭州 450002)

?

支持多子串近似匹配的空間關(guān)鍵詞查詢算法

張素智，丁溫雪，徐家興

(鄭州輕工業(yè)學院 計算機與通信工程學院，河南 鄭州 450002)

隨著空間數(shù)據(jù)飛速增長，不僅POI(Point Of Interest)越來越密集，而且每個空間點的文本描述也越來越多，以往關(guān)鍵詞近似查詢算法中，不同長度的關(guān)鍵詞需要不同的閾值相匹配，影響查詢效率和查詢結(jié)果.針對以上不足提出了支持空間多子串近似匹配的空間關(guān)鍵詞查詢算法，在該算法中不需要考慮閾值的改變，而是將編輯距離直接應用到索引結(jié)構(gòu)中.通過真實數(shù)據(jù)進行實驗，表明該算法在查詢精準性和查詢效率上都有較大的提高.

空間數(shù)據(jù)庫；q-gram倒排索引；查詢算法；RB-tree

近年來，越來越多的搜索引擎開始支持空間關(guān)鍵字查詢[1]，使得越來越多的WEB資源開始擁有位置屬性，例如：新浪微博中發(fā)布自己的地理位置信息、餐館旅游景點的網(wǎng)頁中會附帶位置的信息以及簽到功能等.隨著基于位置服務[2]的快速發(fā)展，空間關(guān)鍵字漸漸的浮現(xiàn)在科技的最前沿.

空間關(guān)鍵字查詢[3](Spatial Keyword Query)是處理空間數(shù)據(jù)的重要方法之一，現(xiàn)有的搜索引擎大多數(shù)都開始支持空間數(shù)據(jù)查詢，通過輸入的文本數(shù)據(jù)和空間約束作為查詢條件，返回滿足空間信息和文本數(shù)據(jù)的結(jié)果，并按照相對應的排序算法[4]把結(jié)果顯示出來.空間數(shù)據(jù)飛速增長、用戶要求不斷提高、終端設備功能擴大以往的查詢算法越來越不能滿足用戶的需求，如何在海量的空間數(shù)據(jù)中找到相對應的結(jié)果成為當前研究的熱點.

本文將改進的支持多子串匹配q-gram倒排結(jié)構(gòu)引入針對空間數(shù)據(jù)建立的空間索引結(jié)構(gòu)當中，實現(xiàn)空間關(guān)鍵詞的近似匹配，將空間距離和權(quán)值有效的結(jié)合起來，通過該索引結(jié)構(gòu)不僅可以不用根據(jù)關(guān)鍵詞的長度變化來改變閾值大小，而且可以對查詢多關(guān)鍵詞進行匹配，并根據(jù)該索引建立有效的Top-k查詢方法.

1 相關(guān)知識和工作介紹

1.1 相關(guān)工作

Yao等[4]提出的MHR-tree，在這之前的索引結(jié)構(gòu)只支持精確匹配查詢，MHR-tree索引首次將近似串匹配(Approximate String Matching,ASM)引入空間查詢當中；Alsubaiee等[5]提出了LBAK-tree內(nèi)存索引結(jié)構(gòu)，在Yao等的基礎上確保索引代價和查詢代價之間保持平衡；Wang等[6]提出的RB-tree將位圖引入索引結(jié)果當中從而提高查詢速率結(jié)果的準確性；Hu等[7]將近似匹配應用到周邊查詢.

這些算法都將近似匹配應用到空間關(guān)鍵字查詢算法當中，確保查詢的可用性，然而存在一些不足例如：①關(guān)鍵詞長度變化使得閾值不能固定，閾值偏大可能造成查詢結(jié)果的冗余，偏小不能保證結(jié)果的召回率.②查詢空間空間數(shù)據(jù)信息人數(shù)增多，當要求頻繁返回空間關(guān)鍵詞時，上述算法不能保證時效性和準確性.本文提供支持多子串近似匹配的空間關(guān)鍵詞查詢需要面對一些挑戰(zhàn)：首先，在閾值大小不變的情況下如何保持原有的匹配效果；其次，需要設計支持容錯的相關(guān)函數(shù)，并返回用戶高效的結(jié)果.

基于以上表述，本文的主要貢獻如下：

1)首先設計支持多子串近似匹配的空間范圍查詢的索引結(jié)構(gòu).與以往的索引結(jié)構(gòu)相比，在空間近似匹配中不需要根據(jù)關(guān)鍵詞的長度來改變閾值的大小，而是將編輯距離融入倒排索引中，減少查詢的時間復雜度和空間復雜度.

2)依據(jù)該索引結(jié)構(gòu)提出高效的Top-k[8-10]算法.

3)通過真實數(shù)據(jù)進行仿真實驗，用結(jié)果證明該算法的優(yōu)越性和可行性.

1.2 相關(guān)知識

在研究領(lǐng)域中將查詢的空間-文本雙屬性對象稱為(Spatial-textual Object)，SKQ[11]中將包含查詢的位置屬性(o.loc)和文本屬性(o.kws)作為查詢條件，從空間數(shù)據(jù)庫中返回滿足位置屬性o.loc以及與o.kws的文本信息的對象集合，并通過排序公式o.f排列輸出.其中文本屬性包含對象多個關(guān)鍵字(k1,k2,…,ki),這些關(guān)鍵字都是對位置信息的描述，關(guān)鍵詞的錯誤輸入、空間數(shù)據(jù)庫[12]的存儲誤差都會導致數(shù)據(jù)不能有效的返回，q-gram[13]倒排索引的引入就是為了解決這些問題，提高空間數(shù)據(jù)查詢的可用性.

2 支持多子串近似匹配空間索引結(jié)構(gòu)建立

2.1 支持多子串匹配的q-gram索引結(jié)構(gòu)

q-gram索引是將q-gram作為索引項的倒排索引結(jié)構(gòu)，索引項為多個固定的長度為q的字符串,通過索引項與數(shù)據(jù)庫中的文本數(shù)據(jù)進行匹配，并設定閾值大小，來對索引項進行近似匹配.但是查詢空間關(guān)鍵詞的長度不同，所設定的閾值大小不相同，本文對查詢的空間關(guān)鍵詞進行再處理，分割成等長的子串，對多個子串的編輯距離進行計算，最后把得到所有的子串哈希地址進行并集運算，得到最后的結(jié)果集.

給定q值，創(chuàng)建索引預處理過程如下：

第1步：設置哈希表HT，該表由長度為σq的數(shù)組組成，為更好的查詢文本庫中的文件位置和查詢關(guān)鍵詞近似串在T中的位置，設置文件順序表FT.在文件順序表中記錄每個文件的路徑和文件尾字符在T的位置.

第2步：建立詞匯表，詞匯表是T中所有不同q-gram索引集合，由于是基于R樹建立的空間索引，所以采用哈希表對詞匯表存儲.并將文本庫中字母表與整數(shù)進行一一映射，映射公式如下：

定義1 采用Karp-Rabin函數(shù)作為哈希函數(shù)，以此將任何長度的字符串映射成為唯一的整數(shù).該公式如下:

(1)

其中：S就是長度為q的索引串，n=q，S[i]是索引串中第i個字符.H(S)就是S的哈希值.在連續(xù)的重疊q-1個字符子串的哈希值可以通過前一個哈希值計算出，既不用重復使用公式(1)，如式：

(2)

依據(jù)式(1)、(2)定位查詢關(guān)鍵詞在詞匯表中的位置.并把索引串對應的位置添加到倒排索引當中.

第3步：建立倒排索引表.當文本庫中的所有文件處理完成，索引建立成功.

2.2 任意多連續(xù)子串地址集合計算思想

例1 假設查詢關(guān)鍵詞的查詢子串的長度為m,q-gram索引中存儲了文本數(shù)據(jù)庫T中所有長度為q的字符串位置集合，依據(jù)查詢子串長度m不同，可將分為三種不同的方法進行討論.

1)當m=q時，按照經(jīng)典q-gram算法計算哈希值，找到與哈希值對應的倒排列表，查詢串子串在文本庫T中的位置集合.

2)當m>q時，由于查詢子串長度大于索引項長度，所以需要多個索引項對子串分割.設查詢子串為supermarket，q值為4，如圖1， 該子串位置可由索引項‘supe’、‘rmar’、‘rket’確定.

圖1 子串長度大于索引項長度的倒排地址Fig.1 The length of the string is longer than the index entry

算法思想：把查詢子串進行拆分，使查詢子串的長度和索引串長度相同，當mmodq≠0則在最后長度小于q子串向前重疊，在圖2中索引串rmar與串rekt重疊一個字符r，記最后索引串位置為m-q.當mmodq=0時，按照原q-gram算法執(zhí)行查詢即可.

他把如何與老梅有染，又如何想和老梅分手，老梅不干，為了擺脫老梅，自己對老梅就下了毒。然后，拿走了她一些值錢的東西。

3)當m

構(gòu)造式(2)得：

(3)

(4)

合并呈等差數(shù)列的倒排文件列表得到最后的地址集合M.

最后將構(gòu)建的新的q-gram倒排索引引入支持空間關(guān)鍵詞查詢的RB-tree索引機構(gòu)中，以此處理以往研究中閾值不確定的問題.

3 基于RB-tree的多子串查詢算法

查詢空間關(guān)鍵詞最直接的方法就是按照關(guān)鍵詞的編輯距離閾值以及相似度進行搜索匹配，然后根據(jù)空間距離遠近進行排序，最初的空間關(guān)鍵字查詢都是將空間數(shù)據(jù)的經(jīng)度和緯度分開存儲，查詢時需要遍歷所有的數(shù)據(jù)才能找到相應的位置，為此將支持空間關(guān)鍵詞近似查詢的RB-tree作為該算法索引結(jié)構(gòu)，該索引樹與IR-tree相似，將空間與文本兩種屬性有效的結(jié)合起來.

3.1 RB-tree索引

RB樹是在R樹的基礎上加入兩個位圖長度位圖LB和Gram位圖來支持空間關(guān)鍵詞的近似匹配，在該索引樹中，SMS集合中的關(guān)鍵詞，可以在LB的基礎上進一步減枝，通過式(3)計算節(jié)點中關(guān)鍵詞的Gram位圖，一旦小于閾值，則直接拋出；在以N為根節(jié)點的RB樹中，每一個節(jié)點不僅包括兩個位圖，為實現(xiàn)對關(guān)鍵詞權(quán)值計算，在節(jié)點中增加倒排文件，該文件是由每個文檔中的詞頻矩陣按照相關(guān)順序排列的關(guān)鍵詞集合.

RB樹中每個非子節(jié)點Ni存儲內(nèi)容為(P，Ni.LB，Ni.GB，MBR，Ni.DI，Ni.CS).

其中P表示節(jié)點對應的磁盤位置；Ni.LB表示該節(jié)點的長度位圖；Ni.GB表示Gram位圖；MBR表示最小矩陣區(qū)域；Ni.DI表示該節(jié)點倒排文件；Ni.CS表示子節(jié)點相關(guān)信息.葉子節(jié)點Nj存儲內(nèi)容包括(P，MBR，Nj.DI)，在索引樹當中，葉子節(jié)點的位圖都是由關(guān)鍵詞集合得來的，而父節(jié)點的位圖是由子節(jié)點位圖得來.

改進的支持多子串匹配的RB-tree結(jié)構(gòu)如圖2.

3.2 基于RB-tree的多子串查詢算法

算法：基于改進RB-tree的Top-k算法

輸入：空間查詢詞K，q-gram索引項長度q，i=0；

輸出：空間查詢詞K在倒排索引中位置S，及Top-k結(jié)果

步驟1:計算查詢關(guān)鍵詞K長度m，對K按照索引項長度進行連續(xù)不重疊分割，獲取多個等長度的索引項,如果最后索引項小于固定索引項長度q，對該索引項向前移動，如圖1所示，直到索引項長度等于定長q，記最后一個索引項在K中的位置為m-q.

圖2 改進支持多子串匹配的RB-tree結(jié)構(gòu)Fig.2 Improved support structure of multi string RB-tree

圖3 查詢兩次的q值分析Fig.3 q value analysis of query two times

步驟2:按照式(2)計算查詢關(guān)鍵詞中首個索引項在數(shù)據(jù)存儲中哈希值，并將與該哈希值相對應的倒排索引作為結(jié)果集S1，i=0.

步驟4：合并步驟2和步驟3結(jié)果集，得結(jié)果集合S.

步驟5：對查詢的結(jié)果進行排序，根據(jù)每個結(jié)果的權(quán)重值進行排序，得到最相關(guān)的前n個結(jié)果.

4 實驗結(jié)果與分析

實驗搭建環(huán)境為Inter(R)Core(TM) i5-4590CPU，4GB安裝內(nèi)存，使用WIN8操作系統(tǒng)，試驗數(shù)據(jù)來自百度地圖中獲取購物中心及餐館組成的11243個空間數(shù)據(jù)數(shù)據(jù)和396個不同的關(guān)鍵詞集合.

實驗過程中，首先對q值進行分析，當僅查詢單次時，當索引項長度q與查詢目標長度相同時，查詢速度最快，本實驗將對多次空間位置進行查詢，并統(tǒng)計不同q值對搜索時間的影響，并用通過多次實驗消耗時間的平均數(shù)來確定q值的選取.

首先，查詢次數(shù)為2次時，選取查詢關(guān)鍵詞長度為7和10，如圖3表示，隨著q值不斷增加，索引時間慢慢減少，這是因為隨著索引項長度增加查詢地址減少，并在查詢詞長度與q值相同時查詢時間最短，當q值不斷增大，消耗時間有有輕微上升趨勢，當q值長度等于最長查詢詞時，時間消耗最小，這是因為地址集合的交運算大于地址集合的并運算.

然后對查詢?nèi)螘r的時間進行實驗，如圖4可看出，與查詢兩次影響相同，都是q值等于最長查詢詞時，查詢時長最小，效率最高.因此，實驗中q值設為9.本文的研究是支持多空間關(guān)鍵詞Top-k查詢算法，最后驗證該算法的可拓展性，因為是基于RB-tree的改進，所以與原有的Top-k算法進行比較，如圖5.

當k值較小時，改進算法的消耗時間與原有算法相近，但隨著取值不斷增大，改進算法查詢效率高于原有算法.

5 結(jié)論

本文設計了支持多子串近似匹配的空間關(guān)鍵詞查詢算法，針對該算法，首先對RB-tree進行改進，在節(jié)點中加入支持多子串近似匹配的q-gram倒排索引，隨后，在該索引結(jié)構(gòu)基礎上提出了相對應的Top-k查詢算法，最后通過實驗真實數(shù)據(jù)表明，該算法能夠有效的支持空間關(guān)鍵詞查詢，并為以后的多空間關(guān)鍵詞查詢奠定一定基礎.

圖4 查詢?nèi)蔚膓值分析Fig.4 q value analysis of query three times

圖5 Top-k查詢結(jié)果 Fig.5 Top-k query results

[1] LIU X P,WAN C X,LiIU D X,et al.Survey on spatial keyword search [J].Journal of Software,2016,27(2):329-347.

[2] 周傲英,楊彬,金激清,等.基于位置的服務：架構(gòu)與發(fā)展[J].計算機學報,2011,34(7):1155-1171.

[3] 陳翀,陳楚南,孫未未.無線數(shù)據(jù)播環(huán)境下的空間關(guān)鍵字查詢[J].計算機研究與發(fā)展,2013,50(S1):145-153.

[4] YAO B,LI F F,HADJIELEFTHERIOU M,et al.Approximate string search in spatial databases[C]//Proc of the ICDE,Washington:IEEE,2010:545-556.

[5] ALSUBAIEE S,BEHM A,LI C.Supporting location-based approximate-keyword queries[C]//Proc of the SIGSPATIAL GIS,New York:ACM Press,2010:61-70.

[6] WANG J B,GAO H,LI J Z,et al.An index supporting spatial approximate keyword search on disks[J].Journal of Computer Research and Development,2012,49(10):2142-2152.

[7] HU J,FAN J,LI G L,CHEN S S.Top-kfuzzy spatial keyword search[C]//Chinese Journal of Computers,2012,35(11):2237-2246.

[8] ZHANG D X,TAN kL,TUNG A.Scalable top-kspatial keyword search[C]//Proc of 16th Int Conf on Extending Database Technology(EDBT2013).New Work:ACM,2013:359-370.

[9] SILBERSTEIN A S,BRAYNARD R,ELLIS C,et al.A Sampling-Based Approach to Optimizing Top-kQueries in Sensor Networks[J].Icde,2013:68-68.

[10] ROCHA-JUNIOR J，GKORGKAS O,JONASSEN S,et al.Efficient processing of top-kspatial keyword queries[C]//LNCS 6849:Proc of the 12 th Int Symp on Spatial and Temporal Databases(SSTD2011).Berlin:Springer,2011:205-222.

[11] 李艷紅,李國徽,張聰.路網(wǎng)中空間關(guān)鍵字連續(xù)k近鄰查詢算法研究[J].華中科技大學學報(自然科學版),2013,41(12):54-58.

[12] 張榆,馬友忠,孟小峰.一種基于HBase的高效空間關(guān)鍵字查詢策略[J].小型微型計算機系統(tǒng),2012,33(10):2141-2146.

[13] 孫德才,王曉霞.一種支持多種子近似串匹配的q-gram索引[J].計算機科學,2014,41(9):279-284.

責任編輯：時 凌

Support Multi Approximate String Matching Keywords Space Query Algorithm

ZHANG Suzhi，DING Wenxue，XU Jiaxing

(School of Computer and Communication Engineering,Zhengzhou University of Light Industry,Zhengzhou 450002,China)

With the rapid growth of spatial data,POI (Points of Interest, referred to as POI) is becoming more and more intensive, and the text description of each spatial point is also gradually increasing. In previous key words approximate query algorithm, the key words of different length match with different thresholds,which affect the efficiency of query and query results. In view of the above problem is proposed to support multi space on the approximation space of keyword matching query algorithm, in this algorithm, it is not needed to consider the change of threshold, because edit distance is directly applied to the index structure. The simulation results show that the proposed algorithm can improve the accuracy and efficiency of query.

spatial database;q-gram inverted index;query algorithm;RB-tree

2016-08-16.

國家自然科學基金項目(61201447).

張素智(1965- )，男，博士，教授，主要從事Web數(shù)據(jù)庫、分布式計算和異構(gòu)系統(tǒng)集成的研究.

1008-8423(2016)03-0241-05

10.13501/j.cnki.42-1569/n.2016.09.001

TP301

A