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

被引：70

作者：

邱越峰

田增平

季文贇

周傲英

机构：

[1] 复旦大学计算机科学系!上海,复旦大学计算机科学系!上海,复旦大学计算机科学系!上海,复旦大学计算机科学系!上海

来源：

计算机学报 | 2001年 / 01期

关键词：

信息集成; 相似重复记录; N-Gram; Pair-wise; 聚类; 优先队列;

D O I：

暂无

中图分类号：

TP399 [在其他方面的应用];

学科分类号：

081203 ; 0835 ;

摘要：

如何消除数据库中的重复信息是数据质量研究中的一个热门课题 .文中提出了一种高效的基于 N- Gram的检测相似重复记录的方法 ,主要工作有 :(1)提出了一种高效的基于 N - Gram的聚类算法 ,该算法能适应常见的拼写错误从而较好地聚类相似重复记录 ,复杂度仅为 O(N) ;同时提出了该算法的改进形式 ,使其在检测的同时能自动校正单词的插入、删除错误 ,提高检测精度 .(2 )采用了一种高效的应用无关的 Pair- wise比较算法 ,该算法以单词间的编辑距离为基础 ,通过计算两记录中单词间的编辑距离来判断记录的相似与否 .(3)给出了一种改进的优先队列算法来准确地聚类相似重复记录 ,该算法使用固定大小的优先队列顺序扫描已排序的记录 ,通过比较当前记录和队列中记录的距离来聚类相似重复记录 .此外 ,该文构造了合适的实验环境并作了大量的算法实验 .在此基础上 ,文中分析了大量、翔实的实验结果从而验证了算法的科学性 .

引用

页码：69 / 77

页数：9

共 4 条

[1] TECHNIQUES FOR AUTOMATICALLY CORRECTING WORDS IN TEXT [J].

KUKICH, K .

COMPUTING SURVEYS, 1992, 24 (04) :377-439

[2] DUPLICATE RECORD ELIMINATION IN LARGE DATA FILES [J].

BITTON, D ;

DEWITT, DJ .

ACM TRANSACTIONS ON DATABASE SYSTEMS, 1983, 8 (02) :255-265

[3]

On the Theory and Computation of Evolutionary Distances[J] . Peter H. Sellers.SIAM Journal on Applied Mathematics . 1974 (4)

[4]

The Merge/Purge problem for large databases .2 Hernandez M,Stolfo S. Proc ACM SIGMOD International Conference on Management of Data . 1995

← 1 →