一种基于字符对比的文本相似度计算方法

2023-06-15汪亚东

计算机时代 2023年6期

汪亚东

摘要：为解决包含重复字符的文本相似度计算问题，提出了一种新的计算方法来获取两文本之间的相似度。首先根据单字符的对比情况统计重复字符数量；其次通过分析总的对比结果剔除重复字符的干扰；然后借助公式计算出正确的文本相似度，并拓展单字节字符和多字节字符混合时的相似度计算方法；最后编写算法代码来进行仿真分析，多组测试结果表明，用该方法计算得到的文本相似度与理论值相吻合。

关键词：自然语言处理；文本相似度；重复字符；计算算法

中图分类号：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