4.2.2 相关研究及存在的问题
目前，关于文本相似度的计算方法有很多，不过因应用领域不同，所采用的计算方法也有所区别，相应的计算方法从不同的角度可以有不同的分类方式。如鲍军鹏等（2003）、曹玉娟等（2011）将计算方法总结为基于字符串比较的方法和基于词频统计的方法。宋玲等（2006）将其分为基于向量空间模型的相似度计算方法、基于集合模型的相似度计算方法、基于层次结构的相似度计算方法、引文图相似度计算方法等。Wan Xiaojun（2006）则从主题相似和结构相似两个方面对流行的相似度计算方法做了较为全面的总结。此外，按所处理文本的长度来分，可以分为针对长文本和短文本的相似度计算方法，例如当下流行的微博由于其字数的限制，所以往往被归结为短文本；另外在自动问答系统中，在对问句或者答案进行匹配优选时也常常涉及对短文本的相似度计算和句子相似度的研究（李彬等，2003；杨思春，2006），为短文本相似度的计算提供了一种有效方案。
在诸多的相似度计算方式中，基于向量空间模型（VSM）（Salton G et al，1975）或者文本处理的方法是两类最主要的手段，文本处理主要是指以字符、词语、句子、段落等为单位对原始文本作适当的处理以及其他一些关于特征项提取的处理。需要注意的是，此处所说的句子，是指广义的句子，即既包含平常意义上的一个完整句子，也包括其他标点符号切分而来的非完整句子，它们是完整句子的一部分。在实际应用中，研究者往往会对处理后的字词句段等元素做进一步的处理以获得能有效表征原始内容的特征项（也称指纹）。特征提取相关的处理，典型的方式有最长公共子串（Matsubara W et al，2008）和最长公共子序列（Hirschberg D et al，1975；Adi S S et al，2010）等，此外还有其他的特征串提取方式（吴平博等，2003）。
要完成文本相似度的计算，首先需要获取文本的表达。文本文档的表达方式较多，此处简要介绍两种最常用的：文本的集合表达和文本的向量表达。
文本的集合表达方式的中心思想是：首先针对原始文本作适当的处理，提取其特征项，然后以这些特征项构建集合，则可以根据文档对应的集合之间交集的情况来判断其相似度。设有两个文档集合分别为Dp、Dq，其特征项记为
（x表示该元素所隶属的文档，i用于标记同一文档的不同特征项），特征项的数目分别为u、v，即：
则Dp、Dq的相似度可以用下面的表达式来计算：
显然，当集合Dp=Dq时，S（Dp，Dq）=1，此时表明两个文档完全一样。
基于VSM的计算方法往往建立在文本处理的基础之上进行，文本的向量表达方式的中心思想是：首先选取合适的向量空间基底，然后计算各个基底的权重，这样就可以由这些权重和基底将文档表示为一个向量，最后通过余弦函数计算两个文档对应的向量的夹角来判断其相似度。设选定的向量空间基底为ei（i=1，2……n），其中n为向量空间的维数，权重记为
（x表所隶属的文档，i用于标记同一文档向量的不同分量），则文档向量Dp、Dq可以表示如下：
当夹角越小时，表明两个文档的相似度越高，反之则表明相似度越低，特别地，当夹角为零时，表明两个文档相似度为100%，即完全相同。
纵观上述两种方式，我们不难看出，当采用集合表达方式时，关键在于提取合适的特征项；当采用向量表达方式时，关键在于提取合适的特征项作为向量空间的基底，并计算各个特征项的权重。由此可以看出，特征项在文档相似度计算中的作用不容忽视。正因为如此，很多研究人员都曾尝试各种提取文档特征项的方法，并取得了不少研究成果。例如先对文档分词，去掉干扰成分，然后统计词频，按照上述VSM的方式来计算文档相似度；部分研究者通过扫描文档中的标点符号，然后取得标点符号附近的文本作为特征项，进而执行后续的计算；此外也有研究者以文档的长句作为特征项来进行相似度计算；还有部分研究者提出了基于n-Gram（Zhang W et al，2011；Damashek M，1995）、s-Gram（Aimmanee P，2011）、RM树（王金宝等，2011）和Shingle的方法来进行文档相似度判别，其本质仍然是基于文本处理；此外还有基于最长公共子串和最长公共序列的方法，这些在上面已有提及，不再赘述。关于特征项的权重计算，常用的有TF-IDF公式（Salton G et al，1988），该公式具有多种变种。
上述方法在计算文档之间的相似度时，会对每个文档都执行特征项的提取及相关计算，其计算流程如图 4-2所示。
图4-2 一般文档相似度的计算流程
其中，文档表示可以采用集合表示、向量表示或者其他有效的文本表示方式。从其执行流程可见，除了需要对参考文档进行特征提取之外，文档集合中每一个需要与参考文档进行相似度计算的文档也都需要执行特征项提取操作，而特征提取这一操作是极其耗时间的一个环节，这也导致了这些计算方法效率比较低下。若特征项的提取建立在分词的基础上，则还需要更大词库的支持。
本节基于n-Gram的概念，结合后缀树的构建，提出了一种基于随机n-Gram（Random n-Gram，R-Gram）的文本相似度计算方法，该计算方法较前述方法更为简单快捷，在搜索引擎查重和网络舆情等特定应用领域有广泛的应用。