基于約束的字符串相似度研究與應(yīng)用

劉月錕

摘 要：為了提高計(jì)算字符串相似度的準(zhǔn)確度，分析了字符串相似度計(jì)算中準(zhǔn)確度難以提高的原因，研究了當(dāng)前編輯距離計(jì)算中存在的問題，對(duì)編輯距離計(jì)算中替換操作代價(jià)進(jìn)行修訂，使編輯距離的計(jì)算更加符合實(shí)際應(yīng)用，提出了相似字符串轉(zhuǎn)換的不可逆，說明孤立的字符串難以做到精確匹配，挖掘與字符串密切相關(guān)的屬性，提出了具有約束的字符串定義，在此基礎(chǔ)上改進(jìn)了萊文斯坦算法，通過對(duì)實(shí)例數(shù)據(jù)分析，驗(yàn)證了該方法在基于關(guān)系型數(shù)據(jù)庫的應(yīng)用系統(tǒng)中的有效性。

關(guān)鍵詞： 編輯距離;字符串相似度;萊文斯坦算法;約束字符串;轉(zhuǎn)換不可逆

文章編號(hào)： 2095-2163（2019）03-0180-04 中圖分類號(hào)： TP391 文獻(xiàn)標(biāo)志碼： A

0 引 言

隨著數(shù)據(jù)規(guī)模的不斷增長(zhǎng)，數(shù)據(jù)共享是各單位間需要迫切解決的關(guān)鍵問題。各單位間數(shù)據(jù)庫結(jié)構(gòu)不同，數(shù)據(jù)代碼差別很大，數(shù)據(jù)共享主要是基礎(chǔ)數(shù)據(jù)共享，而基礎(chǔ)數(shù)據(jù)中至關(guān)重要的就是單位信息。因此關(guān)于不同系統(tǒng)中單位名稱的成功匹配即已成為一個(gè)頗具實(shí)用價(jià)值的研發(fā)項(xiàng)目。不同系統(tǒng)中單位的代碼不同，單位名稱存在很大差距，有的使用簡(jiǎn)稱或當(dāng)?shù)丶s定俗成的名稱，要進(jìn)行單位名稱的有效匹配，字符串相似度度量是有效的技術(shù)方法。通常，求解字符串相似度的方法可依據(jù)不同的特征將其劃分為3類：基于字面相似的方法、基于統(tǒng)計(jì)關(guān)聯(lián)的方法、基于語義相似的方法。其中，基于字面相似的方法中，比較典型的有基于編輯距離的方法[1]。編輯距離廣泛應(yīng)用于字符串近似搜索，與其他度量字符串相似性的算法，如：余弦距離、海明距離、Jaccard距離等相比，編輯距離能夠精確度量2個(gè)字符串的相似程度[2]。

本文對(duì)使用編輯距離度量字符串相似度的方法進(jìn)行了深入剖析，研究提出了相似字符串轉(zhuǎn)換的不可逆定義，同時(shí)證實(shí)了這一命題結(jié)論，即：將字符串作為孤立個(gè)體時(shí)，在一定程度上，難以明顯提高匹配的準(zhǔn)確度，故而本次研究中根據(jù)字符串的背景環(huán)境，考慮了與字符串密切相關(guān)的屬性，進(jìn)而提出了具有約束的字符串定義。在此基礎(chǔ)上，參考關(guān)系型數(shù)據(jù)庫的知識(shí)，通過改進(jìn)Levenshtein算法，實(shí)現(xiàn)了單位名稱的相似度對(duì)比。如此則不但提高了比對(duì)效率，而且也改善了比對(duì)精度。本文最后，通過社會(huì)保險(xiǎn)與稅務(wù)數(shù)據(jù)共享的實(shí)例，也驗(yàn)證了本文方法的良好應(yīng)用效果。

1 字符串相似度的經(jīng)典算法

Levenshtein算法是經(jīng)典的計(jì)算字符串相似度的算法。Levenshtein算法使用編輯距離計(jì)算字符串的相似度，而利用編輯距離計(jì)算字符串的相似度，具有結(jié)果準(zhǔn)確度高，操作簡(jiǎn)單等優(yōu)點(diǎn)。對(duì)此將做出研究闡釋如下。

1.1 編輯距離

編輯距離表示將一個(gè)字符串轉(zhuǎn)換為另一個(gè)字符串所需要的最少編輯次數(shù)，編輯是指將字符串中的字符進(jìn)行插入、刪除或替換操作，這個(gè)概念由Levenshtein于1966年提出[3]，而由其一并提出的求編輯距離算法即稱為L(zhǎng)evenshtein算法，簡(jiǎn)稱為L(zhǎng)D算法。

設(shè)原字符串是s，目標(biāo)字符串為t，編輯距離定義為：distance（t，s）。求取編輯距離的過程詳見如下。

1.2 字符串相似度

設(shè)原字符串為s，目標(biāo)字符串為t，s的長(zhǎng)度為m，t的長(zhǎng)度為n，定義2個(gè)字符串的相似度為：sim（t，s）。研究推得其計(jì)算公式為：

相似度介于[0，1]之間，值越大表示2個(gè)字符串相似程度越大，值為1時(shí)表示2個(gè)字符串完全一致。

1.3 經(jīng)典相似度算法存在的問題

考慮2個(gè)例子，設(shè)t=“ab”，s=“cd”，按照Levenshtein算法計(jì)算2個(gè)字符串的相似度為0.5;設(shè)t=“臨邑縣迎曦大街896號(hào)”，s=“樂陵市湖濱西路140號(hào)”，按照Levenshtein算法計(jì)算2個(gè)字符串的相似度為0.55;顯然，按照字符串字面意義看，這2個(gè)相似度都不可能達(dá)到0.5。

為了便于分析問題，現(xiàn)在簡(jiǎn)化字符串模型，假設(shè)字符串t長(zhǎng)度為n，字符串s長(zhǎng)度為m，n>m，n-m=k，t、s中相同字符串在m長(zhǎng)度中滿足最大對(duì)應(yīng)，事實(shí)上k長(zhǎng)度的字符串中與m相同的字符，可以通過刪除、插入操作變換到t字符串的前面，如：t=“abc”，s=“ac”，t經(jīng)過刪除插入變?yōu)椤癮cb”。由Levenshtein算法可得如下數(shù)學(xué)公式：

此公式的推導(dǎo)過程為：假設(shè)字符串t長(zhǎng)度為n，字符串s長(zhǎng)度為m，n>m，n-m=k，前m個(gè)字符中有相同字符i個(gè)，則字符串t和s前m個(gè)字符變?yōu)橐恢?，需要m-i次替換操作，然后，s字符串經(jīng)過k次插入，轉(zhuǎn)換為與t一致，則編輯距離為：m-i+k=m-i+n-m=n-i，所以，m+n-n+i=m+i，則相似度即為公式（2）。

當(dāng)n=m且i=0時(shí)，即2個(gè)字符串長(zhǎng)度相等且沒有相同字符時(shí)，相似度為0.5，即使i=0，sim>0，相似度永遠(yuǎn)大于零。

2 經(jīng)典相似度算法改進(jìn)

按照公式（2）計(jì)算的相似度永遠(yuǎn)大于零，究其原因就在于求編輯距離時(shí)插入、刪除、替換為基本操作，地位等同，所產(chǎn)生的花費(fèi)最大都是1，但實(shí)際操作中，替換操作的花費(fèi)與插入、刪除是不等同的，替換可以分解為刪除和插入兩個(gè)操作，如將字符a替換為b，操作為刪除a、插入b，字符不同時(shí)，cost應(yīng)為2。

2.1 改進(jìn)的相似度計(jì)算公式

改進(jìn)的相似度計(jì)算公式可表示為：

此公式的推導(dǎo)過程為：字符串模型仍然采用公式（2）的模型，則字符串t和s前m個(gè)字符變?yōu)橐恢滦枰?（m-i）次替換操作，而后，s字符串經(jīng)過k次插入，轉(zhuǎn)換為與t一致，則編輯距離為：2（m-i）+k=2m-2i+n-m=n+m-2i，所以，m+n-n-m+2i=2i，則相似度即為公式（3）。

當(dāng)i=0時(shí)，即2個(gè)字符串沒有相同字符時(shí)，相似度為0。

2.2 改進(jìn)的字符串相似度算法

算法1 2個(gè)字符串的相似度算法改進(jìn)

Input：string s and t

Output：sim_imp（t，s）

字符串s長(zhǎng)度 m=len（s）

字符串t 長(zhǎng)度 n=len（t）

定義二維數(shù)據(jù)dif[n+1][m+1]

初始化dif[n+1][m+1]

for i=1 to n

for j=1 to m

if t[i]=s[j]

cost=0

else

cost=2

dif[i][j]=min（

dif[i-1][j]+1， //刪除

dif[i][j-1]+1，//插入

dif[i-1][j-1]+cost） //替換

return （n+m-dif[n][m]）/（n+m）

按照算法1計(jì)算1.3中2個(gè)例子的字符串的相似度，分別為0和0.09，這是與實(shí)際情況相符的。

2.3 改進(jìn)字符串相似度算法的不足

改進(jìn)后的算法仍然存在不足，在一定地域環(huán)境中人們對(duì)于單位名稱習(xí)慣使用單位簡(jiǎn)稱或約定俗成的叫法，這樣一來就極容易造成誤判，如：“高邑縣第一中學(xué)”和“趙縣第一中學(xué)”在本縣域范圍內(nèi)可能都習(xí)慣使用“第一中學(xué)”作為簡(jiǎn)稱，但與“第一中學(xué)”計(jì)算相似度時(shí)，前者的相似度是0.73，而后者的相似度為0.8，如何提高比對(duì)準(zhǔn)確度即已成為本次課題的研究焦點(diǎn)。

針對(duì)字符串相似度度量中提高準(zhǔn)確率問題，多年來，一些學(xué)者對(duì)字符串的相似度發(fā)表了很多研究成果。文獻(xiàn)[4]根據(jù)簡(jiǎn)稱與全稱的構(gòu)成關(guān)系，構(gòu)造簡(jiǎn)稱規(guī)則，從而與全稱對(duì)照，這樣雖能緩解一定的問題不足，但同樣面臨很多困難，如：“西南大學(xué)”、“西北大學(xué)”都簡(jiǎn)稱“西大”，根據(jù)全稱到簡(jiǎn)稱規(guī)則沒有差別，前兩個(gè)字都代表方位，后兩個(gè)字都代表專用名詞;文獻(xiàn)[5]采用分詞的方式計(jì)算相似度，雖然有一定改進(jìn)，但也同樣遇到了文獻(xiàn)[4]的難題;文獻(xiàn)[6]基于詞向量研究了句子的相似度。文獻(xiàn)[7]綜合編輯距離和分詞等方法，提出了面向用戶查詢意圖的相似度分析方法。文獻(xiàn)[8]提出了使用塊編輯距離計(jì)算字符串相似度的方法，上述方法都試圖從字符串本身，尋找提高相似度計(jì)算的方法，沒有考慮與其他因素的關(guān)聯(lián)關(guān)系，但由于相似字符串轉(zhuǎn)換不可逆，總是存在一定的不確定性，導(dǎo)致相似度度量精確度難獲實(shí)質(zhì)性提升;文獻(xiàn)[9]對(duì)中文簡(jiǎn)稱和全稱設(shè)置置信度，需要大量基礎(chǔ)數(shù)據(jù)源，計(jì)算工作量較大。

定義1 相似字符串轉(zhuǎn)換的不可逆性 由全稱根據(jù)一定規(guī)則能轉(zhuǎn)換為簡(jiǎn)稱，用同樣規(guī)則由簡(jiǎn)稱轉(zhuǎn)換為全稱是不可逆的。同樣，相似字符串之間的轉(zhuǎn)換也是不可逆的。

顯然全稱到簡(jiǎn)稱是多對(duì)一的關(guān)系，就像哈希函數(shù)一樣，所以其過程是不可逆的，即不能簡(jiǎn)單由簡(jiǎn)稱推出全稱。同樣適用字符串相似度比較，雖然從不同研究角度出發(fā)，能尋找出提高計(jì)算字符串相似度的方法，但這些方法具有不確定性。

3 計(jì)算約束字符串相似度的算法

全稱-簡(jiǎn)稱轉(zhuǎn)換是不可逆的，但事物并不是孤立存在的，如：在陜西說起“西大”，人們第一印象是“西北大學(xué)”，在重慶提到“西大”，人們首先想起的是“西南大學(xué)”，簡(jiǎn)稱必然有其密切關(guān)聯(lián)的屬性。在企業(yè)基礎(chǔ)信息的對(duì)比中，企業(yè)名稱、企業(yè)地址、所在區(qū)域是聯(lián)系緊密的3個(gè)屬性。

定義2 具有約束的字符串 將需要比對(duì)的元素和與其有緊密關(guān)系的屬性，組成一個(gè)元組，這個(gè)元組就是有約束關(guān)系的字符串，記為T（d1，d2，……，dn），d1為被約束字符串，d2，……，dn為約束屬性。

在中文環(huán)境的多數(shù)情況下，句子只有在一定語義環(huán)境中，才有具體含義，句子就是被約束字符串，語義環(huán)境就是約束屬性。具有約束的元組求相似度時(shí)，對(duì)應(yīng)屬性分別求相似度，然后合成求出復(fù)合相似度，求相似度應(yīng)用算法2，研究給出設(shè)計(jì)代碼如下。

算法2 具有約束的字符串復(fù)合相似度

Input：元組T and S

Output：com_sim（T，S）

com_rat=1

for i to n

t=T[i]

s=S[i]

rat=sim_imp（t，s）

com_rat=com_rat*rat

return com_rat

4 實(shí)例分析

將稅務(wù)登記信息與社保的參保企業(yè)信息作為分析實(shí)例，按照算法2設(shè)計(jì)相似度算法，尋找單位名稱的相互匹配數(shù)據(jù)，使用Python3.6編程，數(shù)據(jù)庫使用MySQL5.7。

需要匹配的字符串為企業(yè)名稱，名稱相似度閾值設(shè)為0.75，約束屬性為單位地址和行政區(qū)劃代碼，單位地址相似度閾值為0.5，行政區(qū)劃代碼相似度閾值為1，即必須為同一行政區(qū)內(nèi)企業(yè)匹配，不是同一行政區(qū)內(nèi)，相似度為0;具有約束的中文字符串復(fù)合相似度閾值為0.375。約束字符串記為T（name，addr，div），其中name表示企業(yè)名稱，addr表示單位地址，div代表行政區(qū)劃代碼，addr和div為約束屬性。有約束字符串與無約束字符串總體效率情況見表1。

由表1可知，有約束字符串與無約束字符串相比，無效的匹配數(shù)據(jù)下降了41%。而匹配的數(shù)據(jù)準(zhǔn)確率由54%提高到73%。

4.1 簡(jiǎn)稱相同情況對(duì)比分析

選取社保數(shù)據(jù)中單位名稱是“房產(chǎn)管理中心”的單位，無約束相似度匹配結(jié)果見表2，名稱相似度用name_rat表示。

由表2可知，名稱的相似度都是0.80，不能準(zhǔn)確地匹配到正確數(shù)據(jù)。

有約束相似度情況見表3，名稱相似度用name_rat表示，地址相似度用addr_rat表示，行政區(qū)劃相似度用div_rat表示，復(fù)合相似度用com_rat表示。

可以看出具有約束的字符串可以實(shí)現(xiàn)精確匹配。

4.2 同一行政區(qū)劃內(nèi)對(duì)比情況

選取社保數(shù)據(jù)中單位名稱是“寧津縣重達(dá)汽車配件有限公司”的企業(yè)，有約束相似度匹配結(jié)果見表4。

可以看出“山東重達(dá)汽車配件有限公司”與“寧津縣重達(dá)汽車配件有限公司”具有更高的復(fù)合相似度，反映了實(shí)際情況。但是沒有地址約束時(shí)，相似度最高的是“寧津縣伊高汽車配件有限公司”，這是不正確的。

5 結(jié)束語

本文分析了當(dāng)前計(jì)算字符串相似度的Levenshtein算法存在的不足，提出了改進(jìn)方法，給出了相似字符串轉(zhuǎn)換的不可逆定義，指出現(xiàn)在求字符串相似度的局限性，進(jìn)而得出具有約束屬性字符串的概念，不再把字符串看做孤立的個(gè)體，而把字符串、約束屬性視為密切聯(lián)系的整體，基于約束字符串改進(jìn)Levenshtein算法，由于關(guān)系型數(shù)據(jù)庫中字符串約束屬性容易獲得，該方法在關(guān)系型數(shù)據(jù)庫中求解字符串相似度方面具有很好效果。

參考文獻(xiàn)

[1]姜華，韓安琪，王美佳，等. 基于改進(jìn)編輯距離的字符串相似度求解算法[J]. 計(jì)算機(jī)工程，2014，40（1）：222-227.

[2]張潤梁，牛之賢. 基于基本操作序列的編輯距離順序驗(yàn)證[J]. 計(jì)算機(jī)科學(xué)，2016，43（6A）：51-54.

[3]馬立東. 編輯距離算法及其在英語易混詞自動(dòng)抽取中的應(yīng)用[J]. 智能計(jì)算機(jī)與應(yīng)用，2013，3（1）：47-51.

[4]沈嘉懿，李芳，徐飛玉，等. 中文組織機(jī)構(gòu)名稱與簡(jiǎn)稱的識(shí)別[J]. 中文信息學(xué)報(bào)，2007，21（6）：17-21.

[5]黃林晟，鄧志鴻，唐世渭，等. 基于編輯距離的中文組織機(jī)構(gòu)名簡(jiǎn)稱-全稱匹配算法[J]. 山東大學(xué)學(xué)報(bào)（理學(xué)版），2012，47（5）：43-48.

[6]田星，鄭瑾，張祖平. 基于詞向量的Jaccard相似度算法[J]. 計(jì)算機(jī)科學(xué)，2018，45（7）：186-189.

[7]李景玉，張仰森，陳若愚. 面向用戶查詢意圖的句子相似度分層計(jì)算[J]. 計(jì)算機(jī)科學(xué)，2015，42（1）：227-231.

[8]王斌，郭慶，李中博，等. 支持塊編輯距離的索引結(jié)構(gòu)[J]. 計(jì)算機(jī)研究與發(fā)展，2010，47（1）：191-199.

[9]郭暉，董源，周鋼. 基于屬性關(guān)聯(lián)相似度的中文簡(jiǎn)稱匹配算法研究[J]. 計(jì)算機(jī)與數(shù)字工程，2018，46（9）：1726-1730.