基于Levenshtein算法在项目信息重复度检测中的优化及应用

操亚松

摘要：在政府经济管理部门的项目管理工作中，项目申报企业因为各种原因，在多个政府支持政策下重复申报同一个项目，给经济管理部门的项目管理协调工作带了很多问题。而且由于多年的项目积累，对数量巨大的项目进行人工重复监测是一件非常困难的事情，利用Levenshtein字符串相似度算法，并且使用中文分词进行优化，为各个项目信息指标进行相似度比较，可以快速筛选出重复申报的项目。

关键词：字符串相似度；重复检测；中文分词；项目信息

中图分类号 TP301 文献标识码：A 文章编号：1009-3044（2015）22-0126-02

Abstract： In the government's economic management in the project management， project reporting companies because of various reasons， duplicate reporting the same projects in a number of government support policies， with a lot of problems to the project management to coordinate the work of economic management department. And with many years of accumulation of a huge number of projects， the project manual monitoring is a very difficult thing， the Levenshtein string similarity algorithm， and the use of Chinese segmentation optimization， information index of each item similarity comparison， can quickly filter out duplicate reporting project.

Key words： string similarity； duplicate detection； chinese word segmentation； project information

近年来，我国财政对各个行业扶持资金投入快速增长，扶持项目和资金管理不断改进。财政及经济管理部门项目的申报审核管理更加严格。然而，不少项目申报单位为了获得更多的国家资金扶持，在不同的政策扶持中重复申报同一个项目，这样既不利于国家扶持资金的使用效率，也会让决策者得不到正确的宏观经济数据[3]。

Levenshtein算法，用于计算两个字符串之間的Levenshtein距离，指的是两个字符串之间，由一个转换成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。通过该算法获得两个字符串的相似程度，由于在本文中的应用场景为中文的项目信息，所以可以使用中文分词将文本进行分词优化后进行比较以提高项目相似度查重效率。

本文给出了一种基于Levenshtein算法并进行中文分词优化后的对项目申报信息进行查重的方法，减少了工作人员在海量项目中进行项目信息比较的工作量，更准确的筛选出重复申报的可疑项目。

1 Levenshtein算法[2]

使用Levenshtein算法可以计算出两个字符串的Levenshtein距离，Levenshtein距离用来描述两个字符串之间的差异。假如两个字符串的长度分别为m和n，原算法则需要建立一个m×n的矩阵，如果两个字符串的长度分别达到10k个字符且为英文字符的话，则需要建立一个占用800M内存的矩阵用来存储运算结果。而新版本的算法只需要使用2×max（m，n）×8大小的内存来存储运算数据。经过优化过的Levenshtein算法比老版本的算法无论在运算效率上，还是在内存占用上都有很大的优化与提高[4][5]。

2 使用中文分词预处理

由于很多中文大文本数据指标比较的时候，中文分词是能够独立并且有意义的语言成分，英文单词之间是以空格作为自然分界符的，而汉语是以字为基本的书写单位，词语之间没有明显的区分标记，因此，中文词语分析是中文信息处理的基础与关键。使用中文分词预处理，降低字符串比较的维度，能使Levenshtein算法中的时间复杂度大大减少。

2.1Ansj 中文分词工具

Ansj 是一个开源的 Java 中文分词工具，基于中科院的 ictclas 中文分词算法，比其他常用的开源分词工具（如mmseg4j）的分词准确率更高。 Ansj中文分词是一款纯Java的、主要应用于自然语言处理的、高精度的中文分词工具，目标是“准确、高效、自由地进行中文分词”，可用于人名识别、地名识别、组织机构名识别、多级词性标注、关键词提取、指纹提取等领域，支持行业词典、用户自定义词典[1]。

Ansj 是ictclas的一个Java版本（ictclas3.0分词速度单机996KB/s，分词精度98.45%，API不超过200KB，各种词典数据压缩后不到3M，是当前世界上最好的汉语词法分析器），基本原理一致，在分词优化算法上做了一些改进[6][7]。该算法实现分词有以下几个步骤：全切分，原子切分；N最短路径的粗切分，根据隐马尔科夫模型和viterbi算法，达到最优路径的规划；人名识别；系统词典补充；用户自定义词典的补充。

2.2 预处理后效率分析

假如两段文本的长度分别为m和n，Levenshtein需要时间复杂度为O（m×n），两段文本经中文分词预处理并且去掉无意义的字，两段文本被划分为i和j长度的中文分词词组（i<

3 系统的实现

根据本系统的应用场景，对审批的项目信息进行指标分类，然后对各个信息指标内容使用Ansj 中文分词工具进行中文分词预处理，并对指标进行权重加权，对需要比较的指标进行相似度匹配，然后将各个指标相似度乘以权重并求和，算出两个项目信息的相似度，对大于60%的相似度的项目进行提醒，系统用户将会重点关注该项目，人工确定项目是否重复申报[8]。

4 思考

这个只是使用Levenshtein算法并结合中文分词进行信息重复检测的一个简单应用，本系统也是利用现有的相对成熟的算法并以此为基础进行改进，已经初步达到应用的目标。但是依然有很多需要改进的地方，主要表现在以下几点：

1）训练样本和语料库不足，尤其是项目信息包含了非常多的专业术语，随着电子政务信息化的进一步推进，政府需要建立符合项目审批需求的训练样本和语料库，或者考虑购买国内专业的语料库。

2）项目信息指标权重的设置，项目信息重复检测需要涵盖项目各个信息指标，比如项目名称、项目建设内容、项目建设规模等指标，需要对各个指标进行分析，确定该指标在项目信息重复检测中的权重，以跟精确的检测出重复申报的项目，所以建立一个比较符合实际需求的项目指标匹配模式能大大改进应用效果。

5 结论

使用Levenshtein算法并结合中文分词进行相似度研究有很高的理论研究价值和很广阔的应用前景。本文在對相似度计算方法和中文分词技术进行详尽的阐述后，重点对相似度结合中文分词进行项目信息重复检测的应用进行了详细的描述。并将其应用在省级项目信息管理系统中用于发现重复申报套取国家扶持资金的项目，提升了政府项目管理水平。

参考文献：

[1] NLPCN.Ansj中文分词[EB/OL]. http：//www.nlpcn.org/resource/20.

[2] 百度百科.levenshtein[EB/OL]. http：//baike.baidu.com/view/4123766.htm.

[3] 李雪莹，刘宝旭，许榕生.字符串匹配技术研究[J].计算机工程，2004（22）：24-26.

[4] 吉胜军. 基于Levenshtein distance算法的句子相似度计算[J]. 电脑知识与技术，2009（09）：2177-2178.

[5] 赵作鹏，尹志民，王潜平，许新征，江海峰.一种改进的编辑距离算法及其在数据处理中的应用[J]. 计算机应用，2009（2）：424-426.

[6] 胡章荣，王朝斌.基于词典的中文分词算法及其性能评估[J]. 电子技术与软件工程，2015（15）：102-103.

[7] 姚继伟，赵东范.基于短语匹配的中文分词消歧方法[J]. 吉林大学学报（理学版）， 2010（3）：427-433.

[8] 庞雄文，姚占林，李拥军.大数据量的高效重复记录检测方法[J]. 华中科技大学学报（自然科学版），2010（2）：8-11.