编辑距离算法在中文文本相似度计算中的优化与实现

陈正铭，霍　英（韶关学院 信息科学与工程学院，广东 韶关512005）

编辑距离算法在中文文本相似度计算中的优化与实现

陈正铭，霍英
（韶关学院 信息科学与工程学院，广东 韶关512005）

摘要：通过分析编辑距离算法的不足，采用数据结构的方法优化该算法的空间和时间复杂度，采用中文分词、同义词和基于短句的方法优化该算法的准确率，克服了编辑距离算法在中文文本相似度计算时效率低、准确率低、内存消耗高的缺点.通过实验分析，结果表明优化后的算法取得了更高的准确率和更好的时空效率.

关键词：编辑距离算法；相似度计算；算法优化；中文分词

在文本信息处理中，基于编辑距离的文本相似度计算算法在文本分类、知识挖掘、网页去重、问答系统等诸多领域有着极为广泛的应用，是一个基础而关键的技术.目前传统编辑距离算法以字符为单位计算各个字符之间的插入、删除、替换的编辑距离，时空效率较低，对中文文本的相似度计算准确度低.故需对传统的编辑距离算法进行优化，文献［1］提出一种准确性较高的计算字母型字符串相似度的算法，其利用最长公共子串对编辑距离算法进行了改进，修正了字符串相似度度量公式及优化了 Levenshtein矩阵的计算过程，在不改变空间复杂度的情况下提高了准确性；文献［2］针对中西文混合字符串，从输入法的角度提出了采用拼音编码和五笔编码，并将汉字作为西文字符的等价单位计算编辑距离的方法，该方法在提高相似重复记录查全率的同时获得较高的查准率，但因为算法扩大了码长，时间效率比传统编辑距离算法还要低一些；……