祁俊輝，龍 華，邵玉斌，杜慶治

(昆明理工大學(xué) 信息工程與自動(dòng)化學(xué)院，昆明 650000)

0 引 言

作為象形文字的中文，擁有較多的形近字，從而導(dǎo)致在進(jìn)行文字信息處理時(shí)常被錯(cuò)識(shí)。目前，印刷體識(shí)別技術(shù)已經(jīng)有較高的準(zhǔn)確度[1]。但對(duì)圖片中形近字的字形仍存在識(shí)別率不高[2]的問(wèn)題。這是因?yàn)楹芏酀h字的字形差異非常細(xì)微，不容易區(qū)分，如“已”和“己”、“烏”和“鳥(niǎo)”等。因此，如何使識(shí)別系統(tǒng)利用這些細(xì)微差別將相似漢字準(zhǔn)確區(qū)分，是目前文字處理中研究的熱點(diǎn)，同時(shí)也是解決中文信息處理領(lǐng)域其它問(wèn)題的前提[3-4]。

針對(duì)形近字的識(shí)別，林民等[5-7]利用計(jì)算機(jī)技術(shù)獲取字庫(kù)的筆畫(huà)輪廓數(shù)據(jù)，為漢字相似研究奠定了基礎(chǔ)，且后期針對(duì)復(fù)合字進(jìn)一步完善了漢字部件輪廓庫(kù)。栗青生等[8]將漢字筆畫(huà)抽象為有向圖形式，實(shí)現(xiàn)對(duì)漢字字形的部件描述，建立了動(dòng)態(tài)漢字字形描述庫(kù)。趙健等[9]對(duì)漢字的端點(diǎn)、折角點(diǎn)、交叉點(diǎn)等特征提取進(jìn)行創(chuàng)新性的研究，但對(duì)字形復(fù)雜的漢字效果并不理想。胡浩等[10]結(jié)合漢字的構(gòu)詞和拼音屬性，將其映射為32維空間向量形式，便于計(jì)算短文本的相似性。宋柔等[11]將漢字分為獨(dú)體字和復(fù)合字分別進(jìn)行討論，取得較好的成果。孫華等[12]對(duì)5種漢字識(shí)別方法進(jìn)行了分析并闡述了現(xiàn)階段漢字識(shí)別算法中存在的問(wèn)題。劉波等[13]將傳統(tǒng)光學(xué)文字識(shí)別(optical character recognition,OCR)技術(shù)和文字圖像結(jié)合，但識(shí)別率不高且所對(duì)比的漢字模板庫(kù)較小。劉斌等[14]對(duì)含有噪聲的漢字圖片進(jìn)行了矩陣分析，但只研究了單一特征的漢字分類。文獻(xiàn)[15-16]對(duì)各種字符串相似算法，如Levenshtein Distance算法與Greeay String Tiling算法等進(jìn)行了比較，并將傳統(tǒng)的Jaro-Winkler Distance算法與Levenshtein Distance算法進(jìn)行融合，從而提高字符串相似判定。

以上文獻(xiàn)大多采用漢字組合結(jié)構(gòu)和筆畫(huà)對(duì)漢字部件進(jìn)行描述，進(jìn)而通過(guò)編輯距離等算法計(jì)算其字形相似度，亦或使用圖像處理的方法進(jìn)行相似度的計(jì)算。但由于漢字存在種類繁多、結(jié)構(gòu)類型復(fù)雜等因素，目前沒(méi)有較為完整的漢字結(jié)構(gòu)庫(kù)，致使在實(shí)現(xiàn)字形相似識(shí)別中存在困難；其次，將漢字描述為數(shù)學(xué)表達(dá)式形式后，其相似度的計(jì)算也需要進(jìn)一步研究。

本文的主要工作包括對(duì)漢字字形的形式化結(jié)構(gòu)進(jìn)行描述，將漢字描述為特征向量和筆順編碼形式，通過(guò)二值化差值算法計(jì)算基于特征向量的字形相似度，通過(guò)改進(jìn)后的Jaro-Winkler Distance算法計(jì)算基于筆順編碼的字形相似度，2個(gè)相似度分別從不同方面反映了漢字的相似程度，最后再將計(jì)算所得的2個(gè)相似度進(jìn)行融合，得到最終相似度。

1 漢字形式化結(jié)構(gòu)描述

在漢字計(jì)算機(jī)編碼標(biāo)準(zhǔn)中，編碼方式為Unicode的中日韓統(tǒng)一表意文字基本字符集收錄漢字共20 902個(gè)(Unicode碼為4E00～9FA5)，以20 902個(gè)漢字作為數(shù)據(jù)源，對(duì)其進(jìn)行形式化結(jié)構(gòu)描述。

1.1 漢字特征向量

從字體文件中提取出漢字的圖片形式，即漢字圖片大小為l×w(單位為像素點(diǎn))，共計(jì)N個(gè)像素點(diǎn)。將漢字圖片作為輸入源，生成漢字的矩陣形式Il×w，矩陣Il×w中的元素值I(i,j),i∈[1,l],j∈[1,w]即為該像素點(diǎn)的灰度值。以閾值ξ對(duì)矩陣元素進(jìn)行二值化處理表示為

i∈[1,l],j∈[1,w]

(1)

二值化處理后，將矩陣Il×w按照從左至右(j=1→w)、從上至下(i=1→l)的規(guī)則生成漢字的特征向量{x1,x2,…,xN}。將編碼方式為Unicode的基本字符集中的20902個(gè)漢字依照此向量產(chǎn)生規(guī)則生成其漢字特征向量并存入數(shù)據(jù)庫(kù)，組建Unicode漢字特征向量數(shù)據(jù)庫(kù)。

1.2 漢字筆順編碼

任何漢字都可根據(jù)書(shū)寫(xiě)筆畫(huà)順序分為橫、豎、撇、捺、折，即五筆結(jié)構(gòu)，故可按照編碼規(guī)則對(duì)任意漢字生成其漢字筆畫(huà)順序編碼字符串，簡(jiǎn)稱漢字筆順字符串，如表1。

表1 漢字筆畫(huà)編碼規(guī)則

記漢字為X，則該漢字X的筆順字符串X=x1x2x3…xz，其中z為該漢字的筆畫(huà)數(shù)，xi為該漢字第i筆的筆畫(huà)，并且xi∈{a,b,c,d,e},i∈[1,z]。

將編碼方式為Unicode的基本字符集中的20902個(gè)漢字依照此編碼規(guī)則生成其漢字筆順字符串并存入數(shù)據(jù)庫(kù)，組建Unicode漢字筆順編碼數(shù)據(jù)庫(kù)。

2 漢字字形相似度算法

針對(duì)漢字字形相似度的計(jì)算，通過(guò)二值化差值算法計(jì)算基于漢字特征向量的字形相似度，通過(guò)改進(jìn)后的Jaro-Winkler Distance算法計(jì)算基于漢字筆順編碼的字形相似度，2個(gè)相似度分別從不同方面反映了漢字的相似程度，吸取2種算法的優(yōu)勢(shì)對(duì)其進(jìn)行融合，得到最終相似度。融合算法的整體流程框圖如圖1。

圖1 算法整體流程框圖

2.1 基于特征向量的字形相似度

為衡量漢字之間基于特征向量的字形相似度，引入二值化差值算法對(duì)漢字特征向量進(jìn)行運(yùn)算。

算法1基于特征向量的字形相似度算法

輸入：漢字A，B。

輸出：漢字A，B之間基于特征向量的字形相似度Sim1(A,B)。

Step1從Unicode漢字特征向量數(shù)據(jù)庫(kù)中調(diào)取漢字A，B所對(duì)應(yīng)的漢字特征向量A={a1,a2,…,aN}和B={b1,b2,…,bN}。

Step2定義ci=ai-bi,i∈[1,N]，生成漢字A、B所對(duì)應(yīng)的差值特征向量A-B={c1,c2,…,cN}。

Step3求漢字A、B之間基于特征向量的字形相似度Sim1(A,B)可以表示為

(2)

2.2 基于筆順編碼的字形相似度

為衡量漢字之間基于筆順編碼的字形相似度，要使用字符串相似算法對(duì)其進(jìn)行計(jì)算。通常使用Cosine Similarity, Levenshtein Distance, Hamming Distance等算法對(duì)字符串相似進(jìn)行判定，但Cosine Similarity和Hamming Distance算法并不適用于筆順編碼字符串，Levenshtein Distance算法沒(méi)有考慮到字符換位的情況，綜合考慮后引入改進(jìn)后的Jaro-Winkler Distance算法對(duì)漢字筆順字符串進(jìn)行運(yùn)算。

算法2基于筆順編碼的字形相似度算法

輸入：漢字A，B。

輸出：漢字A，B之間基于筆順編碼的字形相似度Sim2(A,B)。

Step1從Unicode漢字筆順編碼數(shù)據(jù)庫(kù)中調(diào)取漢字A，B所對(duì)應(yīng)的漢字筆順字符串strA和strB。

Step2計(jì)算匹配窗口值MW為

(3)

(3)式中：lenA為筆順編碼字符串strA的長(zhǎng)度；lenB為筆順編碼字符串strB的長(zhǎng)度。

Step3由筆順編碼字符串strA，strB及匹配窗口值MW，判決字符是否匹配可以表示為

|pos(a)-pos(b)|

(4)

(4)式中：a是字符串strA中的某一字符；pos(a)為a在字符串strA中的位置下標(biāo)；b是字符串strB中的某一字符；pos(b)為b在字符串strB中的位置下標(biāo)。遍歷字符串strA和strB，計(jì)算匹配字符數(shù)m，即所有滿足 (4) 式的字符總個(gè)數(shù)。應(yīng)注意，在匹配過(guò)程中，需排除被匹配過(guò)的字符，若找到匹配過(guò)的字符，則需跳出此次匹配，進(jìn)行下一字符的匹配。

Step4由筆順編碼字符串strA和strB的匹配字符集確定匹配字符換位數(shù)n，若匹配字符集中字符順序一致，則n=0，否則n為換位數(shù)目的一半。

Step5計(jì)算筆順編碼字符串strA和strB之間的Jaro Distance表示為

(5)

Step6為凸顯筆順編碼字符串中相同部分的重要性，提取筆順編碼字符串strA和strB的最長(zhǎng)公共子串strAB，并獲取其長(zhǎng)度lenAB，進(jìn)一步計(jì)算筆順編碼字符串strA和strB之間的Jaro-Winkler Distance，該值即為漢字A、B之間基于筆順編碼的字形相似度Sim2(A,B)，表示為

Sim2(A,B)=Disj+

(6)

2.3 相似度融合

由算法1計(jì)算所得的基于特征向量的字形相似度Sim1(A,B)和算法2計(jì)算所得的基于筆順編碼的字形相似度Sim2(A,B)取值為[0,1]，反映了漢字A，B之間的字形相似程度，數(shù)值越大則說(shuō)明相似程度越高，但2個(gè)相似度是從不同方面反映了漢字的相似程度，基于特征向量的字形相似度Sim1(A,B)主要從漢字結(jié)構(gòu)、輪廓等角度反映漢字的相似程度，而基于筆順編碼的字形相似度Sim2(A,B)主要從漢字筆畫(huà)、書(shū)寫(xiě)順序等角度反映漢字的相似程度。

由于單獨(dú)使用基于特征向量的字形相似度算法或基于筆順編碼的字形相似度算法對(duì)漢字字形相似進(jìn)行衡量并不嚴(yán)謹(jǐn)。例如，以漢字“未”和“末”為例，若僅以基于筆順編碼的字形相似度算法進(jìn)行衡量，則兩者的相似度為1，但實(shí)際上兩者是存在差異的；再以漢字“由”和“甲”為例，若僅以基于特征向量的字形相似度算法進(jìn)行衡量，則兩者的相似度很小，但實(shí)際上兩者只是上下反轉(zhuǎn)關(guān)系。故本文分別吸取2種算法的優(yōu)勢(shì)，對(duì)其進(jìn)行均衡融合。

算法3相似度融合算法

將基于特征向量的字形相似度Sim1(A,B)與基于筆順編碼的字形相似度Sim2(A,B)進(jìn)行加權(quán)平均，即可得到相似度融合算法，表示為

(7)

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

為驗(yàn)證本文提出的基于特征向量和筆順編碼的字形相似算法的有效性，本文設(shè)計(jì)了3個(gè)對(duì)比實(shí)驗(yàn)：①實(shí)驗(yàn)1使用本文提出的漢字字形相似算法，對(duì)任意輸入的2個(gè)漢字進(jìn)行相似度的計(jì)算，并與文獻(xiàn)[2]進(jìn)行比較，考察本算法對(duì)漢字字形相似度的準(zhǔn)確度；②實(shí)驗(yàn)2使用本文提出的漢字字形相似算法，對(duì)任意輸入漢字提取出與其相似的漢字，并與文獻(xiàn)[11]、文獻(xiàn)[12]進(jìn)行比較，考察本算法是否能夠?qū)h字更準(zhǔn)確、真實(shí)地反映其字形的相似程度以及執(zhí)行效率問(wèn)題；③實(shí)驗(yàn)3使用本文提出的漢字字形相似算法，遍歷編碼方式為Unicode的基本字符集中20 902個(gè)漢字，提取出最為相似的3個(gè)字，考察本算法對(duì)任意漢字的字形相似是否支持。

實(shí)驗(yàn)用Python 3.6編程語(yǔ)言實(shí)現(xiàn)。微軟雅黑字體作為輸入源，提取64×64像素的漢字圖片，取灰度二值化閾值ξ=1，即使圖片中除了純白色像素點(diǎn)外將其他像素點(diǎn)都賦予黑色以凸顯效果。

實(shí)驗(yàn)1

1)實(shí)驗(yàn)設(shè)計(jì)和評(píng)測(cè)方法。實(shí)驗(yàn)采用文獻(xiàn)[2]的實(shí)驗(yàn)樣本，運(yùn)行本文所提出的基于特征向量和筆順編碼的字形相似算法并與文獻(xiàn)[2]進(jìn)行對(duì)比，通過(guò)比較2個(gè)字之間的相似度，考察本算法對(duì)漢字字形相似度識(shí)別的準(zhǔn)確度。

2)實(shí)驗(yàn)結(jié)果和分析。實(shí)驗(yàn)1所采用的漢字樣本如表2。

表2 實(shí)驗(yàn)1的漢字樣本

以編號(hào)為1的樣本為例，執(zhí)行算法1的流程，2個(gè)漢字的特征向量及差值特征向量的形式化描述如圖2， 2個(gè)漢字之間基于特征向量的字形相似度Sim1(A,B)=0.885 3；根據(jù)算法2所述執(zhí)行流程，計(jì)算所得2個(gè)漢字之間基于筆順編碼的字形相似度Sim2(A,B)=0.984 3；執(zhí)行算法3得2個(gè)漢字之間最終字形相似度Sim(A,B)=0.934 8。

對(duì)所有樣本依次計(jì)算其相似度，得到結(jié)果如表3。

表3 算法對(duì)漢字樣本得到的相似度

圖2 漢字“玻”和“坡”的特征向量及差值特征向量

從表3可知，基于筆順編碼的字形相似度因?yàn)橹豢紤]到筆畫(huà)順序，假如2個(gè)漢字的筆順相同則計(jì)算結(jié)果相同，如“坡”和“披”，但這樣是不合理的，故加入基于特征向量的字形相似度對(duì)其進(jìn)行融合，實(shí)現(xiàn)進(jìn)一步區(qū)分。將本實(shí)驗(yàn)結(jié)果與文獻(xiàn)[2]所計(jì)算的結(jié)果進(jìn)行比較，發(fā)現(xiàn)文獻(xiàn)[2]對(duì)樣本2、樣本3的計(jì)算結(jié)果相同，但通過(guò)人眼識(shí)別，事實(shí)上“披”相對(duì)“波”更與“?！毕嗨疲舅惴ㄒ豺?yàn)證了這一點(diǎn)；同樣文獻(xiàn)[2]的算法對(duì)樣本6、樣本7存在相同問(wèn)題。綜合實(shí)驗(yàn)結(jié)果，本算法對(duì)漢字字形相似度的識(shí)別較合理，相似度較文獻(xiàn)[2]提高約27.8%。

實(shí)驗(yàn)2

1)實(shí)驗(yàn)設(shè)計(jì)和評(píng)測(cè)方法。實(shí)驗(yàn)采用文獻(xiàn)[11]的實(shí)驗(yàn)樣本，利用本文提出的基于特征向量和筆順編碼的字形相似算法對(duì)樣本進(jìn)行相似字的提取，并將結(jié)果與文獻(xiàn)[11]進(jìn)行比較，同時(shí)將程序運(yùn)行時(shí)間與文獻(xiàn)[12]進(jìn)行對(duì)比。通過(guò)比較算法對(duì)比同一樣本得到的相似字及運(yùn)行時(shí)間，考察本算法是否能夠?qū)h字更準(zhǔn)確、真實(shí)地反映其字形的相似程度以及執(zhí)行效率問(wèn)題。

2)實(shí)驗(yàn)結(jié)果和分析。實(shí)驗(yàn)2所采用的漢字樣本如表4。

表4 實(shí)驗(yàn)2的漢字樣本

分別利用文獻(xiàn)[11]所介紹的漢字字形相似算法和本文提出的基于特征向量和筆順編碼的字形相似算法對(duì)漢字樣本進(jìn)行相似字的提取，并得到本算法的運(yùn)行時(shí)間，結(jié)果如表5。

表5 算法對(duì)漢字樣本提取的相似字及程序運(yùn)行時(shí)間

從表5可知，本算法對(duì)樣本所提取的相似字與文獻(xiàn)[11]所介紹的算法結(jié)果相比，還是有很大的差異。文獻(xiàn)[11]的結(jié)果并不理想，比如對(duì)樣本1來(lái)說(shuō)，漢字“藹”和“落”、“范”、“莎”等通過(guò)人眼識(shí)別，除了偏旁外并無(wú)相似之處，而本算法所提取的漢字“葛”、“獦”、“噶”確實(shí)與“藹”有相似之處，而且結(jié)果與樣本都包含有相同漢字部件。

此外，本算法在提取相似漢字時(shí)所花費(fèi)的平均時(shí)間為116.6 ms，文獻(xiàn)[12]中的模板匹配算法需要0.2～1.0 s才能識(shí)別一個(gè)字符，結(jié)構(gòu)方法用時(shí)為0.2～0.5 s，神經(jīng)網(wǎng)絡(luò)算法用時(shí)約0.1 s。通過(guò)比較可知，本算法在執(zhí)行效率上較其他算法提高約66.7%。

實(shí)驗(yàn)結(jié)果表明，本算法可以更準(zhǔn)確、真實(shí)地反映漢字字形的相似程度，同時(shí)執(zhí)行效率較高。

實(shí)驗(yàn)3：

1)實(shí)驗(yàn)設(shè)計(jì)和評(píng)測(cè)方法。實(shí)驗(yàn)采用雙層遍歷編碼方式為Unicode的基本字符集中20 902個(gè)漢字的方式，利用本文的基于特征向量和筆順編碼的字形相似算法對(duì)其進(jìn)行相似度計(jì)算及排序，并將與對(duì)比漢字相似度最高的3個(gè)漢字提取出來(lái)。通過(guò)對(duì)結(jié)果進(jìn)行分析，考察本算法對(duì)任意漢字的字形相似是否支持。

2)實(shí)驗(yàn)結(jié)果和分析。實(shí)驗(yàn)利用本文基于特征向量和筆順編碼的字形相似算法對(duì)其進(jìn)行相似度計(jì)算及排序，并將與對(duì)比漢字相似度最高的3個(gè)漢字提取出來(lái)。得到的部分結(jié)果例舉如下：

一：十#0.8430/干#0.8270/丂#0.8209

二：三#0.8669/午#0.8092/干#0.7988

人：入#0.9441/太#0.8681/八#0.8616

木：術(shù)#0.9406/朩#0.9406/本#0.8827

不：丕#0.8900/下#0.8900/丅#0.8604

貝：頁(yè)#0.8676/央#0.8627/見(jiàn)#0.8600

從：叢#0.8771/朲#0.8726/認(rèn)#0.8498

宂：冗#0.8982/宄#0.8970/穴#0.8925

我：牫#0.8740/伐#0.8350/找#0.8330

地：扡#0.8956/坉#0.8876/忚#0.8625

怨：怒#0.8387/忍#0.8288/怹#0.8283

勉：勊#0.8659/葂#0.8251/勀#0.8214

劍：劊#0.8585/釗#0.8306/刢#0.8254

俑：俌#0.8858/涌#0.8823/誦#0.8711

本實(shí)驗(yàn)統(tǒng)計(jì)結(jié)果表明，相似度在0.99以上的漢字有4對(duì)，相似度在0.98～0.99的漢字有12對(duì)，具體如表6；另外，相似度在0.95以上的漢字有297對(duì)，相似度在0.90以上的漢字有6 665對(duì)，相似度在0.85以上的漢字有23 726對(duì)。

表6 相似度在0.98以上的相似字對(duì)

通過(guò)人眼識(shí)別表6所列出的相似漢字，確實(shí)具有很大的字形相似程度，說(shuō)明本文所提出的漢字字形相似算法對(duì)任意漢字(獨(dú)體字、復(fù)合字)都能提供較好的支持。

4 結(jié)束語(yǔ)

本文從漢字自身特征出發(fā)，提出了基于特征向量和筆順編碼的字形相似算法，通過(guò)實(shí)驗(yàn)1驗(yàn)證了本算法的準(zhǔn)確率比文獻(xiàn)[2]提高27.8%；通過(guò)實(shí)驗(yàn)2驗(yàn)證了本算法能夠比文獻(xiàn)[11]、文獻(xiàn)[12]更準(zhǔn)確、真實(shí)地反映漢字字形的相似程度以及執(zhí)行效率；通過(guò)實(shí)驗(yàn)3驗(yàn)證了本算法對(duì)任意漢字之間的字形相似度判斷提供支持。本文可以得到幾個(gè)結(jié)論：①?gòu)臐h字結(jié)構(gòu)、輪廓等角度出發(fā)，將漢字轉(zhuǎn)化為特征向量形式，采用二值化差值算法對(duì)其進(jìn)行計(jì)算，能夠充分刻畫(huà)漢字之間在漢字結(jié)構(gòu)、輪廓方面的字形相似程度；②從漢字筆畫(huà)、書(shū)寫(xiě)順序等角度出發(fā)，將漢字進(jìn)行筆順編碼，采用改進(jìn)后的Jaro-Winkler Distance算法對(duì)其進(jìn)行運(yùn)算，能夠更好地刻畫(huà)漢字之間在筆畫(huà)、書(shū)寫(xiě)順序方面的字形相似程度；③通過(guò)將基于特征向量的字形相似度和基于筆順編碼的字形相似度進(jìn)行融合，減少了單獨(dú)使用某一算法對(duì)漢字字形相似帶來(lái)的誤差，同時(shí)也能吸取2種算法的優(yōu)勢(shì)，從而獲得更好的綜合效果。本文算法對(duì)漢字字形相似度計(jì)算的準(zhǔn)確度高、運(yùn)行時(shí)間短，較3元組遞歸算法準(zhǔn)確度提高約27.8%，較模板匹配算法、結(jié)構(gòu)方法、神經(jīng)網(wǎng)絡(luò)算法執(zhí)行效率平均提高約66.7%，同時(shí)對(duì)任意漢字(獨(dú)體字、復(fù)合字)的字形相似都有較好的支持度。