(桂林电子科技大学 计算机学院，广西 桂林 541004)
摘 要：文章介绍了两种用来发现重复词句的算法——基 于后缀树的方法和基于倒排索引的方法。
关键词：重复词句；重复序列；后缀树；算法；比较
中图分类号：TP391.1 文献标识码：A 文章编 号：1007—6921(2009)01—0073—05
重复词句，有时指字段、短语、搭配等的重复或同现，有时是指重复序列、重复语句、同现 的字句、或重复排列等，它是在一篇文本或文集中出现超过两次的字序列。文本中所有的字 都考虑或者通过 stop list忽略文中某些词，都是随着具体实现而定。一般而言，我们可 把某些词看作特定符号来标记。这样，重复字句的符号标记就和原始文本中的样式一样。重 复及相似内容的识别在信息处理领域中，在利用计算机处理文本信息时，都是个比较重要的 研究课题，它还广泛应用于防抄袭识别、新闻网页去重、自动分类、搜索引擎等系统中。就 一般意义而言，重复字段的抽取和实现是涉及和涵盖了计算语言学和文本挖掘的范围。它们 对聚类、分类、主题发现和其他机器学习和人工智能技术等都有着重要意义。近年来更广泛 的应用于字符串处理，DNA序列比对，文本聚类，XML结构索引等领域中。
1 后缀树
后缀树（此后简略为ST）是一个数据结构，把文档看作是一个由若干短语组成的字符串，而 不是看作一组词集〔1〕。一般算法中用来找出重复语句的传统ST结构都类似于Zamir 〔4〕中阐 述的结构。在最简单的版本中，后缀树算法创建了一个树型结构，每个后缀树的节点，表示 一个词并且根节点为空。这样每个从根节点出发的路径表示了一个语句，这个语句中的字词 是由路径遍历的相应的代表各个字词的结点来标识。后缀树是一个有根树，也是一个有向树 。例如，用下列语句来生成一个后缀树结构。
“can drive trucks safely. Men drive cars safely. Men can drive trucks.”
确定树的最大深度（这样最大语句长度就被确定了）m=3。下图1中所示的就是这种方法 生成的后缀树结构。.gif)
当生成了树形结构后，获得一个单一重复语句的最简单方法是用递归方法从根节点遍历到叶 节点。如果使用非递归执行来获得语句，那将是一个相对复杂的过程并且在相同复杂度的情 况下它不能保证我们能得到更好的效率，因为它取决于目前的编译执行器的执行效率。
一般的，在后缀树最外层描述一个句子的最后一个词的节点中常给出一个句子出现的频率。 在一个代表特定语句的节点集合中，这个节点常常位于一个后缀树结构的底层，这里我们常 把根节点作为一棵树的顶层。
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)
}
每个后缀树节点表示输入文集的一个字词，并且它们平行生成一个对应哈希表的接口。这样 如果在一个后缀树中更深层的节点是重复的话，我们能减少总的存储空间。节点同样包含了 信息，比如这个语句在输入文集中出现的次数，并且它提供了一个关于子节点的列表（如图 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）。
2 重复序列
关于重复序列，早在Justeson,Katz〔5〕和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的第一部分）。这个词表被分类并且只有那些在 文中的不同地方出现了两次或多次的词才能被保留下来。其他的词被移除（见图6的第二部 分）。接下来，相同的副本词被移除，原始词累加（见图6的第三部分）。其余的所有句子 的子句在第四部分中累加，第五部分中做的处理和第三部分相同。最后，新提取出来的序列 添加到重复序列表中，即图6中的第六部分。整个的处理过程对倒排索引中的其他词进行同 样的处理。例如在处理‘construct’时，就能找到语句‘construct psychology’。理论 上来讲，重复序列的最大长度可以是整个文集的长度的一半。但是，更加具有可行性的是将 重复序列的最大长度限定在一个合理的范围内，在本例中就将其设定为了3。大于这个限制 的序列在处理中将被忽略。
2.2 复杂度
算法中的每一步时间复杂度已在伪代码中标注了出来。如图5中所示，其中N是文本中的字数 ，K是文本中原始词的关键码值的字数（如，哈希表中的项），V是文本中的一个词出现的平 均次数。由这三个变量表示的整个算法的时间复杂度是：
O(N+K(VlogV+V)) (1)
又，V=N/K。于是，代入（1）得到：
O(N+K((N/K)log(N/K)+N/K)) (2)
O(N+N+Nlog(N+K)) (3)
特别的，如果K=N，即文中每个词都不相同，公式简化为O（N）。但当K趋近于logN时， 如图7所示，总的时间复杂度是上线性的，即
O(NlogN)[JY](4)
接下来再来考察空间复杂度，我们得到内存中的标记化文本的空间复杂度是O(N)，词的出现 次数的哈希表，例如，倒排索引的空间复杂度是O(N)，一个词在文本中总的出现次数不可能 大于N，并且序列表的空间复杂度是O(N)。这样，总空间复杂度我们得到O(N)。这样我们得 到结论，对于抽取出现在上面的重复序列在时间上是上线性的，在空间上是线性的。
3 结果分析
在五个长度为大约1MB到30MB的不同文本上运行这两个算法，这些文本中字词的总数大 致为几百万个。统计了字句最大长度为3，4和5的句子，并且统计了每个算法的时间和 空间复杂度。在每个文本运行这两种算法得到的抽取重复词大致相同。图7中的曲线证实了 我们对于算法的复杂度的理论假定。ST算法在时间和空间上都是线性的，而RS算法在时间 和空间复杂度上则是上线性的〔8〕。ST算法的空间消耗大致是RS算法空间消耗的两 倍。
两个算法的运行环境都是 C#，使用.NET Framework1.1编译实现 AMD Opteron 1.6GHz 2GB RAM。
对具有30MB大小的英文文档进行了实验。两种不同方法的时间和空间复杂度分别如下所示：
4 总结
文中对重复词抽取的两种算法进行了阐述，并将两者运行实现。通过对实验结果的分 析，比较了二者的性能以及时间和空间复杂度。重复词的抽取技术在当今生物、地理信息、 搜索引擎、信息检索领域都有越来越广泛的应用。两种算法的实验结果看出这两种算法对 于处理大型文本语言是一个基础性的工具。在重复词抽取和去重问题上将会有更加广泛的应 用。对文本挖掘领域，网页去重问题，垃圾邮件过滤，文本聚类〔7〕中都将有更加 广泛的意义。根据本文实验结果，用户可以根据不同文档的时间和空间复杂度要求，来选择 两种算法之一。这两种算法对大型文档的重复词提取都有着广泛应用和重要的意义。接下来 的工作对重复抽取还可以从循环子序列入手，进一步研究重复序列简化模式的提取和检测过 程。
［参考文献］
［1］ Grolmus P., Hynek J., Jezek K.: User Profile Identification Based On Text Mining［C］. Proc. Of 6th Int. Conf. ISIM"03, MARQ Ostrava, pp. 109-118, I SBN 80-85988-84-4, 2003.
［2］ Debar H ，et a1．Fixed vs．variable-length patterns for detecting su spicious process．In J．J．Quisquater，Y．De swarte，C．Meadows，D．Gollmann．ed s［C］. Proc．of the 1998 ESORICS Conference，hum-ber 1485 in LNCS，sep．1998．1 -16.
［3］ Han J., Kamber M.: Data Mining: Concepts and Techniques［M］.Morgan Kaufmann Publishers, 550 pages. ISBN 1-55860-489-8, August 2000.
［4］ Zamir O., Etzioni O.: Web document clustering: A feasibility demonst ration［C］.In Proceedings of the 21st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, Australia, Aug. 24-28 .
［5］ Justeson J., Katz M.: "Technical terminology: some linguistic proper ties and an algorithm for identification in text", Natural Language Engineering ［J］. Vol.1, No.1.pp.9-27,1995.
［6］ 林春燕，朱东华，等．科学文献的模糊聚类算法［J］．计算机应用．2004,24 (11)：66～67.
［7］ 林建敏，谢康林，等．基于PAT-array和模糊聚类的文本聚类方法［J］．计算 机工程2004,30(12)：126～127.
［8］ 吕爱琴,田玉敏,朱明华．基于MATLAB的OFDM系统仿真及性能分析［J］ ．计 算机仿真, 2005,(10).