劉慧婷，黃厚柱，劉志中，趙 鵬

安徽大學 計算機科學與技術學院，合肥 230601

1 引言

字符串相似性查找在數據清洗、數據集成、相似性用戶推薦、文本抄襲檢查等方面有著廣泛的應用。給定一個字符串集合以及一個查找串，字符串相似性查找即找到集合中所有與查找串相似的字符串。在進行字符串相似性查找的過程中通常會給定一個相似性函數來度量兩個字符串間的相似程度，例如漢明距離（hamming distance）、編輯距離（edit distance）、余弦度量（cosine metric）以及杰卡德度量（Jaccard metric）等[1-2]。在這些相似性函數中，余弦度量和杰卡德度量是基于標號的字符串相似性度量函數，即將字符串分割為一系列標號，把字符串表示為以分割后標號組成的集合，然后以集合間的相似性等價地表示字符串間的相似性；編輯距離和漢明距離是基于操作的字符串相似性度量函數，即通過插入、刪除或替換操作的次數來判斷字符串間是否相似。本文所提算法針對對字符串進行插入、刪除或替換操作的情況。其中，編輯距離的應用最為廣泛。因此，本文研究基于編輯距離的字符串相似性查找，但本文算法同樣適用于漢明距離。

字符串的相似性查找可以分為兩類：一類是基于閾值的字符串相似性查找。對于給定的字符串集合S,查找串q以及閾值τ,基于閾值的字符串相似性查找即找到S中所有和q滿足閾值τ相似的字符串。它在現實世界中有著廣泛的應用，例如DNA條形碼是指生物體內的能夠代表物種的、標準的、有足夠變異、易擴增且相對較短的DNA片段，在進行物種鑒定的時候可以把該未知物種的DNA條形碼與基因庫中的DNA片段進行對比，進而鑒定物種的類別。另一類是top-k字符串相似性查找。對于給定的字符串集合S和查找串q,top-k字符串相似性查找即找到S中和q最相似的k個字符串。它在現實生活中的應用也很廣泛，例如在生物信息領域，不同生物體中的相似DNA片段表明這些生物體是有關聯的，可以通過字符串相似性查詢找到一個生物體的top-k相似基因序列，用于疾病預測和新藥品研發(fā)[3]。

目前基于閾值的字符串相似性查找研究多是基于過濾-驗證框架的。在過濾階段首先把集合中的字符串分割為不同的片段，然后把查找串也按照相應的長度進行劃分，最后根據如果兩個字符串相似則必須滿足一定數量的片段相匹配的條件，得到候選集合。文獻[4-9]對過濾方法進行了研究，提出的過濾方法有：長度過濾、數量過濾、位置過濾和前綴過濾。本文則在過濾階段首次加入One-Off條件[10]過濾掉一些無效匹配片段，并在驗證階段對產生的候選集合進行編輯距離驗證得到最終結果。其中，對編輯距離的驗證是處理該類問題的關鍵。由于用傳統(tǒng)的動態(tài)規(guī)劃算法來計算編輯距離比較耗時，本文提出了MultiThreshold算法對編輯距離進行驗證，可以很好地解決編輯距離的計算耗時問題。

top-k問題剛被提出的時候，人們通常使用基于閾值的字符串相似性查找算法來解決該類問題。但是因為在進行top-k查找的時候需要枚舉出多種不同的閾值，從而引起大量不必要的計算。文獻[11-13]給出了top-k字符串相似性查找相關算法，但是算法存在編輯距離的重復計算和查找效率低的問題。本文針對上述問題，提出了基于分割思想的Pb-topk算法和PbCount-topk算法，通過對不滿足條件的字符串進行剪枝，從時間上提高了top-k問題的查找效率。

本文主要工作和創(chuàng)新如下：

（1）采用分割思想解決字符串的相似性查找問題。對于基于閾值的字符串相似性查找問題，提出了基于分割思想和過濾-驗證框架的PBsearch（partitionbased search）算法。在過濾階段，首次加入One-Off條件過濾掉一些無效匹配，有利于在驗證階段對字符串進行重新劃分；在驗證階段，提出了MultiThreshold驗證算法，使得在對候選集進行驗證的過程中驗證效率大幅度提高。

（2）對于top-k字符串相似性查找問題，提出了基于差值遞增的Pb-topk（partition-based topk）算法，減少了需要處理的字符串數量；為了進一步縮小候選集的規(guī)模，提出了基于匹配數目劃分的PbCount-topk（partition-based count topk）算法，提高了top-k問題的求解效率。

（3）通過在真實數據集上比較本文提出的算法和現存的一些算法，證明了PBsearch算法可以有效地降低編輯距離的驗證時間，Pb-topk算法和PbCount-topk算法可以減小候選集的大小，提高了基于閾值的字符串相似性查找和top-k字符串相似性查找的查找效率。

2 相關工作

很多方法被提出用來解決基于閾值的字符串相似性查找問題[4-6,14-19]。其中，大多數方法是基于過濾-驗證框架的[5-6,14-16]。文獻[17]首次提到用基于q-gram的方法解決字符串相似性查找問題。隨后許多適用于q-gram索引的過濾策略被提出，例如長度過濾[8]、數量過濾[7]、前綴過濾[4]、位置過濾[9]等。文獻[4-5,18-20]均采用基于q-gram的方法?；趒-gram的方法雖然具有高效的過濾策略，但是它們在對候選集進行驗證時的處理效果不佳。基于q-gram的方法可分為對稱特征方法和非對稱特征方法。完全使用qgram的方法叫作對稱特征方法，而查找串用q-gram，非查找串用q-chunk，或者反過來的方法叫作非對稱特征方法。相比于對稱特征方法，它在過濾階段的匹配次數更少，因此剪枝效率更高。其中，文獻[18-20]使用了對稱特征方法；文獻[4-5]使用了非對稱特征方法。文獻[13]提出了Bed-tree方法，該方法采用B+-樹的方式對字符串建立索引，但是該方法不能對非相似字符串進行有效的剪枝。由于基于q-gram的方法和基于B+-樹的方法無法同時適用于長字符串和短字符串的相似性查找，文獻[1]提出了基于分割思想的自適應算法，并提出了一系列基于分割方案的過濾和驗證方法。前述的基于q-gram的過濾策略同樣適用于基于分割思想的方法。目前驗證階段有效的方法有Length Aware方法[1]和SingleThreshold方法[14]等。

本文方法均基于分割思想，與之相比上述方法有以下缺點：首先，基于q-gram的方法相比基于分割的方法有著低的剪枝效率，因為為了避免丟解，q的取值不能過大，然而q過小又會限制剪枝效果。其次，基于q-gram的方法不適用于短字符串的查找。最后，基于Bed-tree的方法不適用于長字符串的查找。

傳統(tǒng)使用基于閾值的字符串相似性查找方法解決top-k字符串相似性查找問題時，需要枚舉出所有可能的閾值再進行查找，導致出現大量不必要的計算。文獻[11]提出了基于q-gram的方法來解決top-k問題，該方法需要動態(tài)地調整q的大小，然后對不同的q建立倒排索引，因此算法的時間空間復雜度較高。文獻[13]中的Bed-tree方法也可用于top-k問題，該方法通過B+-樹對字符串的特征建立索引，但是它需要枚舉很多閾值，因此查找效率較低。文獻[12]提出了基于范圍的方法，避免求解編輯距離時的大量重復計算。但是該方法在處理長字符串時非常消耗內存，而且搜索效率較低。以往基于q-gram索引的方法都是使用短且精確的q-gram匹配策略得到候選集合，文獻[21]提出了支持KNN（k-nearest neighbors）序列搜索的方法，該方法可以使用更長但是近似的qgram匹配策略，查找出近似的top-k結果集。因此，得到的最終結果可能是不精確的。

除了上述兩種情況，與字符串相似性查找相關的工作還有字符串的相似性連接。給定兩個字符串集合，字符串的相似性連接即找到兩個集合中所有的近似字符串對。目前處理字符串相似性連接的方法多是基于q-gram來進行研究的，主要的算法有All-Pairs-Ed（all pairs edit similarity）[22]、PP-Join（positional prefix join）[23]和ED-Join（edit similarity join）[24]等。

3 背景知識

3.1 問題定義

字符串相似性查找問題是查尋字符串集合中與查找串相似的字符串。本文用編輯距離來度量兩個字符串間的相似程度。編輯距離是指把一個字符串轉換為另一個字符串所需的最少編輯操作（插入、刪除、替換）次數。本文用ED(r,s)表示字符串r和s間的編輯距離，例如r=“agct”,s=“acgt”,ED(r,s)=2。

定義1（基于閾值的字符串相似性查找）給定字符串集合S，查找串q以及閾值τ,基于閾值的字符串相似性查找即找到所有的字符串s∈S,使得ED(s,q)≤τ。

例1表1是字符串集合S中的字符串，查找串q=“geametic”,τ=2,基于閾值的字符串相似性查找返回結果R={“emetic”,“gemetic”},它們和q的編輯距離分別為2和1。

Table 1 String collectionS表1 字符串集合S

定義2（top-k字符串相似性查找）給定字符串集合S，查找串q,top-k字符串相似性查找即返回結果集R?S,其中|R|=k,并且對任意的r∈R和s∈S-R,都有ED(r,q)≤ED(s,q)。

例2查找串q=“geametic”,對于表1中的集合S,top-2返回的結果集R={“emetic”,“gemetic”},因為它們與q的編輯距離分別為2和1，而S中剩下的字符串與q的編輯距離都大于等于2。

3.2 索引結構

本文采用基于分割的思想解決字符串的相似性查找問題。

定義3（字符串分割）給定字符串s,編輯距離的閾值τ,如果|s|≥τ+1,則把它分割為τ+1個互不相交的片段。

例 3字符串s=“similarity”,τ=2,則把s分割為τ+1=3段，可能的結果為{“sim”,“ila”,“rity”}。

對一個字符串s,把它分割為τ+1段可以有多種方式，本文討論的分割需要滿足一定規(guī)則。片段長度越大，該片段出現在其他字符串中的概率越小，可能會使一些與查找串相似的字符串丟失；片段長度越小，該片段出現在其他字符串中的概率越大，則候選集中字符串的個數越多，增加了驗證時間。因此，片段長度過大或過小都會降低過濾效率，本文把字符串進行均勻分割。

定義4（字符串均勻分割）給定字符串s,編輯距離的閾值τ,如果|s|≥τ+1，則把它分割為τ+1個互不相交的片段，且前τ+1-k個片段的長度為后k個片段的長度為其中

例4字符串s=“algorithm”,τ=3,則可分割為4段，k=9-2×4=1,因此，前三段長度為2，最后一段長度為3，結果為{“al”,“go”,“ri”,“thm”}。

為了便于表述，下面給出一些符號的定義。sl表示S中長度為l的字符串集合，L表示倒排索引，Ll表示長度為l字符串對應的倒排索引，表示Ll中第i個片段對應的倒排索引。

本文在建立倒排索引時，只對長度在[|q|-τ,|q|+τ]范圍內的字符串建立索引，其中q表示查找串。首先對長度相同的字符串進行分割處理；然后對相同序號的子串建立索引。圖1表示對表1的字符串集合s6建立的倒排索引，其中τ=2,s1=“metric”,分割為3個片段{“me”,“tr”,“ic”},它們對應的ID號為 1。同樣的方式分割s2,若對應序號的片段不同，則添加該片段及對應的ID，否則，只添加ID。

Fig.1 Inverted index ofs6圖1 s6對應的倒排索引

4 基于閾值的字符串相似性查找算法

本章提出一種基于分割思想的算法——PBsearch算法來解決基于閾值的字符串相似性查找問題。

4.1 PBsearch算法

引理1給定字符串s,查找串q和閾值τ,把s分割為τ+1段，如果s和q滿足ED(s,q)≤τ,則s中至少有一個片段包含于q。

證明假設s中任何一個片段都不包含于查找串q中，則每個片段至少需要一次編輯操作才能包含于q中，因為有τ+1個片段，編輯距離至少為τ+1。根據反證法可知引理1正確。 □

例5字符串s=“abcdef”,q=“cacd”,τ=2,則s被分割為S={“ab”,“cd”,“ef”},可知s與q有公共子串“cd”,滿足兩個字符串近似的下限1。

引理2給定字符串s和查找串q,如果字符串s和q之間的編輯距離ED(s,q)≤τ,則字符串s和查找串q之間的長度關系滿足：| ||s|-|q|≤τ。

證明對于兩個字符串s和q,假設|s|＞|q|,令Δ=|s|-|q|,經過編輯操作將s轉化為q至少需要Δ次刪除操作，即編輯距離至少為Δ，若Δ＞τ,則編輯距離大于給定的閾值。根據反證法可知引理2正確。 □

例 6字符串s=“abcdef”,q=“cacd”,| ||s|-|q|=2,因此，ED(s,q)≥2。

PBsearch算法首先按照長度和詞典序對集合S中的字符串進行排序，對滿足長度約束的字符串（即，|q|-τ≤|s|≤|q|+τ)且內存中不存在對應長度的索引，則建立索引并對每一個Lil中的字符串按照詞典序排序，否則直接調用已存在的索引，然后根據索引利用二分查找找到與q相似的字符串。其中，第5～13行為過濾階段，第14行為驗證階段。偽代碼如算法1所示。

算法1PBsearch(S,q,τ)

Input：S,待查找的字符串集合

q,查找串

τ,給定的編輯距離的閾值

Output：C={(s∈S)|ED(s,q)≤τ}

1.Begin

2.Divide(S)//把S按照長度分為不同的子集，對每一

個子集中的字符串按照詞典序排序

3.forSl(|q|-τ≤l≤|q|+τ)

4.if!Li

5. ConductIndex(Sl,τ)//對Sl建立倒排索引Ll,并對每一個中的字符串按照詞典序排序

10.ifflag

11.N(si,q)+1//si的計數器加1

12.fors∈Sl

13.ifN(s,q)≥1

14.ifED(s,q)≤τ

15.C=C∪s

16.returnC

17.End

該算法首先調用Divide(S)將字符串集合S按照先長度后詞典序排序，將S分為多個等長度的子集（第2行）；對滿足長度過濾器的集合，若內存中不存在該長度的倒排索引，則調用ConductIndex(Sl,τ)建立該長度字符串對應的倒排索引，并對相應片段中的字符串進行詞典序排序（第3～5行）；根據分割后的每一個片段，調用CreatSub(Lil,q)得到查找串的子串集合，然后在倒排索引中根據對應的字符串集合調用binarySearch(w,Lil.str)進行二分查找，得到每個字符串的計數器（第6～11行）；最后判斷該字符串是否滿足數量過濾器，對滿足數量過濾的字符串進行實際編輯距離的計算并返回結果（第12～15行）。

算法1的時間復雜度包含兩方面：過濾時間和驗證時間。過濾階段對長度在|q|-τ≤l≤|q|+τ范圍內的字符串進行過濾，時間復雜度為驗證階段即驗證q和s能否在閾值τ內相互轉換，時間復雜度為

例 7s1=“algrithm”,s2=“alaruthn”,s3=“aimgaeth”,q=“algriath”,閾值τ=2,把s1,s2和s3分割為3段建立索引，倒排表如圖2所示。對每個倒排表中的字符串按照詞典序排序，在第一個倒排表中進行二分查找后得到N(s1,q)=1,N(s2,q)=1,N(s3,q)=0。同理查找第二和第三個倒排表后得到的計數器值為N(s1,q)=2,N(s2,q)=1,N(s3,q)=0。因此，候選集為{s1,s2}。接下來對s1和s2進行驗證，ED(s1,q)=1,ED(s2,q)=4＞ 2,舍棄s2。

4.2 過濾階段的優(yōu)化

Fig.2 Inverted list of example 7圖2 例7對應的倒排表

定義5（One-Off條件）假設I1=(i1,i2,…,im),J1=(j1,j2,…,jm)為查找串q的任意兩個子串，如果對任意的1≤s,t≤m,都有is≠jt,則稱I1、J1滿足One-Off條件。

在對分割好的每一個片段進行匹配的過程中需要對查找串進行子串劃分。原始的方法是找出查找串的所有相應長度的子串。例如s6=“isometric”,q=“gemetic”,τ=3,則分割后的集合為{“is”,“om”,“et”,“ric”},當匹配片段“ric”時，要得到q的所有長度為3的子串，即{“gem”,“eme”,“met”,“eti”,“tic”}。顯然，這種分割是不必要的，例如“eme”在q中的起始位置是2，而“ric”在s6中的起始位置是7，它們的位置差大于給定的閾值，不可能滿足相似條件。因此，對查找串進行劃分時的起始位置應該在[pi-τ,pi+τ]之間，其中pi表示第i個片段在s中的起始位置。

然而，上述方法仍存在很多不必要的計算。例如，s=“isometric”,q=“tieterwrst”,τ=3,則s被分割為{“is”,“om”,“et”,“ric”},q中有“et”與之相匹配，相匹配的子串分別把s和q分為三部分，其中s為{“isom”,“et”,“ric”},q為{“ti”,“et”,“erwrst”},可以看出它們左邊部分的長度差為2，右邊部分的長度差為3，因此，它們的編輯距離至少為5。在文獻[1]中介紹了一種更加有效的子串過濾方法，該方法可以得到子串劃分的起始位置的上下限，下限LB=max(1,pi-(i-1),pi+Δ-(τ+1-i)),上限UB=min(||q-li+1,pi+(i-1),pi+Δ+(τ+1-i))。其中，Pi表示第i個片段在s中的起始位置，Δ表示兩個字符串的長度差，li表示第i個子串的長度。

引理3給定查找串q和閾值τ,對于i≤τ+1),其中，為中子串的長度。按照這種方法尋找匹配串不會出現丟解的情況。

證明假設q中存在起始位置qi不在[LB,UB]范圍內的匹配片段，則qi＜LB或qi＞UB。令qi＜LB,即qi＜max(1,pi-(i-1),pi+Δ-(τ+1-i))，由文獻[1]可知，LB和UB均由左側優(yōu)先和右側優(yōu)先得到。首先考慮左側優(yōu)先，此時，qi＜max(1,pi-(i-1))，可以得到左側的長度差為dl=pi-qi,右側長度差dr=Δ+pi-qi,因此，dl+dr=Δ+2(pi-qi)＞min(Δ+2(pi-1),Δ+2(i-1))。由于pi表示數據串中片段i的起始位置，每個片段的長度是不小于1的，因此Δ+2(pi-1)＞Δ+2(i-1),最小值只能為Δ+2(i-1)。再考慮右側優(yōu)先，此時，qi＜max(1,pi+Δ-(τ+1-i)),同理可得到dl+dr=Δ+2(qi-pi)＜max(Δ+2(1-pi),Δ+2(Δ-(τ+1-i))),Δ+2(1-pi)-(Δ+2(Δ-(τ+1-i)))=2(τ+2-Δ-pi-i),若后者取得最大值，則τ+2＜Δ+pi+i,得到Δ+2(i-1)＞τ+i-pi,因此，dl+dr＞τ+i-pi不是恒小于τ,假設錯誤；同理，qi＞UB也錯誤。根據反證法可知引理3正確。 □

上述方法對查找串進行分割后會產生一些無效匹配。例如，s=“baacomf”,q=“baconf”,τ=2,則s被分割為3段{“ba”,“ac”,“omf”},q中的“ba”與第一個子串匹配，“ac”與第二個子串相匹配。顯然，匹配過程中出現了沖突，q中的第二個位置出現在兩個匹配中。這將會對下面的驗證算法造成影響，針對該問題，本文在過濾階段加入One-Off條件過濾掉位置被重用的無效匹配。偽代碼見算法2。

定理1給定字符串s和查找串q,若q對應的匹配片段不滿足One-Off條件，則一定會產生無效匹配。

證明假設q1、q2為q對應的兩個匹配片段，若q1、q2不滿足One-Off條件，則一定共享了同一位置的字符。因此，會產生無效匹配。 □

算法2One-Off-Conflict(matching(si,q))

Input:matching(si,q),si和q相匹配的片段集合

Output:no_conflict_matching(si,q),si和q非沖突的相匹配片段集合

1.Begin

2.iter=matching(si,q).begin()

3.no_conflict_matching(si,q).push_back(*iter)//將首片段加入非沖突集合

4.foriter∈matching(si,q)

5.iter1=iter+1

6.iter2=no_conflict_matching(si,q).end()-1

7.if*iter1.firstPos＞*iter2.lastPos

8.no_conflict_matching(si,q).push_back(*iter1)

9.return no_conflict_matching(si,q)

10.End

該算法首先將匹配集合中的第一個元素加入非沖突集合（第2～3行）；然后判斷匹配集合中的余下元素與非沖突集合中的元素是否滿足One-Off條件（第4～8行）；通過比較兩個字符串的起始位置和結束位置來判斷是否滿足One-Off條件，若滿足，則添加到非沖突集合（第7～8行）；第9行返回結果集。

算法2的時間復雜度為O(x),其中x為q和si相匹配片段個數。

4.3 驗證階段的優(yōu)化

在過濾階段得到候選集以后，需要對候選集中的字符串與查找串進行真實編輯距離的驗證。給定字符串s和q,傳統(tǒng)的編輯距離計算方法是基于動態(tài)規(guī)劃思想的，它的計算公式為：

其中，當s[i]=q[j]時，δ=0,否則，δ=1。用該方法求解編輯距離的時間復雜度為O(|s|×|q|)。

因為不滿足閾值τ的字符串與查找串一定是不相似的，所以對在過濾階段被剪枝的字符串不需計算其編輯距離，只需對候選集中的字符串進行真實編輯距離的計算。本文提出了一個高效的編輯距離求解算法——MultiThreshold算法。

把字符串s和q按照匹配的片段劃分后排成一列，其中，匹配的子串一一對應，不匹配的子串一一對應。對每一個匹配子串的左側給定一個局部閾值τi,若左側部分的編輯距離不滿足該閾值，則舍棄；否則，對不匹配的子串求其局部編輯距離，然后再求和。對局部編輯距離閾值τi的計算如下所示：

其中，dr表示右側子串的長度差；τ表示總的閾值。

若字符串s和q的每個不匹配片段的編輯距離均滿足對應的局部閾值τi,則s和q的編輯距離計算如式（3），一旦出現不滿足τi的情況，則終止編輯距離的計算。

其中，size為s和q重新劃分后不匹配片段的個數。

基于式（2）和式（3），MultiThreshold算法的偽代碼如算法3所示。

算法3MultiThreshold(s,q,τ,N(s,q))

Input：s,待驗證的字符串

q,查找串

τ,給定的編輯距離的閾值

N(s,q),s和q的匹配子串集合

Output:C={s|ED(s,q)≤τ}

1.Begin

2.creat not_matching(s)and not_matching(q)withN(s,q)

3.caculateτi//根據式（2）計算局部閾值

4.size=not_matching(s).size()

5.fori=1 tosize-1//判斷各對應片段是否滿足局部閾值

6.vec_ed.push_back(ED(si,qi))

7.ifvec_ed[i]＞τi//不滿足，則提前結束

8.return

9.dd=ED(ssize,qsize),edit=dd

10.forj=1 tosize-1//計算整體編輯距離

11.edit+=vec_ed[j]

12.ifedit＜τ

13.C=C∪s

14.returnC

15.End

首先得到s和q的不匹配子串集合（第2行）；然后根據式（2）計算局部編輯距離（第3行），得到不匹配子串的個數（第4行）；判斷前size-1個不匹配子串的編輯距離與已知局部閾值的大小，若大于局部閾值則提前終止（第5～8行）；計算最后一個不匹配子串的編輯距離（第9行），根據前面已計算的子串編輯距離得到總的編輯距離（第10～11行）；最后進行整體編輯距離的判斷（第12～13行）。

算法3中求s和q的非匹配片段集合的時間復雜度均為O(x+1),其中x為N(s,q)中元素個數。進行編輯距離判斷的時間復雜度為O(size-1)。

例8s=“abna levina”,q=“ovner loevi”,閾值τ=4，s被分割為{“ab”,“na”,“l(fā)”,“ev”,“ina”}。s與q中相匹配的子串為m1=“l(fā)”,m2=“ev”,它們把s和q劃分為5段 ，其 中 不 匹 配的 3段 分 別為S={s1=“abna”,s2=“”,s3=“ina”},Q={q1=“ovner”,q2=“o”,q3=“i”},m1右側的長度差為5-4=1,m2右側的長度差為3-1=2。因此，s1和q1的局部閾值τ1=τ-1=3,s1+s2和q1+q2的局部閾值τ2=τ-2=2。因為ED(s1,q1)=4＞3,所以舍棄s。

5 top-k字符串相似性查找算法

top-k字符串相似性查找與基于閾值的字符串相似性查找相比，它沒有固定的閾值。因此，在使用基于閾值的方法求解top-k問題時需要枚舉出所有可能的閾值，很大程度上降低了算法的效率。為了解決這個問題，提出了兩個基于分割的top-k字符串相似性查找算法——Pb-topk算法和PbCount-topk算法。

5.1 Pb-topk算法

定理2假設查詢串為q,字符串集合為S,當前top-k集合中字符串與q的最大編輯距離為τk,若集合S中剩下的任意字符串s與q的長度差| ||s|-|q|≥τk,則當前top-k集合中的結果為最終結果。

證明由引理2可知，兩個字符串間的編輯距離大于等于它們之間的長度差，因此，若集合中剩余字符串與查找串間的長度差大于等于當前top-k集合中的最大編輯距離τk,則它們之間的編輯距離必定大于等于τk。 □

Pb-topk算法的基本思想是：首先，維護一個優(yōu)先隊列Q用以保存當前的top-k集合，把長度與查找串q最接近的k個字符串入列，并且把這k個字符串從集合中刪除，當前Q中最大的編輯距離UBQ作為第一次分割用的閾值τk。初始化一個差值d=0,每次處理完滿足長度差值的字符串集合后d自增1，對長度為|q|±d的字符串集合按照τk分割后建立倒排索引。若top-k集合更新了，則更新UBQ,并把UBQ作為對d自增后的字符串集合建立索引的τk。算法偽代碼如算法4所示。

算法4Pb-topk(S,q,k)

Input：S,待查找的字符串集合

q,查找串

k,結果個數

Output:優(yōu)先隊列Q中的k個字符串

1.Begin

2.d=0

3.List_Push(S,k,q)//把S按照先長度后詞典序排列，把k個長度和q最接近的字符串加入Q中，求得當前Q中字符串與q的最大編輯距離UBQ

4.τk=UBQ//將UBQ作為第一次分割用的閾值

5.whiled≤UBQdo//長度差值小于當前最大編輯距離，則循環(huán)

6.ifSl±d!=null

7.C=PBsearch(Sl±d,q,τk)

8.for?s∈C

9.ifED( )s,q＜UBQ

10.Q.push(s)//s入列并更新UBQ為當前最大編輯距離

11.d++

12.else

13.d++

14.continue

15.τk=UBQ//更新d自增后分割用的閾值

16.returnQ

17.End

在算法4中，首先初始化差值d為0（第2行），然后調用List_Push(S,k,q)把字符串集合S按照先長度后詞典序的次序排列，選擇長度與查找串q最接近的k個字符串進入優(yōu)先隊列，同時刪除這k個字符串（第3行）。初始化閾值τk為當前隊列中字符串與查找串的最大編輯距離UBQ（第4行），對于長度與查找串滿足當前差值的集合不為空的情況，先調用PBsearch(Sl±d,q,τk)得到滿足當前閾值近似的字符串集合（第7行），再對集合中的字符串進行編輯距離判斷，若小于UBQ則入列（第6～11行），更新UBQ為當前隊列中字符串與查找串的最大編輯距離（第10行）。對于集合為空的情況（第12～14行）則直接增加差值，處理完等長的字符串后，更新下次循環(huán)建立索引的閾值τk為UBQ（第15行），最后返回結果（第16行）。

算法4中首先對字符串進行排序，再初始化優(yōu)先隊列，最壞情況下時間復雜度為O(nlbn+km),其中n、k、m分別代表字符串個數、分組個數及每個分組中最大字符串個數。進行查找時最壞情況下時間復雜度為O(|C|×UBQ)。

雖然基于差值遞增的思想可以過濾大量的非近似字符串，但是Pb-topk算法得到候選集后仍需要耗時計算字符串的編輯距離，然后與當前的UBQ比較，以此判斷是否需要更新UBQ。下面將提出基于匹配數目劃分的PbCount-topk算法，對Pb-topk算法得到的候選集再次進行過濾，減少對編輯距離的計算。

5.2 PbCount-topk算法

定理3假設集合中字符串s和查找串q的相匹配的子串個數為n,如果τ+1-n≥UBQ,則應舍棄s。

證明因為s被分割為τ+1段，匹配子串的個數為n,則τ+1-n為不匹配的子串個數，而轉換兩個不匹配的子串至少需要一次編輯操作，因此，ED(s,q)≥UBQ。 □

算法5PbCount-topk(S,q,k)

Input：S,待查找的字符串集合

q,查找串

k,結果個數

Output:優(yōu)先隊列Q中的k個字符串

1.Begin

2.d=0

3.List_Push(S,k,q)//把S按照先長度后詞典序排列，把k個長度和q最接近的字符串加入Q中，求得當前Q中字符串與q的最大編輯距離UBQ

4.τk=UBQ

5.whiled≤UBQdo

6.ifSl±d!=null

7.C=PBsearch(Sl±d,q,τk)

8.Cn=Creat_Sub(C,N(s1,q))//把C根據匹配個數n重新分類為不同的子集Cn

9.forn=maxntominn

10.ifτ+1-n≥UBQ//當前最大編輯距離滿足定理3

11.for?s∈Cn

12.ifED(s,q)＜UBQ

13.Q.push(s)//s入列并更新UBQ為當前最大編輯距離

14.else

15.break

16.d++

17.else

18.d++

19.continue

20.τk=UBQ//更新d自增后分割用的閾值

21.returnQ

22.End

算法5與算法4的不同之處在第8～16行。首先，調用Creat_Sub(C,N(s1,q))把集合C按照匹配個數n的不同重新分為不同的子集（第8行）；其次，按照n的降序處理不同的子集，對滿足定理2的集合進行編輯距離的判斷并實時更新UBQ,直到遇到不滿足定理2的情況終止循環(huán)（第9～16行）。

算法5中進行查找時最壞情況下的時間復雜度為O((maxn-minn)× |Cn|×UBQ)。

例9查找串q=“geametri”,k=2,字符串集合如表1。|q|=8,首先把長度最接近的s5和s4加入優(yōu)先隊列Q并把它們從集合中刪除，ED(s5,q)=2,ED(s4,q)=3,此時UBQ=3。初始化d=0,τk=UBQ=3長度為8的集合為空，因此d++，得到d=1;先處理長度為|q|-d=7的集合，s3=“gemetic”,把該集合按照τk+1段分割建立索引，得到與q匹配子串個數N(s3,q)=2,由于τk+1-N(s3,q)=2＜3,計算ED(s3,q)=3,不更新UBQ。再處 理 長 度 為 9 的 集 合 ，s6=“isometric”,s7= “biametric”,建立索引，得到N(s6,q)=1,N(s7,q)=2,先求解匹配數大的s7,ED(s7,q)=3,不更新UBQ。因為τk+1-N(s6,q)=3 ≥ 3,所以舍棄s6。同樣處理d++后的情況。

6 實驗及結果分析

將在3個真實數據集上驗證本文算法的性能。

6.1 實驗條件

實驗平臺配置：Intel?CoreTMi3 CPU@3.70 GHz，4 GB內存，500 GB硬盤，64位Windows7操作系統(tǒng)，實驗程序用C++編寫，編譯軟件為VS2013。實驗使用了3個真實數據集：Word（http://dbgroup.cs.tsinghua.edu.cn/dd/projects/topksearch/index.html），DBLP Author（http://www.informatik.uni-trier.de/～ley/db）和 AOL Query Log（http://www.gregsadetsky.com/aol-data/）。 3個數據集的具體信息如表2所示。圖3展示了3個數據集中字符串的長度分布情況。

6.2 驗證基于閾值的字符串相似性查找算法性能

實驗過程中，對每個數據集首先隨機選取20個字符串作為查找串，然后針對每個查找串計算找出對應數據集中所有滿足閾值的字符串所需要的時間，最后計算出找到20個查找串滿足閾值的所有相似字符串所需的平均時間。

Table 2 Description of datasets表2 數據集描述

SingleThreshold[4]算 法 和 Length Aware 算 法[1]都是驗證階段的常用算法，由于SingleThreshold算法對編輯距離的驗證效率優(yōu)于Length Aware算法，在本實驗中，對兩種算法進行比較：算法SingleThres-hold和提出的MultiThreshold。SingleThreshold算法只有一個閾值，它將查找串和待查找串分割為匹配片段集合及不匹配片段集合，然后求解每個不匹配片段的局部編輯距離，將所有局部編輯距離求和后與給定的閾值進行比較。而MultiThreshold方法會給每一個不匹配子串一個額外的局部閾值以提前結束驗證。圖4給出了閾值不同時，在3個數據集上兩種算法的實驗結果?？梢钥闯鯩ultiThreshold方法優(yōu)于SingleThreshold方法，因為MultiThreshold方法可以通過比較局部閾值和相應片段的局部編輯距離的大小，若大于局部編輯距離則繼續(xù)驗證下一個片段，否則，提前結束對編輯距離的計算。

QChunk算法[10]和SegFilter算法[1]分別是基于qgram思想和分割思想的基于閾值的字符串相似性查找算法，本實驗將在3個不同的數據集Word、Author和Query Log上對提出的PBsearch算法和這兩種算法進行對比，具體結果如圖5所示。可以看出本文提出的PBsearch算法在3個數據集上實驗結果理想。例如，在Query Log數據集上τ=8時，PBsearch所用的時間為302 ms，而SegFilter和QChunk所用的時間分別為435 ms和1 573 ms。在所有的對比算法中QChunk結果最差。PBsearch算法實驗結果之所以優(yōu)于QChunk算法的原因如下：第一，本文算法是基于分割思想的，而QChunk算法基于q-gram，基于分割思想的算法除了使用q-gram中的傳統(tǒng)過濾方法外，還設計了有效的子串劃分過濾方法；第二，設計了更加有效的MultiThreshold驗證方法。PBsearch算法和SegFilter算法雖然都是基于分割思想的，但是本文算法要優(yōu)于SegFilter算法：第一，本文在建立索引后將相應倒排表中的片段按照詞典序排序，然后用二分查找尋找匹配片段，減少了尋找匹配對的時間；第二，本文設計了能夠提前結束編輯距離驗證的Multi-Threshold算法。

Fig.3 String length distribution of datasets圖3 數據集字符串長度分布

Fig.4 Comparison with verification methods of string search algorithm based on threshold圖4 基于閾值的查找算法中不同驗證方法的比較

Fig.5 Comparison of string search algorithm based on threshold圖5 基于閾值的查找算法之間的對比

6.3 驗證top-k字符串相似性查找算法性能

首先對提出的PbCount-topk算法和Pb-topk算法進行了比較，實驗結果如圖6所示?？梢钥闯鲈?個數據集上PbCount-topk算法的執(zhí)行效率都有明顯的提高，因為對匹配子串的個數進行分組后，可以提前結束那些匹配個數較少的字符串，減少了對編輯距離的不必要的計算，從而縮短了運行時間。但也存在一些例外，例如在Word數據集上，當k=10時Pbtopk的效率略優(yōu)于PbCount-topk，這是因為在按照匹配數目進行分組計算時所有分組均滿足τ+1-n＜UBQ的條件，沒有出現提前終止閾值判斷的情況。

還通過實驗把PbCount-topk算法和AQ（adaptiveq-gram）算法[11]進行了對比，在3個不同的數據集上分別選取了50個不同的字符串作為查找串，在各自對應的數據集上運行后取其平均時間。實驗在不同的數據集上基于不同的k值對兩種算法進行了對比，結果如圖7所示。可以看到本文的PbCount-topk算法在3個數據集上的效率都優(yōu)于AQ算法。原因有以下幾點：首先，基于分割思想的算法有著高效的過濾和驗證策略；其次，在建立索引時PbCount-topk算法只對滿足長度約束的字符串集合建立索引，大大減少了搜索的范圍；最后，AQ算法雖然可以自適應地改變q值的大小，但是q的初始范圍需要人為設置，而該范圍的大小需做大量實驗后才能確定，因此q的范圍不好把握。還可以看出數據集中的字符串長度越大PbCount-topk算法的優(yōu)勢越明顯。這主要是因為隨著字符串長度的增大，兩個字符串之間的編輯距離會隨之增加，這樣在建立索引時會增加分段的個數，有利于提高過濾和驗證的效率。例如，當k的取值為20時，在3個不同的數據集上AQ算法與PbCount-topk算法所用時間的比分別為1.16、1.55和2.23。

圖8給出了算法PbCount-topk在不同k值和不同大小的數據集上的平均運行時間。由圖8可知，隨著數據集和k值的增大，算法PbCount-topk有較好的可擴展性。例如，在Author數據集上，當k=10,字符串個數是300 000時的平均時間為5.51 s，當字符串個數是500 000時的平均時間為7.42 s。字符串長度增加了67%，而時間僅增加了35%。但是，在Word數據集和Author數據集上算法的執(zhí)行效率出現了少許波動。例如，在Word數據集上，當k=5,字符串個數為60 000時的平均時間大于字符串個數為80 000時的平均時間。這是因為本文算法是按照長度差遞增來獲取近似字符串的，隨著數據集的增大，在某些長度大的倒排表中有更多的近似字符串，所以可以更早地結束查找過程，運行時間也會相應減少。

7 結束語

Fig.6 Comparison of Pb-topk and PbCount-topk圖6 Pb-topk和PbCount-topk的比較

Fig.7 Comparison of different top-k string similarity search圖7 top-k相似性查找不同算法的比較

Fig.8 Scalability of PbCount-topk圖8 PbCount-topk算法的可擴展性

本文研究了字符串的相似性查找問題。針對已有的索引構建方式，提出了PBsearch算法，有效地解決了基于閾值的字符串相似性查找。該算法把One-Off條件首次用于過濾階段進行候選集的過濾，濾除了在尋找匹配對時的無效匹配，有效減少了候選集中字符串的數目；在驗證階段提出了MultiThreshold算法，通過對字符串的重新劃分，給每個不匹配片段一個局部閾值，以在驗證階段提前結束編輯距離的計算，有效地減少編輯距離的計算。同時，本文還提出了基于長度差值遞增的Pb-topk算法和匹配子串數目遞減的PbCount-topk算法，可以降低字符串的查找范圍以及對候選集中字符串的驗證數目，有效地解決top-k字符串相似性查找問題。實驗結果表明了本文算法的高效性和可擴展性。

[1]Li Guoliang,Deng Dong,Wang Jiannan,et al.PASS-JOIN:a partition-based method for similarity joins[J].Proceedings of the VLDB Endowment,2011,5(3):253-264．

[2]Jiang Yu,Deng Dong,Wang Jiannan,et al.Efficient parallel partition-based algorithms for similarity search and join with edit distance constraints[C]//Proceedings of the Joint EDBT/ICDT Workshops,Genoa,Mar 18-22,2013.New York:ACM,2013:341-348．

[3]Kahveci T,Singh A K.Efficient index structures for string databases[C]//Proceedings of 27th International Conference on Very Large Data Bases,Roma,Sep 11-14,2001.San Francisco,USA:Morgan Kaufmann Publishers Inc,2001:351-360.

[4]Chaudhuri S,Ganti V,Kaushik R.A primitive operator for similarity joins in data cleaning[C]//Proceedings of the 22nd International Conference on Data Engineering,Atlanta,Apr 3-8,2006.Washington:IEEE Computer Society,2006:5.

[5]Qin Jianbin,Wang Wei,Lu Yifei,et al.Efficient exact edit similarity query processing with the asymmetric signature scheme[C]//Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data,Athens,Jun 12-16,2011.New York:ACM,2011:1033-1044.

[6]Wang Jiannan,Li Guoliang,Feng Jianhua.Can we beat the prefix filtering?:an adaptive framework for similarity join and search[C]//Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data,Scottsdale,May 20-24,2012.NewYork:ACM,2012:85-96.

[7]Sarawagi S,Kirpal A.Efficient set joins on similarity predicates[C]//Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data,Paris,Jun 13-18,2004.New York:ACM,2004:743-754.

[8]Jin Liang,Koudas N,Li Chen.NNH:improving performance of nearest-neighbor searches using histograms[C]//LNCS 2992:Proceedings of the 9th International Conference on Extending Database Technology Advances in Database Technology,Heraklion,Mar 14-18,2004.Berlin,Heidelberg:Springer,2004:385-402.

[9]Li Chen,Lu Jiaheng,Lu Yiming.Efficient merging and filtering algorithms for approximate string searches[C]//Proceedings of the 24th International Conference on Data Engineering,Cancún,Apr 7-12,2008.Washington:IEEE Computer Society,2008:257-266.

[10]Chen Gong,Wu Xindong,Zhu Xingquan,et al.Efficient string matching with wildcards and length constraints[J].Knowledge and Information Systems,2006,10(4):399-419.

[11]Yang Zhenglu,Yu Jianjun,Kitsuregawa M.Fast algorithms for top-kapproximate string matching[C]//Proceedings of the 24th Conference on Artificial Intelligence,Atlanta,Jul 11-15,2010.Menlo Park:AAAI,2010:1467-1473.

[12]Deng Dong,Li Guoliang,Feng Jianhua,et al.Top-kstring similarity search with edit-distance constraints[C]//Proceedings of the 29th International Conference on Data Engineering,Brisbane,Apr 8-12,2013.Washington:IEEE Computer Society,2013:925-936.

[13]Zhang Zhenjie,Hadjieleftheriou M,Ooi B C,et al.Bed-tree:an all-purpose index structure for string similarity search based on edit distance[C]//Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data,Indianapolis,Jun 6-10,2010.NewYork:ACM,2010:915-926.

[14]Wang Jin,Li Guoliang,Deng Dong,et al.Two birds with one stone:an efficient hierarchical framework for top-kand threshold-based string similarity search[C]//Proceedings of the 31st International Conference on Data Engineering,Seoul,Apr 13-17,2015.Washington:IEEE Computer Society,2015:519-530.

[15]Wandelt S,Deng Dong,Gerdjikov S,et al.State-of-the-art in string similarity search and join[J].ACM SIGMOD Record,2014,43(1):64-76.

[16]Hadjieleftheriou M,Koudas N,Srivastava D.Incremental maintenance of length normalized indexes for approximate string matching[C]//Proceedings of the 2009 ACM SIGMOD International Conference on Management of Data,Providence,Jun 29-Jul 2,2009.New York:ACM,2009:429-440.

[17]Ukkonen E.Approximate string matching with q-grams and maximal matches[J].Theoretical Computer Science,1992,92(1):191-211.

[18]Gravano L,Ipeirotis P G,Jagadish H V,et al.Approximate string joins in a database(almost)for free[C]//Proceedings of 27th International Conference on Very Large Data Bases,Roma,Sep 11-14,2001.San Francisco:Morgan Kaufmann Publishers Inc,2001:491-500.

[19]Li Chen,Wang Bin,Yang Xiaochun.VGRAM:improving performance of approximate queries on string collections using variable-length grams[C]//Proceedings of the 33rd International Conference on Very Large Data Bases,Vienna,Sep 23-27,2007.New York:ACM,2007:303-314.

[20]Yang Xiaochun,Wang Bin,Li Chen.Cost-based variablelength-gram selection for string collections to support approximate queries efficiently[C]//Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data,Vancouver,Jun 9-12,2008.New York:ACM,2008:353-364.

[21]Wang Xiaoli,Ding Xiaofeng,Tung A K H,et al.Efficient and effective KNN sequence search with approximate n-grams[J].Proceedings of the VLDB Endowment,2013,7(1):1-12.

[22]Bayador R J,Ma Yiming,Srikant R.Scaling up all pairs similarity search[C]//Proceedings of the 16th International Conference on World Wide Web,Banff,May 8-12,2007.New York:ACM,2007:131-140.

[23]Xiao Chuan,Wang Wei,Lin Xuemin,et al.Efficient similarity joins for near duplicate detection[C]//Proceedings of the 17th International Conference on World Wide Web,Beijing,Apr 21-25,2008.New York:ACM,2008:131-140.

[24]Xiao Chuan,Wang Wei,Lin Xuemin.Ed-Join:an efficient algorithm for similarity joins with edit distance constraints[J].Proceedings of the VLDB Endowment,2008,1(1):933-944.