一種基于字符對比的文本相似度計算方法

汪亞東

摘? 要： 為解決包含重復(fù)字符的文本相似度計算問題，提出了一種新的計算方法來獲取兩文本之間的相似度。首先根據(jù)單字符的對比情況統(tǒng)計重復(fù)字符數(shù)量；其次通過分析總的對比結(jié)果剔除重復(fù)字符的干擾；然后借助公式計算出正確的文本相似度，并拓展單字節(jié)字符和多字節(jié)字符混合時的相似度計算方法；最后編寫算法代碼來進行仿真分析，多組測試結(jié)果表明，用該方法計算得到的文本相似度與理論值相吻合。

關(guān)鍵詞： 自然語言處理； 文本相似度； 重復(fù)字符； 計算算法

中圖分類號：TP391? ? ? ? ? 文獻標(biāo)識碼：A? ? ?文章編號：1006-8228（2023）06-87-05

Text similarity calculation method based on character comparison

Wang Yadong

（School of Instrument and Electronics， North University of China， Taiyuan， Shanxi 030051， China）

Abstract： In order to solve the problem of text similarity calculation with repeated characters， a new method is proposed to obtain the similarity between two texts. First， the number of repeated characters is counted according to the comparison of single characters. Then， the interference of repeated characters is eliminated by analyzing the total comparison results. And then， the correct text similarity is calculated by the formula， and the similarity calculation method of single-byte characters and multi-byte characters mixed is expanded. Finally， the algorithm code is compiled for simulation analysis， and several groups of test results show that the text similarity calculated by this method is consistent with the theoretical value.

Key words： natural language processing; text similarity; repeated character; computing algorithm

0 引言

語言是人類知識、文化、思維的載體，人類語言也稱為自然語言。自然語言處理，主要研究用計算機來理解和生成人類語言的理論和方法[1-2]。自然語言處理囊括數(shù)學(xué)、計算機科學(xué)、心理學(xué)和語言學(xué)等的多學(xué)科領(lǐng)域，常用于檢索識別、機器翻譯、機器對話等方面[3]。

基于統(tǒng)計的語料數(shù)據(jù)庫處理方法[4]常用于自然語言處理。基于統(tǒng)計的方法需要將可能碰到的語句提前放入語料庫，待輸入語句后將該語句與語料庫中的語句進行對比，以此來“理解”語句，理解的準(zhǔn)確性有賴于語料庫的完備性。另一種比較常用的解決策略是基于規(guī)則的處理方法[5]，它同樣需要一個簡易語料庫，但不是完整的句子，而是一些獨立的字、詞、短句，待輸入語句后將該語句拆分并與簡易語料庫對比，輔以語法規(guī)則和情感分析去理解語句所表達的意思[6-7]。

無論是哪種處理方式，都依靠一個基礎(chǔ)的字詞庫或語句庫，需要判斷出輸入的語句中有哪些字、詞或句，這些是從形式上的初步“理解”，后續(xù)才會從含義上深入“理解”。因文字使用場景、習(xí)慣存在差異以及基礎(chǔ)語料庫不完備等多重影響，能夠百分百匹配的語句是少數(shù)。為了提高匹配度并適應(yīng)較多的使用環(huán)境，往往需要降低語句匹配的閾值，即通過計算語句相似度并按需劃定對比閾值，這樣有利于找到最佳匹配語句。文本相似度的計算也因此成為自然語言處理中的重要一環(huán)。

常用文本相似度計算方法如圖1所示[8]：

基于字符串的處理方式包括字符和詞語兩部分，兩者均是在文本的形式上進行探討，是忽略文本深層表意的處理方式，兩者的主要區(qū)別是處理的最小單元（單次處理字符數(shù)量）不同。

基于語料庫的相似度處理方式是在文本的形和意上進行探討，需要考慮語法、結(jié)構(gòu)、場景、習(xí)慣等各方面的影響，識別準(zhǔn)確度更高，但應(yīng)用局限性大， 實現(xiàn)也較為困難。

本研究主要介紹一種基于字符對比的文本相似度計算新方法，用以解決忽略字符位置關(guān)系時出現(xiàn)重復(fù)字符的相似度計算問題，為此設(shè)計出判斷重復(fù)字符的方法，重點論述單字符比較的判重條件，并通過搭建測試環(huán)境進行仿真分析，得出的相似度反映語句間相同字符的占比情況。

1 文本相似度處理基礎(chǔ)

在國家標(biāo)準(zhǔn)GB 18030-2005[9]（現(xiàn)行）中，明確了單字節(jié)字符集（常用符號及字母）和雙字節(jié)字符集（多種符號和漢字）的編碼方式，即用8位二進制數(shù)和16位二進制數(shù)來表示字符。因后續(xù)描述需要，可以簡單理解為：一個字母是1字節(jié)的字符，一個漢字是2字節(jié)的字符。如圖2所示為單字節(jié)字符“A”的編碼和雙字節(jié)字符“啊”的編碼。

一個句子是由多個字符組成的字符串，可以是英文句子、漢字句子或者中英文混合句子。在進行相似度計算的時候，計算的是兩個字符串之間相同字符數(shù)量的占比情況，為了得到相同字符數(shù)又需要進行單個字符的比較，而單字符比較的則是該字符對應(yīng)的二進制編碼是否相等。

2 相似度計算

基于字符的文本相似度計算常使用“距離”參數(shù)來描述，即處理時僅使用替換、插入和刪除操作將其中一個句子轉(zhuǎn)變?yōu)榱硪粋€句子所需的最少步驟數(shù)稱為“編輯距離（Evenshtein Distance）[10-11]”， 根據(jù)距離的多少來辨別相似度。計算公式如下[12]：

[SU=1-KL]? ⑴

其中，SU為相似度，K為編輯距離，L為最長操作串的長度（單位為字節(jié)）。例如：

句子一：“LingYuan！”。

句子二：“LinqYua！”。

將句子一轉(zhuǎn)變成句子二需要兩步，第一步是將“g”替換成“q”，第二步是將“n”刪除，編輯距離為2，且最長操作串為句子一，長度為9，所以句子一與句子二的相似度為0.78。

使用這種計算方式已經(jīng)將字符的位置考慮在其中，但設(shè)計替換、插入和刪除操作較為復(fù)雜費時。

很多應(yīng)用場合無需考慮字符出現(xiàn)的位置，可以直接統(tǒng)計相同字符數(shù)量來計算相似度，但設(shè)計算法時需要考慮重復(fù)字符的影響。計算公式如下[13-14]：

[SU=FMAXL1，L2]? ⑵

其中，SU為相似度，MAX（L1，L2）為兩對比語句長度（單位為字節(jié)）的最大值，F(xiàn)為相同字節(jié)數(shù)。

2.1 不存在重復(fù)字符的解決策略

句子三：“自然語言處理”，長度L1=12。

句子四：“自然語言處理的方法”，長度L2=18。

操作時將句子三中的字逐個取出，與句子四中的字對比，每次做兩個單字的對比，如圖3所示。

統(tǒng)計相同字節(jié)數(shù)F，每次加2，因為一個漢字（常規(guī)漢字）占兩個字節(jié)。操作結(jié)束時總共進行54次對比，相同字符為：“自然語言處理”，最終F=12。根據(jù)式⑵得出句子三和句子四的相似度為：

[SU=FMAX（L1，L2）=1218=0.67]? ⑶

2.2 存在重復(fù)字符的解決策略

句子五：“自然語言的處理”，長度L3=14.

句子六：“自然語言的處理的方法”，長度L4=20。

重復(fù)字符為句子六中出現(xiàn)的兩個“的”字，若依舊使用同樣的策略，當(dāng)提取到句子五中的“的”字，并將它與句子六進行逐一比較時，如圖4所示。

此時“的”字進行的10次對比中有兩次是有效的，使得F多增加了2，最終計算的相似度為0.8，與實際的相似度0.7存在差異，即碰到重復(fù)字符導(dǎo)致結(jié)果偏大。此外，不僅僅是句子六中的字會重復(fù)，句子五中的字也會重復(fù)，重復(fù)的數(shù)量可為2，也可為N，錯誤偏差也將倍增。為了解決出現(xiàn)重復(fù)字符時相似度的計算問題， 提出如下策略：

句子七：“自自然語言言言處理”，長度L5=18。

句子八：“自自言言言言處理的方法”，長度L6=22。

重復(fù)字符的解決要點是確定重復(fù)字符的個數(shù)。

首字分析處理如圖5所示。將句子七中的第一個字“自”提出與句子八中的其他字進行對比時，可以不用考慮“自”在句子七和句子八中的重復(fù)個數(shù)，當(dāng)對比到句子八中出現(xiàn)的第一個“自”字后，操作F并退出，進行下一輪對比，否則遍歷句子八，再進行下一輪對比。下一輪對比：將句子七中的第二個字“自”提出與句子八中的字對比。

非首字分析：如圖6所示，提出句子七中的某個字后，將之與句子七中該字之前的字進行對比，如果相同則重復(fù)數(shù)N1（每輪開始前清除為0）自加1。此后再將句子七中提出的該字與句子八中的字進行對比，統(tǒng)計相同字?jǐn)?shù)N2（每輪開始前清除為0），當(dāng)N2>N1時才統(tǒng)計F（自加2）并退出，進行下一輪對比，否則不操作F。

按照此方法進行操作，句子七有9個字，需要進行9輪對比，詳細過程如表1所示。

計算得到的相似度為：

[SU=FMAX（L1，L2）=1422=0.64]? ⑷

2.3 單字節(jié)字符與雙字節(jié)字符混合語句的解決策略

因單字節(jié)字符與雙字節(jié)字符占據(jù)字節(jié)的長度不同，使用計算機處理字符的時候往往會出現(xiàn)亂碼的情況，例如：

句子九：“o是字母還是數(shù)字呢？”，字節(jié)長度L7=19。

句子十：“1是數(shù)字不是字母！”，字節(jié)長度L8=17。

“o”和“1”是單字節(jié)字符，其余為雙字節(jié)字符。若按照雙字節(jié)字符的處理方式，句子九中“o”僅占一個字節(jié)，而“是”占兩個字節(jié)，每次讀兩個字節(jié)時碰到單字節(jié)字符“o”會多讀一個字節(jié)，肯定得不到正確的結(jié)果。而同樣使用單字節(jié)字符的處理方式在碰到漢字時也會少讀一個字節(jié)。因此每次取字符進行對比時需要考慮該字符是單字節(jié)字符還是雙字節(jié)字符。

現(xiàn)行的單字節(jié)字符只有128個，對比時可以僅提取一個字節(jié)的內(nèi)容來判斷，假如它在這128個字符的編碼范圍內(nèi)則可以判斷為單字節(jié)字符，此時的最小處理單元是一個字節(jié)，若對比的字符是雙字節(jié)字符則可以直接跳過兩個字節(jié)的位置取下一個字節(jié)，對比相同則相同字符數(shù)量F自加1（單字節(jié)）。若提取的一個字節(jié)不在128個字符的編碼范圍內(nèi)，則為雙字節(jié)字符（暫不考慮其他多字節(jié)字符），此時的最小處理單元是兩個字節(jié)，每次取兩個字節(jié)的內(nèi)容來對比，相同則相同字符數(shù)量F自加2。最終可以計算出相似度。

同理，處理其他多字節(jié)字符時，也可以依據(jù)編碼范圍逐級判斷屬于幾字節(jié)字符，以此確定對比所取的字節(jié)數(shù)。

3 算法描述

一種改進的計算文本相似度的計算算法。

輸入：待比較的兩文本（字符串）。

輸出：相似度，0到1之間的數(shù)值，精確到小數(shù)點后兩位。

步驟1 輸入字符串S1和S2。

步驟2 單字節(jié)字符與雙字節(jié)字符判斷。

步驟3 重復(fù)字符判斷并統(tǒng)計。

步驟4 對比并計算相似度。

該算法設(shè)計起來更加簡潔，在純粹的文字對比中效果更好，并且充分考慮到了單字節(jié)字符與雙字節(jié)字符混合的情況，提出了可行的解決策略，最重要的是創(chuàng)新性的給出了解決相似度計算中出現(xiàn)重復(fù)字符問題的方法。

4 仿真分析

搭建測試環(huán)境對設(shè)計進行仿真。

使用軟件“VC++2010”編寫C語言程序進行測試并記錄。測試時輸入兩條語句，通過算法計算返回相似度，測試過程及結(jié)果如表2所示。

測試包括：雙字節(jié)字符對比（序號1）；單字節(jié)字符對比（序號2）；單雙字節(jié)字符混合對比（序號3）；出現(xiàn)重復(fù)字符的對比（序號5、7）；特殊符號對比（序號4、6）。結(jié)果為句子一與句子二中相同字符的占比情況。通過測試可以得到該相似度計算結(jié)果與理論值相同，解決了出現(xiàn)重復(fù)字符的相似度計算問題，符合設(shè)計要求。但這是忽略字符出現(xiàn)位置和深層表意的結(jié)果，應(yīng)用場合受限。更適合于淺層文字處理，例如文字檢索；或者作為深度自然語言處理的基礎(chǔ)步驟，例如文字識別。

5 結(jié)束語

本文提出了在忽略字符位置關(guān)系情況下的文本相似度計算新方法，解決了出現(xiàn)重復(fù)字符的相似度計算問題，對計算原理進行了詳細的分析，給出了設(shè)計算法的具體步驟。通過仿真分析表明：該計算方法得到的相似度的值與理論值吻合；出現(xiàn)重復(fù)字符時，無論重復(fù)次數(shù)多少、位置如何，均能得到對應(yīng)的相似度的值；對于單字節(jié)字符和多字節(jié)字符的混合語句仍能發(fā)揮自身功能。充分證明了該文本相似度計算方法的有效性。

參考文獻（References）：

[1] 孫茂松，李涓子，張鈸.自然語言處理研究前沿[J].中文信息

學(xué)報，2022，36（1）：F0003

[2] 徐琴，馮志偉.關(guān)于自然語言處理的對話——馮志偉教授訪

談錄[J].現(xiàn)代語文，2022（6）

[3] 宋一凡.自然語言處理的發(fā)展歷史與現(xiàn)狀[J].中國高新科技，

2019（3）：64-66

[4] 王海寧.自然語言處理技術(shù)發(fā)展[J].中興通訊技術(shù)，2022，28

（2）：59-64

[5] 車萬翔，張偉男.人機對話系統(tǒng)綜述[J].人工智能， 2018（1）：

76-82

[6] Lam C， Hannah MA. The social help desk： Examining

howTwitter is used as a technical support tool. CommunicationDesign Quarterly，2016，4（2）：37-51

[7] Paul R， Barbu A， Felshin S， et al. Temporal

groundinggraphs for language understanding with accrued visual-linguistic context. arXiv：1811.06966， 2018

[8] 馮志偉.自然語言處理的歷史與現(xiàn)狀[J].中國外語，2008（1）：

14-2

[9] 全國信息技術(shù)標(biāo)準(zhǔn)化技術(shù)委員會. GB 18030-2005信息

技術(shù)中文編碼字符集[M].北京：中國標(biāo)準(zhǔn)出版社，2006

[10] 劉嬌，李艷玲，林民.人機對話系統(tǒng)中意圖識別方法綜述[J].

計算機工程與應(yīng)用，2019，55（12）：1-7，43

[11] 韓程程，李磊，劉婷婷，等.語義文本相似度計算方法[J].華東

師范大學(xué)學(xué)報（自然科學(xué)版），2020（5）：95-112

[12] 董星彤，陳士宏，陳淑鑫.自然語言處理文本查重優(yōu)化算法

設(shè)計[J].科學(xué)技術(shù)與工程，2022，22（3）：1091-1097

[13] 陳二靜，姜恩波.文本相似度計算方法研究綜述[J]. 數(shù)據(jù)分

析與知識發(fā)現(xiàn)，2017（6）：1-11

[14] 邵恒，馮興樂，包芬.基于深度學(xué)習(xí)的文本相似度計算[J].

鄭州大學(xué)學(xué)報（理學(xué)版），2020，52（1）：66-71，78