基于分詞的文本模糊匹配分析

本文出自 Tencent CDC
原文地址?https://cdc.tencent.com/2020/08/30/如何有效的進(jìn)行公司名稱匹配/

1. 背景及主要問題

項(xiàng)目需要把兩個獨(dú)立的系統(tǒng)通過公司名稱的匹配來實(shí)現(xiàn)數(shù)據(jù)打通，其中一個系統(tǒng)的公司數(shù)有40萬+，另一個系統(tǒng)中需要匹配的公司數(shù)3600+，如果直接通過SQL LIKE形式的方式來關(guān)聯(lián)兩個系統(tǒng)，發(fā)現(xiàn)只有1100多家公司名稱可以匹配，如果剩余2500家左右的公司需要純?nèi)斯し绞绞謩悠ヅ?，不僅工作量大而且效率低。

通過分析bad case發(fā)現(xiàn)公司名稱難匹配的主要問題有以下兩點(diǎn)：

1.1 公司簡稱形式多樣

公司簡稱往往是人們根據(jù)習(xí)慣約定而成的，沒有標(biāo)準(zhǔn)的形式。比如深圳市騰訊計算機(jī)系統(tǒng)有限公司的簡稱是騰訊，這種用公司全稱的某一部分作為簡稱很容易通過字符串包含的方式來匹配。但是很多公司的簡稱是其它形式，比如中國銀行股份有限公司的簡稱是中行，中國石油化工有限公司的簡稱是中石化，這種取公司全稱中不同部分拼接而來的簡稱很難直接通過字符串模糊匹配取得較好的效果。另外有些公司的簡稱可能存在多種，比如中國東方航空有限公司有人簡稱東航，也有人簡稱東方航空。

總之，各式各樣的簡稱形式導(dǎo)致字符串匹配時很難正確識別。傳統(tǒng)的解決辦法通常是維護(hù)一個公司全稱和簡稱的 Mapping 關(guān)系作為常識庫，但如果僅僅依靠常識庫來解決，由于公司數(shù)量眾多而且隨時間而變化，維護(hù)和更新常識庫就會成為一個很大的問題。

1.2 簡稱字?jǐn)?shù)少時錯誤率高

比如深圳市閱文教育咨詢有限公司的簡稱是閱文，但是當(dāng)拿閱文去系統(tǒng)做LIKE形式的匹配時會發(fā)現(xiàn)總共有35家?guī)в?code style>閱文子串的公司全稱，部分如下：

• 北京大閱文化傳播有限公司
• 成都悅閱文化傳播有限公司
• 杭州怡閱文化傳媒有限公司
• 北京鼎閱文學(xué)信息技術(shù)有限公司
• 深圳華閱文化傳媒有限公司
• 上海親閱文化科技發(fā)展有限公司

這些匹配的公司全稱往往所包含的匹配子串在語義上是割裂的，但是直接的包含匹配無法進(jìn)行語義上的分割，導(dǎo)致匹配的錯誤率隨著簡稱字?jǐn)?shù)的減少而升高。

2.方案設(shè)計

基于以上問題，在處理公司名稱匹配時將工作主要分為了兩大部分：

• 數(shù)據(jù)清洗，主要通過分詞將公司全稱拆解并對可能的簡稱形式進(jìn)行組合；
• 模糊匹配，主要是基于最短編輯距離算法計算猜測的簡稱和需要匹配的簡稱的匹配分?jǐn)?shù)，然后通過篩選最高匹配分?jǐn)?shù)來找到最佳的匹配結(jié)果。

以下為各部分工作的詳細(xì)介紹：

2.1 形式化表示公司全稱

公司名稱一般由地區(qū)(Region)、關(guān)鍵詞(X)、行業(yè)(Industry)和公司后綴(Org_Suffix)四部分組成。
比如深圳市萬網(wǎng)博通科技有限公司，地區(qū)為深圳市、萬網(wǎng)博通是關(guān)鍵詞、科技是行業(yè)詞，有限公司是公司后綴，這樣我們就可以用RXIO表示此公司的名稱結(jié)構(gòu)。
其他結(jié)構(gòu)的公司名稱也可以用類似的方式表示，比如：

在實(shí)現(xiàn)方面借助了分詞工具jieba^[1] 提供的詞性標(biāo)注功能，因?yàn)樵~性標(biāo)注需要提前分詞然后識別每個詞的詞性，所以這塊的準(zhǔn)確率與使用的分詞工具和分詞模式有一定的關(guān)系。
例如上海景栗信息科技有限公司分詞后標(biāo)注詞性如下[上海/ns 景栗/x 信息/n 科技/n 有限公司/n]，所以可以很容易把他的結(jié)構(gòu)表示為RXIIO，效果如圖：

有了分詞及每個token的詞性標(biāo)注，就可以根據(jù)詞性把不同的token歸類到RXIO這四大類中。其中屬于公司后綴O類型的數(shù)量有限，可以采用建立公司后綴詞庫的形式識別。地區(qū)R類型可以直接使用詞性為ns(代表地名)的token完成分類。對于關(guān)鍵詞X類型和行業(yè)I類型的識別這塊是比較模糊的，所以我沒有嚴(yán)格的區(qū)分，主要結(jié)合了詞性和自定義的行業(yè)詞庫完成對關(guān)鍵詞和行業(yè)的分類。在對所有公司全稱按如上方式清洗后就可以得到一張其形式化表示的數(shù)據(jù)，如圖所示：

2.2 構(gòu)造可能的簡稱形式

有了公司全稱的形式化表示后，下一步是猜測其可能的簡稱結(jié)構(gòu)。
比如中國移動有限責(zé)任公司的簡稱是中移動就可以表示為 RXO => R[1-1]X，其中R[1-1]代表取第一個地區(qū)分詞的第一個字；
又比如中國聯(lián)通有限責(zé)任公司的簡稱是中國聯(lián)通可以表示為 RXO => RX, 這樣我們就得到了RXO這種形式公司全稱可能的簡稱形式有 R[1]X 和 RX 兩種形式。
依此類推，通過對部分公司全稱對應(yīng)的簡稱形式的統(tǒng)計，我們就可以得到一份規(guī)則用來表示不同形式化結(jié)構(gòu)的公司全稱可能對應(yīng)的簡稱形式:

同時也可以不斷向里面添加新的規(guī)則，當(dāng)把2.1步驟獲得所有公司全稱形式化表示的數(shù)據(jù)應(yīng)用這些規(guī)則后，就可以得到一份每個公司全稱對應(yīng)的可能的簡稱形式，如圖所示：

2.3 最短編輯距離匹配

有了公司全稱的所有可能簡稱組合后，就可以通過字符串相似度算法來計算他們的匹配度，如果匹配分?jǐn)?shù)達(dá)到一定的閾值就可以認(rèn)為是匹配的。

常用的字符串相似度算法有最短編輯距離算法和余弦相似度算法，這里的匹配使用了最短編輯距離的算法實(shí)現(xiàn)。關(guān)于最短編輯算法的介紹如下：

Minimum Edit Distance(最短編輯距離) 算法
任給兩個字符串X 和Y，使用以下三種操作將字符串X變到字符串Y ：

• 插入(Insert)操作，代價為1；
• 刪除操作(delete)，代價為1；
• 替換操作(substitute)，代價為2，這里是Levenshtein Edit Distance，其他算法中替換操作的代價和其他兩類操作一樣(為1)；

比如 ”intention” 變成 “execution” 執(zhí)行了三次替換，一次刪除，一次插入，因此這兩個單詞的最短編輯距離是8(圖示如下)。

1. 更多參考：
   https://web.stanford.edu/class/cs124/lec/med.pdf
2. 具體的編程實(shí)現(xiàn)可參考:
   https://www.geeksforgeeks.org/edit-distance-dp-5/

算出最短編輯距離后，可以根據(jù)他們字符串的長度計算其相似度，公式如下：

相關(guān)代碼如下：

有了相似度計算公式，就可以對一家公司名所有可能的簡稱形式分別與待匹配公司名計算相似度，然后取分?jǐn)?shù)最高者作為兩家公司最終的匹配分?jǐn)?shù)，效果如圖：

3. 問題與改進(jìn)

3.1 最短編輯距離匹配的問題

在check匹配分?jǐn)?shù)時會發(fā)現(xiàn)有些公司的匹配結(jié)果明顯不對，但是他們的匹配分?jǐn)?shù)很高的現(xiàn)象。比如深圳市麟云科技有限公司的簡稱猜測是麟云科技時與云遙科技的相似度最高，匹配得分是92分。而云遙網(wǎng)絡(luò)科技（上海）有限公司的簡稱云遙網(wǎng)絡(luò)與云遙科技的相識度匹配得分只有83分。

很明顯單純的使用最短編輯距離來計算公司名稱的相似度忽略的公司名稱各部分權(quán)重的不同，導(dǎo)致科技比云遙關(guān)鍵字的匹配一樣或更重要。

3.2 改進(jìn)最短編輯距離匹配

針對單純使用最短編輯算法匹配無法反應(yīng)語意上的相似性，在匹配時引入了對公司名稱各部分權(quán)重的計算。同樣的編輯距離，如果權(quán)重越高的詞匹配則匹配度越高。比如云遙網(wǎng)絡(luò)科技（上海）有限公司和深圳市麟云科技有限公司在分詞時已經(jīng)標(biāo)注了關(guān)鍵詞、行業(yè)詞和地名詞，如果所示：

在匹配時先分別計算每個部分的匹配分?jǐn)?shù)，然后按照8:1:1的權(quán)重分配計算最終的加權(quán)匹配分?jǐn)?shù)，這樣就修正了直接匹配時的不足，讓關(guān)鍵詞部分匹配分?jǐn)?shù)越高的公司最終的匹配分?jǐn)?shù)越高：

3.3 提升效果

相比原來SQL LIKE形式只匹配了1100+家公司，這種方案在此基礎(chǔ)上新增了匹配分?jǐn)?shù)為 100 分的456家，匹配分?jǐn)?shù)在 90 分以上的789家，匹配分?jǐn)?shù)在 80 分以上的1810家。

4. 不足與方向

此種方案主要是在字符串模糊匹配的基礎(chǔ)上做了語義化的拆分和加權(quán)匹配，它的效果依賴于前期分詞和形式化分類的好壞，如果不能正確的按照語義把公司名稱拆分并歸類到不同的分類中，后面的加權(quán)匹配效果就會大打折扣。

隨著人工智能的發(fā)展，基于深度學(xué)習(xí)的語義匹配已成為NLP領(lǐng)域基礎(chǔ)技術(shù)，也可以參考這方面的技術(shù)。

5. 總結(jié)與沉淀

本文需要解決的是公司簡稱和全稱之間的匹配問題，傳統(tǒng)的字符串模糊匹配在匹配字符數(shù)量相差很大的情況下通常得分很低（簡稱長度通常在2～6個字符，全稱則通常是10個字符以上）。針對此問題本文總結(jié)了一些方式和方法來提高匹配率，主要包括如下四個步驟：

1. 形式化表示公司全稱。對公司全稱進(jìn)行分詞并根據(jù)各部分的詞性形式化的表示公司名稱結(jié)構(gòu)(RXIO)。
2. 猜測可能的簡稱形式。根據(jù)既定的規(guī)則分解出全稱可能的簡稱形式，作為待匹配項(xiàng)。
3. 所有待匹配項(xiàng)和簡稱進(jìn)行加權(quán)模糊匹配。匹配時根據(jù)最短編輯距離計算 XIRO 各部分的匹配分?jǐn)?shù)，再按照每個部分的權(quán)重計算最終的加權(quán)匹配分?jǐn)?shù)，減少非關(guān)鍵詞部分對匹配分?jǐn)?shù)的影響。
4. 選擇所有匹配中的最高分作為此全稱和簡稱匹配的最終得分。

所以在遇到傳統(tǒng)單獨(dú)字符串模糊匹配無法有效解決匹配問題時，嘗試通過分詞與自定義規(guī)則組合，再結(jié)合字符串模糊匹配和加權(quán)系數(shù)，可能取得較好的效果。

參考資料