海量数据的相似重复记录检测算法

计算机应用 ›› 2013, Vol. 33 ›› Issue (08): 2208-2211.

海量数据的相似重复记录检测算法

周典瑞,周莲英

江苏大学计算机科学与通信工程学院，江苏镇江 212013

收稿日期:2013-02-25 修回日期:2013-04-06 出版日期:2013-08-01 发布日期:2013-09-11
通讯作者: 周典瑞
作者简介:周典瑞(1987-)，男，山东泰安人，硕士研究生，主要研究方向：数据清洗;
周莲英(1964-)，女，江苏泰州人，教授，博士，主要研究方向：计算机网络性能分析、信息安全、电子商务、网络信息系统。
基金资助:
江苏省科技支撑项目

Algorithm for detecting approximate duplicate records in massive data

ZHOU Dianrui,ZHOU Lianying

School of Computer Science and Telecommunication Engineering, Jiangsu University, Zhenjiang Jiangsu 212013, China

Received:2013-02-25 Revised:2013-04-06 Online:2013-09-11 Published:2013-08-01
Contact: ZHOU Dianrui

摘要/Abstract

摘要： 针对海量数据下相似重复记录检测算法的低查准率和低效率问题，采用综合加权法和基于字符串长度过滤法对数据集进行相似重复检测。综合加权法通过结合用户经验和数理统计法计算各属性的权重。基于字符串长度过滤法在相似检测过程中利用字符串间的长度差异提前结束编辑距离算法的计算，减少待匹配的记录数。实验结果表明，通过综合加权法计算的权重向量更加全面、准确反映出各属性的重要性，基于字符串的长度过滤法减少了记录间的比对时间,能够有效地解决海量数据的相似重复记录检测问题。

关键词: 海量数据, 相似重复记录, 综合加权法, 编辑距离

Abstract: For the problem of low precision and low time efficiency of approximate duplicate records detection algorithm in massive data, integrated weighted method and filtration method based on the length of strings were adopted to do the approximate duplicate records detection in dataset. Integrated weighted method integrated user experience and mathematical statistics to calculate the weight of each attribute to make weight calculation more scientific. The filtration method based on the length of strings made use of the length difference between strings to terminate the edit distance algorithm earlier which reduced the number of the records to be matched during the detection process. The experimental results show that the weight vector calculated by the integrated weighted method makes the importance of each field more comprehensive and accurate. The filtration method based on the length of strings reduces the comparison time among records and effectively solves the problem of the detection of approximate duplicate records under massive data.

Key words: massive data, approximate duplicate record, integrated weighted method, edit distance

中图分类号:

TP311

周典瑞周莲英. 海量数据的相似重复记录检测算法[J]. 计算机应用, 2013, 33(08): 2208-2211.

ZHOU Dianrui ZHOU Lianying. Algorithm for detecting approximate duplicate records in massive data[J]. Journal of Computer Applications, 2013, 33(08): 2208-2211.

[1]	朱怡, 宁振虎, 周艺华. 基于视觉特征的仿冒域名轻量级检测技术[J]. 计算机应用, 2020, 40(8): 2279-2285.
[2]	唐林川, 邓思宇, 吴彦学, 温柳英. 基于pHash分块局部探测的海量图像查重算法[J]. 计算机应用, 2019, 39(9): 2789-2794.
[3]	赵宏, 常兆斌, 王乐. 基于词法特征的恶意域名快速检测算法[J]. 计算机应用, 2019, 39(1): 227-231.
[4]	徐林, 范昕炜. 基于改进遗传算法的餐厅服务机器人路径规划[J]. 计算机应用, 2017, 37(7): 1967-1971.
[5]	陈羽中, 郭松荣, 陈宏, 李婉华, 郭昆, 黄启成. 基于并行分类算法的电力客户欠费预警[J]. 计算机应用, 2016, 36(6): 1757-1761.
[6]	赵霞, 林天华, 马素霞, 齐林海. 基于选择性加载策略的电能质量数据处理[J]. 计算机应用, 2016, 36(5): 1434-1438.
[7]	刘超, 胡成玉, 姚宏, 梁庆中, 颜雪松. 面向海量非结构化数据的非关系型存储管理机制[J]. 计算机应用, 2016, 36(3): 670-674.
[8]	梁俊杰, 甘文婷, 余敦辉. 基于位置编码索引树的个性化推荐算法[J]. 计算机应用, 2016, 36(2): 419-423.
[9]	白鹤翔, 王健, 李德玉, 陈千. 基于粗糙集的非监督快速属性选择算法[J]. 计算机应用, 2015, 35(8): 2355-2359.
[10]	张久杰, 王春晖, 张丽萍, 侯敏, 刘东升. 基于Token编辑距离检测克隆代码[J]. 计算机应用, 2015, 35(12): 3536-3543.
[11]	孙远帅陈垚官新均林琛. 基于Hadoop的大矩阵乘法处理方法[J]. 计算机应用, 2013, 33(12): 3339-3344.
[12]	张永浮盼盼张玉婷. 基于分层聚类及重采样的大规模数据分类[J]. 计算机应用, 2013, 33(10): 2801-2803.
[13]	刘雪琼武刚邓厚平. Web信息整合中的数据去重方法[J]. 计算机应用, 2013, 33(09): 2493-2496.
[14]	刘丽霞张志强. 基于Trie树的相似字符串查找算法[J]. 计算机应用, 2013, 33(08): 2375-2378.
[15]	黄国林郭丹胡学钢. 基于通配符和长度约束的近似模式匹配算法[J]. 计算机应用, 2013, 33(03): 800-805.