Algorithm 版 (精华区)

发信人: AA (积极的人生、美好的人生), 信区: Algorithm
标  题: 中文全文信息检索系统中索引项技术及分词系统的实现
发信站: 哈工大紫丁香 (2002年05月23日19:42:35 星期四), 站内信件


ou还要贴贴贴。。。1 引言

在全文信息检索系统中，索引项的选择是一个基本的，也是非常重要的问题。对
输入的文档及用户查询要做的第一件事就是将它们分解为索引项的集合，然后才
有可能计算出查询与文档的相关度。在英文的全文信息检索系统中，将查询及文
档分解为索引项集合是件非常简单的事因为通常选用词为索引项, 而英文中词与
词之间存在分隔符（如空格）。对中文全文信息检索系统来说将查询及文档分解
为索引项集合就复杂些。首先要确定以什么单位为索引项，是以字，词还是短语
为索引项？现有的研究中大部份认为应以词为索引项。这是因为首先以词为单位
比较符合人的自然思维习惯，其次以词为索引项就可以借用英文全文检索系统中
已有的理论及方法。

以词为索引项，就要进行分词，也就是将由汉字组成的连续字符串分解为词的集
合，要进行正确的分词不是一件十分容易的事，首先在中文中字与之间，词与词
之间是不存在分隔符的，因此分词一般都要借助词典来进行，而中文的构词非常
灵活，词的数目几乎是无限的，因此要构造完备的词典是不可能的。为了克服以
词为索引项所带来的困难，人们提出了一些别的方法如以字为索引项，以二元，
三元语法为索引项等。

本文首先对各种类型的索引项技术作简单介绍，分析它们应用于中文检索中的优
缺点，然后着重讨论以词为索引项时的分词系统的设计及实现。



2 索引项及中文文本的表示方式

2.1 字

使用字为索引项是最简单的方法，将文本分解为索引项时非常容易实现。按照GB
2312的规定共有6763个汉字。这样索引集合就非常小，最大不会超过6763。在这
一点上与其它索引项技术(如词，N元语法)相比优点是非明显的。但以字为索引单
位也有其明显的缺点。首先是匹配的准确性不高，例如用户的查询为 "识别"，而
某文档中存在 "你是否还认别的人?" 这样一句话。则基于字的检索方法则会认为
该查询与文档是相关的。其次在中文中同一概念可以有多种表达方式如 "中文"，
"汉语"，"国语"。基于字的检索方法是无法处理这类问题的。

2.2 n元语法

在全文检索中常用的为二元及三元语。二元语法的思想为将文本中所有相邻汉字
均作为索引项，这样前一个索引项的后一个字与下一索引项头个字是相同的。例
如有一个字符串C1C2C3C4C5，则由它生成的索引项为C1C2，C2C3，C3C4，C4C5。
三元语法的思想与二元语法相同，差别仅为三元语法的索引项由三个字构成，例
如对上面的字符串由其生成的三元语法索引项为C1C2C3，C2C3C4，C3C4C5。

同样n元法的优点为将文本分解为索引项集合是十分容易的。但其索引空间是十分
巨大的。使用n元语法同样也会使系统无法利用语言学知识。

2.3 词

目前大多数研究者认为中文全文检索也应以词为索引单位。也就是索引项应该为
中文的词。这样做的好处是十分明显的。首先符合人的习惯，有利于提高查询的
准确性，也便于系统利用语言学知识。如果要进一步设计跨语种查询系统则非要
以词为索引项不可。但使用词为索引项则应先解决好分词问题。



3. 一种混合型正向最大匹配算法

中文分词问题的研究己有二十多年历吏。其间己提出了多种分词算法。总的来说
这些算法可分为四大类。第一类为基于词典的机械分词算法。第二类为基于统计
的分词算法。第三类为第一类和第二类的混合型分词算法。第四类为基于知识的
分词专家系统。

但各种分词算法均有其适用领域，针对全文检索中文档数量大，要求速度快的特
点。我们设计了一个混合型正向最大匹配算法，该算法可利用规则及字频信息来
处理分词中的歧义并使用了三词块方法[1]。为加快分词过程中词的查找速度，按
首字索引结构对词典进行了组织。

3.1 三词块及处理歧义的规则

三词块是一种处理分词歧义的方法。分词中遇到歧义时（假设有一字符串C1C2C3
C4C5C6，当前处理到汉字C1，且C1为词C1C2也为词），则向前多找两个词，这种
由三个词组成的串称之为三词块。处理中我们将找出所有可能的三词块并且认为
具有最大长度的三词块是最有可能的分词。

假设有字符串C1C2C3C4C5C6，且C1,C1C2均为词并有如下一些可能的三词块。

1 C1 C2 C3C4

2 C1C2 C3C4 C5

3 C1C2 C3C4 C5C6

具有最大长度的词块为第三个。这样我们就认为第三个词块中的C1C2为正确的分
法。取其为词。从C3外再次开始进行分词，一直到字符串结束。

我们所设计的分词算法以正向最大匹配算法为框架。分词过程中遇到歧义时则应
用下例规则加以解决。

规则1

具有最大长度的词块的第一个词为正确分词。

规则2

如具有最大长度的词块不唯一则寻找具有最小词长变化的三词块。该规则的隐含
假设为在文档中词长是均匀分布的。

例如: 1 研究 生命 的 起源

2 研究生 命 的 起源

按规则选取块1中的"研究"为正确分词。

规则3

当具有最大长度的词块不唯一并且有相同的词长变化则具最大平均词的块中的第
一个词为正确分词。该规则的隐含假设为遇到多字词的概率大于遇到一字词的概
率。该规则仅当某些词块由一个或二个词构成时才有用。

规则4

当前面规则均不能确定选取那词块时，则分别计算各块中一字词的词频和，取词
频和最大的词块。

3.2 词典的组织及词的查找

整个词典由12万个词条信息构成。词典组织结构为首字索引结构，其示意图如下

词典由两部份组成，一部份为索引部份，另一部份则为词典正文。索引部份由字
，字频，指针组成。其中指针指向以该字为首字的所有词的首地址。正文部份为
词条。词条按其长短从短向长的顺序存放。词典采取这种组织方式是为了加快词
的查找速度。



4 结束语

本文介绍了一种混合型分词算法。为解决分词歧义问题引入了四条规则。在分词
中遇到歧义时则通过生成三词块并引用规则来解决。文中提出的分词算法已在一
全文检索系统中进行了实际应用。



  
--
                人世间的事谁也无法掌握
                  该执著的  永不怨悔
                  改舍去的  不在牵挂
                  改珍惜的  好好把握

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: NLPCenter.hit.edu.cn]