论文部分内容阅读
摘 要：串匹配问题是计算机科学研究中比较广泛的问题之一，目前字符串匹配算法主要是针对英文等字符的匹配居多，而针对中文等字符的匹配比较少，本文将针对中文字符匹配的算法进行浅析，提出一种适合中文字符模式近似匹配算法的设计，通过实验证明了该算法的有效性。
关键词：串匹配；匹配率；考试系统；中文字符串
中图分类号：TP391.1
近似字符串匹配在入侵检测、文本编辑、移动短消息过滤、信息查询、信息提取等领域都有重要应用，已成为计算机算法设计的一个重要研究课题，本文的研究主要是在考试系统中的中文字符串匹配。
在考试系统中，对选择题的答案进行判断时，我们需要的是将考生输入的答案跟标准答案进行匹配即可，匹配函数也较为简单，很多开发软件都自带有相应的功能，可以直接导入答案进行匹配，看串匹配是否完全一致即可判断是否正确。但对中文录入的题型，若简单地比较考生输入的答案与给定的答案是否一致，显然是科学的，在此要求出最大两个中文字符串的最大相似度，在本文中称为最大匹配率，然后根据所求的匹配率来给出成绩。
1 问题分析及相关研究
在对中文字符串进行比较时，不对字符串的顺序进行相应的检查，因此，在对字符串进行比较时，需要对两个字符串用相应的英文字符来进行标识。方法如下：对于给定答案中的中文字符串，用字母来标识每一个中文汉字或词组，对考生输入的字符也进行标识，如果输入的字符在给定的答案中没有出现，则统一用一个英文字符W来标识。但是中文的字符串不像英文字符串，中文字符串，从汉语的表达方式来看，字符串中各个字符与相邻字符关系都是密不可分的，因此利用汉语表达的这个特点，找出了一种更合理的判定两个中文字符串的相似度的方法，并对原有的偏移距离算法做了相应的改进，方法如下：
首先，设字符串S1长度为n，字符串S2长为m，ed[i，j]表示偏移距离，定义一个矩阵Emn
进行迭代算法编辑如下，
其次，初始化：ed[i，0]=i；ed=[0，j]=j；
E[i，0]=0；E[0，j]=0；
然后通过伪代码进行程序编写，输入字符串A和字符串B，并进行相应的字符偏离误差值进行设置，进行字符的相似匹配率的算法。这样，运行一次偏移距离匹配算法不仅可以得到两个字符串的偏移距离ed[i，j]值，而且可以得到更重要的关于字符串之间相同字符组合单元的信息，因此，这无疑将大大提高对两个字符串相似度判定的精确率。
另外，由于在规则匹配过程中，规则字符串长度各不相同，那么偏移距离误差阀值也应当有所不同，因此在本考试系统中，是动态的设定偏移距离误差阀值。在对A、B两字符串进行比较进行求匹配率时，首先要求出两个字符串中相匹配的字符个数。而这里所说的匹配是一种近似的匹配，要求不像完全匹配那样严格。它只要求字符按照一定的顺序来进行匹配，但不要求字符连续匹配，可以间断性的匹配。假如A字符串与B字符串中的字符跳跃性地进行匹配，相匹配的字符数为25，而标准字符串中字符的个数为35，所以A字符串与B字符串的匹配率为0.71，从这个匹配的情况来看，就涉及到匹配的时间及匹配的准确度。
2 匹配结果分析比较
为了更好的分析匹配效果，下面就实验的情况及结果进行分析对比，实验用的数据是比较规则的字符串，词组相对也比较多，我们从这些数据中随机选取一部分，从语义的理解上对可以匹配的字符进行统计，然后采用传统的偏移距离算法和改进后的偏移距离算法分别对选取的数据进行相似度比较分析，通过偏移距离误差阀值的大小来进行统计，如偏移距离小，则认为两中文字符串可以匹配，衡量算法有效性的标准是查准率Q和检测时间T，查准率Q是指判定两中文字符串可匹配的准确率，定义如下：Q=正确判断出可匹配的字符串对数目除以给定需要匹配的字符串字符数目。
检测时间T是指采用不同算法的程序来判定完所有实验数据所需要的时间。所有实验均在同一台计算机上完成，实验结果情况如下：
耗时比较情况：
由本实验结果可见，笔者提出的改进后的偏移距离算法，由于在算法步骤上比传统偏移距离算法多了一步数据的遍历，故在算法耗时上稍微多一点，但在匹配率上，有了较大的提高，因此在本系统中的规则匹配模块中使用改进的偏移距离算法，取得了一定的效果。
3 小结及展望
本文介绍了中文字符匹配的相关技术，依据实验中分析得到的结果，针对中文字符串的匹配还是有一定的效果，并通过偏移距离算法来最大程度的找出最大匹配率 ，也针对中文语言表达的特点提出了改进后的偏移距离算法，并用实验数据验证了改进后的偏移距离算法的有效性，并分析了这些算法的不足之处。
笔者在研究过程当中深深感到，中文字符的匹配是比较复杂的，但要体现出其实用价值，必须要和其它相关应用的领域密切的结合起来，这就必须具备多方面的知识，如自然语言处理技术，词组、短语拆分技术等，因此，对于语义处理和知识表示方面都存在许多困难，也因为中文字符的组合词义比较丰富，语法和语义方面与英文差别较大，所以要将算法应用于中文匹配中，还要加大研究。本文在研究过程中，限于中文字符的复杂性，在自然语言的理解上并没有进行改进，只是利用自然语言现有的研究成果。另外，本文中算法性能的相关测试都是本人验证，由于思维、数据的局限性，这可能影响实验的充分性，中文字符匹配算法一直没有受到足够的关注，但随着国内语言系统、知识发现等研究的深入，中文语言的识别技术的发展和突破，在一定程度上会促进中文字符匹配技术的研究和发展，因此，通过大家的不断努力，基于考试系统中的中文匹配处理技术必将给人们的工作及生活提高效率。
参考文献：
[1]陈开渠，赵洁，彭志威.快速中文字符串模糊匹配算法[J].中文信息学报，2004，18（2）.
[2]C.Chai-Hui，K.Mohanmmed.A Survey of Web Information Extrac-tion Systems，IEEE Transactions on Knowledge and Data Engineering，Vol.18，2006.
[3]张振莲，李金莱.XML数据与关系数据库的转换及实现[J].南阳师范学院学报，2009，12（8）.
[4]邓梦浪，陈斌全，刘琳岚.一种XML Schema到关系模式的转换方法[J].计算机应用与软件，2010，27（6）.
作者简介：黄荣喜（1979-），讲师，研究方向：软件开发及应用。
作者单位：广西大学计算机与电子信息学院，南宁 530004；广西农业职业技术学院，南宁 530007
关键词：串匹配；匹配率；考试系统；中文字符串
中图分类号：TP391.1
近似字符串匹配在入侵检测、文本编辑、移动短消息过滤、信息查询、信息提取等领域都有重要应用，已成为计算机算法设计的一个重要研究课题，本文的研究主要是在考试系统中的中文字符串匹配。
在考试系统中，对选择题的答案进行判断时，我们需要的是将考生输入的答案跟标准答案进行匹配即可，匹配函数也较为简单，很多开发软件都自带有相应的功能，可以直接导入答案进行匹配，看串匹配是否完全一致即可判断是否正确。但对中文录入的题型，若简单地比较考生输入的答案与给定的答案是否一致，显然是科学的，在此要求出最大两个中文字符串的最大相似度，在本文中称为最大匹配率，然后根据所求的匹配率来给出成绩。
1 问题分析及相关研究
在对中文字符串进行比较时，不对字符串的顺序进行相应的检查，因此，在对字符串进行比较时，需要对两个字符串用相应的英文字符来进行标识。方法如下：对于给定答案中的中文字符串，用字母来标识每一个中文汉字或词组，对考生输入的字符也进行标识，如果输入的字符在给定的答案中没有出现，则统一用一个英文字符W来标识。但是中文的字符串不像英文字符串，中文字符串，从汉语的表达方式来看，字符串中各个字符与相邻字符关系都是密不可分的，因此利用汉语表达的这个特点，找出了一种更合理的判定两个中文字符串的相似度的方法，并对原有的偏移距离算法做了相应的改进，方法如下：
首先，设字符串S1长度为n，字符串S2长为m，ed[i，j]表示偏移距离，定义一个矩阵Emn
进行迭代算法编辑如下，
其次，初始化：ed[i，0]=i；ed=[0，j]=j；
E[i，0]=0；E[0，j]=0；
然后通过伪代码进行程序编写，输入字符串A和字符串B，并进行相应的字符偏离误差值进行设置，进行字符的相似匹配率的算法。这样，运行一次偏移距离匹配算法不仅可以得到两个字符串的偏移距离ed[i，j]值，而且可以得到更重要的关于字符串之间相同字符组合单元的信息，因此，这无疑将大大提高对两个字符串相似度判定的精确率。
另外，由于在规则匹配过程中，规则字符串长度各不相同，那么偏移距离误差阀值也应当有所不同，因此在本考试系统中，是动态的设定偏移距离误差阀值。在对A、B两字符串进行比较进行求匹配率时，首先要求出两个字符串中相匹配的字符个数。而这里所说的匹配是一种近似的匹配，要求不像完全匹配那样严格。它只要求字符按照一定的顺序来进行匹配，但不要求字符连续匹配，可以间断性的匹配。假如A字符串与B字符串中的字符跳跃性地进行匹配，相匹配的字符数为25，而标准字符串中字符的个数为35，所以A字符串与B字符串的匹配率为0.71，从这个匹配的情况来看，就涉及到匹配的时间及匹配的准确度。
2 匹配结果分析比较
为了更好的分析匹配效果，下面就实验的情况及结果进行分析对比，实验用的数据是比较规则的字符串，词组相对也比较多，我们从这些数据中随机选取一部分，从语义的理解上对可以匹配的字符进行统计，然后采用传统的偏移距离算法和改进后的偏移距离算法分别对选取的数据进行相似度比较分析，通过偏移距离误差阀值的大小来进行统计，如偏移距离小，则认为两中文字符串可以匹配，衡量算法有效性的标准是查准率Q和检测时间T，查准率Q是指判定两中文字符串可匹配的准确率，定义如下：Q=正确判断出可匹配的字符串对数目除以给定需要匹配的字符串字符数目。
检测时间T是指采用不同算法的程序来判定完所有实验数据所需要的时间。所有实验均在同一台计算机上完成，实验结果情况如下：
耗时比较情况：
由本实验结果可见，笔者提出的改进后的偏移距离算法，由于在算法步骤上比传统偏移距离算法多了一步数据的遍历，故在算法耗时上稍微多一点，但在匹配率上，有了较大的提高，因此在本系统中的规则匹配模块中使用改进的偏移距离算法，取得了一定的效果。
3 小结及展望
本文介绍了中文字符匹配的相关技术，依据实验中分析得到的结果，针对中文字符串的匹配还是有一定的效果，并通过偏移距离算法来最大程度的找出最大匹配率 ，也针对中文语言表达的特点提出了改进后的偏移距离算法，并用实验数据验证了改进后的偏移距离算法的有效性，并分析了这些算法的不足之处。
笔者在研究过程当中深深感到，中文字符的匹配是比较复杂的，但要体现出其实用价值，必须要和其它相关应用的领域密切的结合起来，这就必须具备多方面的知识，如自然语言处理技术，词组、短语拆分技术等，因此，对于语义处理和知识表示方面都存在许多困难，也因为中文字符的组合词义比较丰富，语法和语义方面与英文差别较大，所以要将算法应用于中文匹配中，还要加大研究。本文在研究过程中，限于中文字符的复杂性，在自然语言的理解上并没有进行改进，只是利用自然语言现有的研究成果。另外，本文中算法性能的相关测试都是本人验证，由于思维、数据的局限性，这可能影响实验的充分性，中文字符匹配算法一直没有受到足够的关注，但随着国内语言系统、知识发现等研究的深入，中文语言的识别技术的发展和突破，在一定程度上会促进中文字符匹配技术的研究和发展，因此，通过大家的不断努力，基于考试系统中的中文匹配处理技术必将给人们的工作及生活提高效率。
参考文献：
[1]陈开渠，赵洁，彭志威.快速中文字符串模糊匹配算法[J].中文信息学报，2004，18（2）.
[2]C.Chai-Hui，K.Mohanmmed.A Survey of Web Information Extrac-tion Systems，IEEE Transactions on Knowledge and Data Engineering，Vol.18，2006.
[3]张振莲，李金莱.XML数据与关系数据库的转换及实现[J].南阳师范学院学报，2009，12（8）.
[4]邓梦浪，陈斌全，刘琳岚.一种XML Schema到关系模式的转换方法[J].计算机应用与软件，2010，27（6）.
作者简介：黄荣喜（1979-），讲师，研究方向：软件开发及应用。
作者单位：广西大学计算机与电子信息学院，南宁 530004；广西农业职业技术学院，南宁 530007