关于重复词句提取的两种算法分析.docx

关于重复词句提取的两种算法分析 (桂林电子科技大学 计算机学院，广西 桂林 541004) 摘 要：文章介绍了两种用来发现重复词句的算法 基 于后缀树的方法和基于倒排索引的方法。 关键词：重复词句；重复序列；后缀树；算法；比较 中图分类号：TP391.1 文献标识码：A 文章编 号： 10076921(XX)01007305 重复词句，有时指字段、短语、搭配等的重复或同现， 有时是指重复序列、重复语句、同现 的字句、或重复排列 等，它是在一篇文本或文集中出现超过两次的字序列。文 本中所有的字 都考虑或者通过 stop list 忽略文中某些词， 都是随着具体实现而定。一般而言，我们可 把某些词看作 特定符号来标记。这样，重复字句的符号标记就和原始文 本中的样式一样。重 复及相似内容的识别在信息处理领域 中，在利用计算机处理文本信息时，都是个比较重要的 研 究课题，它还广泛应用于防抄袭识别、新闻网页去重、自 动分类、搜索引擎等系统中。就 一般意义而言，重复字段 的抽取和实现是涉及和涵盖了计算语言学和文本挖掘的范 围。它们 对聚类、分类、主题发现和其他机器学习和人工 智能技术等都有着重要意义。近年来更广泛 的应用于字符 串处理，DNA 序列比对，文本聚类，XML 结构索引等领域中。 1 后缀树 后缀树是一个数据结构，把文档看作是一个由若干短 语组成的字符串，而 不是看作一组词集1。一般算法 中用来找出重复语句的传统 ST 结构都类似于 Zamir 4 中阐 述的结构。在最简单的版本中，后缀树算法创建了一 个树型结构，每个后缀树的节点，表示 一个词并且根节点 为空。这样每个从根节点出发的路径表示了一个语句，这 个语句中的字词 是由路径遍历的相应的代表各个字词的结 点来标识。后缀树是一个有根树，也是一个有向树 。例如， 用下列语句来生成一个后缀树结构。 “can drive trucks safely. Men drive cars safely. Men can drive trucks.” 确定树的最大深度 m=3。下图 1 中所示的就是这种方法 生成的后缀树结构。 740)this.width=740“ border=undefined 当生成了树形结构后，获得一个单一重复语句的最简 单方法是用递归方法从根节点遍历到叶 节点。如果使用非 递归执行来获得语句，那将是一个相对复杂的过程并且在 相同复杂度的情 况下它不能保证我们能得到更好的效率， 因为它取决于目前的编译执行器的执行效率。 一般的，在后缀树最外层描述一个句子的最后一个词 的节点中常给出一个句子出现的频率。 在一个代表特定语 句的节点集合中，这个节点常常位于一个后缀树结构的底 层，这里我们常 把根节点作为一棵树的顶层。 1.1 ST 算法执行中的一个细节描述 ST 算法执行的伪代码如下列图 2 所示。我们同时指出 了每一步的时间复杂度。 首先，一个输入文集被存储在分表中，以一种方式使 得特定的词被连续存储，并且句子或由 标点分开的连续句 子在空间上也被划界。 接下来生成一个根节点。这个根节点的特殊性在于它 不能指向任何一个字词。然后分表的第 一个位置的词被读 出，并被添加到有关键码值的哈希表中，使用哈希表是用 来加快存储 字句的存取。 Create a root node of ST-structure; O(1) While (input is not empty) Clear parent list; O(N) While (get next input word != sentence delimiter) Add word to hash table; O(N) Add word to node to root node; O(N) Add reference to parent list; O(N) For each node from parent list (except the last one added) Add word node to current node; O(N*m) Add reference to parent list; O(N*m) Remove currently processed node from parent list; O(N*m) Traverse created ST-structure recursively to obtain ST-phrases O(N) 740)this.width=740“ border=undefined 每个后缀树节点表示输入文集的一个字词，并且它们 平行生成一个对应哈希表的接口。这样 如果在一个后缀树 中更深层的节点是重复的话，我们能减少总的存储空间。 节点同样包含了 信息，比如这个语句在输入文集中出现的 次数，并且它提供了一个关于子节点的列表。 如果一个字词，在分表中被读出并写入到哈希表中， 根节点应检测：当它是一个父节点时它 是否包含一个节点 表示当前的字词。如果它是这样一个父节点的话，出现次 数的计数应当累 加。否则，生成一个表示当前字词的新节 点并且把它添加到根节点的孩子节点的列表中。在 两种情 况下，表示当前字词的节点都被添加到了父节点列表的末 尾。 现在，处理包含着先前步骤中所添加节点的父列表。 因为这些节点都是当前字词的父节点，就是说它们表示出 现在 输入文集中当前字词的前面，我们能简单地将它处理 成根节点的情况。父节点被从父表中移 出。相应地，如果 一个表示当前字词的节点的层次和最大后缀树层次相等的 话，那么这个表 示当前字词的节点并不能添加到父表中。 接下来，下一个字词被读出并且这个过程如上述重复 进行，直至分表读完。图 4 描述了一个 后缀树结构的四个 步骤，输入句子是“can drive trucks safely”，最大层 次 m=3。 1.2 复杂度 如在图 2 中所提到的，其中 N 是所有输入文集中字词 的数目，m 是后缀树的最大层次，时 间复杂度是 O(N+N*m+N)。 空间复杂度是 O(N),有关键码值的哈希表是 O(K)。其 中 K 是在输入文集中关键词的个数，所有 的后缀树节点 O(N*m)的情况是最坏的情况，所有的 ST 语句得到 O(N*m)。 这样，总的时间和空 间复杂度是线性的。 740)this.width=740“ border=undefined 2 重复序列 关于重复序列，早在 Justeson,Katz5 和 Salem 等的著作中都提出过这个概念。在 这些著作 中，重 复序列有特定的含义并且在定义上有着严格的限制。他们 要求每个重复序列必须包含 一个名词，对于是否包含介词 等也有相应的要求。这种意义上的重复序列是指它由几个 词组 成并且有一个特定的含义。为了发现名词和相应的动 词，发现重复序列就需要增加额外的资 源，如不同的过滤 器等。对于这种严格定义的重复序列来说，它本身基于语 义有着严格的语 法特性。另一个问题是它不具有语言独立 性。 后来发展出了另一种发现重复序列的工具 LIKES。它使 用两个过滤器，一个切割过滤器有一 串不能组成其他队列 的单独的词组成，多为关联词和动词。另一个语法过滤器 有一串可以引 导一个序列的代名词组成。这些过滤器有着 语言依赖性。LIKES 能创建一个关于整个文档各 个段、句 子、词的树。它可以找到一个序列在文中的特定位置。 在接下来我们的实验中，重复序列都是指单纯的重复 的词句，并不是指上面所提到的这些 特定的限制。另外， 本文中的实验文本和算法都是基于英文文档而言的。 2.1 算法 下图 5 是算法的伪代码。同时在旁边标注了每个步骤 的时间复杂度。下面来进一步解释说明 此类算法。 我们这里的算法并没有具体考虑每一种不同的过滤器， 因为算法从文本中提取出的每个标记 并不是严格的都是以 字词作为基准的，只要是它们符合语法形态学的意义，作 为每个标记的 内容，可以是字词也可以是任何意义上的符 号。图 6 给出了算法的核心步骤。我们将根据下 面的每一 步来说明算法。将下列句子作为输入文本： “Personal construct psychology. Personal construct psychology. Personal constru ct theory. Personal construct technology.” /读符号化文档并更新倒排索引 for each word in text add to hash table; O(N) for each key in hash table O(K) /creates list of words following each occurrence of key word get following words; O(V) /modifies list so as only one sequences remain that occur twice at least reduce empty columns; O(V) /counts newly discovered segments and adds them remove empty columns; O(V) remove duplicates; O(V) add inclusions; O(V+VlogV) add segments; O(V) 输入文本的预处理，如：标记化、标准化等都是在算 法外实现的，这样算法真正输入的是标 记词的队列。我们 将每个词添加到哈希表中时，都同时创建了一个倒排索引。 并且哈希表有 一个关于每个词出现次数的表。这张伴随表 的内容是这些词在文本中出现的相应位置 6 。 例如：对personal这个词来说，我们查寻了它在文本 中的出现并创建了一个在文本的不 同位置紧接着 personal的词表。这个词表被分类并且只有那些在 文 中的不同地方出现了两次或多次的词才能被保留下来。其 他的词被移除。接下来，相同的副本词被移除，原始词累 加。其余的所有句子 的子句在第四部分中累加，第五部分 中做的处理和第三部分相同。最后，新提取出来的序列 添 加到重复序列表中，即图 6 中的第六部分。整个的处理过 程对倒排索引中的其他词进行同 样的处理。例如在处理 construct时，就能找到语句construct psychology。理论 上来讲，重复序列的最大长度可以是 整个文集的长度的一半。但是，更加具有可行性的是将 重 复序列的最大长度限定在一个合理的范围内，在本例中就 将其设定为了 3。大于这个限制 的序列在处理中将被忽略。 2.2 复杂度 算法中的每一步时间复杂度已在伪代码中标注了出来。 如图 5 中所示，其中 N 是文本中的字数 ，K 是文本中原始 词的关键码值的字数，V 是文本中的一个词出现的平 均次 数。由这三个变量表示的整个算法的时间复杂度是： O(N+K(VlogV+V) (1) 又，V=N/K。于是，代入得到： O(N+K(N/K)log(N/K)+N/K) (2) O(N+N+Nlog(N+K) (3) 特别的，如果 K=N，即文中每个词都不相同，公式简化 为 O。但当 K 趋近于 logN 时， 如图 7 所示，总的时间复杂 度是上线性的，即 O(NlogN)JY(4) 接下来再来考察空间复杂度，我们得到内存中的标记 化文本的空间复杂度是 O(N)，词的出现 次数的哈希表，例 如，倒排索引的空间复杂度是 O(N)，一个词在文本中总的 出现次数不可能 大于 N，并且序列表的空间复杂度是 O(N)。 这样，总空间复杂度我们得到 O(N)。这样我们得 到结论， 对于抽取出现在上面的重复序列在时间上是上线性的，在 空间上是线性的。 740)this.width=740“ border=undefined 3 结果分析 在五个长度为大约 1MB 到 30MB 的不同文本上运行这两 个算法，这些文本中字词的总数大 致为几百万个。统计了 字句最大长度为 3，4 和 5 的句子，并且统计了每个算法的 时间和 空间复杂度。在每个文本运行这两种算法得到的抽 取重复词大致相同。图 7 中的曲线证实了 我们对于算法的 复杂度的理论假定。ST 算法在时间和空间上都是线性的， 而 RS 算法在时间 和空间复杂度上则是上线性的8 。ST 算法的空间消耗大致是 RS 算法空间消耗的两 倍。 两个算法的运行环境都是 C#，使用.NET Framework1.1 编译实现 AMD Opteron 1.6GHz 2GB RAM。 对具有 30MB 大小的英文文档进行了实验。两种不同方 法的时间和空间复杂度分别如下所示： 740)this.width=740“ border=undefined 4 总结 文中对重复词抽取的两种算法进行了阐述，并将两者 运行实现。通过对实验结果的分 析，比较了二者的性能以 及时间和空间复杂度。重复词的抽取技术在当今生物、地 理信息、 搜索引擎、信息检索领域都有越来越广泛的应用。 两种算法的实验结果看出这两种算法对 于处理大型文本语 言是一个基础性的工具。在重复词抽取和去重问题上将会 有更加广泛的应 用。对文本挖掘领域，网页去重问题，垃 圾邮件过滤，文本聚类7 中都将有更加 广泛的意义。 根据本文实验结果，用户可以根据不同文档的时间和空间 复杂度要求，来选择 两种算法之一。这两种算法对大型文 档的重复词提取都有着广泛应用和重要的意义。接下来 的 工作对重复抽取还可以从循环子序列入手，进一步研究重 复序列简化模式的提取和检测过 程。 参考文献 1 Grolmus P., Hynek J., Jezek K.: User Profile Identification Based On Text MiningC. Proc. Of 6th Int. Conf. ISIM03, MARQ Ostrava, pp. 109-118, I SBN 80-85988-84-4, XX. 2 Debar H ，et a1Fixed vsvariable- length patterns for detecting su spicious processIn JJQuisquater，YDe swarte，CMeadows，DGollmanned sC. Procof the 1998 ESORICS Conference，hum-ber 1485 in LNCS，sep19981 -16. 3 Han J., Kamber M.: Data Min