一种融合位置信息的字符串相似度度量方法  

New method for calculating string similarity fusing location information

作　　者：肖雨[1] 崔荣一[1] 怀丽波[1] 

机构地区：[1]延边大学计算机科学与技术学系智能信息处理研究室,吉林延吉133002

出　　处：《计算机应用研究》2015年第11期3287-3290,共4页Application Research of Computers

基　　金：延边大学延大科合字(2013)第12号项目

摘　　要：针对传统字符串相似度算法复杂的局限,在向量空间模型(VSM)的基础上,提出一种同时考虑字符相邻位置关系和词序的字符串相似度计算模型。通过计算VSM中向量的汉明距离来描述字符串相邻程度,并以向量的曼哈顿距离作为衡量字符先后次序的指标。最后对两个指标加权求和得到字符串相似度的定量描述。与传统的算法比较,该算法更简便,时间复杂度为O(n log(n))。实验结果表明,该方法提高了字符串相似度的准确率,得到的数据结果更合理。Aimed at the limitation of traditional string similarity complex algorithm, this paper proposed an algorithm based on vector space model to calculate string similarity, which fused both character adjacent position relation and word order information. This method described adjacent degree through computing Hamming distance of vector in VSM. Then it figured out word order similarity based on vector Manhattan distance. Finally, the algorithm presented quantitative description to string similarity fusing the word order and character adjacent degree. Compared with the traditional method, the proposed algorithm decreases the time complexity to 0（ n log（n） ）. Experimental results show that the method improves precision rate and gets more reasonable data result.

关 键 词：字符串相似度 相邻字符 词序 汉明距离 

分 类 号：TP301.5[自动化与计算机技术—计算机系统结构]