文档介绍：李彬
(武汉理工大学计算机学院武汉 430070)
摘要:用两个字符串滑动比较时匹配的字符数和两字符串滑动比较的重叠率定义了相似度的衡量指标,在确定一个字符串较另一个字符串较少的情况下,设计了一种算法,实现了在字符串匹配矩阵中确定插入空格的位置使相似度指标达到最大值,可以用于信息的模糊检索。
关键词:匹配率;相似度;匹配矩阵;信息量
中图法分类号:
The Matrix Arithmetic puting Strings' Similar Degree
LI Bin
( Department puter Of Wu’han University of Technology Wu’han 430070 China)
Abstract:The similar degree is defined based on the number of matching chars and the overlaping ratio of two strings’ chars when two strings parison during a arithmetic under the sistuation that making sure the length of one string is smaller than another strings’ and makeing sure the position of inserting blank space in strings’ matching matrix makes similar degree gain the biggest value,this arithmetic can used for the misty index of the information.
Key Words: Matching Ratio;Similar Degree;Matching Matrix;Information Quantity
1 引言
随着现代科学技术的发展,生物学中的DAN序列的相似性的比较可以用于亲子鉴定等,医学中应用病毒基因的相似性来诊治疾病。与之相似,随着计算机的发展,字符串的相似问题也成了计算科学中一个非常重要的问题,也提出了很多关于字符串匹配和相似度的算法,现有的计算字符串相似度的方法按照计算所依据的特征的不同,可以划分为三种方法:基于字面相似的方法、基于统计关联的方法、基于语义相似的方法。三种方法各有优缺点,还有人提出了综合考虑三种方法的多层特征方法[2]。其中,基于字面相似的计算方法主要有基于编辑距离的计算方法[3]和基于相同字或词的方法[4]。字符串序列相似度计算在异构数据库操作、音乐乐谱分析、基因序列分析[1],信息检索等方面有较好的应用。
本文通过定义的字符串相似度的衡量指标,利用匹配矩阵对字符串的相似度进行计算。对于长度不相等的字符串,通过插入空格的方法使字符串的长度相等,根据设计的算法确定空格的位置,使相似度的值达到最大,可以使模糊检索的信息更有意义。
2 计算字符串相似度的算法
给定两个长度相等的任意字符串Str1=“abcddacbcb”和Str2=“bddc”,对