基于特征向量的中文文献相似度评价.doc

基于特征向量的中文文献相似度评价杜薇薇（中国科学技术信息研究所 北京 100038）摘 要：在这个日新月异的时代，科技文献如潮水般不断涌现，为科学技术的发展提供了无限动力。但是，其中也存在着一些不和谐的声音。天下文章一大抄，科技文献抄袭的现象也时有发生，这严重损害了文献原作者，也给科技文献的严肃性提出了挑战。本文利用分词技术提取文献特征向量，并结合动态规划算法对文献的相似度给出具体评价，针对不同抄袭的现象，发现其中存在的规律，具体问题具体分析。最后，给出实际实验结果，为文献评审专家提供参考。关键词：特征向量；相似度；中文文献；中文分词；动态规划中图分类法：TP3Feature Vector-based Similarity of Chinese LiteratureDu Weiwei(Institute of Scientific and Technical Information of China, Beijing 100038)Abstract: In this rapidly changing era, scientific and technical literature such as the flood continue to emerge, for the development of science and technology, unlimited power. However, where there are some discordant voices. The world is a big copy articles, scientific literature the phenomenon of plagiarism have occurred from time to time, which severely damaged the original author of the literature, but also to the scientific literature of the seriousness of the challenges. In this paper, segmentation techniques extract feature vectors literature, combined with dynamic programming algorithm to the similarity of the literature is given a specific evaluation copy for different phenomena, found that there is the law of a concrete analysis of specific issues. Finally, the actual experimental results, in order to provide a reference literature evaluation experts.Key Words: Feature Vector; Similarity; Chinese Literature; Chinese Word Segmentation; Dynamic Programming0 引 言随着计算机的发展尤其是网络技术的空前应用，各类论文等文献的数量极具攀升。其间，由于各种原因，文献抄袭甚至拷贝的现象时有发生。伴随文献库的日益庞大，要评价一篇文献是否有抄袭之嫌，对文献评审专家提出了新的挑战，也是自动化评审系统面临的新课题。本文旨在通过对文献中特征向量的相似度给出评价，帮助评审专家对一篇待评文献，与文献库的文献一一比较，并提取相似文献，供评审专家参考。对于一篇文献是否抄袭另外一篇文献，直观的看，就是两篇文献中重复的文字比率，如果有50%以上重复，那必定有抄袭之嫌。但是逐字逐句的比较理论上是可行的，但是实际应该有很多问题。其一，是效率问题，一篇普通文献基本在一万字，如果两篇文章比较，就是一万字和一万字比较，显然复杂都很高，况且我们比较的是一个文献库，有几十万，甚至上百万篇文献，那么这样的比较效率是很低的，实际基本不可取。其二，论文抄袭现象本身很复杂，有的抄袭是简单的复制，有的只改变文献的段落顺序，有的在文献中穿插其他内容，因此，逐字逐句的方式显然不能涵盖这些复杂的情况。那么，怎么办？受到文献检索和WEB搜索的启发，本文在两个方面展开对文献相似度评价的实践，其分析的内容组织如下：第一部分介绍文献特征的提取，这个是文献相似度评价的前提，是文献匹配的对象，没有比较对象，怎么比较就无从谈起；第二部分讨论特征向量动态规划匹配算法；第三部分实验和结果分析；第四部分结语。1 特征向量前面简单介绍了逐字逐句是不可取的，那么怎么办？关键字首当其冲，但是只是关键字显然是不够的，需要更多的信息。受到文献全文检索的启发，采用提取文献主体特征向量的办法，来丰富对于文献相关度的评价。现在，难点就转移到了文献特征向量的提取。首先，摆在面前的问题是特征向量的粒度问题，就是向量的维度。一篇文献取多少合适，既满足相似度评价性能要求，又满足可靠性要求。对于中文文献而言，一万字的文献，字的粒度太小，段的粒度太大，这些是显然的。那么就剩句子和词组的粒度，基于文献检索经验的考虑，这里采用词组的粒度。那么现在就要提取特征向量，第一步需要完成文献的中文分词，把一篇文献转化为中文词组的组合。X是特征向量，n是特征向量的维度。1.1 分词技术介绍中文分词技术，发展至今已经有很多种，有基于词库的1，有基于统计的2，有基于语义的3，还有组合4-7的，根据应用环境的不同侧重点也不同。最成熟也是应用最广泛的是基于词库的分词，本文也是基于此。在基于词库的分词技术中，按匹配方向又分为正向匹配和反向匹配，按匹配尺度又分为最大匹配、最小匹配与最小切分。其实分词本身并不复杂，但是为什么有这么多分支呢？其核心是语义分歧，简称歧义。我们的老祖宗太有智慧了，中文一句话的语义，在不同的环境下有不同的理解。这也是基于词库的简单分词必然会带来歧义的原因。比如，“这个门把手弄坏了”，就是这样一个句子，如果没有语境，怎么分呢？是“这个门把手弄坏了”，还是“这个门把手弄坏了”，中文太奇妙了。基于语义的分词当然是要解决这个问题，但就目前而言，离实际应用还有一段时间。下面重点介绍基于词库和词性的正向最大匹配分词的实现，因为对于相似度的判别，是大量特征词的判别，对分词歧义的敏感度不高，可以忽略。1.2 词库首先，是词库。要建立一个带有词性的词库，并且是便于分词的。快速分词是分词技术显著的一个特性，因为要在成千上万的文献中，把每篇文献切分成词组组合，如果没有速度，显然是没有效率的。基于此，需要完成以下几步。第一步把词汇表中的词建立在一棵查找树，词组中的字分布在不同的树枝层，树根在第0层，查找时从树根开始，查找树根子孩子是否还有查找的字，如果存在，就以查找到的子树为最新的查找树枝，在它的子孩子中查找下一个字，依次类推。如果子树的集合采用Hash表，那么这样匹配一个词的时间复杂度基本是O(n)，n是词的长度。但是，Hash表占用的空间复杂度通常都比较大，另外，建立这样一棵树，也是很费时间的，因此，为了避免重复构建，首先把建立好的树保存到一个文件中重复利用。Hash表本身也不适合保存，因此采用有序数组作为子树的集合，二分法进行查找，时间复杂度是O(log n)。中北国华京人人民民共和国图一 词库树分层结构先看树枝节点的C+描述：struct NodeNode() throw() : ch_(-1), tag_(0) / 初始化Node(wchar_t ch) throw() : ch_(ch), tag_(0) bool operator (const Node & rhs) const throw() / 排序比较 return ch_ rhs.ch_; wchar_t ch_; / 汉字wchar_t tag_; / 词性标识和词组标志int offset_; / 这个树枝节点的子节点的结尾偏移，也就是下一个节点的子节点偏移，偏移的单位是节点数。 * root_;这里采用了一个技巧，就是按从树根开始按树的广度遍历，其中offset字段保存了这个树枝的子树的结尾偏移，而这个树枝的子树的开始偏移，是前一个树枝的子树的结尾偏移。这样，很容易就找到了一个树枝的子孩子的范围。树根从0开始偏移，那么树根的子树就是从1开始偏移，而树根子树的结尾偏移就是树根节点中的offset。01根offset第一个子树offset第二个子树offset根根的子树根的第一个子树的子树根的第一？个子树的子树图二 词库树的平面结构一个树枝节点在32位机器上占用两个机器字，8个字节。对于一个百万级的词库，这样一棵查找树的节点数在2百万z左右，占用空间大小不到20M，且大小基本和词库成线性增长O(n)，空间上是高效的。时间上，采用二分法8，每个节点查找是O(log n)，也是高效的。至于这个树的生成，限于篇幅，这里不再贴出完整代码，下面重点介绍基于这棵树的分词。1.3 基于词库的最大匹配（正向或者反向）有了词库，现在就是切词的问题了，要把一篇文献的内容切分成词组组成的集合，也就是本文研究的特征向量。这里采用最大匹配算法7，词性参与歧义的优化，但是实际上文也提到了，只要采用相同的分词算法，对于同一段抄袭的文本，怎么切都是一样的，即使存在歧义，也是同时存在，对于大量的词组，歧义的比例可以忽略。这样，得到一个结论，在文献相似度评价中，对分词的歧义不敏感。下面给出最大匹配的算法。template / 正向或者反向文本读取器，用于正向或者反向文本的下一个字的读取int FindMax(const char * words) const throw() / words 待分词的文本F f(words, strlen(words); / 建立一个文本读取器，正向或者反向。int result = 0; / 分词个数for (const char * p; f;) / 是否还有未分词的文本，如果存在就继续；否则结束分词。p = f; / 分词词组的开始位置int offset = 1; / 树枝的子节点开始偏移，1是树根的子节点的开始偏移，因为第一个节点上树根。const Node * node = root_; / 树根树枝根节点/ 二分法查找树枝节点的子节点是否存在当前的字if (node = Search(root_ + offset, node-offset_ - offset, (const wchar_t)f)int old = result; / 记录当前分词个数，用于比较是否找到新的词组。int tag, pos, len; / 词性、位置和长度doif (node-tag_ & TERMINATOR) / 找到的节点上终止节点/ 表示从根到此构成一次词组tag = node-tag_ & TERMINATOR; / 读取词性pos = f.Get(p, len); / 读取词在文本中的位置和长度+old;/ 找到节点的前一个节点，因为前一个节点的子节点偏移就是此节点的子节点偏移。offset = (node - 1)-offset_;/ 如果存在下一个字，则取出，并在当前树枝子节点中查找这个字，如果存在就继续，否则推出循环。 while (bool)(+f, +f, f) & (node = Search(root_ + offset, node-offset_ - offset, (const wchar_t)f);if (result old) / 是否找到词组 / 找到新的词组/ 记录分词结果（词性、位置和长度）/ tag, pos, len;/ 保存分词结果/ Hash(pos, len);+result;else*f 0 ? +f, +f : +f; / 取下一个字return result; / 返回分词词组数上述算法用tag/pos/len记录一次最大匹配分词的结果，在do/while中，如果有新的词组找到，证明新词组比以前词组更长，因此，出了do/while，如果找到词组，tag/pos/len中必是最大匹配词组。这样就完成了一段文本的分词，最终找到一篇文献的特征词组。一篇一万字的文献，一般的分词结果在一千到两千词之间。找到的词组全部作为文献的特征向量，作为下一步相似度匹配的特征向量。1.4 Hash有了词组组成的特征向量，就可以直接进行相似度的匹配，但是，出于性能考虑，还需要对词组向量进行优化。因为词组是字符串，比较字符串就需要一个字一个字比较是否一样，如果比较两个长度分别是m和n的两个词组，需要的时间复杂度是O(mn)，虽然分词后的词组组成的特征向量中，m和n通常比较小，但是由于特征向量维度很大，所以逐字比较有优化的余地。这里采用简单的字符串Hash算法，对分词后的特征向量中的每一个维度，进行Hash，结果是一个32位的整数。这样，在相似度匹配的时候，只需要比较Hash的整数是否一致就可以了，显然复杂度就变成了O(1)，这样将更加高效。Hash算法是单向，也就是说两个不同词组的Hash可能也相等。但是，这样的概率还是比较低的，而且相似度比较的是相等，而不是不等，因此，Hash是可靠的。Hash的算法很多教科书上都有，这里就不再列出。至此，完成了评价的第一步，特征向量的提取，特征向量是由分词后词组的Hash值组成了一个整数多维向量。2 相似度评价一篇文献和另一篇文献的相似度，已经转化为两个特征向量相似度的评价。受最大公共子序列算法的启发，如果两个特征向量的最大公共子向量的维度越大，那么两个特征向量就更相似，从而两篇文献也就更相似。而最大公共子序列算法采用的是动态规划算法，下面简单介绍一下。2.1 动态规划动态规划8-9算法是一个多阶段决策问题，一般由初始状态开始，通过对中间阶段决策的选择，达到结束状态。这些决策形成了一个决策序列，确定了完成整个过程的一条活动路线。采用动态规划求解的问题必须满足一定的条件，其一是问题中的状态必须满足最优化原理；其二是问题中的状态必须满足无后效性。动态规划算法是求最优解的一个有效算法。它有两个显著的特征，其一，是最有子结构，就是求解问题的最优解必然包含其子问题的最优解；其二，是重叠子问题，就是说子问题相似或者相同。通常动态规划算法求解，分两步，第一自顶向下将问题划分为若干子问题，第二自下而上求子问题的解，然后利用子问题的解求问题的解10。现在，已知特征向量求它们的最大公共子向量。显然如果X和Y的维度为0时，那么最大公共子向量的维度必然也是0。先假设X和Y向量的子向量和，且它们的中最大公共子向量为Z，维度为k。显然，X和Y向量的最大公共子向量必然包含Z，这就是最有子结构。现在，比较和，如果它们相等，那么和的最大公共子向量的维度必然是k+1，如果他们不相等，那么它们的子向量的维度必然是和或者是和的最大公共子向量维度的大者。总结一下：2.2 乱序回头想一想，最大公共子向量真的反应了两篇文献的相似度吗？先看一个例子，假设两篇文献有其中两段，用A表示第一段，B表示第二段，如果文献一段落顺序是AB，而文献二段落顺序是BA，采用最长公共子向量算法，比较的结果就是A和B中特征向量维度大的那个（忽略A和B本身的相似度）。这显然是不精确的，因为其实这两篇文献可以认为是一样的，只是顺序颠倒而已。因此，纯粹只依据最大公共子向量判别文献的相似度，应该是不精确的，相应的相似度应该是被低估了。那应该怎么办？这里，采用变异的最大公共子向量算法，称为公共子向量集算法。什么意思？就是说，这里不是求最大值，而是求公共子向量的一个集合。只要子向量满足一定的条件，就认为是相似的一段，应该参与相似度的评价。这个条件就是一个阀值F，只要公共子向量的维度大于阀值F，就记录这段公共子向量，并最终参与相似度评价。下面是算法描述：struct Weight / 维度缓存节点，记录子向量信息。 int wk_ : 16, sub_ : 16; ; / 字向量的维度和所在的子向量索引template / 模板参数，这里就是Hash的值，一个整数类型int CommonSimilarity (const T * seq1, int len1, const T * seq2, int len2, int sub1, int sub2, int len, int size, Weight * weight, int length, int threshold = 16) / 求相似度/ seq1 / len1是特征向量1，作为横坐标。/ seq2 / len2是特征向量2，作为纵坐标。/ sub1 / sub2 / len是公共子向量分别在两个特征向量的位置/ threshold承认是公告子向量的阀值/ weight / length是环境，用于计算的空间缓存，存放维度，length是特征向量的最大允许维度值。维度初值为0，至少x或者y为0，维度为0。int result = 0;int skip = length - len1; /缓存空间长度和横坐标长度的差，Weight * k = weight, * w = k + length + 1; / w表示i,j，而k则表示i-1,j-1const T * p, * q, * end1 = seq1 + len1, * end2 = seq2 + len2; / end监视向量结尾for (q = seq2; q end2; +q, w += skip, k += skip) / 遍历向量2纵坐标for (p = seq1; p wk_ = k-wk_ + 1; / 维度增加if (threshold wk_) / 维度大于阀值/ 取子向量索引，如果是第一次满足就分配新的。w-sub_ = k-sub_ sub_;sub1w-sub_ = int(p - seq1); / 子向量1位置sub2w-sub_ = int(q - seq2); / 子向量2位置elsew-wk_ = 0; / 断了，重新开始记录。return result; / 公共子向量的个数向 量 1向量2 000112121图三 公共子向量集算法从图也可以清楚地看到公共子向量集必是图中有数字对角线，图中标识了三个公共子向量。因此，实际上求公共子向量集比求最长公共子序列的算法还要简单、直观。2.3 评价有了特征向量的公共子向量集，就可以对两篇文献的相似度作出评价。这里有两个概念，其一是两个文献的相似度，其二是文献不在另外一个文献中的比例，简单称之为自有度，这里自有度的概念是待评文献和整个文献库的一个评价。判断一个文献是否抄袭，相似度是一个参数，但是文献的自有度更能反映文献的可靠性，一篇文献，东抄一点，西抄一点，因此自有度是一个全局的概念。评价这两个度，概率首当其冲，直观的认识，相似度是公共子向量集在两个特征向量中的比例，而自有度是1-公共子向量集在待检特征向量中的比例。公式表示如下：特征向量的维度是已知的，那么问题就集中在公共子向量集的维度上，简单的认为是各个子向量维度的和，而这显然是不正确的。看一下图三就知道了，子向量存在重合现象，直观认识就是一段子向量在多个地方出现。因此，需要把子向量集做一次展开，把所有的公共子向量映射到待检特征向量上，看图三，如果待检的是向量1，则映射到横坐标上，如果待检的是向量2，则映射到纵坐标上。这样在待检向量上得到一个公共子向量的片段集，只要映射到的就证明是相似，把所有的映射相加就是相似维度。受图像腐蚀与膨胀启发，在求相似维度的时候，也采用类似算法加以优化。增加一个扰动参数，更进一步就是如果有两个公共子向量映射到待检向量上后，发现它们之间“紧”挨着，那么就把它们连起来，这里也简单称之为腐蚀与膨胀算法，而扰动参数控制两个公共子向量映射距离，一般取1或者2。如此，就得到了优化后的相似维度，代入公式就可以简单的计算相似度和自有度了。3 实验结合以上算法，本文给出相应实验数据。实验环境IBM XERIES_3850M2，Intel (R) Xeon (TM) CPU 3.00GHz，32.00GB的内存，Microsoft Windows Server 2003 Enterprise Edition Service Pack 2。文献集包括中文论文117,293篇。第一步，对所有论文进行分词建立特征向量，共采集特征向量91,739,562，总共耗时981秒，平均每篇采集782个特征向量，每秒采集120篇。相似度的匹配，平均匹配一次，耗时23秒，每秒处理5100篇。系统提供待评文献的自有度，同时分别提供相关文献的相似度，以及相似的文字。实验证明算法是有效的，基本正确的，有很强的实用性。4 结语问题发展总是