李 彤，崔琪偉，李 夏

（航空工業(yè)西安航空計(jì)算技術(shù)研究所，陜西 西安 710065）

0 引言

電子元器件是武器裝備的基礎(chǔ)與核心，其研制水平的高低對(duì)武器裝備發(fā)展的影響與日俱增。規(guī)范化的元器件數(shù)據(jù)信息管理以及快捷式的匹配流程等會(huì)大大促進(jìn)國(guó)產(chǎn)電子元器件的普及與選用，在保障武器裝備國(guó)產(chǎn)化需求的同時(shí)，也會(huì)激發(fā)國(guó)內(nèi)元器件廠家自主、高質(zhì)量研發(fā)的熱情，形成正循環(huán)產(chǎn)業(yè)鏈，有利于促進(jìn)國(guó)內(nèi)元器件產(chǎn)業(yè)的良性發(fā)展，故各方都對(duì)快速地進(jìn)行元器件信息匹配、查詢等提出了迫切的需求。

但是由于型號(hào)元器件數(shù)量龐大、來源不一，往往會(huì)出于主觀性差異、數(shù)據(jù)錄入錯(cuò)誤、異源融合[1]等因素導(dǎo)致收集到的元器件數(shù)據(jù)質(zhì)量差，直接通過EXCEL進(jìn)行數(shù)據(jù)處理效率低下，且當(dāng)處理的數(shù)據(jù)量較大時(shí)會(huì)出現(xiàn)運(yùn)行崩潰的現(xiàn)象，而傳統(tǒng)的基于編輯距離[2]（EditDistance，ED）的模糊匹配方法耗時(shí)長(zhǎng)，且其基于動(dòng)態(tài)規(guī)劃計(jì)算時(shí)使用的矩陣也會(huì)增加不少空間復(fù)雜度，導(dǎo)致項(xiàng)目進(jìn)度緩慢。為了解決這一問題，我們基于改進(jìn)的詞頻加權(quán)和余弦相似度，提出一種模糊匹配算法，該算法首先根據(jù)建立的多個(gè)數(shù)據(jù)庫(kù)，包括元器件廠家規(guī)范庫(kù)、元器件封裝庫(kù)、元器件型號(hào)特殊字符庫(kù)等，快速地對(duì)原始元器件數(shù)據(jù)進(jìn)行清洗和歸一化，接著基于TF-IDF、特征加權(quán)、余弦相似度等開展模糊匹配，根據(jù)元器件型號(hào)信息快速計(jì)算出量化的相似度，根據(jù)相似度排序，并篩選數(shù)據(jù)，生成匹配數(shù)據(jù)表，再人工核查匹配數(shù)據(jù)表，最終完成元器件信息的匹配、查詢和管理等。將該算法與傳統(tǒng)的EXCEL工具、編輯距離算法、Jaccard相似度匹配算法[3]以及Sorensen Dice相似度匹配算法等進(jìn)行實(shí)驗(yàn)對(duì)比，保證其匹配效率及準(zhǔn)確度均最優(yōu)。

1 相關(guān)研究

1.1 編輯距離算法

編輯距離（Minimum Edit Distance，MED），也稱萊文斯坦距離（LevenshteinDistance），通常用來度量?jī)蓚€(gè)字符串的相似程度，例如在兩個(gè)序列之間，編輯距離即為序列w1轉(zhuǎn)換為另一個(gè)序列w2所需要的最少的單字符操作次數(shù)，該操作有且僅有3種：插入、刪除和替換。

1.2 Jaccard相似度匹配算法

Jaccard相似度主要用于衡量?jī)蓚€(gè)集合的相似程度，其定義為給定兩個(gè)集合A、B，其Jaccard系數(shù)為集合A、B交集大小與并集大小的比值。Jaccard系數(shù)取值區(qū)間為[0，1]，Jaccard系數(shù)值越大，則認(rèn)為兩集合相似度越高，但該方法的缺點(diǎn)是其受數(shù)據(jù)規(guī)模的影響較大。

1.3 Sorensen Dice相似度匹配算法

與Jaccard類似，Sorensen Dice系數(shù)也是一種簡(jiǎn)單集合之間相似度的計(jì)算方法，也可用來衡量字符串間的相似性，但其計(jì)算方式與Jaccard系數(shù)略有不同，Sorensen Dice系數(shù)是兩個(gè)集合交集的2倍除以兩集合相加，而非并集，其取值范圍為[0，1]。同樣，Sorensen Dice系數(shù)值越大，認(rèn)為兩集合相似度越高。相較于Jaccard系數(shù)，該方法更為直觀展示了字符串間的重疊百分比，但其也受數(shù)據(jù)集規(guī)模的影響較大。

1.4 TF-IDF

TF-IDF（Term Frequency-Inverse Document Frequency，詞頻-逆文件頻率），是一種常用的文本特征選擇方式，常用于信息檢索與文本挖掘的加權(quán)。其中，TF（Term Frequency）表示關(guān)鍵詞在文章中出現(xiàn)的頻率，該關(guān)鍵詞在文章中出現(xiàn)的次數(shù)越多，則越重要；IDF（Inverse Document Frequency）表示逆文件頻率，意味著該關(guān)鍵詞在文檔集中出現(xiàn)越頻繁，對(duì)于文檔的區(qū)分能力就越小，其重要性隨之下降。Gu Y H等[4]提出，當(dāng)前對(duì)文本中關(guān)鍵詞的權(quán)值計(jì)算主要采用TF-IDF方法。周麗杰等[5]認(rèn)為，TF-IDF值是NLP（Natural Language Processing，自然語言處理）中普遍應(yīng)用的關(guān)鍵詞權(quán)重計(jì)算方法。其主要思想是，文本的重要性隨著它在文件中出現(xiàn)的次數(shù)成正比增加，但同時(shí)會(huì)隨著它在語料庫(kù)中出現(xiàn)的頻率成反比下降。即如果一個(gè)詞語在某篇文章中出現(xiàn)的頻率TF較高，且在其他文章中很少出現(xiàn)，則認(rèn)為該詞語具有很好的類別區(qū)分能力。

1.5 余弦相似度

余弦相似度（cosinesimilarity），又稱余弦相似性，是通過計(jì)算兩個(gè)向量的夾角余弦值來評(píng)估他們的相似度，其只與向量的方向有關(guān)，與其幅值無關(guān)。一個(gè)向量空間中兩個(gè)向量夾角間的余弦值越接近1，表明這兩個(gè)向量越相似。在度量一對(duì)文本的相似度時(shí)，將文本矢量化后，就可將兩個(gè)向量夾角的余弦值作為兩個(gè)文本的相似度評(píng)估標(biāo)準(zhǔn)。

陳仕鴻等[6]指出，計(jì)算兩個(gè)文本余弦相似度的方法分為四個(gè)步驟：文本分詞、刪去停用詞、文本矢量化、計(jì)算余弦相似度。同時(shí)，李鯤程等[7]指出，根據(jù)TF-IDF的原理，一個(gè)單詞出現(xiàn)的頻率越高，說明這個(gè)單詞就越重要，因此生成文本矢量時(shí)，可以用詞頻來代替該文本矢量每個(gè)維度的值。當(dāng)兩個(gè)文本長(zhǎng)度差距很大，但內(nèi)容相近時(shí)，如果使用詞頻或詞向量作為特征，它們?cè)谔卣骺臻g的歐式距離可能會(huì)很大，但是其向量夾角可能會(huì)相對(duì)較小，因而余弦相似度較高。此外，相較于歐氏距離易受特征向量維度影響的特性，余弦相似度在特征維度較高時(shí)取值仍保持[-1，1]，較為穩(wěn)定。

2 基于詞頻加權(quán)和余弦相似度的匹配算法

元器件型號(hào)數(shù)據(jù)有很強(qiáng)的規(guī)范性，其大多是以字母加數(shù)字組合構(gòu)建而成，與傳統(tǒng)的編輯距離方法、Jaccard相似度匹配算法、Sorensen Dice相似度匹配算法等不同，我們針對(duì)這種規(guī)范性較強(qiáng)的數(shù)據(jù)，提出基于詞頻加權(quán)和余弦相似度的模糊匹配算法，其核心思想是通過TF-IDF的詞頻分析，將元器件型號(hào)數(shù)據(jù)映射到固定特征的一維向量中，同時(shí)根據(jù)元器件型號(hào)數(shù)據(jù)的長(zhǎng)度和字符特征對(duì)該向量進(jìn)行加權(quán)，最后通過余弦相似度進(jìn)行相似度計(jì)算，返回相似度值最大的向量所對(duì)應(yīng)的元器件型號(hào)數(shù)據(jù)。

2.1 元器件型號(hào)數(shù)據(jù)向量化

元器件型號(hào)數(shù)據(jù)是一類規(guī)范性較強(qiáng)的數(shù)據(jù)，通常以字母和數(shù)字組合的方式構(gòu)成，當(dāng)然很多元器件型號(hào)數(shù)據(jù)會(huì)添加很多額外信息，例如封裝、元器件類型、質(zhì)量等級(jí)、顏色等，所以需要對(duì)元器件型號(hào)進(jìn)行預(yù)處理，刪除不需要參與匹配的冗余信息。根據(jù)TF-IDF算法思想，對(duì)元器件型號(hào)數(shù)據(jù)進(jìn)行“詞頻”統(tǒng)計(jì)，詞頻是一個(gè)相對(duì)概念，對(duì)于元器件型號(hào)數(shù)據(jù)而言，字符之間并沒有強(qiáng)相關(guān)含義聯(lián)系，所以可以將每個(gè)字符看作一個(gè)詞進(jìn)行詞頻統(tǒng)計(jì)，且元器件型號(hào)數(shù)據(jù)的長(zhǎng)度不統(tǒng)一，導(dǎo)致向量空間不統(tǒng)一，詞頻統(tǒng)計(jì)結(jié)果不能作為輸入直接運(yùn)算，為了將所有元器件型號(hào)數(shù)據(jù)統(tǒng)一到同一個(gè)向量空間中，同時(shí)為了方便計(jì)算，設(shè)計(jì)固定的映射關(guān)系，可將所有型號(hào)數(shù)據(jù)映射到統(tǒng)一的向量空間。且以經(jīng)驗(yàn)看來，當(dāng)兩個(gè)元器件型號(hào)規(guī)格的字符串長(zhǎng)度相差較大時(shí)，極大概率不是同一個(gè)元器件，故將元器件型號(hào)長(zhǎng)度作為文本向量的第一維。向量空間如下：

2.2 元器件型號(hào)數(shù)據(jù)特征及向量加權(quán)

元器件型號(hào)數(shù)據(jù)的詞頻分析，不僅對(duì)于型號(hào)數(shù)據(jù)的位置信息敏感，同時(shí)其對(duì)字符間的相對(duì)順序是敏感的，相同的詞頻向量對(duì)應(yīng)的原始元器件型號(hào)數(shù)據(jù)可能截然不同，具體的表現(xiàn)為某兩個(gè)型號(hào)例如為“GHYHY27395”“GHYYH27395”在詞頻角度去看這兩個(gè)數(shù)據(jù)的向量是相同的，但卻是兩種完全不同的元器件，所以針對(duì)這種情況，提出對(duì)基于詞頻統(tǒng)計(jì)的元器件型號(hào)數(shù)據(jù)向量進(jìn)行加權(quán)，權(quán)重與元器件型號(hào)數(shù)據(jù)字符的位置相關(guān)，位置越靠前的字符，其權(quán)重越高。到了一定位置后，后續(xù)的字符不需要再加權(quán)，這一點(diǎn)是由元器件型號(hào)數(shù)據(jù)的屬性帶來的。元器件型號(hào)靠前部分的數(shù)據(jù)通常表示該元器件的系列、種類等，靠后的部分通常代表元器件數(shù)據(jù)的細(xì)節(jié)信息，例如內(nèi)存大小，管腳數(shù)量等，所以在元器件前端部分相同的情況下，代表著兩種元器件屬于一個(gè)系列，核心功能等方面大致相同，故只需要給元器件型號(hào)數(shù)據(jù)位置靠前的部分進(jìn)行加權(quán)即可。權(quán)重向量如下：

向量加權(quán)：

2.3 數(shù)據(jù)向量化余弦相似度計(jì)算

兩條數(shù)據(jù)分別為D1、D2，經(jīng)過詞頻統(tǒng)計(jì)后由元器件型號(hào)數(shù)據(jù)轉(zhuǎn)化為詞頻向量，經(jīng)過加權(quán)后得到基于詞頻加權(quán)的向量，它們之間的余弦相似度計(jì)為cosθ12。余弦相似度：

3 實(shí)驗(yàn)結(jié)果

3.1 實(shí)驗(yàn)環(huán)境及數(shù)據(jù)集

計(jì)算機(jī)配置：Win11系統(tǒng)、16G內(nèi)存、i7-12700 CPU、python3.9。實(shí)驗(yàn)數(shù)據(jù)集選擇進(jìn)口元器件型號(hào)數(shù)據(jù)，元器件信息均來自互聯(lián)網(wǎng)，目前國(guó)內(nèi)外無相關(guān)領(lǐng)域的開源數(shù)據(jù)集。

實(shí)驗(yàn)內(nèi)容主要是對(duì)基于詞頻分析和余弦相似度的模糊匹配算法與EXCEL工具、編輯距離算法、Jaccard相似度匹配算法、Sorensen Dice相似度匹配算法就匹配準(zhǔn)確度和運(yùn)行效率進(jìn)行對(duì)比分析，選擇3 000條數(shù)據(jù)作為原始數(shù)據(jù)，3000條數(shù)據(jù)作為知識(shí)庫(kù)數(shù)據(jù)進(jìn)行匹配。

3.2 實(shí)驗(yàn)結(jié)果分析

在同樣的數(shù)據(jù)集中，通過多種匹配算法計(jì)算得到結(jié)果比對(duì)見表1。

表1 各算法匹配結(jié)果對(duì)比

從表1可以看出在同樣的數(shù)據(jù)集下基于詞頻加權(quán)和余弦相似度的模糊匹配算法在準(zhǔn)確率和運(yùn)行時(shí)間方面明顯優(yōu)于其他方法。傳統(tǒng)的EXCEL工具無論是在準(zhǔn)確率還是運(yùn)行時(shí)間方面均不占優(yōu)勢(shì)，且其在處理海量數(shù)據(jù)時(shí)，往往會(huì)因?yàn)橛?jì)算量過大出現(xiàn)“卡死”現(xiàn)象，大大影響了工作效率；而單純用余弦相似度的方法由于忽略了字符的位置加權(quán)信息，準(zhǔn)確率有一定幅度地降低；基于動(dòng)態(tài)規(guī)劃的匹配算法如編輯距離等由于時(shí)間復(fù)雜度過高，當(dāng)數(shù)據(jù)量較大時(shí)，運(yùn)行時(shí)間會(huì)較長(zhǎng)，同時(shí)匹配準(zhǔn)確率也會(huì)下降；而利用“交集”除以“并集”思想的Jaccard算法和Sorensen Dice算法在處理特定任務(wù)時(shí)可以在低時(shí)間復(fù)雜度的前提下做到匹配準(zhǔn)確率較高，但是由于元器件型號(hào)規(guī)格數(shù)據(jù)寫法多樣，不能進(jìn)行去重操作，當(dāng)數(shù)據(jù)量較大時(shí)，這兩種方法的匹配準(zhǔn)確率會(huì)顯著降低。而提出的基于詞頻加權(quán)和余弦相似度的模糊匹配算法充分考慮到電子元器件型號(hào)規(guī)格的組成特點(diǎn)及字符特性，對(duì)詞頻向量進(jìn)行加權(quán)，再計(jì)算待匹配向量和庫(kù)向量間的余弦相似度，大大提高了匹配準(zhǔn)確率。而且該算法在對(duì)數(shù)據(jù)庫(kù)進(jìn)行一次計(jì)算后就將其向量存儲(chǔ)起來，后續(xù)匹配時(shí)可直接將待匹配向量與存儲(chǔ)起來的庫(kù)向量進(jìn)行匹配，提高工作效率。

4 結(jié)論

隨著電子元器件產(chǎn)業(yè)的蓬勃發(fā)展，快速且準(zhǔn)確地進(jìn)行元器件模糊匹配能有效提升各方工作效率，在以往的匹配算法基礎(chǔ)上，提出一種基于詞頻加權(quán)和余弦相似度的模糊匹配算法。經(jīng)多個(gè)對(duì)比實(shí)驗(yàn)驗(yàn)證，算法在準(zhǔn)確率和運(yùn)行時(shí)間兩個(gè)主要方面均有較大改善，提升匹配準(zhǔn)確率的同時(shí)，縮短運(yùn)行時(shí)間，可用于電子元器件領(lǐng)域型號(hào)規(guī)格的模糊匹配，有效解決當(dāng)前電子元器件數(shù)量龐大、信息模糊、處理效率低下等問題。