一种高效的检测相似重复记录的方法

1、第24卷第1期2001年1月计算机学报CHINESEJ1COMPUTERSVol.24No.1Jan.2001一种高效的检测相似重复记录的方法邱越峰田增平季文周傲英(复旦大学计算机科学系上海200433)摘要.N2Gram的检测相似重复记录的方法,主要工作有:(1)N2,该算法能适应常见的拼写错误从而较好地聚类相似重复记录,N,使其在检测的同时能自动校正单词的插入、.)Pair2wise比较算法,该算法以.(3)给出了一种改进的优,该算法使用固定大小的优先队列顺序扫描已排序的记录,通过比较当前.此外,该文构造了合适的实验环境并作了大量的算法实验.在此基础上,、翔实的实验结果从而验证了算法的科学

2、性.关键词信息集成,相似重复记录,N2Gram,Pair2wise,聚类,优先队列中图法分类号:TP311AnEfficientApproachforDetectingApproximatelyDuplicateDatabaseRecordsQIUYue2FengTIANZeng2PingJIWen2YunZHOUAo2Ying(DepartmentofComputerScience,FudanUniversity,Shanghai200433)AbstractEliminatingduplicationsinlargedatabaseshasdrawngreatattention,andit

3、graduallybecomesahotissueintheresearchofdataquality.Inthispaper,theproblemisstudiedandanefficientN2Grambasedapproachfordetectingapproximatelyduplicatedatabaserecordsispro2posed.Thecontributionsofthispaperare:(1)AnefficientN2Grambasedclusteringalgorithmisproposed,whichcantoleratethemostcommontypesofs

4、pellingmistakesandclusterthoseap2proximatelyduplicatedrecordstogether.Besides,animprovedN2Grambasedalgorithmispro2posedaswell,whichcouldnotonlydetectthoseduplicationsbutalsorevisemostoftheinsertionanddeletionspellingmistakesinthewordsofrecordsautomatically.TheadvantageisthattheN2Grambasedalgorithmis

5、onlywiththecomputingcomplexityofO(N).(2)AveryefficientapplicationindependentPair2Wisecomparisonalgorithmbasedontheeditdistanceisexploited.Itverifieswhethertworecordsareapproximatelyduplicaterecordsviacomputingtheeditdistancebetweeneachpairofwordsinthetworecords.(3)Fordetectingapproximatelyduplicater

6、ecords,animprovedalgorithmthatemploysthepriorityqueueispresented.Itusesapriorityqueuetoscanallsortedrecordssequentially,andmakesthoseapproximatelyduplicaterecordsclustertogetherthroughcomparingthedistancebetweencurrentrecordandthecorrespondingrecordinthepriorityqueue.Furthermore,aneffectiveexperimen

7、talenvironmentissetupandalotofalgorithmtestsarecarriedout.Plentyofresultsareproducedthroughagreatdealofdiffer2收稿日期:1999210218;修改稿收到日期:2000203221.邱越峰,男,1976年生,硕士,研究方向为数据库和知识库.田增平,男,1968年生,博士,副教授,研究方向为数据库和知识库、数据挖掘和知识发现.季文,男,1974年生,博士研究生,研究方向为数据库和知识库.周傲英,男,1965年生,博士,教授,博士生导师,研究方向为数据库和知识库、数据挖掘和知识发现、多媒体数

8、据库.70计算机学报2001年entactualexperiments.Thecorrespondingaborativeanalysisisalsopresentedhere.Basedonalloftheexperimentsandanalysisinthispaper,theefficiency,rationalityandscientificityoftheN2Grambasedapproximatelyduplicaterecorddetectingapproachisvalidated.Keywordsinformationintegration,approximatelydupl

9、icatedrecords,N2Gram,Pair2wise,clustering,priorityqueue1引言,的应用.,.在有关数据质,最关键的问题之一,因此重复信息、类似信息的检测和消除也成为一个研究的热点1,2.本文主要研究如何检测数据库中相似重复记录的问题,提出了一种高效的基于N2Gram的检测相似重复记录的方法.下面的基本概念是贯穿全文的,定义如下:(1)数据库中相似重复记录.那些客观上表示现实世界同一实体的,但是由于在格式、拼写上有些差异而导致DBMS不能正确识别的记录.(2)记录的N2Gram值.N2Gram值是根据记录的内容并参照全局统计信息而计算出的一个表示记录特征的整

10、数值.以下也简称记录的N2Gram值为RNGN.(3)记录之间的距离D.D是根据两记录的内容而计算出的一个表示两记录相似程度的整数值.D越小则两记录相似程度越高,若D=0,则两记录全等.(4)记录间的Pair2.两记录间距离Dwise比较的计算过程.(5)cluster.相似重复记录的集合.其中任何一个记录都称为该cluster的代表记录.本文主要贡献如下:(1)给出了一种基于N2Gram的聚类方法,它能处理常见的拼写错误如插入、删除、交换、替换和单词的交换.该算法的时间复杂度为O(N).(2)给出了一种高效的应用无关的Pair2wise比较算法.(3)Pair2wise比较检测相似重复记录时

11、,采用了高效准确的优先队列方法.在本文以下各节中,将详细介绍检测相似重复记录的综合方法.第2节介绍了迄今为止的一些相32的聚类算;2比较算法;第5节综合了46节给出了有关实验结果及其分析;第7节总结了我们的工作.2相关工作在相似重复记录的检测方面已经有了一些成果.传统的“排序&合并”算法解决了如何检测数据库中完全重复记录的问题.它先将数据库中记录排序,然后通过比较邻近记录是否相等来检测完全重复记录.我们利用这样的思想,在记录已排序的基础上,作邻近范围内记录间的Pair2wise比较,就能计算出记录间距离D,从而确定是否为相似重复记录.由此可见,在相似重复记录的检测上,“排序&合

12、并”算法思想也是很有效的.文献1对“排序&合并”算法做了一些改进,它通过在排序时就识别出完全重复的记录来提高检测相似重复记录的效率.文献3使用某种应用相关的键来将相似记录聚类到邻近位置.文献4使用“联结”的方法来近似匹配记录的域.文献2根据用户定义的键值来重排表记录,并采用滑动窗口来Pair2wise比较窗口内的记录.文献5将每个记录看作“源记录”,以之为基础查询和构造相似记录组.文献5中的方法采用N2Gram聚类算法将相似记录聚到一个cluster中,并对每个cluster中的记录作Pair2.为提wise比较高准确率和效率,文献6先将表中所有记录排序,而后使用包含一定数量clust

13、er的优先队列来顺序扫描所有的排序记录并动态地将它们聚类.上述所有的相关工作均采用“排序&合并”思想来聚类相似重复记录.文献2,6中提到的方法都是先将整个数据库表按字典序来重排,然后作邻近记录的Pair2wise比较(它们唯一不同的是前者采用键来标识记录,而后者把整个记录看成一个字符串).按字典序重排记录后,相似记录被放在较接近的位置,从而可以在相对集中的范围内作记录的.但是由于字典序对错误的位置非常Pair2wise比较1期邱越峰等:一种高效的检测相似重复记录的方法71敏感,因此这种方法有很大的局限性.此外,对整个数据库表进行重排的开销也很大,时间复杂度为O(N×logN)

14、,因此经过深入的研究和实验,我们改进了传统的方法,采用N2Gram方法来重排数据库文件.RNGN值为序将相应数据库记录映射为当前记录,然后将当前记录与队列中所有代表记录作Pair2wise比较,如果和队列中某个代表记录重复,则把当前记录合并到相应的cluster中;否则,构造新的.cluster,5.2(NGC)的.2w(字符串).4节中以字符串的Pair2ise,详细说明记录间Pair2wise的比.3.2采用Bigram方法计算记录的RNGN值单词(字符串)的一个N2Gram是指该单词中任意n个字母的有序组合.在实际应用中,当赋于不同的n值,便有了相应的Bigram(n=2),Trigra

15、m(n=3),.经过比较和分析,我们发现在Quadgram(n=4)等计算记录的RNGN时,仅计算字母两两组合的Bigram方法要优于其它方法,这是因为(1)Bigram方法适合处理单词因为在N2Gram系列方法中,N值越大对长字符串的处理能力越强、精度越高.英语单词的长度很短,因此用Bigram方法完全能处理任何长度的单词.最关键的是Trigram,Quadgram等方法无法处理长度小于等于3的短单词,而Bigram方法却能处理得很好.(2)Bigram方法效率较高从检测的精度和时间、空间的开销来考虑,.这在6.3小节Bigram方法优于其它N2Gram方法中有详细的论述.考虑到以上两点,我

16、们采用Bigram方法来计算记录的RNGN值.假定有下面两个记录:3基于N-Gram的聚类算法3.1算法的基本思想基于N2Gram:个记录赋一个N2Gram值,类.在N2Gram高的记录的,.(1)标记为了给记录标记上一个N2Gram值,需要顺序地遍历整个记录文件两次.第一次遍历产生有关单词的统计信息(N2Gram信息)并统计到重复矩阵M中.第二次遍历根据单词中出现的所有N2Gram,参照重复矩阵M的信息为每个单词分派一个.一条记录中所有单词的WNGN之和构WNGN值成了记录的RNGN,即该记录的N2Gram值.该值是聚类记录时的键值.5.1小节给出了N2Gram标记算法(NGM)的详细描述.

17、(2)聚类我们采用了一定大小的优先队列来把相似重复记录聚到同一个cluster中.优先队列中的每个记录均为某个cluster的代表记录,因此优先队列中的所有记录均不互为相似重复记录.现假定优先队列中已存放了一定数量的代表记录:首先以记录的12ColonelFanninlonelFanninDepartmentofComputerScience,UniversityofCalifornia,SanDiego,CA92093Departm,ofCaliforniaU,SanDiego,可以看出,表中记录2是1的重复记录,2包含了5种最常见的拼写错误:插入(Departmen),删除(Un),交换(

18、),替换(puter,)7和单词的交换().我们按下面的步骤统计单词的Bigram信(2)计算重复矩阵M.M是一个四维矩阵,M的分量,)是相应Bigrami,j,出现的总次数,称为M(i,j,i,j,的重复数.Bigram(3)给每个Bigram赋一个BNGN值.BNGN值为该Bigram的重复数,即相应重复矩阵分息并最终计算记录的RNGN值:(1)枚举出一个单词的所有Bigram,为此,定义一个函数.一个Bigram是B来把每个单词映射为一个Bigram的集合量M(i,j,)的值.(4)每个单词w赋一个WNGN值:Q(w)=M(i,j,),i,j,B(w).一个四元组i,j,.其中,为单词中

19、任意两个字母且满足在前;i,j为字母,在单词中出现的位置.(5)给每个记录r赋一个RNGN值:G(r)=Q(w),wr.72计算机学报2001年上述算法仅是最朴素的计算记录RNGN值的方法.我们从中可以看出,影响RNGN值的关键因素是单词的WNGN值.第(4)步我们仅仅累加了单词中所有Bigram的重复数从而得出单词的错误多、单词间有WNGN值,这在面临数据量大、相互影响,特别是当单词中的插入󰃗删除错误比较多时是远远不能胜任的.因此我们需用更复杂的估算方法来准确地计算一个单词的WNGN值.3.3小节对上述基本算法作了改进,使它能较准确地估算单词的WNGN值;3.4使算法能自动检

20、测和更正插入󰃗.3.3准确估算单词N2本法算单词WNGNBigram值累加,这样和单Bigram值均被计算到.下面的改进算法的主WNGN,显然这是不合适的要作用是滤掉噪音Bigram(这里噪音Bigram指和错误字母相关的Bigram).假定单词W,长度为󰃜w󰃜,过滤噪音Bigram的阈值为(0<<1).(1)计算单词Bigram的个数2.bigramNumber=󰃜w󰃜×(󰃜w󰃜-1)󰃗(2)计算单词所有Bigram的重复次数之和totalFr

21、equency=,在单词中出现的位置).通过比较单词的正向Bigram集和逆向Bigram集,可以判断该单词是否存在插入󰃗删除错误,然后采用相应的Bigram矩阵校正插入󰃗删除错误.同样地,我们假定单词W,长度为󰃜w󰃜,判定是否为插入删除的阈值1,2(2<1).:().ig:2.umber=󰃜w󰃜×(󰃜w󰃜-1)󰃗2)计算单词所有Bigram的正向和逆向重复次数之和totalFrequency=M(j,k,),j,k,B(w)(正向),

22、=totalFrequency(j,k,),j,k,B(w)(逆向).M3)计算w的正向和逆向平均重复次数averageFrequency=totalFrequency󰃗bigramNumber,=totalFrequency󰃗averageFrequencybigramNumber.(2)如果下列条件之一满足,则该单词存在插入󰃗删除错误,否则转向(6)(无插入󰃗删除错误).1)正向和逆向平均重复数差别较大,即)󰃗(MIN(averageFrequency,averageFrequency)<1.MAX(av

23、erageFrequency,averageFrequency2)单词的首尾字母构成的Bigram0,󰃜w󰃜-1,M(i,j,),B(w).i,j,的重复数远小于平均重复数:M(0,󰃜w󰃜-1,)averageFrequency×2或(3)计算单词的平均重复次数averageFrequency=totalFrequency󰃗bigramNumber.(0,󰃜w󰃜-1,M,)averageFrequency×2.(4)计算单词的WNGN值WNGN=(3)选择参考矩阵

24、.M(i,j,),B(w)i,j,比较正向平均重复数和逆向平均重复数,如果aver2,则采用逆向重复矩阵作ageFrequency<averageFrequency,)averageFrequency×M(i,j,averageFrequency×(1󰃗).为参考矩阵,并使用逆向Bigram集;反之则采用正向重复矩阵作为参考矩阵并使用正向Bigram集.(4)估算单词插入󰃗删除错误的位置.我们定义字母的平均重复数为与该字母相关的Bigram集重复数的平均值.即有单词W,长度为󰃜w󰃜,某个字母位)为置为i,

25、则的平均重复数D()=(D(上述方法以单词的平均重复次数为基准,通过阈值的限制,将一些重复数偏差较大的噪音Bigram滤掉,保证了计算到WNGN的均是正确的Bigram.以下,我们把采用本小节算法作为估算WNGN的.N2Gram方法称为N2Gram1方法3.4检测和校正插入󰃗删除错误N2Gram1方法可以很好地检测一般的交换和替换错误,但对插入󰃗删除错误很敏感.例如在单词首有插入错误时,由于Bigram是位置相关的,因此该单词的所有Bigram均发生差错,以致最终单词的WNGN值很不准确.为了能更好地处理插入󰃗删除错误,我们引入了逆向重复矩阵M,

26、该矩阵的结构和正向重复矩阵M完全一致,只是存储的是单词逆向Bigram的信息(逆向Bigram是一个四元组i,j,.其中,为单词中任意两个字母且满足在后;i,j为字母M(i,j,)+M(k,i,)󰃗(󰃜w󰃜-1).,),D()计算并比较单词各个字母的平均重复数D(值最小的字母的位置i即为插入󰃗删除错误的位置.(5)判断错误类型并校正单词的WNGN值.采用试探法来判断错误类型(插入󰃗删除).(5.1)假定单词存在插入错误,这时i为插入的多余字母.我们删除i,并重新构造新单词的.然后再采用(1),(2)步的方法来Big

27、ram集考察新单词:如果仍存在插入󰃗删除错误,则转2);反之则认为单词确实存在插入错误且已被更正,计算新单词的WNGN值,转(7).1期邱越峰等:一种高效的检测相似重复记录的方法(5.2)假定单词存在删除错误,此时i应为被删除的73鬃母的位置.我们在i位置插入任一字母(这样删除错误变成替换错误,而N2Gram1方法适合于检测替换错误),并重新构造新单词的.然后再采用(1),(2)步的方法来Bigram集考察新单词:如果仍存在插入󰃗删除错误,则认为该单词的错误无法自动校正,转(6)(采用常规处理);反之则认为单词确实存在删除错误且已被更正,计算新单词的WNGN值,

28、转(7).(6)常规处理.换记录r1,r2的内容;过程SwitchValue(Integeri,Integerj)交换i和j的值;函数ComputDist(Wordw1,Wordw2)返回单词w1和w2的编辑距离,它采用了文献9的算法;MAX为预定义的一个极大值.输入:两单词距离的阈值1,r1和r2,记录().:T󰃗.=0;󰃗计算记录r1的单词数um(r1);󰃗Get󰃗计算记录r2的单词数WordNum(r2);󰃗4.if(n1>n2)then󰃗󰃗以单词数相对少的记录为参考记单

29、词没有插入󰃗删除错误,方法.WNGN值(7)结束.录,置于外循环中5.begin6.7.删除N2Gram1󰃗错误.我们把这样的经过扩充的方法称为N2Gram2方法.N2Gram2方法提高了检测精度,同时也增加了时间上的开销.对于插入󰃗删除错误比率很高的数据,使用N2Gram2方法是有意义的,但是对于一般数据而言,我们未必一定需要N2Gram2方法.因此在实际应用时采用何种方法应视数据的质量和需求而定.本文第6节对两种方法的实验结果作了比较.󰃗交换记录r1和r2的内容SwitchRecord(r1,r2);󰃗b

30、3255;交换n1和n2的值SwitchValue(n1,n2);󰃗8.end;9.fori=1ton1do10.begin7.18.=MAX;󰃗󰃗初始化minWordDist值minWordDist为某一极大值,该变量为两记录单词间的最小距离=1ton2doforjbegin=ComputDist(w1i,w2j);󰃗计算单词w1i和󰃗distw2j的距离4Pair-wise比较算法关于Pair2wise比较算法的研究已有了一些成果.文献8,9提出的都是计算字符串“编辑距离”

31、的算法,两者是类似的.而文献8和10提出的算法尽管理论基础不同,也是很相似的且复杂度均为O(m×n).文献9对文献8的算法作了改进,增加了对字符交换的处理功能,且文献9提出的算法复杂度仍为O(m×n),因此在计算字符串编辑距离的算法中,文献9的性能是比较好的.此外,较著名的11Smith2Waterman算法主要参考文献10,12,其复杂度为O(m×n×max(m,n).本文检测相似重复记录的方法中,记录间的Pair2wise比较依赖于记录单词的逐个Pair2wise比较,因此单词(字符串)的Pair2wise比较是一个相当重要的原子操作,其效率直接影响

32、整个算法的效率.经过比较和分析,采用文献9的算法来计算串的编辑距离较之其它算法有着时间复杂度小、识别重复记录能力强的优点.本文采用了该方法.Pair-wise比较算法PW函数GetWordNum(Recordr)返回记录r的单词数;过程SwitchRecord(Recordr1,Recordr2)交if(dist<minWordDist)thenminWordDist=dist;󰃗󰃗根据dist重新对minWordDist置值end;󰃗如果两if(minWordDist>1)thenreturnfalse󰃗=recor

33、dDist+minWordDist;elserecordDist记录任意单词间距离均大于1,则它们不是相似重复记录󰃗󰃗否则,记录距离变量recordDist相应增加minWordDist19.end;20.If(recordDist2)thenreturnTrue;󰃗󰃗如果记录间距小于2,则认为它们是相似重复记录21.elsereturnFalse;󰃗󰃗否则,不是相似重复记录算法第1216行for循环通过求出r2中与w1i距离最小的单词作为w1i的对应单词.记录的距离为对应单词的距离之和.这样很好地

34、处理了单词交换错误.算法的第1718行作了优化:即如果两记录存在一个单词对,它们之间的距离大于阈值时,就认为两记录是不相似的.5检测重复记录的算法综合第3,4节,我们给出了本文检测相似重复记录方法的详细描述.该方法分为N2Gram标记算法和N2Gram聚类算法两部分.74计算机学报(4)根据R值从记录文件读取物理记录r.2001年5.1N-Gram标记算法(NGM).算法NGM算法对重复矩阵的使用作了优化使用了基于域的重复矩阵来代替全局的重复矩阵.(5)把r和Queue中所有代表记录作Pair2wise比较:(5.1)如果Queue中有代表记录ri和r的距离小于即记录r的域i上所有单词的Big

35、ram信息均统计到重复矩阵Mi上,不同域单词的Bigram是不相关的.将记录逐域比较可以提高检测精度.NGM算法输入:记录文件:db,记录所含的域的数目:fieldNumber.输出:一个记录索引向量Rvector,Rvector的每个元素索引一个记录,它包含记录号和该记录的RNGN(1)初始化Mi的每个分量,这里ifber.(2)从记录文件db(3)对于r,i(j,k,),则r为ri所属的cluster的成员,把r加入该cluster中;如果ri为单个记录,则将ri和r构成一个新的cluster.(5.2)如果Queuer,则将加入,已满,则按一(6R,则结束并输CIvector,否则转向(

36、2).7)结束.值增加1.ij,k,B(w).(4)b,转向(2).(5).(6)从记录文件db当前位置读一个记录r.(7)对于记录中r中所有单词w,计算w的WNGN.(8)RNGN=WNGN(w是记录r的单词).(9)输出r的记录号和RNGN值到索引向量Rvector.(10)如果记录文件db未结束,转向(6).(11)结束.本算法中的第(7),(8)步是核心.这两步使用N2Gram1或N2Gram2方法计算单词的WNGN从而得到记录的RNGN值.假设记录文件中最大单词长度为󰃜w󰃜,则计算单词WNGN的时间复杂度为2O(󰃜w󰃜)

37、;又假设记录中单词个数的上界为K,则算法中第(7),(8)步整个的时间复杂度为O(k×󰃜w󰃜2),这和记录的数量是无关的,可视为常量c.而整个NGM算法遍历记录文件两次,因此它的时间复杂度为O(N×c),即为O(N)(N是记录文件的记录总数).5.2N-Gram聚类算法(NGC)NGM算法给每个记录赋了一个RNGN值,并输出到索引向量Rvector.NGC算法先以RNGN为键快速排序索引向量,然后使用一个优先队列Queue来聚类Rvector索引的记录.当Rvector被遍历时,把Rvector当前值索引的记录和队列Queue中存放的所有记录

38、作Pair2wise比较,根据比较结果调整队列并存储聚类信息.NGC算法输入:RNGN向量:Rvector,记录文件:db,队列Queue的大小S,Pair2wise比较的阈值;输出:聚类信息向量:CIvector.(1)初始化优先队列Queue,大小为S.(2)快速排序索引向量Rvector.(3)从索引向量Rvector当前位置读取一个索引值R.算法的核心部分是第(5)步.它每处理一个记录需扫描Queue一遍,因此处理一个记录的时间复杂度为O(S).如果Rvector中有N个分量,那么NGC算法的复杂度为O(S×N).算法第(2)步快速排序索引向量Rvector虽然理论上的复杂度

39、为O(N×logN),但由于快速排序的是内存中的整数值,根本无需I󰃗O操作;而传统的排序合并算法排序的是字符串,且有大量I󰃗O操作开销,两者相比较,基于N2Gram值的排序时间远远小于排序合并算法的排序时间.算法第(5)步当队列已满时有新的代表记录加入时,按某种策略淘汰一个原有的记录.此时可以根据实际情况选用FIFO,FI.LO等策略6实验结果我们首先构造了N2Gram处理系统,该系统实现了算法的全部细节;其次构造了一个测试数据生成系统,该系统可以按参数要求生成不同质量的测试数据并同步生成重复信息;然后我们定义了一组测试参数来评估测试结果;最后采用N2

40、Gram处理系统全面地分析不同规模、不同质量的数据.本文所有实验均在PC工作站上完成,工作站的硬件配置为CPUPentiumII350,RAM512M,软件配置为WindowsNT4.0.测试数据生成系统主要功能是模拟噪音,它使用的原始数据主要是常用人名、学校名和专业名,这些数据分别采自权威网站.测试数据生成系统可以通过设置参数来生成各种不同错误类型、不同错误比率、不同规模的近似重复数据.而我们实验的基础也正是这些数据.http:󰃗󰃗.gov󰃗ftp.censusgeo󰃗www󰃗gazetteer󰃗

41、places.html󰃗http:󰃗󰃗university.html󰃗http:󰃗󰃗collegecompass1期邱越峰等:一种高效的检测相似重复记录的方法75测试的结果参数有R(Recall),P(Precision),T(Time).先定义如下参数:重复记录集合RO是测试数据中重复记录的集合;检测到的重复记录集合RD是N2Gram处理系统检测到的重复记录集合;则󰃜RO󰃜P=󰃜RDRO󰃜󰃗󰃜RD

42、83260;T为算法执R=󰃜RD󰃜󰃗行的时间.检测精度主要取决于R,P的值,而衡量效率的指标是T值.6.1数据规模检测精度和运行时间.,采用N2Gram1方法(2见6.2小节)R.这是由于NGC,因此数,但是总体上说算法能胜任大数据量的处理.而P曲线始终维持高百分比(99.9%以上),说明算法的误检率几乎为零.由于N2Gram算法Precision值始终在99.9%以上,为了图表的简洁明了,在以下涉及精度的实验中我们均省略了P曲线而仅提供了最为关键的R曲线.图2表明,随着数据量的增加,算法的运行时间也相应增加,但两者呈线性关系,因此证明了算法的时

43、间复杂度为O(N).在数据规模测试中,我们保持了另外一个重要的参数优先队列的大小不变,6.4小节的实验着重讨论了优先队列大小对算法效率的影响.6.2N-Gram1和N-Gram2的方法的比较如3.4小节分析,N2Gram1方法的运行时间较短,但对于插入󰃗删除错误的检测能力比N2Gram2要弱.为了检测不同的错误类型对算法N2Gram1和N2Gram2的影响,类型的测试数据.:错误类型E=I,S,(insertion)、)、交换(transpo2wordswitching).为简化处.如某数据集的数X(XET),表示该数据集含有的错误均为X类型的错误.其它小节的实验中,我们均采用

44、错误均匀分布的测试数据.图3是在数据量为32000条记录的情况下对五种错误分布作了检测.可以看出,在错误类型为插入、删除时,N2Gram2的检测效果好于N2Gram1;对于交换和替换错误两者检测结果相近.对于单词交换错误,两者的检测结果均高达99%以上,这是因为基于N2Gram的检测方法是单词位置无关的,所以单词交换错误对N2Gram检测方法根本没有影响.这也是N2Gram方法相比传统的排序和合并方法的优点之一(传统方法对错误的位置以及单词的位置敏感).图4反映了处理等量数据(错误为均匀分布)时,N2Gram2由于附加了检测和校正插入删除错误算法,所需的处理时间比N2Gram1要多,但是两者和

45、时间开销均成线性关系.76计算机学报2001年上述结果表明,为了更好地检测插入󰃗删除错误,必须额外地付出时间的代价.对于插入󰃗删除错误比率高的数据,N2Gram2方法是有意义的.但是对于一般应用数据,当错误的分布趋于平均时,N2Gram2方法对于精度的改进效果不明显,此时使6.4优先队列大小对运行时间和检测精度的影响在NGC算法中,优先队列是用于聚类的主要数据结构.因此优先队列的大小对算法的效率起了关键的作用.实验以N2Gram1算法为例,测试了不影响.图7表明,高,Pair2wise比较.而图8却表明,优先.因为每一个当Pair2wise比较,大优先队列导致每

46、一个记录Pair2wise比较的次数增多,所以运行时间也相应增加.又因为每个记录Pair2wise比较时只扫描一遍优先队列,因此算法运用N2Gram1方法就能很好地检测重复记录.我们应当在应用中根据实际情况选择合适的方法.6.3Bigram方法和其它N-Gram方法的比较3.2小节简单分析了Bigram方法和其它N2方法的差别.在此我们从时间复杂度、检测精度三方面给出详.5说Bigram,而图6Trgram方法在检测(1)假设单词w,长度为󰃜w󰃜,构造单词两两组合的Bigram集的运行时间为O(󰃜w󰃜2),而构造单词三三组合的Tr

47、igram集的运行时间为O(󰃜w󰃜3),依次类推,因此Bigram方法时间开销最小.(2)假定允许的单词的最大长度为L1,字母表的最大长度为L2,那么使用Bigram检测时,重复矩2阵M的大小为a×L21×L2(这里a是一个常系数);3如果使用Trigram则为a×L31×L2,依次类推,因此行时间和优先队列的大小呈线性关系.使用Bigram方法空间开销最小.(3)在检测精度方面,我们选取Trigram方法作为其它N2Gram方法的代表来比较它和Bigram方法的差异.实验数据中单词的最大长度从8到14不等,图6实验结果表

48、明Bigram方法检测精度略微高于其它方法,这是由于Bigram能处理其它方法不能处理的短单词.时间复杂度N2Gram(2)(3)(4)(󰃜󰃜n)空间复杂度2××La×L3L×4a×L×L234nna×L×L6.5N-Gram方法和其它方法的比较图5从第2节相关工作中,我们知道文献2,6是传统方法中比较有代表性且是较优的两种方法.它们都是先将整个数据库表按字典序来重排,然后作邻近记录的Pair2.从数据库的角度来看,由wise比较于数据库记录是按一定的模式存放的,因此文献2采用键标识

49、记录的方法比文献6把整个记录看作一个字符串更为合理.因此我们选择了文献2提出的方法(该方法简称为Merge󰃗Purge)来和N2Gram方法作比较.图9表明N2Gram方法和Merge󰃗1期邱越峰等:一种高效的检测相似重复记录的方法77.当检测插入、Purge方法在检测错误能力上的差异删除错误时,N2Gram1,N2Gram2和Merge󰃗Purge三者检测的精度相近,其中N2Gram2稍高;而当检测其余的交换、替换和单词交换时,N2Gram方法(包括N2Gram1和N2Gram2)的检测精度明显要大于Merge󰃗.图10表明,虽然N2Gram2Purge方法附加了检测和校正插入删除错误算法而运行时间比较长,但N2Gram1方法不但精度高于Merge󰃗Purge方法,Merge󰃗Purge方法,因此证明了N2复杂度小,检测精度较高.其中,N2Gram聚类算法能适应常见的拼写