基于动态规划的缩写发现算法.pdf

( ) 第 37 卷 第 1 期 武汉大学学报 工学版 Vol. 37 No. 1 2004 年 2 月 Engineering Journal of Wuhan University Feb. 2004 ( ) 文章编号 2004 0112804 基于动态规划的缩写发现算法 李华　 , 易宝林 , 桂 　浩 (华中科技大学计算机科学与技术学院 , 湖北 武汉 　430074) 摘要 :数据清理中重复记录的识别一般采用动态规划算法或过滤算法 ,然而很少算法考虑了数据中的缩写问 题 ,因此容易漏掉一些重复记录 ,影响了数据清理的质量 , 因此在动态规划的基础上提出了缩写发现算法 , 同已 有算法相比 ,它的算法复杂度较小 ,而且能够发现汉语等无分隔符的语言中的缩写 ,最后给出了缩写情况下判断 字符串近似匹配的方法. 关键词 : 数据清理 ;动态规划 ;缩写发现算法 ;字符串相似匹配 : TP391 　　　 A 中图分类号 文献标识码 : Abbreviationdiscovered algorithm based on dynamic programming L I Huayang , YI Baolin , GU I Hao (College of Computer Sci. and Tech. , Huazhong University of Sci. Tech. , Wuhan 430074 , China) Abstract : In data cleaning , generally , the dynamic pro gramming algorithm or filter algorithm is adopted in the identification of duplicated records. Whereas few algorithms involve in sowing abbreviation problem witch tend to result in duplicated records and affect data quality negatively. Therefore , the thesis presents discover ing abbreviation algorithm based on dynamic pro gramming. Compared with the existing algorithms , discover ing abbreviation algorithm is relatively much simpler and able to discover the language abbreviation in those languages which have no delimiter. More over , it puts forward the method about how to recognise the dupli cated records based on abbreviationdiscovered algorithm. Key words : data cleaning ; dynamic pro gramming ; abbreviationdiscovered algorithm ; string approximate matching 离等.