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

安徽大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，合肥 230601

1 引言

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

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

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

top-k問(wèn)題剛被提出的時(shí)候，人們通常使用基于閾值的字符串相似性查找算法來(lái)解決該類(lèi)問(wèn)題。但是因?yàn)樵谶M(jìn)行top-k查找的時(shí)候需要枚舉出多種不同的閾值，從而引起大量不必要的計(jì)算。文獻(xiàn)[11-13]給出了top-k字符串相似性查找相關(guān)算法，但是算法存在編輯距離的重復(fù)計(jì)算和查找效率低的問(wèn)題。本文針對(duì)上述問(wèn)題，提出了基于分割思想的Pb-topk算法和PbCount-topk算法，通過(guò)對(duì)不滿(mǎn)足條件的字符串進(jìn)行剪枝，從時(shí)間上提高了top-k問(wèn)題的查找效率。

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

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

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

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

2 相關(guān)工作

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

本文方法均基于分割思想，與之相比上述方法有以下缺點(diǎn)：首先，基于q-gram的方法相比基于分割的方法有著低的剪枝效率，因?yàn)闉榱吮苊鈦G解，q的取值不能過(guò)大，然而q過(guò)小又會(huì)限制剪枝效果。其次，基于q-gram的方法不適用于短字符串的查找。最后，基于Bed-tree的方法不適用于長(zhǎng)字符串的查找。

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

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

3 背景知識(shí)

3.1 問(wèn)題定義

字符串相似性查找問(wèn)題是查尋字符串集合中與查找串相似的字符串。本文用編輯距離來(lái)度量?jī)蓚€(gè)字符串間的相似程度。編輯距離是指把一個(gè)字符串轉(zhuǎn)換為另一個(gè)字符串所需的最少編輯操作（插入、刪除、替換）次數(shù)。本文用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,基于閾值的字符串相似性查找返回結(jié)果R={“emetic”,“gemetic”},它們和q的編輯距離分別為2和1。

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

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

例2查找串q=“geametic”,對(duì)于表1中的集合S,top-2返回的結(jié)果集R={“emetic”,“gemetic”},因?yàn)樗鼈兣cq的編輯距離分別為2和1，而S中剩下的字符串與q的編輯距離都大于等于2。

3.2 索引結(jié)構(gòu)

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

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

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

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

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

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

為了便于表述，下面給出一些符號(hào)的定義。sl表示S中長(zhǎng)度為l的字符串集合，L表示倒排索引，Ll表示長(zhǎng)度為l字符串對(duì)應(yīng)的倒排索引，表示Ll中第i個(gè)片段對(duì)應(yīng)的倒排索引。

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

Fig.1 Inverted index ofs6圖1 s6對(duì)應(yīng)的倒排索引

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

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

4.1 PBsearch算法

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

證明假設(shè)s中任何一個(gè)片段都不包含于查找串q中，則每個(gè)片段至少需要一次編輯操作才能包含于q中，因?yàn)橛笑?1個(gè)片段，編輯距離至少為τ+1。根據(jù)反證法可知引理1正確。 □

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

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

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

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

PBsearch算法首先按照長(zhǎng)度和詞典序?qū)蟂中的字符串進(jìn)行排序，對(duì)滿(mǎn)足長(zhǎng)度約束的字符串（即，|q|-τ≤|s|≤|q|+τ)且內(nèi)存中不存在對(duì)應(yīng)長(zhǎng)度的索引，則建立索引并對(duì)每一個(gè)Lil中的字符串按照詞典序排序，否則直接調(diào)用已存在的索引，然后根據(jù)索引利用二分查找找到與q相似的字符串。其中，第5～13行為過(guò)濾階段，第14行為驗(yàn)證階段。偽代碼如算法1所示。

算法1PBsearch(S,q,τ)

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

q,查找串

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

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

1.Begin

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

個(gè)子集中的字符串按照詞典序排序

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

4.if!Li

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

10.ifflag

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

12.fors∈Sl

13.ifN(s,q)≥1

14.ifED(s,q)≤τ

15.C=C∪s

16.returnC

17.End

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

算法1的時(shí)間復(fù)雜度包含兩方面：過(guò)濾時(shí)間和驗(yàn)證時(shí)間。過(guò)濾階段對(duì)長(zhǎng)度在|q|-τ≤l≤|q|+τ范圍內(nèi)的字符串進(jìn)行過(guò)濾，時(shí)間復(fù)雜度為驗(yàn)證階段即驗(yàn)證q和s能否在閾值τ內(nèi)相互轉(zhuǎn)換，時(shí)間復(fù)雜度為

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

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

Fig.2 Inverted list of example 7圖2 例7對(duì)應(yīng)的倒排表

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

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

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

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

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

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

定理1給定字符串s和查找串q,若q對(duì)應(yīng)的匹配片段不滿(mǎn)足One-Off條件，則一定會(huì)產(chǎn)生無(wú)效匹配。

證明假設(shè)q1、q2為q對(duì)應(yīng)的兩個(gè)匹配片段，若q1、q2不滿(mǎn)足One-Off條件，則一定共享了同一位置的字符。因此，會(huì)產(chǎn)生無(wú)效匹配。 □

算法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

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

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

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

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

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

因?yàn)椴粷M(mǎn)足閾值τ的字符串與查找串一定是不相似的，所以對(duì)在過(guò)濾階段被剪枝的字符串不需計(jì)算其編輯距離，只需對(duì)候選集中的字符串進(jìn)行真實(shí)編輯距離的計(jì)算。本文提出了一個(gè)高效的編輯距離求解算法——MultiThreshold算法。

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

其中，dr表示右側(cè)子串的長(zhǎng)度差；τ表示總的閾值。

若字符串s和q的每個(gè)不匹配片段的編輯距離均滿(mǎn)足對(duì)應(yīng)的局部閾值τi,則s和q的編輯距離計(jì)算如式（3），一旦出現(xiàn)不滿(mǎn)足τi的情況，則終止編輯距離的計(jì)算。

其中，size為s和q重新劃分后不匹配片段的個(gè)數(shù)。

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

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

Input：s,待驗(yàn)證的字符串

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//根據(jù)式（2）計(jì)算局部閾值

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

5.fori=1 tosize-1//判斷各對(duì)應(yīng)片段是否滿(mǎn)足局部閾值

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

7.ifvec_ed[i]＞τi//不滿(mǎn)足，則提前結(jié)束

8.return

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

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

11.edit+=vec_ed[j]

12.ifedit＜τ

13.C=C∪s

14.returnC

15.End

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

算法3中求s和q的非匹配片段集合的時(shí)間復(fù)雜度均為O(x+1),其中x為N(s,q)中元素個(gè)數(shù)。進(jìn)行編輯距離判斷的時(shí)間復(fù)雜度為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右側(cè)的長(zhǎng)度差為5-4=1,m2右側(cè)的長(zhǎng)度差為3-1=2。因此，s1和q1的局部閾值τ1=τ-1=3,s1+s2和q1+q2的局部閾值τ2=τ-2=2。因?yàn)镋D(s1,q1)=4＞3,所以舍棄s。

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

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

5.1 Pb-topk算法

定理2假設(shè)查詢(xún)串為q,字符串集合為S,當(dāng)前top-k集合中字符串與q的最大編輯距離為τk,若集合S中剩下的任意字符串s與q的長(zhǎng)度差| ||s|-|q|≥τk,則當(dāng)前top-k集合中的結(jié)果為最終結(jié)果。

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

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

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

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

q,查找串

k,結(jié)果個(gè)數(shù)

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

1.Begin

2.d=0

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

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

5.whiled≤UBQdo//長(zhǎng)度差值小于當(dāng)前最大編輯距離，則循環(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為當(dāng)前最大編輯距離

11.d++

12.else

13.d++

14.continue

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

16.returnQ

17.End

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

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

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

5.2 PbCount-topk算法

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

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

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

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

q,查找串

k,結(jié)果個(gè)數(shù)

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

1.Begin

2.d=0

3.List_Push(S,k,q)//把S按照先長(zhǎng)度后詞典序排列，把k個(gè)長(zhǎng)度和q最接近的字符串加入Q中，求得當(dāng)前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根據(jù)匹配個(gè)數(shù)n重新分類(lèi)為不同的子集Cn

9.forn=maxntominn

10.ifτ+1-n≥UBQ//當(dāng)前最大編輯距離滿(mǎn)足定理3

11.for?s∈Cn

12.ifED(s,q)＜UBQ

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

14.else

15.break

16.d++

17.else

18.d++

19.continue

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

21.returnQ

22.End

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

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

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

6 實(shí)驗(yàn)及結(jié)果分析

將在3個(gè)真實(shí)數(shù)據(jù)集上驗(yàn)證本文算法的性能。

6.1 實(shí)驗(yàn)條件

實(shí)驗(yàn)平臺(tái)配置：Intel?CoreTMi3 CPU@3.70 GHz，4 GB內(nèi)存，500 GB硬盤(pán)，64位Windows7操作系統(tǒng)，實(shí)驗(yàn)程序用C++編寫(xiě)，編譯軟件為VS2013。實(shí)驗(yàn)使用了3個(gè)真實(shí)數(shù)據(jù)集：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個(gè)數(shù)據(jù)集的具體信息如表2所示。圖3展示了3個(gè)數(shù)據(jù)集中字符串的長(zhǎng)度分布情況。

6.2 驗(yàn)證基于閾值的字符串相似性查找算法性能

實(shí)驗(yàn)過(guò)程中，對(duì)每個(gè)數(shù)據(jù)集首先隨機(jī)選取20個(gè)字符串作為查找串，然后針對(duì)每個(gè)查找串計(jì)算找出對(duì)應(yīng)數(shù)據(jù)集中所有滿(mǎn)足閾值的字符串所需要的時(shí)間，最后計(jì)算出找到20個(gè)查找串滿(mǎn)足閾值的所有相似字符串所需的平均時(shí)間。

Table 2 Description of datasets表2 數(shù)據(jù)集描述

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

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

Fig.3 String length distribution of datasets圖3 數(shù)據(jù)集字符串長(zhǎng)度分布

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

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

6.3 驗(yàn)證top-k字符串相似性查找算法性能

首先對(duì)提出的PbCount-topk算法和Pb-topk算法進(jìn)行了比較，實(shí)驗(yàn)結(jié)果如圖6所示。可以看出在3個(gè)數(shù)據(jù)集上PbCount-topk算法的執(zhí)行效率都有明顯的提高，因?yàn)閷?duì)匹配子串的個(gè)數(shù)進(jìn)行分組后，可以提前結(jié)束那些匹配個(gè)數(shù)較少的字符串，減少了對(duì)編輯距離的不必要的計(jì)算，從而縮短了運(yùn)行時(shí)間。但也存在一些例外，例如在Word數(shù)據(jù)集上，當(dāng)k=10時(shí)Pbtopk的效率略?xún)?yōu)于PbCount-topk，這是因?yàn)樵诎凑掌ヅ鋽?shù)目進(jìn)行分組計(jì)算時(shí)所有分組均滿(mǎn)足τ+1-n＜UBQ的條件，沒(méi)有出現(xiàn)提前終止閾值判斷的情況。

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

圖8給出了算法PbCount-topk在不同k值和不同大小的數(shù)據(jù)集上的平均運(yùn)行時(shí)間。由圖8可知，隨著數(shù)據(jù)集和k值的增大，算法PbCount-topk有較好的可擴(kuò)展性。例如，在Author數(shù)據(jù)集上，當(dāng)k=10,字符串個(gè)數(shù)是300 000時(shí)的平均時(shí)間為5.51 s，當(dāng)字符串個(gè)數(shù)是500 000時(shí)的平均時(shí)間為7.42 s。字符串長(zhǎng)度增加了67%，而時(shí)間僅增加了35%。但是，在Word數(shù)據(jù)集和Author數(shù)據(jù)集上算法的執(zhí)行效率出現(xiàn)了少許波動(dòng)。例如，在Word數(shù)據(jù)集上，當(dāng)k=5,字符串個(gè)數(shù)為60 000時(shí)的平均時(shí)間大于字符串個(gè)數(shù)為80 000時(shí)的平均時(shí)間。這是因?yàn)楸疚乃惴ㄊ前凑臻L(zhǎng)度差遞增來(lái)獲取近似字符串的，隨著數(shù)據(jù)集的增大，在某些長(zhǎng)度大的倒排表中有更多的近似字符串，所以可以更早地結(jié)束查找過(guò)程，運(yùn)行時(shí)間也會(huì)相應(yīng)減少。

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

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算法的可擴(kuò)展性

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

[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.