【作者】 邱越峰； 田增平； 季文赟； 周傲英；

【Author】 Qiu Yuefeng,Tian Zengping,Ji Wenyun,Zhou Aoying (Department of Computer Science Fudan University Shanghai 200433)

【机构】 复旦大学计算机系；

【摘要】 如何消除数据库中的重复信息已成为数据质量研究中一个热门话题.本文提出了一种基于N-Gram的检测相似重复记录的方法,主要工作有:(1)给出了一种高效的基于N-Gram的聚类算法,该算法能适应常见的拼写错误如插入、删除、替换、交换等,复杂度为O(N);(2)介绍了一种高效的应用无关的Pairwise比较算法,复杂度为O(k~2);(3)采用了一种改进的优先队列算法来准确地聚类相似重复记录.更多还原

【Abstract】 Eliminating duplications in large database has drawn some attentions.In this paper,the problem is studied.An N-gram based approach is introduced.The contributions of this paper are:(1) an efficient n-gram based clustering algorithm is given,which can tolerate the most common types of errors in misspelled words like insertion,deletion,transposition,substitution,and reordering of the words in a record.It is only with the computing complexity of O(N).(2) A very efficient application independent Pairwise comparison algorithm is presented.It has the computing complexity of O(k~2).(3) For detecting duplicate records in the indexed table,an algorithm that modifies the priority queue method is presented.更多还原