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

汪亞東

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

關鍵詞： 自然語言處理； 文本相似度； 重復字符； 計算算法

中圖分類號：TP391? ? ? ? ? 文獻標識碼：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]。自然語言處理囊括數學、計算機科學、心理學和語言學等的多學科領域，常用于檢索識別、機器翻譯、機器對話等方面[3]。

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

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

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

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

基于語料庫的相似度處理方式是在文本的形和意上進行探討，需要考慮語法、結構、場景、習慣等各方面的影響，識別準確度更高，但應用局限性大， 實現也較為困難。

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

1 文本相似度處理基礎

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

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

2 相似度計算

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

[SU=1-KL]? ⑴

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

句子一：“LingYuan！”。

句子二：“LinqYua！”。

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

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

很多應用場合無需考慮字符出現的位置，可以直接統計相同字符數量來計算相似度，但設計算法時需要考慮重復字符的影響。計算公式如下[13-14]：

[SU=FMAXL1，L2]? ⑵

其中，SU為相似度，MAX（L1，L2）為兩對比語句長度（單位為字節）的最大值，F為相同字節數。

2.1 不存在重復字符的解決策略

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

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

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

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

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

2.2 存在重復字符的解決策略

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

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

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

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

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

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

重復字符的解決要點是確定重復字符的個數。

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

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

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

計算得到的相似度為：

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

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

因單字節字符與雙字節字符占據字節的長度不同，使用計算機處理字符的時候往往會出現亂碼的情況，例如：

句子九：“o是字母還是數字呢？”，字節長度L7=19。

句子十：“1是數字不是字母！”，字節長度L8=17。

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

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

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

3 算法描述

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

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

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

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

步驟2 單字節字符與雙字節字符判斷。

步驟3 重復字符判斷并統計。

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

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

4 仿真分析

搭建測試環境對設計進行仿真。

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

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

5 結束語

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

參考文獻（References）：

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

學報，2022，36（1）：F0003

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

談錄[J].現代語文，2022（6）

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

2019（3）：64-66

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

（2）：59-64

[5] 車萬翔，張偉男.人機對話系統綜述[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] 馮志偉.自然語言處理的歷史與現狀[J].中國外語，2008（1）：

14-2

[9] 全國信息技術標準化技術委員會. GB 18030-2005信息

技術中文編碼字符集[M].北京：中國標準出版社，2006

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

計算機工程與應用，2019，55（12）：1-7，43

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

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

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

設計[J].科學技術與工程，2022，22（3）：1091-1097

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

析與知識發現，2017（6）：1-11

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

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