高效的top-k相似字符串查詢算法

陳子陽(yáng)，韓玉俊，王璿，周軍鋒

（1. 燕山大學(xué) 信息科學(xué)與工程學(xué)院，河北 秦皇島 066004；2. 河北省計(jì)算機(jī)虛擬技術(shù)與系統(tǒng)集成重點(diǎn)實(shí)驗(yàn)室，河北 秦皇島 066004）

1 引言

top-k字符串相似性查詢?cè)诤芏囝I(lǐng)域有重要應(yīng)用，如數(shù)據(jù)清洗、數(shù)據(jù)集成、生物信息學(xué)和模式識(shí)別等。一個(gè)典型的例子是對(duì)文本進(jìn)行拼寫(xiě)檢查時(shí)，spellchecker需要從詞典庫(kù)里查找k個(gè)與用戶輸入最相似的單詞[1]。在生物信息領(lǐng)域，字符串相似性查詢用來(lái)找到 top-k相似基因序列，用于疾病預(yù)測(cè)和新藥品研發(fā)[2]。數(shù)據(jù)清洗會(huì)從一個(gè)實(shí)體集合找到top-k個(gè)與給定實(shí)體最相似的實(shí)體[1]。

已有的基于閾值的字符串相似性查詢方法[1,3～5]需要用戶提前指定相似性函數(shù)(如編輯距離)和閾值，然后返回與查詢字符串相似性以及在給定閾值內(nèi)的字符串。當(dāng)應(yīng)用該方法求解 top-k相似字符串時(shí)，用戶很難提前確定一個(gè)合適的閾值，當(dāng)返回結(jié)果為空或者返回大量結(jié)果時(shí)，需要多次根據(jù)不同的閾值重復(fù)計(jì)算，查詢效率低。文獻(xiàn)[6]使用Trie樹(shù)索引來(lái)組織集合中的所有字符串，通過(guò)遞增的方式計(jì)算查詢字符串與Trie樹(shù)節(jié)點(diǎn)所對(duì)應(yīng)的字符串之間的編輯距離來(lái)求解top-k結(jié)果，由于Trie樹(shù)節(jié)點(diǎn)所對(duì)應(yīng)的字符串僅是字符串集合中字符串的前綴，當(dāng)字符串長(zhǎng)度變大時(shí)，由于長(zhǎng)字符串的公共前綴較短，該方法會(huì)處理很多不相似字符串的前綴，導(dǎo)致系統(tǒng)性能下降。

針對(duì)已有方法在求解 top-k相似字符串時(shí)效率低的問(wèn)題，提出了一種長(zhǎng)度跳躍索引以及基于該索引的長(zhǎng)度過(guò)濾策略和計(jì)數(shù)過(guò)濾策略，用以減少需要處理的字符串?dāng)?shù)量；提出無(wú)匹配特征的字符串之間的編輯距離下界，用以進(jìn)一步減少需要處理的候選字符串?dāng)?shù)量。基于以上策略，提出了相應(yīng)的 top-k字符串相似性查詢算法，并在不同特征的數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果驗(yàn)證了本文算法的高效性和擴(kuò)展性。

2 背景知識(shí)

2.1 問(wèn)題定義

用Σ表示一個(gè)有限字符的集合，字符串s可以看成由Σ中字符組成的有序序列，|s|表示字符串s的長(zhǎng)度。

現(xiàn)有廣泛使用的衡量字符串相似性的標(biāo)準(zhǔn)之一是編輯距離[1～8]。2個(gè)字符串的編輯距離是將一個(gè)字符串轉(zhuǎn)換成另一個(gè)字符串所需要的最少單字符編輯操作次數(shù)，允許的單字符編輯操作有：插入、刪除和替換。符號(hào)ed(r,s) 表示字符串r和s之間的編輯距離。假設(shè)r=“srajit”,s=“seraji”，則ed(r,s) = 2表示將字符串“srajit”變?yōu)椤皊eraji”所需的最少單字符編輯操作次數(shù)為2。

問(wèn)題定義(top-k字符串相似性查詢)：給定字符串集合S和查詢字符串σ，top-k字符串相似性查詢返回集合R?S，其中|R|=k，且對(duì)?r∈R和?s∈S-R，有 ed(r,σ) ≤ ed(s,σ)。

例1表1是字符串集合S中的字符串，假定查詢字符串σ=“geometric”，top-3 字符串相似性查詢返回的結(jié)果R={“geometrics”，“isometric”，“biometric”}，σ與這3個(gè)字符串的編輯距離分別是1、2、2，集合中其他字符串與σ的編輯距離都不小于2。

表1 字符串集合S中的字符串

2.2 基本概念

q-gram和q-chunk：q-gram 是字符串中所有長(zhǎng)度為q的子串，gq(s)表示字符串s的q-gram集合，為保證s中每個(gè)字符都有對(duì)應(yīng)的q-gram，需要在字符串s結(jié)尾添加q-1個(gè)$字符。q-chunk是指字符串中長(zhǎng)度為q且起始位置為iq(i≥ 0)的子串，字符串s的q-chunk集合是對(duì)s完整且不相交的劃分，用cq(s)表示。為了保證字符串最后一個(gè)q-chunk有q個(gè)字符，需要在s結(jié)尾添加(q-(|s|%q))%q個(gè)$字符。以字符串“genetic”為例，q= 2，gq(“genetic”) ={“ge”,“en”,“ne”,“et”, “ti”, “ic”,“c$”}，cq(“genetic”) = {“ge”,“ne”,“ti”,“c$”}。

字符串s的任意q-gram和q-chunk都稱為s的特征(signature)。由于直接計(jì)算字符串之間的編輯距離代價(jià)較高，已有方法[1,3,5,8～12]在計(jì)算與給定查詢串相似的字符串時(shí)，第一步通過(guò)字符串特征進(jìn)行過(guò)濾，以便縮小候選字符串的數(shù)量，進(jìn)而降低第二步編輯距離計(jì)算的代價(jià)。

為了在第一步執(zhí)行過(guò)濾，文獻(xiàn)[1,4,5,8～10,13,14]都會(huì)為字符串集合中的所有字符串特征(q-gram)建立倒排表。倒排表中的每個(gè)元素是一個(gè)二元組＜id,pos＞，其中id表示相應(yīng)的q-gram在id對(duì)應(yīng)的字符串中出現(xiàn)，pos表示相應(yīng)的q-gram在該字符串中出現(xiàn)的起始位置。每一個(gè)倒排表按照id升序有序，其中id值相等的元組按照pos升序有序。預(yù)處理時(shí)，可以按照字符串的長(zhǎng)度排序，進(jìn)而設(shè)定每個(gè)字符串的id，因此本文的后續(xù)討論中，id小的字符串長(zhǎng)度也較短。圖1展示了表1中字符串集合的部分q-gram對(duì)應(yīng)的倒排表。對(duì)于q-gram =“eo”，由圖1可知，“eo”在字符串s3、s6、s7中出現(xiàn)，且起始位置都是1。

2.3 相關(guān)工作

在top-k字符串相似性查詢方面，除了第1部分介紹的文獻(xiàn)[6]，文獻(xiàn)[7]通過(guò)動(dòng)態(tài)調(diào)整q-gram的長(zhǎng)度來(lái)解決 top-k字符串相似性查詢，但是動(dòng)態(tài)調(diào)整q-gram 長(zhǎng)度非常費(fèi)時(shí)，過(guò)濾代價(jià)很大，導(dǎo)致查詢效率降低[6]，且該方法需要為不同長(zhǎng)度的q-gram建立索引，所需的存儲(chǔ)空間大。文獻(xiàn)[3]使用B樹(shù)來(lái)索引S中字符串的特征(如q-gram)，通過(guò)迭代方式遍歷B樹(shù)中的節(jié)點(diǎn)，動(dòng)態(tài)計(jì)算節(jié)點(diǎn)下的字符串與σ的編輯距離下界，并基于此更新閾值進(jìn)行過(guò)濾，最后通過(guò)計(jì)算編輯距離求得 top-k相似性結(jié)果。這種方法需要枚舉很多字符串來(lái)動(dòng)態(tài)更新閾值，尤其當(dāng)k較小時(shí)，閾值不緊確，剪枝效果不好[6]。

圖1 倒排索引

除以上工作外，和 top-k字符串相似性查詢相關(guān)的工作還體現(xiàn)在基于閾值的字符串相似性查詢和相似性連接。

基于閾值的字符串相似性查詢的問(wèn)題定義可表述為：給定字符串集合S、查詢字符串σ、字符串相似性函數(shù)(如編輯距離)以及一個(gè)閾值τ，返回S中與σ相似性小于等于τ的字符串。

已有基于閾值的方法[1,2,4,5,7]在過(guò)濾階段利用q-gram倒排表得到和查詢串的公共q-gram不小于|σ|-q+1-qτ的候選字符串；驗(yàn)證階段調(diào)用動(dòng)態(tài)規(guī)劃算法求解每個(gè)候選串和查詢串的編輯距離，并根據(jù)閾值τ確定該候選是否滿足條件。當(dāng)應(yīng)用該方法來(lái)求解top-k相似字符串時(shí)，由于很難根據(jù)k值確定合適的閾值τ，因而可能存在返回結(jié)果過(guò)多和過(guò)少的問(wèn)題，進(jìn)而導(dǎo)致根據(jù)不同的閾值重復(fù)計(jì)算、效率較低。

以上基于閾值的方法對(duì)查詢串和被查詢串使用的都是q-gram，稱之為對(duì)稱特征方案，與此相反，文獻(xiàn)[10]研究基于非對(duì)稱特征方案的字符串相似性查詢問(wèn)題(非對(duì)稱特征方案指查詢串用q-chunk，被查詢串用q-gram，或者反過(guò)來(lái)也稱為非對(duì)稱特征方案)，并給出了非對(duì)稱特征方案下2個(gè)字符串相似的公共特征下界。即給定2個(gè)字符串s和σ，假設(shè)ed(s,σ) ≤τ，如下2個(gè)不等式成立。

g和c表示相同的子串，對(duì)于式(1)和式(2)中二者匹配(即g=c)，當(dāng)且僅當(dāng)g和c的位置差不大于τ。

相似性連接方面，對(duì)于給定的2個(gè)字符串集合S和R、字符串相似性函數(shù)(如編輯距離)以及相似性閾值，文獻(xiàn)[8～10, 12～18]返回所有分屬2個(gè)集合且相似性在閾值之內(nèi)的(top-k)相似字符串對(duì)，感興趣的讀者可以參考相關(guān)文獻(xiàn)獲取詳細(xì)信息。

3 top-k字符串相似查詢算法

3.1 top-kLength算法

本節(jié)首先提出了一種長(zhǎng)度跳躍索引，基于該索引提出了一種提前終止策略，根據(jù)該策略只需掃描局部倒排表；然后提出了查詢字符串與字符串集合之間編輯距離的緊確下界，根據(jù)該下界，可以確定是否需要處理與查詢串σ沒(méi)有公共特征的字符串?；谏鲜?種策略，給出了基本的top-k字符串相似性查詢算法，稱為top-kLength 算法。

3.1.1 基于長(zhǎng)度跳躍索引的長(zhǎng)度過(guò)濾策略

給定查詢串σ和字符串s，根據(jù)編輯距離的定義，如果 ed(σ,s)≤τ，則||s|-|σ||≤τ。根據(jù)該結(jié)論，將原始的q-gram倒排表(如圖2(a)所示)按照字符串長(zhǎng)度分段組織，如圖2(b)所示，其中長(zhǎng)度用來(lái)快速定位特定長(zhǎng)度的字符串，在求解基于閾值的相似字符串時(shí)，通過(guò)該索引可以快速定位倒排表中和σ長(zhǎng)度差不大于τ的字符串，從而實(shí)現(xiàn)基于長(zhǎng)度的過(guò)濾策略，將該索引稱為長(zhǎng)度跳躍索引。

圖2 長(zhǎng)度跳躍索引舉例

以圖2(b)為例，倒排表中長(zhǎng)度為9的字符串有s4和s5。

顯然，基于長(zhǎng)度跳躍索引可以高效支持基于閾值的相似字符串查詢問(wèn)題，但是當(dāng)應(yīng)用基于閾值的方法來(lái)解決 top-k相似字符串查詢時(shí)，存在冗余計(jì)算問(wèn)題。例如，給定查詢串的長(zhǎng)度|σ| = 9,k= 5，假設(shè)τ =1，則根據(jù)長(zhǎng)度過(guò)濾的要求，需要處理的字符串長(zhǎng)度應(yīng)在[8,10]內(nèi)，即s3,s4,s5,s7。由于被處理字符串個(gè)數(shù)小于5，需要增大閾值。當(dāng)增大τ的取值來(lái)增加被處理字符串的個(gè)數(shù)時(shí)，需要重復(fù)計(jì)算s3,s4,s5,s7，顯然存在重復(fù)計(jì)算問(wèn)題。當(dāng)|σ| = 9,k= 1,τ=1，假設(shè)ed(σ,s5) = 1，則不需要計(jì)算s3,s7，而基于閾值的方法會(huì)處理s3,s7，顯然仍然存在冗余計(jì)算問(wèn)題。

針對(duì)以上方法存在的冗余計(jì)算問(wèn)題，提出一種基于長(zhǎng)度跳躍索引的高效過(guò)濾策略，和以上方法相比，處理的字符串?dāng)?shù)量更少，且只需要一遍處理。其總體思路是根據(jù)被處理字符串和查詢串的長(zhǎng)度差從小到大進(jìn)行處理。

定理1 假設(shè)當(dāng)前top-k結(jié)果中與查詢串σ編輯距離最大的字符串為sk，則對(duì)任意尚未處理的字符串r，如果||σ|-|r||≥ ed(σ,sk)，則有 ed(σ,r)≥ ed(σ,sk)。

證明 假定 ed(σ,sk) =τk，因?yàn)閨|σ|-|r||≥τk，即σ和r的長(zhǎng)度之差不小于τk，根據(jù)編輯距離的定義，必有 ed(σ,r)≥τk。證畢。

根據(jù)定理 1，當(dāng)按照與查詢串的長(zhǎng)度差遞增方式處理被查詢串時(shí)，如果長(zhǎng)度差滿足定理1的條件，則可以提前終止，無(wú)需處理剩余字符串。

例2假定查詢?chǔ)? “geometrics”，k= 1，以表1中的字符串集合為例，σ的q-chunk所對(duì)應(yīng)的長(zhǎng)度跳躍索引如圖 3所示。因?yàn)閨σ|=10，所以首先處理長(zhǎng)度為10的字符串，即字符串s6,s7，此時(shí)ed(σ,s7) = 0；對(duì)于倒排表中剩余的任意字符串r有||σ|-|r||≥1，根據(jù)定理1，只需處理倒排表中的字符串s6,s7，其他字符串無(wú)需處理。

3.1.2 無(wú)匹配特征的字符串的處理策略

當(dāng)處理完σ的q-chunk對(duì)應(yīng)的倒排表后，根據(jù)定理2，假設(shè)當(dāng)前top-k結(jié)果中與σ編輯距離最大的字符串為sk，當(dāng) ed(sk,σ)≤|cq(σ)時(shí)，可以保證當(dāng)前top-k結(jié)果即最終結(jié)果；反之，當(dāng)大于|cq(σ)|時(shí)，僅依賴σ對(duì)應(yīng)的倒排表不能保證top-k結(jié)果的正確性，為了保證結(jié)果的正確性，這時(shí)仍然需要處理字符串集合中與查詢串σ沒(méi)有公共特征的字符串。

例3 假設(shè)σ=“geometric”，q= 2,k= 3，則|cq(σ)|=5。當(dāng)處理完查詢串σ的q-chunk對(duì)應(yīng)的倒排表后，假設(shè)當(dāng)前top-k結(jié)果與σ的編輯距離分別為0, 1, 2, 由于 2 ＜ 5； 根據(jù)定理 2，當(dāng)前 top-k結(jié)果即最終結(jié)果。假設(shè)當(dāng)前top-k結(jié)果與σ的編輯距離分別為0, 1, 7，則仍需要處理字符串集合S中與σ沒(méi)有公共特征的字符串，且這些字符串的長(zhǎng)度應(yīng)滿足||s|-|σ||＜ed(sk,σ)。

3.1.3 top-kLength算法描述

基于以上討論，給出了top-kLength算法。在算法的執(zhí)行過(guò)程中，使用一個(gè)優(yōu)先隊(duì)列Qtop-k來(lái)保存當(dāng)前所求的 top-k結(jié)果，優(yōu)先隊(duì)列中的元素個(gè)數(shù)上限為k。

算法1top-kLength算法

輸入：字符串集合S，查詢字符串σ，結(jié)果個(gè)數(shù)k

圖3 提前終止策略舉例

輸出：top-k相似字符串

算法1按照與查詢字符串長(zhǎng)度差遞增的方式來(lái)處理倒排表中的字符串，初始化最初的長(zhǎng)度差為ld=0(第2)行)。算法首先得到查詢字符串σ的q-chunk對(duì)應(yīng)的倒排表(第 3)行)，在第 4)～10)行，根據(jù)長(zhǎng)度差及長(zhǎng)度跳躍索引確定滿足||s|-|σ||=ld的局部倒排表(第5)行)，然后調(diào)用 processPartialInvList()來(lái)計(jì)算局部的top-k結(jié)果(第6)行)。處理完局部的倒排表后，如果Qtop-k中有k個(gè)結(jié)果且head(Qtop-k).dis＜ld+1 (第7)行)，則根據(jù)定理1可以提前終止，不需要遍歷剩余的倒排表；否則按照與查詢字符串長(zhǎng)度差遞增的方式來(lái)處理剩余的倒排表。當(dāng)處理完σ的q-chunk對(duì)應(yīng)的倒排表后，算法得到當(dāng)前的 top-k結(jié)果。最壞情況下，當(dāng) head(Qtop-k)dis＞ |cq(σ)|時(shí)，根據(jù)定理 2，僅依賴查詢串對(duì)應(yīng)的倒排表不能保證當(dāng)前 top-k結(jié)果等于最終的結(jié)果。為了保證結(jié)果的正確性，這時(shí)仍然需要處理字符串集合中與查詢串σ沒(méi)有公共特征的字符串(第11)和12)行)。本文使用動(dòng)態(tài)規(guī)劃計(jì)算2個(gè)字符串的編輯距離[19]。

3.2 top-kLengthCount算法

與用基于閾值的方法來(lái)計(jì)算 top-k相似字符串相比，雖然 top-kLength 算法避免了對(duì)字符串的重復(fù)處理，且減少了需要處理的字符串?dāng)?shù)量，但對(duì)于需要處理的每個(gè)字符串，都需要計(jì)算編輯距離，代價(jià)較高。針對(duì)以上問(wèn)題，提出了自適應(yīng)計(jì)數(shù)過(guò)濾策略，進(jìn)一步減少需要計(jì)算編輯距離的字符串?dāng)?shù)量。

3.2.1 自適應(yīng)計(jì)數(shù)過(guò)濾策略

定理3 假設(shè)當(dāng)前top-k結(jié)果中與查詢串σ編輯距離最大的字符串為sk，ed(σ,sk) =τk,對(duì)于下一個(gè)要處理的字符串s，如果 ed(s,σ) ≤τk，則有下面的不等式(3)和式(4)成立

證明 首先證明式(3)，式(4)根據(jù)對(duì)稱性可得。

定理 3說(shuō)明，下一個(gè)被處理的字符串是否能被過(guò)濾掉，依賴于當(dāng)前所求得的sk與查詢串σ的匹配特征個(gè)數(shù)。與文獻(xiàn)[11]不同，對(duì)于top-k相似性查詢，應(yīng)用定理3時(shí)，閾值是動(dòng)態(tài)調(diào)整的。在處理字符串的過(guò)程中，τk是單調(diào)遞減的，所以公共特征匹配個(gè)數(shù)的下界在不斷增大，因此可以過(guò)濾更多的字符串。

當(dāng)應(yīng)用定理3時(shí)，關(guān)鍵的操作是快速統(tǒng)計(jì)查詢串的q-chunk與被查詢串的q-gram的匹配個(gè)數(shù)。提出一種自適應(yīng)的歸并跳躍策略來(lái)求解查詢串的q-chunk與被查詢串的q-gram的匹配個(gè)數(shù)，如函數(shù)adaptiveMergeSkip所示。

假設(shè)當(dāng)前top-k結(jié)果中與查詢串σ編輯距離最大的字符串為sk，ed(σ,sk) =τk，則根據(jù)定理 3，后續(xù)處理的字符串和σ的匹配個(gè)數(shù)不能少于，函數(shù)adaptiveMergeSkip中用Tk表示該閾值。第2個(gè)輸入?yún)?shù)INVp表示根據(jù)長(zhǎng)度跳躍索引得到的對(duì)應(yīng)特定長(zhǎng)度的局部倒排表集合。

輸入：INVp, 查詢字符串σ，結(jié)果個(gè)數(shù)k，特征匹配閾值Tk

輸出：top-k相似字符串

函數(shù)adaptiveMergeSkip使用優(yōu)先隊(duì)列Qp來(lái)存儲(chǔ)當(dāng)前需要處理的元素，Qp中元素按照id升序排序，并在第2)行將INVp中每個(gè)倒排表的第一個(gè)待處理元素插入Qp。在第3)～21)行，只要Qp不空，算法首先將與隊(duì)頭元素表示的字符串相同的所有元素出隊(duì)列(第5)行)，如果當(dāng)前Qtop-k中少于k個(gè)結(jié)果，則算法直接計(jì)算隊(duì)頭元素所表示的字符串s和查詢串的編輯距離，并將計(jì)算結(jié)果插入Qtop-k(第6)～8)行)，并將彈出元素涉及的倒排表中的下一個(gè)元素入Qp(第 9)行)。反之，如果|Qtop-k| ＞k，算法首先計(jì)算下一個(gè)候選字符串s和σ的公共匹配個(gè)數(shù)的下界Tk(第11)行)，然后判斷出隊(duì)列元素個(gè)數(shù)n和Tk的關(guān)系。如果n＜Tk(第 12)行滿足)，則調(diào)用 pushBinSearch()(第 13)行)，從隊(duì)列中進(jìn)一步彈出Tk-1-n個(gè)元素，加上前面處理的元素，總共從優(yōu)先隊(duì)列中出來(lái)Tk-1個(gè)元素。因?yàn)樗械牡古疟碇邪凑兆址甶d遞增排序，令s’表示當(dāng)前的隊(duì)頭元素，對(duì)于元素id小于s’的元素對(duì)應(yīng)的字符串，其匹配的特征個(gè)數(shù)最好的情況下是Tk-1，必小于Tk，所以對(duì)于彈出元素的Tk-1個(gè)倒排表，直接定位到大于等于s’的最小元素r，中間的元素表示的字符串不需要處理，然后將r插入優(yōu)先隊(duì)列Qp。如果n≥Tk，則根據(jù)位置進(jìn)一步計(jì)算n個(gè)元素中匹配的特征個(gè)數(shù)m(第15)行)，如果m≥Tk，調(diào)用verifyEDThreshold( )函數(shù)計(jì)算s和σ的編輯距離d(第17)行)，當(dāng)d小于τk，即s和σ的編輯距離小于當(dāng)前top-k結(jié)果和σ的最大編輯距離，則用s替換Qtop-k中編輯距離最大的字符串（第 18)～20)行）。并將彈出元素涉及倒排表中的下一個(gè)元素入Qp。

例 4假設(shè)經(jīng)過(guò)長(zhǎng)度過(guò)濾得到的局部倒排表如圖4(a)的虛線框所示，且Tk=4。為了處理虛線框中的字符串，函數(shù) adaptiveMergeSkip()首先將每個(gè)倒排表的第一個(gè)待處理元素，即36,100,50,115,115進(jìn)入優(yōu)先隊(duì)列，如圖4(b)所示。然后36出隊(duì)列，這時(shí)n=1，由于1＜Tk=4，所以再?gòu)膬?yōu)先隊(duì)列中彈出Tk-1-n=2個(gè)元素，即彈出50和100，這時(shí)共有Tk-1=3個(gè)元素出隊(duì)列，50和100不可能是滿足條件的結(jié)果，可以直接跳過(guò)，無(wú)需計(jì)算編輯距離。之后當(dāng)前優(yōu)先隊(duì)列中最小的元素為 115。對(duì)于剛剛彈出元素的Tk-1=3個(gè)倒排表，直接定位大于等于115的最小元素，這樣可以跳過(guò)很多不可能成為top-k結(jié)果的元素，隊(duì)列狀態(tài)如圖4(c)所示。下次處理時(shí)，當(dāng)前優(yōu)先隊(duì)列的頭元素為 115，個(gè)數(shù)為 4，調(diào)用基于閾值的編輯距離函數(shù) verifyEDThreshold()來(lái)驗(yàn)證查詢串σ和115對(duì)應(yīng)的候選串的編輯距離。如果二者的編輯距離小于當(dāng)前 top-k結(jié)果的最大編輯距離，則更新當(dāng)前的 top-k結(jié)果，并根據(jù)定理 3更新匹配的q-gram和q-chunk的閾值為Tk。

圖4 adaptiveMergeSkip函數(shù)舉例

假設(shè)top-k結(jié)果中與查詢串σ編輯距離第k大的字符串為sk, ed(σ,sk) =τk，在給定τk情況下只需判斷字符串σ與s的編輯距離是否大于τk，根據(jù)文獻(xiàn)[15]中的length pruning 策略，可以降低計(jì)算編輯距離的時(shí)間復(fù)雜度，如果2個(gè)字符串的編輯距離大于τk，則返回τk+1，否則返回實(shí)際編輯距離，用verifyEDThreshold(s1,s2,τk)表示基于閾值的編輯距離算法，verifyED(s1,s2)表示計(jì)算2個(gè)字符串的實(shí)際編輯距離的動(dòng)態(tài)規(guī)劃算法。

與 merge-skip[1]使用固定閾值的方法不同，adaptiveMergeSkip 函數(shù)的閾值是動(dòng)態(tài)調(diào)整的?？梢钥闯觯紫仁褂瞄L(zhǎng)度跳躍索引定位特定長(zhǎng)度的字符串，并使用 adaptiveMergeSkip函數(shù)對(duì)局部倒排表進(jìn)行處理，可以首先定位與查詢字符串較相似的字符串，所以τk可以快速降低，相應(yīng)的q-gram和q-chunk的匹配個(gè)數(shù)快速增加，從而加速掃描查詢相關(guān)的倒排表。

3.2.2 top-kLengthCount算法描述

基于以上介紹的自適應(yīng)計(jì)數(shù)過(guò)濾策略，給出了top-kLengthCount算法，如算法2所示。

算法2top-kLengthCount 算法

輸入：字符串集合S，查詢字符串σ，結(jié)果個(gè)數(shù)k

輸出：top-k相似字符串

top-kLengthCount算法與top-kLength算法的不同之處體現(xiàn)在：1)在第6)行調(diào)用adaptiveMergeSkip函數(shù)對(duì)局部倒排表進(jìn)行處理，并在處理完局部倒排表后，根據(jù)定理2 更新Tk(第 10)行)；2)與 top-kLength算法處理字符串集合中與查詢串σ沒(méi)有公共特征的字符串不同，在processNoCommonStr()中，雖然σ的q-chunk集合與未處理的字符串的q-gram集合的交集為空，根據(jù)式(4)，通過(guò)計(jì)算σ的q-gram集合與未處理的字符串的q-chunk集合的交集(第3)行)，進(jìn)一步減少需要計(jì)算編輯距離的字符串。如果匹配的特征個(gè)數(shù)大于下界(第 4)行)，則調(diào)用verifyEDThreshold()進(jìn)行編輯距離的計(jì)算(第5)行)，如果二者的編輯距離小于當(dāng)前 top-k結(jié)果的最大編輯距離，則更新當(dāng)前的top-k結(jié)果(第6)～8)行)。

4 實(shí)驗(yàn)評(píng)估

4.1 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)所用的機(jī)器配置為Intel Pentium G2020，2.90 GHz CPU，4 GB內(nèi)存，操作系統(tǒng)為 Ubuntu 12.04 LTS。

根據(jù)文獻(xiàn)[6]的實(shí)驗(yàn)結(jié)果，Range算法比AQ[3]、Bed-tree[4]和 Flamingo[1]更高效，因此實(shí)驗(yàn)中只和Range算法進(jìn)行比較，Range算法源碼由原文作者提供注1注1 http://dbgroup.cs.tsinghua.edu.cn/dd/projects/topksearch/index.html注2 http://dbgroup.cs.tsinghua.edu.cn/dd/data/data.tar注3 http://www.ncbi.nlm.nih.gov/pubmed/注4 http://www.cse.unsw.edu.au/～weiw/project/simjoin.html#_download。基于C++實(shí)現(xiàn)了本文中提出的算法，并使用-O3flag的GCC4.8.2進(jìn)行編譯。實(shí)驗(yàn)環(huán)境與Range算法完全相同。

所用數(shù)據(jù)來(lái)自3個(gè)真實(shí)數(shù)據(jù)集，分別是：1) word數(shù)據(jù)集注2注1 http://dbgroup.cs.tsinghua.edu.cn/dd/projects/topksearch/index.html注2 http://dbgroup.cs.tsinghua.edu.cn/dd/data/data.tar注3 http://www.ncbi.nlm.nih.gov/pubmed/注4 http://www.cse.unsw.edu.au/～weiw/project/simjoin.html#_download，包含常用的英語(yǔ)單詞字符串；2) author數(shù)據(jù)集，包含作者名稱的字符串，從期刊pubMed注3注1 http://dbgroup.cs.tsinghua.edu.cn/dd/projects/topksearch/index.html注2 http://dbgroup.cs.tsinghua.edu.cn/dd/data/data.tar注3 http://www.ncbi.nlm.nih.gov/pubmed/注4 http://www.cse.unsw.edu.au/～weiw/project/simjoin.html#_download提取；3) DBLP數(shù)據(jù)集注4注1 http://dbgroup.cs.tsinghua.edu.cn/dd/projects/topksearch/index.html注2 http://dbgroup.cs.tsinghua.edu.cn/dd/data/data.tar注3 http://www.ncbi.nlm.nih.gov/pubmed/注4 http://www.cse.unsw.edu.au/～weiw/project/simjoin.html#_download，包含作者名字與文章名字連接起來(lái)的長(zhǎng)字符串。表2給出了3個(gè)數(shù)據(jù)集的基本統(tǒng)計(jì)信息。圖5中展示了3個(gè)數(shù)據(jù)集中字符串的長(zhǎng)度分布情況。由圖5可知，所有數(shù)據(jù)集的字符串長(zhǎng)度都呈近似的正態(tài)分布，其中word和author數(shù)據(jù)集的字符串長(zhǎng)度較短，而DBLP數(shù)據(jù)集的字符串長(zhǎng)度較長(zhǎng)。

對(duì)于每一個(gè)數(shù)據(jù)集，從數(shù)據(jù)集中隨機(jī)選擇了100組查詢，然后比較平均運(yùn)行時(shí)間。

表2 數(shù)據(jù)集基本信息

4.2 性能比較

4.2.1q-gram長(zhǎng)度的確定

由于本文算法的性能與q-gram的長(zhǎng)度相關(guān)，這部分首先通過(guò)實(shí)驗(yàn)為每個(gè)數(shù)據(jù)集確定合適的q-gram長(zhǎng)度。在每個(gè)數(shù)據(jù)集上運(yùn)行100個(gè)查詢，每個(gè)查詢返回top-100結(jié)果。圖6展示了在q-gram長(zhǎng)度變化的情況下，本文算法的性能波動(dòng)情況。由圖6可知，本文算法在word/author/DBLP數(shù)據(jù)集上性能最好時(shí)q-gram的長(zhǎng)度分別為2、2、6，因此，在后續(xù)實(shí)驗(yàn)中，本文算法的運(yùn)行時(shí)間都是基于這里確定的q-gram長(zhǎng)度。

圖5 數(shù)據(jù)集字符串長(zhǎng)度分布

圖6 不同q-gram 長(zhǎng)度運(yùn)行時(shí)間

4.2.2 過(guò)濾效果比較

由于本文得到的Range算法是二進(jìn)制可執(zhí)行代碼，沒(méi)有算法運(yùn)行過(guò)程中的統(tǒng)計(jì)信息，因此這里的過(guò)濾效果僅展示本文方法之間的比較。

由表3可知，通過(guò)長(zhǎng)度跳躍索引進(jìn)行過(guò)濾，在求解top-10結(jié)果時(shí)，本文算法無(wú)需計(jì)算所有字符串(每個(gè)數(shù)據(jù)集的字符串?dāng)?shù)量見(jiàn)表2)的編輯距離。對(duì)于word、author、DBLP數(shù)據(jù)集來(lái)說(shuō)，需要計(jì)算編輯距離的字符串?dāng)?shù)量分別為22 488、279 046、976（表3第5列），比例分別為相應(yīng)數(shù)據(jù)集中字符串總量的3/20, 1/5, 1/100。進(jìn)而，通過(guò)提出的自適應(yīng)計(jì)數(shù)過(guò)濾技術(shù)，在驗(yàn)證結(jié)果時(shí)計(jì)算編輯距離的字符串?dāng)?shù)量分別為9 266、134 560、141，和不使用計(jì)數(shù)過(guò)濾技術(shù)相比，需要計(jì)算編輯距離的字符串?dāng)?shù)量分別為原來(lái)的2/5, 12/25, 7/50。

另外，從表3的第3列可知，算法top-kLength Count需要的過(guò)濾時(shí)間比算法top-kLength稍長(zhǎng)，但是驗(yàn)證階段所用時(shí)間得到了顯著的改善（表3第4列），原因在于通過(guò)計(jì)數(shù)過(guò)濾，減少了需要計(jì)算編輯距離的字符串?dāng)?shù)量（表3第5列）。

4.2.3 查詢時(shí)間比較

圖 7給出本文的算法 top-kLengthCount和Range算法的運(yùn)行時(shí)間比較。由圖 7(a)可知，對(duì)于word數(shù)據(jù)集而言，算法top-kLengthCount在k小于18的時(shí)候要比Range算法慢，但是隨著k值的增大本文的算法要比 Range算法更高效。原因在于Range算法采用一種遞進(jìn)的方式來(lái)計(jì)算top-k結(jié)果，需要計(jì)算所有字符串的前綴，當(dāng)k值較小的時(shí)候，需要計(jì)算的字符串前綴的數(shù)量少，運(yùn)行時(shí)間比較短；但隨著k值逐步增大，需要計(jì)算前綴字符串?dāng)?shù)量迅速增多(根據(jù)文獻(xiàn)[6]，當(dāng)k從10變到100時(shí)，需要處理的字符串前綴數(shù)量增長(zhǎng)了 5倍多)，需要的運(yùn)行時(shí)間相應(yīng)變長(zhǎng)，而本文的算法 top-kLengthCount按照與查詢串長(zhǎng)度差遞增的方式訪問(wèn)倒排表中的字符串，同時(shí)使用計(jì)數(shù)過(guò)濾并結(jié)合提前終止條件來(lái)減少需要處理的字符串，當(dāng)k值增大時(shí)，需要處理的字符串?dāng)?shù)量的增長(zhǎng)沒(méi)有Range算法增長(zhǎng)的字符串前綴數(shù)量(當(dāng)k從10變到100時(shí)，需要處理的字符串前綴數(shù)量增長(zhǎng)了3倍)，因而當(dāng)k值增大時(shí)，可以獲得比Range算法更好的處理性能。

表3 3個(gè)數(shù)據(jù)集上處理top-10結(jié)果時(shí)本文算法的性能比較

圖7 top-kLengthCount算法與Range算法性能對(duì)比

隨著字符串?dāng)?shù)量和平均長(zhǎng)度的同時(shí)增長(zhǎng)，本文的算法top-kLengthCount在author和DBLP數(shù)據(jù)集上較 Range算法的優(yōu)勢(shì)更明顯(如圖 7(b)和圖 7(c)所示)。原因在于，字符串?dāng)?shù)量以及字符串長(zhǎng)度同時(shí)增加(word數(shù)據(jù)集包含146 033個(gè)字符串，而author和DBLP數(shù)據(jù)集分別包含1 266 150和156 506個(gè)字符串，長(zhǎng)度由8.76增長(zhǎng)到151.9)會(huì)導(dǎo)致字符串前綴數(shù)量的成倍增加，加之相應(yīng)的查詢串變長(zhǎng)，Range需要處理的字符串前綴數(shù)量的增長(zhǎng)速度更快，所需時(shí)間更長(zhǎng)。與之對(duì)應(yīng)，本文算法基于自適應(yīng)的長(zhǎng)度和計(jì)數(shù)過(guò)濾，可以過(guò)濾很多字符串而不用處理。由圖7(b)和圖7(c)可知，當(dāng)k取100時(shí)，本文的算法在author數(shù)據(jù)集上比Range 算法快4.5倍，在DBLP數(shù)據(jù)集上比Range算法快2.5倍。

4.3 擴(kuò)展性

圖8展示的是本文算法top-kLengthCount在不同k值和不同大小的數(shù)據(jù)集上處理100個(gè)查詢的平均運(yùn)行時(shí)間。

圖8 可擴(kuò)展性

由圖8可知，隨著數(shù)據(jù)集和k值的增大，算法top-kLengthCount體現(xiàn)出了較好的擴(kuò)展性。以author數(shù)據(jù)集為例，當(dāng)k=100、字符串個(gè)數(shù)是900 000時(shí)，運(yùn)行時(shí)間是326 ms，當(dāng)數(shù)據(jù)集是1 200 000個(gè)字符串時(shí)，運(yùn)行時(shí)間是390 ms。在DBLP數(shù)據(jù)集上，當(dāng)k=10時(shí)，基于150 000字符串的運(yùn)行時(shí)間比基于120 000和90 000個(gè)字符串的運(yùn)行時(shí)間還要少，原因在于算法top-kLengthCount按照與查詢字符串的長(zhǎng)度差遞增的方式訪問(wèn)倒排表，隨著數(shù)據(jù)集的增大，在局部倒排表中有更多的相似字符串。按照早終止策略，可以更早地得到 top-k結(jié)果，所以在數(shù)據(jù)集增大的時(shí)候，運(yùn)行時(shí)間會(huì)更短。

5 結(jié)束語(yǔ)

針對(duì)已有 top-k相似字符串算法存在的冗余計(jì)算問(wèn)題，提出了基于長(zhǎng)度跳躍索引的2種高效的自適應(yīng)過(guò)濾策略，包括基于字符串長(zhǎng)度差遞增方式的過(guò)濾策略和基于當(dāng)前 top-k結(jié)果的動(dòng)態(tài)計(jì)數(shù)過(guò)濾策略，以減少字符串之間的編輯距離計(jì)算次數(shù)，針對(duì)查詢串對(duì)應(yīng)的倒排表存在不能正確求解 top-k結(jié)果的問(wèn)題，提出了查詢字符串與不匹配字符串集合的編輯距離下界來(lái)進(jìn)一步減少字符串之間編輯距離的計(jì)算次數(shù)。實(shí)驗(yàn)結(jié)果表明，被處理的字符串越長(zhǎng)，本文方法的優(yōu)勢(shì)越明顯；k=100時(shí)，所提算法比現(xiàn)有的最好算法快2～4倍。

[1] LI C, LU J, LU Y. Efficient merging and filtering algorithms for approximate string queries[A]. ICDE[C]. 2008. 257-266.

[2] KAHVECI T, SINGH A K. Efficient index structures for string databases[A]. VLDB[C]. 2001.351-360.

[3] ZHANG Z, HADJIELEFTHERIOU M, OOI B C,et al. Bed-tree: an all-purpose index structure for string similarity query based on edit distance[A]. SIGMOD[C]. 2010.915-926.

[4] CHAUDHURI S, GANJAM K, GANTI V,et al. Robust and efficient fuzzy match for online data cleaning[A]. SIGMOD[C]. 2003.313-324.

[5] HADJIELEFTHERIOU M, KOUDAS N, SRIVASTAVA D. Incremental maintenance of length normalized indexes for approximate string matching[A]. SIGMOD[C]. 2009.429-440.

[6] LI G, DENG D, FENG J,et al. Top-kString Similarity Search with Edit-Distance Constraints[A]. ICDE[C]. 2013.925-936.

[7] YANG Z, YU J, KITSUREGAWA M. Fast algorithms for top-kapproximate string matching[A]. AAAI[C]. 2010.1467-1463.

[8] GRAVANO L, IPEIROTIS P G, JAGADISH H V,et al. Approximate string joins in a database (almost) for free[A]. VLDB[C]. 2001. 491-500.

[9] XIAO C, WANG W, LIN X. Ed-join: an efficient algorithm for similarity joins with edit distance constraints[A]. VLDB[C]. 2008.933-944.

[10] XIAO C, WANG W, LIN X,et al. Top-kset similarity joins[A].ICDE[C]. 2009.916-927.

[11] QIN J, WANG W, LU Y,et al. Efficient exact edit similarity query processing with the asymmetric signature scheme[A]. SIGMOD[C].2011.1033-1044.

[12] ARASU A, GANTI V, KAUSHIK R. Efficient exact set-similarity joins[A]. VLDB[C]. 2006. 918-929

[13] CHAUDHURI S, GANTI V, KAUSHIK R. A primitive operator for similarity joins in data cleaning[A]. ICDE[C]. 2006.5-16.

[14] SARAWAGI S, KIRPAL A. Efficient set joins on similarity predicates[A]. SIGMOD[C]. 2004.743-754.

[15] BAYARDO R J, MA Y, SRIKANT R. Scaling up all pairs similarity query[A]. WWW[C]. 2007.131-140

[16] WANG J, LI G, FENG J. Trie-join: efficient trie-based string similarity joins with edit-distance constraints[A]. VLDB[C]. 2010. 1219-1230.

[17] WANG J, LI G, FENG J. Fast-join: An efficient method for fuzzy token matching based string similarity join[A]. ICDE[C]. 2011.458-469.

[18] LI G, DENG D, WANG J,et al. Pass-join: A partition-based method for similarity joins[A]. VLDB[C]. 2011.253-264.

[19] WAGNER R A, ANDFISCHER M J. The string-to-string correction problem[A]. ACM[C]. 1974.168-173.