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

陳子陽，韓玉俊，王璿，周軍鋒

（1. 燕山大學 信息科學與工程學院，河北 秦皇島 066004；2. 河北省計算機虛擬技術與系統集成重點實驗室，河北 秦皇島 066004）

1 引言

top-k字符串相似性查詢在很多領域有重要應用，如數據清洗、數據集成、生物信息學和模式識別等。一個典型的例子是對文本進行拼寫檢查時，spellchecker需要從詞典庫里查找k個與用戶輸入最相似的單詞[1]。在生物信息領域，字符串相似性查詢用來找到 top-k相似基因序列，用于疾病預測和新藥品研發[2]。數據清洗會從一個實體集合找到top-k個與給定實體最相似的實體[1]。

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

針對已有方法在求解 top-k相似字符串時效率低的問題，提出了一種長度跳躍索引以及基于該索引的長度過濾策略和計數過濾策略，用以減少需要處理的字符串數量；提出無匹配特征的字符串之間的編輯距離下界，用以進一步減少需要處理的候選字符串數量。基于以上策略，提出了相應的 top-k字符串相似性查詢算法，并在不同特征的數據集上進行實驗，實驗結果驗證了本文算法的高效性和擴展性。

2 背景知識

2.1 問題定義

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

現有廣泛使用的衡量字符串相似性的標準之一是編輯距離[1～8]。2個字符串的編輯距離是將一個字符串轉換成另一個字符串所需要的最少單字符編輯操作次數，允許的單字符編輯操作有：插入、刪除和替換。符號ed(r,s) 表示字符串r和s之間的編輯距離。假設r=“srajit”,s=“seraji”，則ed(r,s) = 2表示將字符串“srajit”變為“seraji”所需的最少單字符編輯操作次數為2。

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

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

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

2.2 基本概念

q-gram和q-chunk：q-gram 是字符串中所有長度為q的子串，gq(s)表示字符串s的q-gram集合，為保證s中每個字符都有對應的q-gram，需要在字符串s結尾添加q-1個$字符。q-chunk是指字符串中長度為q且起始位置為iq(i≥ 0)的子串，字符串s的q-chunk集合是對s完整且不相交的劃分，用cq(s)表示。為了保證字符串最后一個q-chunk有q個字符，需要在s結尾添加(q-(|s|%q))%q個$字符。以字符串“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)。由于直接計算字符串之間的編輯距離代價較高，已有方法[1,3,5,8～12]在計算與給定查詢串相似的字符串時，第一步通過字符串特征進行過濾，以便縮小候選字符串的數量，進而降低第二步編輯距離計算的代價。

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

2.3 相關工作

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

圖1 倒排索引

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

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

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

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

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

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

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

3.1 top-kLength算法

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

3.1.1 基于長度跳躍索引的長度過濾策略

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

圖2 長度跳躍索引舉例

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

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

針對以上方法存在的冗余計算問題，提出一種基于長度跳躍索引的高效過濾策略，和以上方法相比，處理的字符串數量更少，且只需要一遍處理。其總體思路是根據被處理字符串和查詢串的長度差從小到大進行處理。

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

證明 假定 ed(σ,sk) =τk，因為||σ|-|r||≥τk，即σ和r的長度之差不小于τk，根據編輯距離的定義，必有 ed(σ,r)≥τk。證畢。

根據定理 1，當按照與查詢串的長度差遞增方式處理被查詢串時，如果長度差滿足定理1的條件，則可以提前終止，無需處理剩余字符串。

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

3.1.2 無匹配特征的字符串的處理策略

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

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

3.1.3 top-kLength算法描述

基于以上討論，給出了top-kLength算法。在算法的執行過程中，使用一個優先隊列Qtop-k來保存當前所求的 top-k結果，優先隊列中的元素個數上限為k。

算法1top-kLength算法

輸入：字符串集合S，查詢字符串σ，結果個數k

圖3 提前終止策略舉例

輸出：top-k相似字符串

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

3.2 top-kLengthCount算法

與用基于閾值的方法來計算 top-k相似字符串相比，雖然 top-kLength 算法避免了對字符串的重復處理，且減少了需要處理的字符串數量，但對于需要處理的每個字符串，都需要計算編輯距離，代價較高。針對以上問題，提出了自適應計數過濾策略，進一步減少需要計算編輯距離的字符串數量。

3.2.1 自適應計數過濾策略

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

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

定理 3說明，下一個被處理的字符串是否能被過濾掉，依賴于當前所求得的sk與查詢串σ的匹配特征個數。與文獻[11]不同，對于top-k相似性查詢，應用定理3時，閾值是動態調整的。在處理字符串的過程中，τk是單調遞減的，所以公共特征匹配個數的下界在不斷增大，因此可以過濾更多的字符串。

當應用定理3時，關鍵的操作是快速統計查詢串的q-chunk與被查詢串的q-gram的匹配個數。提出一種自適應的歸并跳躍策略來求解查詢串的q-chunk與被查詢串的q-gram的匹配個數，如函數adaptiveMergeSkip所示。

假設當前top-k結果中與查詢串σ編輯距離最大的字符串為sk，ed(σ,sk) =τk，則根據定理 3，后續處理的字符串和σ的匹配個數不能少于，函數adaptiveMergeSkip中用Tk表示該閾值。第2個輸入參數INVp表示根據長度跳躍索引得到的對應特定長度的局部倒排表集合。

輸入：INVp, 查詢字符串σ，結果個數k，特征匹配閾值Tk

輸出：top-k相似字符串

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

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

圖4 adaptiveMergeSkip函數舉例

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

與 merge-skip[1]使用固定閾值的方法不同，adaptiveMergeSkip 函數的閾值是動態調整的。可以看出，首先使用長度跳躍索引定位特定長度的字符串，并使用 adaptiveMergeSkip函數對局部倒排表進行處理，可以首先定位與查詢字符串較相似的字符串，所以τk可以快速降低，相應的q-gram和q-chunk的匹配個數快速增加，從而加速掃描查詢相關的倒排表。

3.2.2 top-kLengthCount算法描述

基于以上介紹的自適應計數過濾策略，給出了top-kLengthCount算法，如算法2所示。

算法2top-kLengthCount 算法

輸入：字符串集合S，查詢字符串σ，結果個數k

輸出：top-k相似字符串

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

4 實驗評估

4.1 實驗環境

實驗所用的機器配置為Intel Pentium G2020，2.90 GHz CPU，4 GB內存，操作系統為 Ubuntu 12.04 LTS。

根據文獻[6]的實驗結果，Range算法比AQ[3]、Bed-tree[4]和 Flamingo[1]更高效，因此實驗中只和Range算法進行比較，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++實現了本文中提出的算法，并使用-O3flag的GCC4.8.2進行編譯。實驗環境與Range算法完全相同。

所用數據來自3個真實數據集，分別是：1) word數據集注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，包含常用的英語單詞字符串；2) author數據集，包含作者名稱的字符串，從期刊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數據集注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，包含作者名字與文章名字連接起來的長字符串。表2給出了3個數據集的基本統計信息。圖5中展示了3個數據集中字符串的長度分布情況。由圖5可知，所有數據集的字符串長度都呈近似的正態分布，其中word和author數據集的字符串長度較短，而DBLP數據集的字符串長度較長。

對于每一個數據集，從數據集中隨機選擇了100組查詢，然后比較平均運行時間。

表2 數據集基本信息

4.2 性能比較

4.2.1q-gram長度的確定

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

圖5 數據集字符串長度分布

圖6 不同q-gram 長度運行時間

4.2.2 過濾效果比較

由于本文得到的Range算法是二進制可執行代碼，沒有算法運行過程中的統計信息，因此這里的過濾效果僅展示本文方法之間的比較。

由表3可知，通過長度跳躍索引進行過濾，在求解top-10結果時，本文算法無需計算所有字符串(每個數據集的字符串數量見表2)的編輯距離。對于word、author、DBLP數據集來說，需要計算編輯距離的字符串數量分別為22 488、279 046、976（表3第5列），比例分別為相應數據集中字符串總量的3/20, 1/5, 1/100。進而，通過提出的自適應計數過濾技術，在驗證結果時計算編輯距離的字符串數量分別為9 266、134 560、141，和不使用計數過濾技術相比，需要計算編輯距離的字符串數量分別為原來的2/5, 12/25, 7/50。

另外，從表3的第3列可知，算法top-kLength Count需要的過濾時間比算法top-kLength稍長，但是驗證階段所用時間得到了顯著的改善（表3第4列），原因在于通過計數過濾，減少了需要計算編輯距離的字符串數量（表3第5列）。

4.2.3 查詢時間比較

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

表3 3個數據集上處理top-10結果時本文算法的性能比較

圖7 top-kLengthCount算法與Range算法性能對比

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

4.3 擴展性

圖8展示的是本文算法top-kLengthCount在不同k值和不同大小的數據集上處理100個查詢的平均運行時間。

圖8 可擴展性

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

5 結束語

針對已有 top-k相似字符串算法存在的冗余計算問題，提出了基于長度跳躍索引的2種高效的自適應過濾策略，包括基于字符串長度差遞增方式的過濾策略和基于當前 top-k結果的動態計數過濾策略，以減少字符串之間的編輯距離計算次數，針對查詢串對應的倒排表存在不能正確求解 top-k結果的問題，提出了查詢字符串與不匹配字符串集合的編輯距離下界來進一步減少字符串之間編輯距離的計算次數。實驗結果表明，被處理的字符串越長，本文方法的優勢越明顯；k=100時，所提算法比現有的最好算法快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.