4.2.3 方法及原理
研究文本相似度，首先需要明确文本相似度的界定问题。关于文本相似度的内涵的详细论述，请参见文献（Yan T W et al，1995），本部分所讨论的文档都指文本文档，所讨论的相似仅局限于狭义上的相似，例如新闻的转载或者电子文档的抄袭等所造成的文本文档相似。文档相同是相似的一种特例，即相似度为100%。
对于各种文本文档，其组成都遵从如下基本事实：由字构词，由词组句，由句成段，由段成篇。当然也有单字成词、单词成句的情况。此外，为了语意表达，还需要借助于适当的标点符号。在不考虑字义的情况下，可以将字与标点符号同等对待。
基于上述事实，任何文本文档都可被视为是一个集合，该集合的元素可以为字、词、句子、标点符号、段落等。设文本长度为n，则该集合应该含有n个长度为1的元素，含有（n-1）个长度为2的元素……1个长度为n的元素，这些元素即n-Gram，是由大小为n的滑动窗口从文本起始位置开始向终止位置滑动所形成的。上述描述可以一般化表达为，该集合含有（n-m+1）个长度为m的元素（1≤m≤n），不过考虑到集合的特性，需要剔除相同的元素，所以长度为m的元素的数目上限是（n-m+1），当滑动窗口越小时，元素数目越偏离（n-m+1）；滑动窗口越大时，越接近（n-m+1）。很明显，该集合大小的上限为
。故可以将该集合作如下表述：
其中n1，n2……nm等分别表示长度为1，2…，m元素的个数，而
表示该元素是所有长度为m的元素中的第k个。
在不考虑元素长度的情况下，为了表述方便，可以将上述集合表述为：
文档Di与Dj的相似度评价函数定义为：
其中
，即若元素ek不是同时存在于Di、Dj中，则该元素对相似度无贡献。W（ek）是元素ek的权重评价函数，若元素是经过某种方式优选出来的，则该函数的值主要由自变量ek本身内容所贡献；若元素为随机挑选的，则该函数的值主要由自变量ek的长度来贡献，从这里我们可以看出权重评价函数的地位举足轻重。针对不同的应用场合，权重评价函数的选择也不尽相同，其选择应该遵从一定的选择原则：在相似度计算时贡献大的元素应该赋予较大的权值，反之则应该赋予较小的权值。一般而言，辨识能力强的元素贡献也较大，反之则贡献较小。很显然，0≤S（Di，Dj）≤1，当S（Di，Dj）=1，Di=Dj，即两个文档完全相同，此时Di、Dj这两个集合互为子集。
上述相似度评价函数可以完美地评价文本的相似度，但当文档较大时，可操作性不强，因为可能耗费大量的时间。事实上，也没有必要遍历所有元素，在实际应用中，只需要从比较文档中随机挑选其中的n-Gram，然后判断该n-Gram是否也在参考文档集合中，并计算相应的贡献，最终即可判别两个文档的相似度，其流程如图4-3所示：
图4-3 改进的文档相似度计算流程
与图4-2对比可见，改进后的计算方法不必再消耗大量的时间在特征项的提取上，只需要构建参考文档后缀树，此后从各个比较文档中按照指定的随机抽取策略来抽取n-Gram即可，从而大幅度地提升了整个计算过程的效率。