基于分割的字符串相似性查找算法*

刘慧婷，黄厚柱，刘志中，赵 鹏

安徽大学 计算机科学与技术学院，合肥 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相似基因序列，用于疾病预测和新药品研发[3]。

目前基于阈值的字符串相似性查找研究多是基于过滤-验证框架的。在过滤阶段首先把集合中的字符串分割为不同的片段，然后把查找串也按照相应的长度进行划分，最后根据如果两个字符串相似则必须满足一定数量的片段相匹配的条件，得到候选集合。文献[4-9]对过滤方法进行了研究，提出的过滤方法有：长度过滤、数量过滤、位置过滤和前缀过滤。本文则在过滤阶段首次加入One-Off条件[10]过滤掉一些无效匹配片段，并在验证阶段对产生的候选集合进行编辑距离验证得到最终结果。其中，对编辑距离的验证是处理该类问题的关键。由于用传统的动态规划算法来计算编辑距离比较耗时，本文提出了MultiThreshold算法对编辑距离进行验证，可以很好地解决编辑距离的计算耗时问题。

top-k问题刚被提出的时候，人们通常使用基于阈值的字符串相似性查找算法来解决该类问题。但是因为在进行top-k查找的时候需要枚举出多种不同的阈值，从而引起大量不必要的计算。文献[11-13]给出了top-k字符串相似性查找相关算法，但是算法存在编辑距离的重复计算和查找效率低的问题。本文针对上述问题，提出了基于分割思想的Pb-topk算法和PbCount-topk算法，通过对不满足条件的字符串进行剪枝，从时间上提高了top-k问题的查找效率。

本文主要工作和创新如下：

（1）采用分割思想解决字符串的相似性查找问题。对于基于阈值的字符串相似性查找问题，提出了基于分割思想和过滤-验证框架的PBsearch（partitionbased search）算法。在过滤阶段，首次加入One-Off条件过滤掉一些无效匹配，有利于在验证阶段对字符串进行重新划分；在验证阶段，提出了MultiThreshold验证算法，使得在对候选集进行验证的过程中验证效率大幅度提高。

（2）对于top-k字符串相似性查找问题，提出了基于差值递增的Pb-topk（partition-based topk）算法，减少了需要处理的字符串数量；为了进一步缩小候选集的规模，提出了基于匹配数目划分的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的方法。基于q-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的方法不适用于长字符串的查找。

传统使用基于阈值的字符串相似性查找方法解决top-k字符串相似性查找问题时，需要枚举出所有可能的阈值再进行查找，导致出现大量不必要的计算。文献[11]提出了基于q-gram的方法来解决top-k问题，该方法需要动态地调整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段可以有多种方式，本文讨论的分割需要满足一定规则。片段长度越大，该片段出现在其他字符串中的概率越小，可能会使一些与查找串相似的字符串丢失；片段长度越小，该片段出现在其他字符串中的概率越大，则候选集中字符串的个数越多，增加了验证时间。因此，片段长度过大或过小都会降低过滤效率，本文把字符串进行均匀分割。

定义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 过滤阶段的优化

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均由左侧优先和右侧优先得到。首先考虑左侧优先，此时，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)。再考虑右侧优先，此时，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 验证阶段的优化

在过滤阶段得到候选集以后，需要对候选集中的字符串与查找串进行真实编辑距离的验证。给定字符串s和q,传统的编辑距离计算方法是基于动态规划思想的，它的计算公式为：

其中，当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”,“ev”,“ina”}。s与q中相匹配的子串为m1=“l”,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算法的基本思想是：首先，维护一个优先队列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:优先队列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//长度差值小于当前最大编辑距离，则循环

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个字符串进入优先队列，同时删除这k个字符串（第3行）。初始化阈值τk为当前队列中字符串与查找串的最大编辑距离UBQ（第4行），对于长度与查找串满足当前差值的集合不为空的情况，先调用PBsearch(Sl±d,q,τk)得到满足当前阈值近似的字符串集合（第7行），再对集合中的字符串进行编辑距离判断，若小于UBQ则入列（第6～11行），更新UBQ为当前队列中字符串与查找串的最大编辑距离（第10行）。对于集合为空的情况（第12～14行）则直接增加差值，处理完等长的字符串后，更新下次循环建立索引的阈值τk为UBQ（第15行），最后返回结果（第16行）。

算法4中首先对字符串进行排序，再初始化优先队列，最坏情况下时间复杂度为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:优先队列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的情况终止循环（第9～16行）。

算法5中进行查找时最坏情况下的时间复杂度为O((maxn-minn)× |Cn|×UBQ)。

例9查找串q=“geametri”,k=2,字符串集合如表1。|q|=8,首先把长度最接近的s5和s4加入优先队列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操作系统，实验程序用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算法对编辑距离的验证效率优于Length Aware算法，在本实验中，对两种算法进行比较：算法SingleThres-hold和提出的MultiThreshold。SingleThreshold算法只有一个阈值，它将查找串和待查找串分割为匹配片段集合及不匹配片段集合，然后求解每个不匹配片段的局部编辑距离，将所有局部编辑距离求和后与给定的阈值进行比较。而MultiThreshold方法会给每一个不匹配子串一个额外的局部阈值以提前结束验证。图4给出了阈值不同时，在3个数据集上两种算法的实验结果。可以看出MultiThreshold方法优于SingleThreshold方法，因为MultiThreshold方法可以通过比较局部阈值和相应片段的局部编辑距离的大小，若大于局部编辑距离则继续验证下一个片段，否则，提前结束对编辑距离的计算。

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算法实验结果之所以优于QChunk算法的原因如下：第一，本文算法是基于分割思想的，而QChunk算法基于q-gram，基于分割思想的算法除了使用q-gram中的传统过滤方法外，还设计了有效的子串划分过滤方法；第二，设计了更加有效的MultiThreshold验证方法。PBsearch算法和SegFilter算法虽然都是基于分割思想的，但是本文算法要优于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所示。可以看出在3个数据集上PbCount-topk算法的执行效率都有明显的提高，因为对匹配子串的个数进行分组后，可以提前结束那些匹配个数较少的字符串，减少了对编辑距离的不必要的计算，从而缩短了运行时间。但也存在一些例外，例如在Word数据集上，当k=10时Pbtopk的效率略优于PbCount-topk，这是因为在按照匹配数目进行分组计算时所有分组均满足τ+1-n＜UBQ的条件，没有出现提前终止阈值判断的情况。

还通过实验把PbCount-topk算法和AQ（adaptiveq-gram）算法[11]进行了对比，在3个不同的数据集上分别选取了50个不同的字符串作为查找串，在各自对应的数据集上运行后取其平均时间。实验在不同的数据集上基于不同的k值对两种算法进行了对比，结果如图7所示。可以看到本文的PbCount-topk算法在3个数据集上的效率都优于AQ算法。原因有以下几点：首先，基于分割思想的算法有着高效的过滤和验证策略；其次，在建立索引时PbCount-topk算法只对满足长度约束的字符串集合建立索引，大大减少了搜索的范围；最后，AQ算法虽然可以自适应地改变q值的大小，但是q的初始范围需要人为设置，而该范围的大小需做大量实验后才能确定，因此q的范围不好把握。还可以看出数据集中的字符串长度越大PbCount-topk算法的优势越明显。这主要是因为随着字符串长度的增大，两个字符串之间的编辑距离会随之增加，这样在建立索引时会增加分段的个数，有利于提高过滤和验证的效率。例如，当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数据集上算法的执行效率出现了少许波动。例如，在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.