1常用相似重复记录检测算法
相似重复记录检测的最简单方法是用一条记录和数据库中其它记录逐一对比，这种方法实现简单，精确度最高，然而时间耗费是极其可怕的，其时间复杂度达到O(n2)，所以在实际应用中是不可取的．相似重复记录清洗方法最常用的是基于排序-合并的方法，即先利用数据表的某个属性或若干个属性进行排序，再对排好序后的记录在邻近的宽度内比对，然后对检测到的相似重复记录进行清洗与合并．常见的基于排序-合并方法的相似重复记录检测算法有SNM算法(Sorted-NeighborhoodMethod)[1-2]、MPN算法(Multi-PassSortedNeighborhood，MPN)[1-2]．SNM算法的基本思想是设定若干条记录宽度的窗口，在窗口内进行记录的相似重复判定．该算法实现简单，算法的时间复杂度为O(nlogn)，排序是时间开销最大的一环．MPN算法对SNM算法进行了改进，该算法使用不同的关键字进行排序，每次排序后单独在一个较小的窗口内使用SNM算法判重．
2客户关系数据库相似重复记录清洗算法
经研究大量的企业客户关系数据库，发现客户关系数据表的属性个数均不多，一般为10个左右，且客户信息基本包含了姓名、性别、身份证号、住址等属性．对于住址等属性由于描述方式不一或采用简写等方面的原因，造成同一个人在同一张表中出现了多条住址不一样的记录．然而如果两条或多条记录相似重复，其姓名、性别和身份证号等属性必定相同，所以对于客户关系数据表判重前的排序使用“姓名+性别+身份证号”的多关键字排序方式．经排序，相似和重复记录已位于邻近的区间内．在排序的基础上，对相邻数据记录进行比对，如构成相似重复记录，则进行合并，合并后删除原来的两条记录，将新合并的记录插入数据表，然后用新合并的记录和之后的记录再进行比对，以此类推．记录的排序、合并和删除实现起来均非常简单，所以清洗中最麻烦的一环便是数据记录的比对即相邻记录相似重复的判定．此外，客户关系数据库中常出现许多无用的数据，即“废卡”信息，为了减少这些“脏数据”占用系统资源，也为了提高相似重复记录的清洗速度，在相似重复记录清洗前有必要对这些数据先行清洗．由于客户关系数据库都会记录卡片使用情况，如用卡时间等信息，可以根据这些信息对所有的记录进行扫描，导出无用的数据，由人工方式判断是否予以删除．
3小结
在客户关系数据库中存在大量的客户信息，有些客户的信息是以多条记录的方式存在于同一关系表中，这些记录构成了相似重复记录．通过制定算法对相似重复记录进行清洗并合并，可以提高系统空间的利用率，降低记录数量还可以提高新数据插入、无用数据删除和查询的速度．本文提出利用关系表的若干个属性对关系表的数据记录进行排序，对排序后的相邻记录通过设置属性权值和记录相似度闸值，求相邻记录的相似度，如相邻记录构成相似重复，再对其清洗并合并，取得了较好的效果．然而算法的属性权重和记录相似度闸值是凭经验设置，实际应用中应设置多大较合适，文中未有定论，这将是下一步需进一步研究的地方．
作者：郭文龙 单位：福建江夏学院
