一种有效检测汉语相似重复记录的方法文学论文

　　摘要：从排序属性的选择、匹配方法、相似度计算、检测和处理相似重复记录以及实验结果几个方面，阐述了一种有效检测汉语相似重复记录的方法。

　　关键词：相似重复记录;匹配;排序属性

　　Web系统、数据挖掘系统、决策支持系统都离不开高质量的数据。由于系统所需数据常常来自不同数据源中的Web文件、各种格式文档文件和数据库文件，而集成这些文件中的数据极易产生包括相似重复记录在内的各种质量问题。重复记录是指描述同一个对象的记录，而相似记录是指不完全相同但相似度超过了给定阈值的记录。产生相似重复记录出现的原因很多，包括输入错误、缩写、计量单位不同、字符串分割错误、模式转换错误等。相似重复记录的存在不仅浪费系统的存储资源，而且还会造成系统得到有偏差的、甚至是错误的结果。因此，检测和消除相似重复记录是保证系统性能的一项重要工作。检测重复记录的方法很多：在记录层次，有机器学习方法、领域知识方法和基于距离的方法;在属性层次，则有基于字符相似度、基于标记相似度、基于语音相似度和基于数值相似度等方法[1]。在大型数据库中检测相似重复记录，排序—比较—处理是一个有效的方法[2]。

　　排序的目的是将相似或重复记录尽可能聚集在一起，以便缩小记录之间的比较范围，缩短检测时间，而用于排序的属性一般是关键属性或权重值大的属性[3-4]。比较是检测数据库中相似重复记录的过程，它需要逐个比较记录的各个属性，最后根据各个属性总的匹配程度判断两个记录是否是重复记录或相似记录。处理是对检查出的重复记录或相似记录进行处理，对重复记录一般删除，对相似记录则可以选择保留、合并或删除。在排序—比较—处理方法中，核心工作是字符串之间的匹配，无论是英文还是中文字符串，基于距离的匹配是常用方法[5-6]。

　　本文提出了一种新的排序—比较—处理方法，实验结果表明，该方法的查准率和运行时间均优于目前已有的方法。

　　1排序属性的选择

　　检测数据库中的相似重复记录时，如果不限制比较范围，每条记录从自己的下一条记录开始进行比较直到最后一条记录为止。如果数据库有N条记录，总共需要比较(N-1)!次。如果先排序再比较，则由于具有相同或相似属性值的记录聚集在相近位置，每个记录只需要比较临近的少量记录，这样可以大大降低每条记录的比较次数。设属性Ai值的种类分别有δi种，则用Ai排序后，记录比较的范围是N/δi+ε(ε<

　　2匹配方法

　　在排序属性的选择、记录排序和检测记录是否是相似重复记录过程中，都需要进行汉字匹配。汉字字符串匹配、比较时要考虑以下3种情况：一是省略，如“东华大学”和“上海东华大学”相比，省略了“上海”2个字;二是缩写，如“中科大”是“中国科技大学”的缩写;三是输入错误，输入同音、近音字或字形相似的字。

　　对于前两种情况，通过查找子串算法解决;对于第三种情况，则通过查找相似汉字表解决。相似汉字表选用GB 2312—80中的常用字，按读音对它们进行编码，每个汉字有唯一的区位码。而当满足下面条件之一时，两个汉字被认为是相似的：(1)区码相同，位码差值的绝对值小于8;

　　(2)区码不同，但属紧邻的区，且位码差值的绝对值小于8。

　　字符串S和T的匹配方法如下，Ω存放S和T中相同字符个数：步骤1：计算字符串长度|S|和|T|。

　　步骤2：如果|S|≥|T|，则指针i指向T的第1个字符，指针j指向S的第1个字符;否则相反。

　　步骤3：保存j的值到变量head作为下次比较开始位置。如果i和j所指字符相同，Ω加1，i和j的值加1，使其指向下一个待比较字符。如果i的值大于Min(|S|，|T)|，匹配束;如果不相同，则查询同音字表;如果在表中的相似度等于0，则j的值增1，否则λ加1，i和j的值加1，使其指向下一个待比较字符。