(桂林电子科技大学 计算机学院，广西 桂林 541004)
摘 要：文章介绍了两种用来发现重复词句的算法——基 于后缀树的方法和基于倒排索引的方法。
关键词：重复词句；重复序列；后缀树；算法；比较
中图分类号：tp391.1  文献标识码：a  文章编 号：1007—6921(2009)01—0073—05

重复词句，有时指字段、短语、搭配等的重复或同现，有时是指重复序列、重复语句、同现 的字句、或重复排列等，它是在一篇文本或文集中出现超过两次的字序列。文本中所有的字 都考虑或者通过 stop list忽略文中某些词，都是随着具体实现而定。一般而言，我们可 把某些词看作特定符号来标记。这样，重复字句的符号标记就和原始文本中的样式一样。重 复及相似内容的识别在信息处理领域中，在利用计算机处理文本信息时，都是个比较重要的 研究课题，它还广泛应用于防抄袭识别、新闻网页去重、自动分类、搜索引擎等系统中。就 一般意义而言，重复字段的抽取和实现是涉及和涵盖了计算语言学和文本挖掘的范围。它们 对聚类、分类、主题发现和其他机器学习和人工智能技术等都有着重要意义。近年来更广泛 的应用于字符串处理，dna序列比对，文本聚类， 结构索引等领域中。
1 后缀树

后缀树（此后简略为st）是一个数据结构，把文档看作是一个由若干短语组成的字符串，而 不是看作一组词集〔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所示。我们同时指出了每一步的时间复杂度。

首先，一个输入文集被存储在分表中，以一种方式使得特定的词被连续存储，并且句子或由 标点分开的连续句子在空间上也被划界（如图3）。

接下来生成一个根节点。这个根节点的特殊性在于它不能指向任何一个字词。然后分表的第 一个位置的词被读出，并被添加到有关键码值的哈希表中，使用哈希表是用来加快存储 字句的存取。
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>

每个后缀树节点表示输入文集的一个字词，并且它们平行生成一个对应哈希表的接口。这样 如果在一个后缀树中更深层的节点是重复的话，我们能减少总的存储空间。节点同样包含了 信息，比如这个语句在输入文集中出现的次数，并且它提供了一个关于子节点的列表（如图 3）。

如果一个字词，在分表中被读出并写入到哈希表中，根节点应检测：当它是一个父节点时它 是否包含一个节点表示当前的字词。如果它是这样一个父节点的话，出现次数的计数应当累 加。否则，生成一个表示当前字词的新节点并且把它添加到根节点的孩子节点的列表中。在 两种情况下，表示当前字词的节点都被添加到了父节点列表的末尾。

现在，处理包含着先前步骤中所添加节点的父列表（见图2）。因为这些节点（除了最 后添加的节点——它是为了下一步做准备）都是当前字词的父节点，就是说它们表示出现在 输入文集中当前字词的前面，我们能简单地将它处理成根节点的情况。父节点被从父表中移 出。相应地，如果一个表示当前字词的节点的层次和最大后缀树层次相等的话，那么这个表 示当前字词的节点并不能添加到父表中。

接下来，下一个字词被读出并且这个过程如上述重复进行，直至分表读完。图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)。这样，总的时间和空 间复杂度是线性的（如图7）。

740)this.width=740" border=undefine