張素智，丁溫雪，徐家興

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

?

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

張素智，丁溫雪，徐家興

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

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

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

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

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

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

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

1.1 相關(guān)工作

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

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

基于以上表述，本文的主要貢獻(xiàn)如下：

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

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

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

1.2 相關(guān)知識(shí)

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

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

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

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

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

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

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

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

(1)

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

(2)

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

第3步：建立倒排索引表.當(dāng)文本庫(kù)中的所有文件處理完成，索引建立成功.

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

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

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

2)當(dāng)m>q時(shí)，由于查詢子串長(zhǎng)度大于索引項(xiàng)長(zhǎng)度，所以需要多個(gè)索引項(xiàng)對(duì)子串分割.設(shè)查詢子串為supermarket，q值為4，如圖1， 該子串位置可由索引項(xiàng)‘supe’、‘rmar’、‘rket’確定.

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

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

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

3)當(dāng)m

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

(3)

(4)

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

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

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

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

3.1 RB-tree索引

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

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

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

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

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

算法：基于改進(jìn)RB-tree的Top-k算法

輸入：空間查詢?cè)~K，q-gram索引項(xiàng)長(zhǎng)度q，i=0；

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

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

圖2 改進(jìn)支持多子串匹配的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)計(jì)算查詢關(guān)鍵詞中首個(gè)索引項(xiàng)在數(shù)據(jù)存儲(chǔ)中哈希值，并將與該哈希值相對(duì)應(yīng)的倒排索引作為結(jié)果集S1，i=0.

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

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

4 實(shí)驗(yàn)結(jié)果與分析

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

實(shí)驗(yàn)過(guò)程中，首先對(duì)q值進(jìn)行分析，當(dāng)僅查詢單次時(shí)，當(dāng)索引項(xiàng)長(zhǎng)度q與查詢目標(biāo)長(zhǎng)度相同時(shí)，查詢速度最快，本實(shí)驗(yàn)將對(duì)多次空間位置進(jìn)行查詢，并統(tǒng)計(jì)不同q值對(duì)搜索時(shí)間的影響，并用通過(guò)多次實(shí)驗(yàn)消耗時(shí)間的平均數(shù)來(lái)確定q值的選取.

首先，查詢次數(shù)為2次時(shí)，選取查詢關(guān)鍵詞長(zhǎng)度為7和10，如圖3表示，隨著q值不斷增加，索引時(shí)間慢慢減少，這是因?yàn)殡S著索引項(xiàng)長(zhǎng)度增加查詢地址減少，并在查詢?cè)~長(zhǎng)度與q值相同時(shí)查詢時(shí)間最短，當(dāng)q值不斷增大，消耗時(shí)間有有輕微上升趨勢(shì)，當(dāng)q值長(zhǎng)度等于最長(zhǎng)查詢?cè)~時(shí)，時(shí)間消耗最小，這是因?yàn)榈刂芳系慕贿\(yùn)算大于地址集合的并運(yùn)算.

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

當(dāng)k值較小時(shí)，改進(jìn)算法的消耗時(shí)間與原有算法相近，但隨著取值不斷增大，改進(jìn)算法查詢效率高于原有算法.

5 結(jié)論

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

圖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] 周傲英,楊彬,金激清,等.基于位置的服務(wù)：架構(gòu)與發(fā)展[J].計(jì)算機(jī)學(xué)報(bào),2011,34(7):1155-1171.

[3] 陳翀,陳楚南,孫未未.無(wú)線數(shù)據(jù)播環(huán)境下的空間關(guān)鍵字查詢[J].計(jì)算機(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] 李艷紅,李國(guó)徽,張聰.路網(wǎng)中空間關(guān)鍵字連續(xù)k近鄰查詢算法研究[J].華中科技大學(xué)學(xué)報(bào)(自然科學(xué)版),2013,41(12):54-58.

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

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

責(zé)任編輯：時(shí) 凌

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.

國(guó)家自然科學(xué)基金項(xiàng)目(61201447).

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

1008-8423(2016)03-0241-05

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

TP301

A