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

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

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

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

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

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

在文本信息处理中，基于编辑距离的文本相似度计算算法在文本分类、知识挖掘、网页去重、问答系统等诸多领域有着极为广泛的应用，是一个基础而关键的技术.目前传统编辑距离算法以字符为单位计算各个字符之间的插入、删除、替换的编辑距离，时空效率较低，对中文文本的相似度计算准确度低.故需对传统的编辑距离算法进行优化，文献［1］提出一种准确性较高的计算字母型字符串相似度的算法，其利用最长公共子串对编辑距离算法进行了改进，修正了字符串相似度度量公式及优化了 Levenshtein矩阵的计算过程，在不改变空间复杂度的情况下提高了准确性；文献［2］针对中西文混合字符串，从输入法的角度提出了采用拼音编码和五笔编码，并将汉字作为西文字符的等价单位计算编辑距离的方法，该方法在提高相似重复记录查全率的同时获得较高的查准率，但因为算法扩大了码长，时间效率比传统编辑距离算法还要低一些；文献［3］则引入计算前后非相邻字符间的交换操作来改进编辑距离算法，实现了编辑操作的最小化，某种程度上也提高了算法的准确度；文献［4］则通过计算词汇之间的语义距离，并对不同编辑操作赋予不同的权重来实现了相似句子检测，算法复杂，时空效率较低.已知针对中文文本相似度计算的编辑距离的方法存在的较多问题是：优化了准确度却牺牲了算法效率，优化了字母字符准确度又无法兼顾中文文本的准确度.对此本文通过分析研究，提出了一种基于编辑距离改进的和中文分词等技术相融合的计算文本相似度的算法，该算法具有较高的准确率和兼顾了时空效率.

1　传统编辑距离算法

编辑距离又称Levenshtein距离 （也叫做Edit Distance），是由俄国科学家V1adimir Levenshtein于1965年在文献［5］中提出的，是一种常用的距离函数度量方法，在文本相似度检测领域得到了广泛的应用.

表1　编辑距离算法的计算步骤

文本相似度计算［6］：编辑距离越大，相似度越小.假设源字符串S与目标字符串T长度的最大值为Lmax，编辑距离为LD，相似度为S，则：

假设m,n分别表示源字符串S和目标字符串T的长度，则编辑距离算法的空间复杂度为O（m*n），时间复杂度为O（m*n）.

尽管编辑距离算法简单易于实现，在文本相似度检测方面具有一定的优势，但仍然存在一些问题，比如算法忽略了字符串长度对编辑距离产生的影响，当字符串长度过大时，所耗内存也较大；单纯以字为单位计算各个字符之间的编辑距离，计算出来的距离只是文字表面的距离，并没有充分考虑词语的概念，使得计算结果的准确率不高，特别是对中文的相似度计算得不到满意的结果.

2　编辑距离算法的优化

2.1空间效率优化

传统编辑距离算法使用二维数组存储计算过程的各阶段编辑距离值，但实际上在每一次循环中只有一行的数据参与了计算，计算过的数据行往后都不再参与计算，因此可对算法进行调整，将二维数组改为两个一维数组（见表2）.经验证，计算速度和结果与传统编辑距离算法几乎相同，但空间复杂度降为：O（min（m,n））.

表2　优化空间后的编辑距离算法的计算步骤

2.2时间效率优化

传统编辑距离算法时间复杂度为O（m*n），考虑其动态规划思路无法通过改造算法结构实现时间复杂度的降维，但可通过减少m与n的值，实现一定的优化.仔细分析传统编辑距离算法计算过程，发现两个字符串对应位置上的字符相同时，如果把这两个相对应的相同的字符删除后，编辑距离计算结果不变.但删除相对应位置相同的字符后将会减少参与计算的两字符串的长度，从而使得计算的时间减少，同时也减少了计算所占用的空间.经验证，计算时间比传统编辑距离算法减少，时间复杂度降为O（m'*n'）（m'＜=m，n'＜=n）.

表3　优化时间后的编辑距离算法的计算步骤

2.3准确度优化

以下准确度的优化研究为仅以中文文本为研究模型的研究内容.

2.3.1基于中文分词的编辑距离算法

传统编辑距离算法以字为单位计算字符串之间的编辑距离，计算出相似度结果可能与实际情况出入较大，而且字符串的长度对计算时间也有很大的影响，针对这些情况，考虑先对字符串进行中文分词（本研究采用的是开源的盘古中文分词模块［7］），然后再进行计算，从而使计算结果更符合字符串词语相似度计算的要求，计算速度和相似度的准确率都得以提高（见表4）.

表4　基于中文分词的编辑距离计算例子

2.3.2基于同义词处理的编辑距离算法

上述基于分词的编辑距离算法虽然以词为单位计算字符串之间的编辑距离，计算速度与结果已经比传统编辑距离算法精确不少，但还是与实际情况有一定出入，尤其如上例所示，“爱”与“喜欢”这两词为同义词，实际一个意思，针对这些情况，考虑进行编辑距离计算过程时，步骤“如果词条s［i］=t ［j］，则编辑代价cost为0；如果词条s［i］!=t［j］，则编辑代价cost为1；”利用同义词库变更为：“如果词条s［i］同义于 t［j］，则编辑代价cost为0；如果词条s［i］非同义于 t［j］，则编辑代价cost为1；”，从而使计算结果更符合字符串词语相似度计算的要求（见表5）.

表5　基于同义词处理的编辑距离计算例子

另同义词词典的构造可利用分词系统的词典进行扩展，其数据结构为：（编号，拼音，词条，同义词编号列表），并按编号与拼音项进行索引及散列.判断两词条是否同义，可根据第一词条的值先检索其相关记录，然后根据同义词编号列表检测第二词条是否在第一词条的同义词集合内，如果在则返回同义标志，否则返回非同义标志.

2.3.3基于短句的编辑距离算法

为进一步提高相似度计算的准确度，可引入基于短句的编辑距离相似度算法，思路如下：先把文本按标点划分为若干短句，然后按短句为基本单位使用上述基于同义词处理的编辑距离算法进行计算，当两短句相似度为某阈值（如0.9）以上时则返回相似标志，否则返回非相似标志.为提高计算速度，可先对两短句的长度进行比较，如果长度相差超过一倍则直接返回非相似标志.

表6　基于短句的编辑距离算法的计算步骤

3　结语

上述对编辑距离算法的优化都未能从数量级上降低其运算的时间复杂度，但通过数据结构的方法，空间复杂度从O（m*n）降为了O（min（m,n）），时间复杂度也从O（m*n）降为了为O（m'*n'）（m'＜= m，n'＜=n），另外通过中文分词、同义词检测与基于短句为基本计算单位的方法，极大的提高了中文文本相似度检测的准确度，也进一步的降低了算法的时间复杂度.

参考文献：

［1］姜华，韩安琪，王美佳，等.基于改进编辑距离的字符串相似度求解算法［J］.计算机工程，2014，40（1）：222-227.

［2］刁兴春，谭明超，曹建军.一种融合多种编辑距离的字符串相似度计算方法［J］.计算机应用研究，2010，27（12）：4523-4525.

［3］赵作鹏，尹志民，王潜平，等.一种改进的编辑距离算法及其在数据处理中的应用［J］.计算机应用，2009，29（2）:424-426.

［4］车万翔，刘挺，秦兵，等.基于改进编辑距离的中文相似句子检索［J］.高技术通讯，2004，14（7）:15-20.

［5］Levenshtein V I.Binary Code CaPab1e of Correcting de1etions，insertions and reversa1s［J］.Dok1ady Akademii NaukSSSR，1966，163 （4）:708-710.

［6］廖宏建，杨玉宝，唐连章.改进的编辑距离计算及其在自动评分中的应用［J］.广州大学学报，2012，11（4）：79-83.

［7］开源中国社区.盘古分词首页文档和下载［EB/OL］.［2015-03-02］.httP://www.oschina.net/P/Pangu.

（责任编辑：欧恺）

中图分类号：TP391.1

文献标识码：A

文章编号：1OO7-5348（2O15）12-OOO8-O5

［收稿日期］2015-09-04

［基金项目］韶关市科技计划项目（2013CX/K38）；韶关学院科研项目（一般项目2014-14）；广东省自然科学基金资助项目（2014A030307029）；广东省高等学校科技创新（重点）项目（2013KJCX0168）.

［作者简介］陈正铭（1978-），男，江西南康人，韶关学院信息科学与工程学院讲师，硕士；研究方向：数据结构算法与数据库信息系统.

0Ptimization and ImPlementation of the Edit Distance Algorithm in Chinese Similarity Calculation

CHEN Zheng-ming，HUO Ying
（Institute of Information Science and Engineering，Shaoguan University，Shaoguan 512005，Guangdong，China）

Abstract:By ana1yzing the 1ess of edit distance a1gorithm，using the method of data structure oPtimize sPace and time comP1exity of the a1gorithm，using the method of Chinese word，synonyms and Phrases oPtimize the accuracy of the a1gorithm，overcomes the shortcomings of a1gorithm efficiency 1ow，accurate 1ow and memory consumPtion high.By way of examP1e test and ana1ysis，the resu1ts show that the oPtimized a1gorithm is achieve a higher accuracy and better temPora1 efficiency.

Key words:edit distance a1gorithm；simi1arity ca1cu1ation；a1gorithm oPtimization；Chinese segmentation