《一种基于ngram的检测相似重复记录的高效方法》由会员分享，可在线阅读，更多相关《一种基于ngram的检测相似重复记录的高效方法（7页珍藏版）》请在金锄头文库上搜索。
1、第3 5卷专料 1 9 9 9年8月 兰 州 大 学 学 报 ( 自 然 科 学 版 ) V o l.3 5 S u p p J o u r n a l o f L a n z h o u U n iv e r s i t y (Na tu r a l S c i e n c e ) Au g . 1 9 9 9 文幸编号:0 4 5 5 - 2 0 5 9 ( 1 9 9 9 ) 0 2 5 5 - 0 7 一种基于N - G r a m的检测相似重复记录的高效方法 郑 越峰，田 增平 ，季文赞 ，周 傲英 复4大学 计算机系_ L 海 2 0 0 4 3 3 ) 摘要:如何消除数据库中的重
2、复信息己成为数据质量研究中一个热门话题.本文提出了一种 幕于 N - G r a m的检测相似重复记录的方法.主要T作有:( 1 )给出了一种高效的基于N - G r a m的 聚类算法，该算法能适应常见的拼写错误如插入、删除，替换、交换等，复杂度为0 ( N ) : ( 2 ) 介纽了一种高效的应用无关的P a i r w i s e比较算法，复杂度为。 ( k ) ; ( 3 )采用了 一种改进的优 先队列算法来准确地聚类相似或复记录. 关 键词: N - C r a m ; R N G N ; p a i ; w i s e ;聚 类: 优先队列 0 前言 在 信息技术高速发展的 今天，
3、 信息集 成在 I T各个领域都 有厂 泛的应 用.集成信息是信 息服务的 基础，因此集 成数据的质量直 接影响到以后信息 服务 的质量，在有 关数据质量的各 种问 题中 ，多数据 源合并 造成的信息T ( 复是最关键的问题 之一 本文主要 研究如何检测数 据 库中重复记录的问题.我们定义的重复 记录是指那些表示现实世界同一实体的，但是在格 式、拼写上有些差异而导致 D B M S不能止确识别的记录.这里，我们提出了一种基于N - G r a m 的检测相似重复 记录的方法. 本文主要的新思 想如下: ( l ) 给出了 一种基于 N - G r a m的聚 类方法， 它能 处理常见的拼 写错
4、误如插入、删除、交换、替换和单词的交换.该算法的时间复杂度为 O W) ; ( 2 )给出 了一种高效的应用无关的 P a i r w i s e比较算法，它的时间复杂度为 0 W) ( k是记录串的平 均长度) :( 3 )在P a i r w i s e比较检测相似重复记录时，采用改进了的更为高效准确的优先队 列方法. 在本文以下部分中，将详细介绍检测相似重复记录的方法.为了叙述的简便，我们简称 该算法为 “ 检测重复记录”算法.第 2部分通过一个实例详细介绍了基于N - G r a m的聚类算 法. 第3 部分介绍了P a i r w i s e 比 较算法.第9 部 分结合2 . 3
5、部分， 提出了 一种检测重复记 录的 综合方法. 第5 部分 给出了 有关算 法效率的 实验结果 评价. 第6 部分 总结了我 们的 J 二 作. 收稿日期:1 9 9 9 . 0 5 - 1 5 . 作者简介:邱越峰 ( 1 9 7 6 - ) ,男，硕 Hd f 究生 一以 - #R ( 4 * Vt ?k )一一一一一 % 3 5 4- 1基于N - G r 二 的聚类算法 1 . 1 算法的基 本思想 荃于N - G r 。 的 聚类算法的基本思 想是:给侮个 记录赋一个N - G r a m 值，以该值为 键来对 记录聚类.在N - G r a m 赋值时必须尽可能地使相似程度越高的
6、记录的N - G r a m值越接近，以保 证它们将被聚到临近的区域. 上述方法可以分成标记和聚类两个步骤来实现.为了给记录标记上一个 N - G r a m值，需 要顺序地遍历裂个记录文件两次 第一 次 遍历产有关单词的统计信息 ( N - G r a m信息) 井记 录到重复矩阵m中 .第二次遍历根 据单 词中出现的所有N - G r a m ，参照重复 矩阵M的 信息 为 每个单词分派 一个 W N G N 值 一条记录中 所有单 词的W N G N 之和构成了 记录的R N G N ,即该记 录的 N - G r a m 值，该值是聚类记录的键. 聚类处理时， 按照记录的R N G N
7、值顺序地将当前记录与队列中所有记录作P a i r w i s e比较， 如果和队列中 某个记 录重复 ，则把当前 记录加入原有的c l u s t e r 或形成新的c l u s t e r .反之 则 把当 前记录单 独加到队 列中，并调整 优先级.记录作 P a i r w i s e比 较的基础是单词 ( 字符 串)的 P a i r w i s e比较.我们将在第3节 中详细说明P a i r w i s e的比较方法. 1 . 2 计算记录的R N G N 值 如果有 卜 面两个记录: YI Co l o n el 动 D e p a r t m e n t o f C o m
8、p u t e r S c i e n c e , D n i v e r s i t v o f C n l i f o r n 叔 S a n D i e g o , C A 9 2 0 9 3 肠 了 o ne lFannFann初F m n p p t e l D e p a r t a m n r t , o f C a l i f o r n i a D n i v e r sv , S a n D i e g o谬 9 2 0 9 9 可以看出，表中记录 Y 2是 Y 1的重复记录。 Y 2包含了五种最常见的拼写错误:插入 ( D e p u r tm e n r t) ,删除
9、( U n i v e r s i y ) ， 交换 (S c r d n c e ) ， 替换 ( E o m p u t e r , C B , 9 2 0 9 -9 ) k u k 9 2 T 11 域 中单词的交 换 ( F o m n u i e r S c ie n c e D e p = t) . 我们按下 面的 步骤计算记 录的R N R iN值: 1 ) 枚举出 一个单词的所有B i g r a m ， 为 此， 定义一个函 数 B来把 每个单 词映射为 一个 B i g r a m 的集合.一个B i g r a m 是一个四元组 .其中，a , i3 为 单词中 任意 两
10、个字母 且满足。在) 3 前:i , j 为字母 a ， i3 在单词中出现的位置. 2 ) 计算重复矩阵M ， 对于 每个B i g r a m ( i , j , 。 ， B ，M的 分M : M G , j , a ， B ) 是 该B i g r a i n 出 现的总次数. 3 )给每个 B i g r a m 赋一个B N G N值 1 ) 若B i g r a m 1 Q( w) = 其它 5 )给fa个记录赋一个R N G N值: C ( 二 ) = 艺 Q (w ) 当 ， 是记录 厂中的单词， 从计算R N G N 的方法可以看出，影响R N G N值的关键因素是单词的 W
11、 N G N .在上述第四步 过 程中， 我们仅仅 用了一个非常简单 的函数来 计算W N G N . 但当 面临数据量人， 错误多，单 词间 有互相影响时， 这 样的函 数估算单词d u p l i c a t o r 及计算单词的W N G N 值往 往不够准确. 在 处理大量数据时，我们需用更复杂的估算方法来计算出一个单词的W N G N值. 2 P a i r w i s e比较算法 关于 P a i r w i s e比 较算法的研究己 有了一 些成果. S m i t h - W a t e r m a n算 法 S W 8 1 主要参考 S e 7 4 和 W S B 7 6 ，
12、其 复杂度为O ( m * n * m a x ( m , n ) ) . W F 7 4 PII S e 1 7 4 提出的都是计 算字符串 “ 编辑距离” 的算 法， 两者是类似的. 而 W F 7 4 f I I S e 1 7 4 提出的 算法尽r,理论 基础不同，也 是 很相似的 且复杂度 均为 O ( m * n ) . L W 7 5 ! 对 W F 7 4 的算法作了改进， 增加了 对字符交换的 处 理功能. L W7 5 提出 的算法复杂 度仍为。 ( m * n ) . 采JI J L W 7 5 的算 法来计算串的 编辑距离较 之阳 W 8 1 有着算法 复杂度小，识别
13、重复记录能力 强的优点.本文采 用了 该方 法. P a i r w i s e比 较算 法P w 函数 G e t W o r d N u m ( R e c o r d r ) 返回记录 r 的单词数: 过程 S w i t c h R e c o r d ( R e c o r d r , R e c o r d r 2 ) 交换记录 r l . r 2 ;过 程 S w i t c h V a l u e ( l n t e g e r i , S n t e g e r j ) 交换 i和 i的 值: 函数 C o m p u t D i s t ( W o r d w l , W
14、o r d w 2 ) 返回单i4 J w 1 和w 2的 编辑距离; M A X 为预定义的 一个极大 值. 输入: 输出: l . 2 3 4 5 两个记录r l和 r 么 T r u e /F a l s e . r e c o r d D i s t : 二 0 n 1二 G e t W o r d N u m n 2 二 G e t W o r d N u m i f (n l) n 2) b e g i n S w i t c h(川 . 记录距离的阐值s( 该值用于判定记录是否相似) ( 了 I ) ( r 2, t h e n r 2 ) 2 5 8兰 9 r大学 学 报 自然
15、 科 学 版)第3 5 卷 7 . S w i t c h(n 1，n 2) ; 8 .e n d ; 9 . f o r i ; 一 1 t o n l d o 1 0 . b e g i n 1 1 . m i n W o r d D i s t : M A X ; 1 2 . f o r j ! = 1 1 0 11 2 d o 1 3 . b e g i n 1 4 . d i s t: 二C o m p u l D i s t ( w， R , ) ; 1 5 . i f(d i s tm i n W o r d D i s t)t h e n m i n W o r d D i s
16、 t:d i s t ; 1 6 . e n d ; 1 7 . r e c o r d D i s t : 二 r e c o r d D i s t m i n W o r d D i s t ; 1 8 . e n d ; 1 9 . i f(r e c o r d D i s tS)t h e n r e t u r n T r u e ; 2 0 . e l s e r e t u r n 助 I s e ; P W 算法中第 1 4行 C o m p u t e D i s t函数采用了 L W 7 5 )计算编辑距离的算法.算法第 1 2 - 1 6 行f o r循环通过求出r 2 中与w距离最小的单词 作为w 、 ， 的 对应单词. 记录的距离为每 对对 应单词的距离之和.这样很好地处理了单词交换错误 我们把7 L 录 r l和 r 2看成L 度分别为u和 v的字符串，整个M l
