基于Levenshtein算法在項(xiàng)目信息重復(fù)度檢測(cè)中的優(yōu)化及應(yīng)用

操亞松

摘要：在政府經(jīng)濟(jì)管理部門的項(xiàng)目管理工作中，項(xiàng)目申報(bào)企業(yè)因?yàn)楦鞣N原因，在多個(gè)政府支持政策下重復(fù)申報(bào)同一個(gè)項(xiàng)目，給經(jīng)濟(jì)管理部門的項(xiàng)目管理協(xié)調(diào)工作帶了很多問(wèn)題。而且由于多年的項(xiàng)目積累，對(duì)數(shù)量巨大的項(xiàng)目進(jìn)行人工重復(fù)監(jiān)測(cè)是一件非常困難的事情，利用Levenshtein字符串相似度算法，并且使用中文分詞進(jìn)行優(yōu)化，為各個(gè)項(xiàng)目信息指標(biāo)進(jìn)行相似度比較，可以快速篩選出重復(fù)申報(bào)的項(xiàng)目。

關(guān)鍵詞：字符串相似度；重復(fù)檢測(cè)；中文分詞；項(xiàng)目信息

中圖分類號(hào) TP301 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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

近年來(lái)，我國(guó)財(cái)政對(duì)各個(gè)行業(yè)扶持資金投入快速增長(zhǎng)，扶持項(xiàng)目和資金管理不斷改進(jìn)。財(cái)政及經(jīng)濟(jì)管理部門項(xiàng)目的申報(bào)審核管理更加嚴(yán)格。然而，不少項(xiàng)目申報(bào)單位為了獲得更多的國(guó)家資金扶持，在不同的政策扶持中重復(fù)申報(bào)同一個(gè)項(xiàng)目，這樣既不利于國(guó)家扶持資金的使用效率，也會(huì)讓決策者得不到正確的宏觀經(jīng)濟(jì)數(shù)據(jù)[3]。

Levenshtein算法，用于計(jì)算兩個(gè)字符串之間的Levenshtein距離，指的是兩個(gè)字符串之間，由一個(gè)轉(zhuǎn)換成另一個(gè)所需的最少編輯操作次數(shù)。許可的編輯操作包括將一個(gè)字符替換成另一個(gè)字符，插入一個(gè)字符，刪除一個(gè)字符。通過(guò)該算法獲得兩個(gè)字符串的相似程度，由于在本文中的應(yīng)用場(chǎng)景為中文的項(xiàng)目信息，所以可以使用中文分詞將文本進(jìn)行分詞優(yōu)化后進(jìn)行比較以提高項(xiàng)目相似度查重效率。

本文給出了一種基于Levenshtein算法并進(jìn)行中文分詞優(yōu)化后的對(duì)項(xiàng)目申報(bào)信息進(jìn)行查重的方法，減少了工作人員在海量項(xiàng)目中進(jìn)行項(xiàng)目信息比較的工作量，更準(zhǔn)確的篩選出重復(fù)申報(bào)的可疑項(xiàng)目。

1 Levenshtein算法[2]

使用Levenshtein算法可以計(jì)算出兩個(gè)字符串的Levenshtein距離，Levenshtein距離用來(lái)描述兩個(gè)字符串之間的差異。假如兩個(gè)字符串的長(zhǎng)度分別為m和n，原算法則需要建立一個(gè)m×n的矩陣，如果兩個(gè)字符串的長(zhǎng)度分別達(dá)到10k個(gè)字符且為英文字符的話，則需要建立一個(gè)占用800M內(nèi)存的矩陣用來(lái)存儲(chǔ)運(yùn)算結(jié)果。而新版本的算法只需要使用2×max（m，n）×8大小的內(nèi)存來(lái)存儲(chǔ)運(yùn)算數(shù)據(jù)。經(jīng)過(guò)優(yōu)化過(guò)的Levenshtein算法比老版本的算法無(wú)論在運(yùn)算效率上，還是在內(nèi)存占用上都有很大的優(yōu)化與提高[4][5]。

2 使用中文分詞預(yù)處理

由于很多中文大文本數(shù)據(jù)指標(biāo)比較的時(shí)候，中文分詞是能夠獨(dú)立并且有意義的語(yǔ)言成分，英文單詞之間是以空格作為自然分界符的，而漢語(yǔ)是以字為基本的書寫單位，詞語(yǔ)之間沒(méi)有明顯的區(qū)分標(biāo)記，因此，中文詞語(yǔ)分析是中文信息處理的基礎(chǔ)與關(guān)鍵。使用中文分詞預(yù)處理，降低字符串比較的維度，能使Levenshtein算法中的時(shí)間復(fù)雜度大大減少。

2.1Ansj 中文分詞工具

Ansj 是一個(gè)開源的 Java 中文分詞工具，基于中科院的 ictclas 中文分詞算法，比其他常用的開源分詞工具（如mmseg4j）的分詞準(zhǔn)確率更高。 Ansj中文分詞是一款純Java的、主要應(yīng)用于自然語(yǔ)言處理的、高精度的中文分詞工具，目標(biāo)是“準(zhǔn)確、高效、自由地進(jìn)行中文分詞”，可用于人名識(shí)別、地名識(shí)別、組織機(jī)構(gòu)名識(shí)別、多級(jí)詞性標(biāo)注、關(guān)鍵詞提取、指紋提取等領(lǐng)域，支持行業(yè)詞典、用戶自定義詞典[1]。

Ansj 是ictclas的一個(gè)Java版本（ictclas3.0分詞速度單機(jī)996KB/s，分詞精度98.45%，API不超過(guò)200KB，各種詞典數(shù)據(jù)壓縮后不到3M，是當(dāng)前世界上最好的漢語(yǔ)詞法分析器），基本原理一致，在分詞優(yōu)化算法上做了一些改進(jìn)[6][7]。該算法實(shí)現(xiàn)分詞有以下幾個(gè)步驟：全切分，原子切分；N最短路徑的粗切分，根據(jù)隱馬爾科夫模型和viterbi算法，達(dá)到最優(yōu)路徑的規(guī)劃；人名識(shí)別；系統(tǒng)詞典補(bǔ)充；用戶自定義詞典的補(bǔ)充。

2.2 預(yù)處理后效率分析

假如兩段文本的長(zhǎng)度分別為m和n，Levenshtein需要時(shí)間復(fù)雜度為O（m×n），兩段文本經(jīng)中文分詞預(yù)處理并且去掉無(wú)意義的字，兩段文本被劃分為i和j長(zhǎng)度的中文分詞詞組（i<

3 系統(tǒng)的實(shí)現(xiàn)

根據(jù)本系統(tǒng)的應(yīng)用場(chǎng)景，對(duì)審批的項(xiàng)目信息進(jìn)行指標(biāo)分類，然后對(duì)各個(gè)信息指標(biāo)內(nèi)容使用Ansj 中文分詞工具進(jìn)行中文分詞預(yù)處理，并對(duì)指標(biāo)進(jìn)行權(quán)重加權(quán)，對(duì)需要比較的指標(biāo)進(jìn)行相似度匹配，然后將各個(gè)指標(biāo)相似度乘以權(quán)重并求和，算出兩個(gè)項(xiàng)目信息的相似度，對(duì)大于60%的相似度的項(xiàng)目進(jìn)行提醒，系統(tǒng)用戶將會(huì)重點(diǎn)關(guān)注該項(xiàng)目，人工確定項(xiàng)目是否重復(fù)申報(bào)[8]。

4 思考

這個(gè)只是使用Levenshtein算法并結(jié)合中文分詞進(jìn)行信息重復(fù)檢測(cè)的一個(gè)簡(jiǎn)單應(yīng)用，本系統(tǒng)也是利用現(xiàn)有的相對(duì)成熟的算法并以此為基礎(chǔ)進(jìn)行改進(jìn)，已經(jīng)初步達(dá)到應(yīng)用的目標(biāo)。但是依然有很多需要改進(jìn)的地方，主要表現(xiàn)在以下幾點(diǎn)：

1）訓(xùn)練樣本和語(yǔ)料庫(kù)不足，尤其是項(xiàng)目信息包含了非常多的專業(yè)術(shù)語(yǔ)，隨著電子政務(wù)信息化的進(jìn)一步推進(jìn)，政府需要建立符合項(xiàng)目審批需求的訓(xùn)練樣本和語(yǔ)料庫(kù)，或者考慮購(gòu)買國(guó)內(nèi)專業(yè)的語(yǔ)料庫(kù)。

2）項(xiàng)目信息指標(biāo)權(quán)重的設(shè)置，項(xiàng)目信息重復(fù)檢測(cè)需要涵蓋項(xiàng)目各個(gè)信息指標(biāo)，比如項(xiàng)目名稱、項(xiàng)目建設(shè)內(nèi)容、項(xiàng)目建設(shè)規(guī)模等指標(biāo)，需要對(duì)各個(gè)指標(biāo)進(jìn)行分析，確定該指標(biāo)在項(xiàng)目信息重復(fù)檢測(cè)中的權(quán)重，以跟精確的檢測(cè)出重復(fù)申報(bào)的項(xiàng)目，所以建立一個(gè)比較符合實(shí)際需求的項(xiàng)目指標(biāo)匹配模式能大大改進(jìn)應(yīng)用效果。

5 結(jié)論

使用Levenshtein算法并結(jié)合中文分詞進(jìn)行相似度研究有很高的理論研究?jī)r(jià)值和很廣闊的應(yīng)用前景。本文在對(duì)相似度計(jì)算方法和中文分詞技術(shù)進(jìn)行詳盡的闡述后，重點(diǎn)對(duì)相似度結(jié)合中文分詞進(jìn)行項(xiàng)目信息重復(fù)檢測(cè)的應(yīng)用進(jìn)行了詳細(xì)的描述。并將其應(yīng)用在省級(jí)項(xiàng)目信息管理系統(tǒng)中用于發(fā)現(xiàn)重復(fù)申報(bào)套取國(guó)家扶持資金的項(xiàng)目，提升了政府項(xiàng)目管理水平。

參考文獻(xiàn)：

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

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

[3] 李雪瑩，劉寶旭，許榕生.字符串匹配技術(shù)研究[J].計(jì)算機(jī)工程，2004（22）：24-26.

[4] 吉?jiǎng)佘? 基于Levenshtein distance算法的句子相似度計(jì)算[J]. 電腦知識(shí)與技術(shù)，2009（09）：2177-2178.

[5] 趙作鵬，尹志民，王潛平，許新征，江海峰.一種改進(jìn)的編輯距離算法及其在數(shù)據(jù)處理中的應(yīng)用[J]. 計(jì)算機(jī)應(yīng)用，2009（2）：424-426.

[6] 胡章榮，王朝斌.基于詞典的中文分詞算法及其性能評(píng)估[J]. 電子技術(shù)與軟件工程，2015（15）：102-103.

[7] 姚繼偉，趙東范.基于短語(yǔ)匹配的中文分詞消歧方法[J]. 吉林大學(xué)學(xué)報(bào)（理學(xué)版）， 2010（3）：427-433.

[8] 龐雄文，姚占林，李擁軍.大數(shù)據(jù)量的高效重復(fù)記錄檢測(cè)方法[J]. 華中科技大學(xué)學(xué)報(bào)（自然科學(xué)版），2010（2）：8-11.