魏自強，班元郎，徐 偉，王文璽

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

0 引 言

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

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

1 研究現狀

1.1 短文本聚合模型

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

1.2 Jaro-Winkler算法

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

(1)Jaro算法。

(1)

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

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

(2)

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

(3)

(3)Jaro-Winkler計算公式。

Jaro-Winkler算法的相似度計算公式為：

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

(4)

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

1.3 Levenshtein(編輯距離)算法

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

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

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

(5)

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

(6)

其中，

(7)

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

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

(8)

式中，Sim為最終的相似度計算結果。越相似的2個字符串，Sim的值將越大。

2 改進Jaro-Winkler算法

2.1 供方數據特征

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

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

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

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

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

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

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

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

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

2.2 算法改進

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

Levenshtein算法對2個字符串的長度、位序等相對比較敏感，因此對相似的反例能較準確匹配，而對長度差異相對較大的正例易出現匹配錯誤。因此Levenshtein算法對特征(4)到(6)的反例，容易匹配正確；因為全稱和簡稱、總公司和子公司字符串的長度差異大，因此容易對特征(1)到(3)的正例拒絕匹配。

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

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

(9)

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

3 改進算法在航天元器件合格供方中的應用

3.1 供方名稱清洗及映射

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

表1 供方名稱映射表部分數據

3.2 建立停用詞字典

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

表2 停用詞表部分數據

續(xù)表2

3.3 合格供方匹配過程

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

圖1 合格供方匹配過程

3.4 閾值及系數的確定

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

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

圖2 相似度-閾值曲線

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

表3 改進算法的匹配情況

3.5 合格供方匹配結果分析

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

圖3 合格供方匹配

4 結束語

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