魏自強(qiáng)，班元郎，徐 偉，王文璽

(貴州航天計(jì)量測試技術(shù)研究所，貴州 貴陽 550009)

0 引 言

工業(yè)化和信息化的深度融合，信息技術(shù)在軍工企業(yè)產(chǎn)業(yè)鏈中的應(yīng)用越來越廣。簡潔的短文本，已然成為適應(yīng)人們快速高效工作的信息載體[1]。例如元器件供方簡稱就常作為供方名稱的短文本替代出現(xiàn)航天各個(gè)業(yè)務(wù)系統(tǒng)中。由于航天元器件信息來源于ERP、TDM等多個(gè)平臺，其中元器件的廠商名稱即供方名稱是定義唯一一個(gè)元器件的標(biāo)準(zhǔn)之一。但各系統(tǒng)的供方定義標(biāo)準(zhǔn)不同、不同人員對供方數(shù)據(jù)的理解不同導(dǎo)致同一條供方數(shù)據(jù)出現(xiàn)多條不同的記錄。最終導(dǎo)致在采購流程中，不同業(yè)務(wù)部門所提交的采購單中同一元器件供方信息數(shù)據(jù)出現(xiàn)不一致的情況。因此，在采購流程中，對供方數(shù)據(jù)和合格供方目錄進(jìn)行匹配是必要步驟之一。

供方數(shù)據(jù)和合格供方目錄都是短文本數(shù)據(jù)。供方數(shù)據(jù)匹配可以看作是文本匹配問題。在對現(xiàn)有的Jaro-Winkler算法以及Levenshtein(編輯距離)算法進(jìn)行測試后，發(fā)現(xiàn)這兩個(gè)算法在供方匹配應(yīng)用中有各自的優(yōu)勢，但都不能很好地滿足供方匹配需求。該文根據(jù)供方數(shù)據(jù)的特征，將Jaro-Winkler算法與Levenshtein(編輯距離)算法進(jìn)行結(jié)合與改進(jìn)。改進(jìn)的算法結(jié)合了兩種算法的優(yōu)勢，在計(jì)算元器件供方名稱與合格供方目錄的相似度時(shí)，提高了匹配的準(zhǔn)確率，滿足了供方匹配應(yīng)用的需求。

1 研究現(xiàn)狀

1.1 短文本聚合模型

加入短文本聚合模型的定義(1到2句話)在短文本聚合模型中，采用相似度算法對文本進(jìn)行相似度匹配。計(jì)算兩個(gè)字符串相似度算法主要可分三類[2]：基于字面、基于語義、基于統(tǒng)計(jì)關(guān)聯(lián)的相似度算法?；谧置娴南嗨贫人惴ㄓ芯庉嬀嚯x的方法和相同字或詞的方法，代表性的有Jaro-Winkler[3-4]、Levenshtein[5-6]算法、最長公共子串算法[LCS][7-8]、余弦相似度算法[9]。文獻(xiàn)[10]通過計(jì)算前后非相鄰字符間的交換操作，改進(jìn)了編輯距離算法，實(shí)現(xiàn)了編輯操作的最小化。

1.2 Jaro-Winkler算法

Jaro-Winkler算法是用來計(jì)算2個(gè)字符串的相似度，由Jaro改進(jìn)而來。該算法適合計(jì)算兩個(gè)較短的字符序列的相似度，運(yùn)算結(jié)果在0到1范圍內(nèi)。0表示完全不匹配，1表示完全匹配[11]，運(yùn)算的值越大表示相似度越高。

(1)Jaro算法。

(1)

其中，|s1|和|s2|分別為字符串s1和s2的字符串長度，m為匹配字符串個(gè)數(shù)，t為換位數(shù)目。

(2)匹配窗口MW(matching window)計(jì)算公式：

(2)

其中，|s1|和|s2|分別為s1和s2的字符串長度，當(dāng)字符串s1中的一個(gè)字符在字符串s2中，但位置不同，需要換位操作時(shí)，如果這2個(gè)字符的距離小于等于MW，則表示這兩個(gè)字符為匹配字符。統(tǒng)計(jì)所有能匹配的字符的所有換位操作數(shù)，記為tj，則換位的字符數(shù)目t，記為：

(3)

(3)Jaro-Winkler計(jì)算公式。

Jaro-Winkler算法的相似度計(jì)算公式為：

dw=dj+(lp(1-dj))

(4)

式中，p范圍為(0～0.25)，默認(rèn)值為0.1；l是字符串s1和s2的前綴部分匹配長度。

1.3 Levenshtein(編輯距離)算法

編輯距離于1965年被提出[12]，編輯距離[13]是由原字符串S轉(zhuǎn)換成目標(biāo)字符串T最少需要進(jìn)行的編輯操作次數(shù)。編輯操作包含3種操作，分別是字符的替換、添加、刪除，這3種操作次數(shù)的總和記為這2個(gè)字符串的編輯距離。編輯距離越小，相似度越高。

設(shè)字符串S=s1s2…sm，T=t1t2…tn，建立S和T的(m+1)×(n+1)階匹配關(guān)系矩陣LD：

LD(m+1)×(n+1)={dij}(0≤i

(5)

按公式(6)初始填充矩陣LD：

(6)

其中，

(7)

矩陣LD，右下角元素dm,n即為字符串S和字符串T之間的Levenshtein距離，也叫編輯距離，記為ld。

根據(jù)編輯距離ld，定義字符串S和T的相似度為[14]：

(8)

式中，Sim為最終的相似度計(jì)算結(jié)果。越相似的2個(gè)字符串，Sim的值將越大。

2 改進(jìn)Jaro-Winkler算法

2.1 供方數(shù)據(jù)特征

供方數(shù)據(jù)主要來源于貴州航天計(jì)量測試技術(shù)研究所的ERP、TDM等系統(tǒng)。在對多源數(shù)據(jù)進(jìn)行匯集后，發(fā)現(xiàn)同一供方的名稱數(shù)據(jù)有大量不一致的情況。

在航天元器件數(shù)據(jù)中，元器件供方名稱和合格供方名稱存在不一致問題，典型特征如下：

(1)合格供方名稱和元器件供方名稱，存在全稱和簡稱情況。例如“中國電子科技集團(tuán)有限公司第四十九研究所”和“中電四十九所”，“天水天光半導(dǎo)體有限責(zé)任公司”和“天水天光”。

(2)合格供方名稱和元器件供方名稱，存在總公司和子公司信息。例如“易訊科技股份有限公司”和“易訊科技股份有限公司哈爾濱分公司”，“中國航天科工集團(tuán)有限公司”和“中國航天科工集團(tuán)第二研究院”。

(3)合格供方名稱和元器件供方名稱，一個(gè)可以區(qū)分類別詞、一個(gè)沒有，例如“施耐德電氣有限公司”和“施耐德”。

(4)合格供方名稱和元器件供方名稱相似但不是同一家公司。例如“中國航天科工集團(tuán)有限公司”和“中國航天科技集團(tuán)有限公司”。

(5)合格供方名稱和元器件供方名稱相似，但類別詞不同。例如“深圳海瑞達(dá)電子有限公司”和“深圳海瑞達(dá)時(shí)頻設(shè)備有限公司”。

(6)合格供方名稱和元器件供方名稱字面很相似，但順序不一致。例如“聯(lián)創(chuàng)電子有限公司”和“創(chuàng)聯(lián)電子有限公司”。

前三種情形為正例，名稱有差異，但是應(yīng)該匹配成功。后三種情況為反例，名稱相似，但不應(yīng)該匹配成功。

2.2 算法改進(jìn)

Jaro-Winkler算法中缺乏對相同字符在原字符串中的間隔問題的考慮[14]，因此對相對相似的兩個(gè)名稱不能夠有效地拒絕匹配，對于前綴部分相同的兩字符，Jaro-Winkler匹配效果相對比較好。因此Jaro-Winkler算法對特征(4)中的名稱很相似的不同公司，錯(cuò)誤的匹配成功；對特征(6)中公司名稱明顯錯(cuò)位，但依然匹配成正例。

Levenshtein算法對2個(gè)字符串的長度、位序等相對比較敏感，因此對相似的反例能較準(zhǔn)確匹配，而對長度差異相對較大的正例易出現(xiàn)匹配錯(cuò)誤。因此Levenshtein算法對特征(4)到(6)的反例，容易匹配正確；因?yàn)槿Q和簡稱、總公司和子公司字符串的長度差異大，因此容易對特征(1)到(3)的正例拒絕匹配。

由于Jaro-Winkler算法能對前綴部分相同的字符串加分，因此Jaro-Winkler相似度算法對正例匹配效果比較好，但對字符位序、對相同字符之間的間隔沒有處理，所以對反例的匹配效果并不好。而Levenshtein算法考慮了字符串的長度、位序等情況。因此，考慮通過引入調(diào)整閾值及系數(shù)融合Jaro-Winkler和Levenshtein算法，以提高整體的匹配正確率，計(jì)算公式如下：

ana=?dw+βsim (?+β=1)

(9)

其中，dw為Jaro-Winkle算法計(jì)算的距離，sin為Levenshtein算法計(jì)算的相似度。

3 改進(jìn)算法在航天元器件合格供方中的應(yīng)用

3.1 供方名稱清洗及映射

采購單中的元器件數(shù)據(jù)來源于不同系統(tǒng)，而不同系統(tǒng)中的元器件供方名稱的字段長度、類型存在不一致的問題。在對供方名稱進(jìn)行處理時(shí)，先對數(shù)據(jù)進(jìn)行清洗能有效提高匹配正確率。數(shù)據(jù)清洗的對象主要是相似的記錄、異常值等。以建立供方名稱映射表方式，在不改變原始數(shù)據(jù)的情況下對供方名稱進(jìn)行清洗。映射表部分?jǐn)?shù)據(jù)如表1所示。

表1 供方名稱映射表部分?jǐn)?shù)據(jù)

3.2 建立停用詞字典

在匹配供方數(shù)據(jù)時(shí)，供方名稱中的部分后綴文本屬于冗余數(shù)據(jù)，如有限公司、研究院等。這些冗余數(shù)據(jù)在匹配過程中會影響匹配的準(zhǔn)確率。通過建立停用詞表，可減少冗余數(shù)據(jù)對匹配準(zhǔn)確率造成的干擾。在匹配供方時(shí)，去除供方和合格供方名稱中的停用詞，可有效提升匹配的正確率。通過對供方數(shù)據(jù)的分析與梳理，構(gòu)建了停用詞表。停用詞表部分?jǐn)?shù)據(jù)如表2所示。

表2 停用詞表部分?jǐn)?shù)據(jù)

續(xù)表2

3.3 合格供方匹配過程

首先對TDM、ERP等系統(tǒng)數(shù)據(jù)進(jìn)行抽取，在將供方數(shù)據(jù)匯集到數(shù)據(jù)倉庫過程中，對相似的、異常的供方名稱值進(jìn)行標(biāo)記，形成供方名稱映射表。采購部門用戶導(dǎo)入采購單，系統(tǒng)對采購單進(jìn)行分解，提取供方數(shù)據(jù)。然后系統(tǒng)對供方和合格供方數(shù)據(jù)按照供方名稱映射表進(jìn)行清洗。清洗完成后對供方和合格供方數(shù)據(jù)進(jìn)行停用詞處理。處理停用詞后，利用改進(jìn)的算法對供方和合格供方進(jìn)行匹配。最后利用堆排序，對每個(gè)供方選擇出匹配度最高的5個(gè)合格供方，供專業(yè)人員對其進(jìn)行判斷，如圖1所示。

圖1 合格供方匹配過程

3.4 閾值及系數(shù)的確定

在進(jìn)行供方匹配時(shí)，需要針對供方名稱和合格供方名稱按照相似度算法計(jì)算相似度，然后將結(jié)果與一個(gè)選擇設(shè)定的相似度閾值進(jìn)行比較，如果大于閾值，則認(rèn)為該供方為合格供方，否則，判定為不合格供方。文獻(xiàn)[1]對Jaro-Winkle和Levenshtein的最優(yōu)閾值進(jìn)行了分析，其中Jaro-Winkle的最優(yōu)閾值為0.709，其精確率為85.9%，Levenshtein的最優(yōu)閾值為0.662，其精確率約為62.2%。因此設(shè)定改進(jìn)算法的閾值為Jaro-Winkle的最優(yōu)閾值和Levenshtein的最優(yōu)閾值的平均值0.68。

為了確定?與β的值，隨機(jī)從供方數(shù)據(jù)集中抽取三組數(shù)據(jù)，每組數(shù)據(jù)有100條數(shù)據(jù)，計(jì)算每組數(shù)據(jù)在不同?與β值情況下的相似度。調(diào)整?的步長為0.1，0

圖2 相似度-閾值曲線

對三組數(shù)據(jù)精確率進(jìn)行判斷，其中第一組數(shù)據(jù)中62個(gè)正例58個(gè)匹配正確，38個(gè)反例28個(gè)拒絕匹配；其中第二組數(shù)據(jù)中66個(gè)正例60個(gè)匹配正確，34個(gè)反例28個(gè)拒絕匹配；其中第三組數(shù)據(jù)中58個(gè)正例51個(gè)匹配正確，42個(gè)反例34個(gè)拒絕匹配；三組平均精確率為86.3%。因此改進(jìn)的算法閾值設(shè)定為0.68，系數(shù)設(shè)定為?=0.6,β=0.4時(shí)，精確率略高于Jaro-Winkle算法，如表3所示。

表3 改進(jìn)算法的匹配情況

3.5 合格供方匹配結(jié)果分析

在業(yè)務(wù)系統(tǒng)中測試合格供方匹配功能，結(jié)果如圖3所示。用戶導(dǎo)入的采購單中有500條隨機(jī)選取供方數(shù)據(jù)。導(dǎo)入完畢后系統(tǒng)自動進(jìn)行匹配工作，匹配結(jié)果正確率相對較高。因此，改進(jìn)的算法能夠很好地完成合格供方匹配。

圖3 合格供方匹配

4 結(jié)束語

建立供方名稱清洗表、停用詞表，基于Jaro-Winkler算法并對其改進(jìn)，改進(jìn)后算法能很好地實(shí)現(xiàn)供方名稱和合格供方名稱的匹配，實(shí)現(xiàn)批量合格供方匹配的自動化，能極大地提高匹配效率，有助于航天元器件的采購工作，有效保證航天元器件的可靠性。