《网络信息检索》课件第4章

第4章网页文本处理和索引4.1文本的特性4.2网页信息的特征4.3网页去噪4.4文本处理4.5索引4.6小结思考题

4.1文本的特性

一般来讲，文本由有限的字母符号构成[1]。它既可以表示为一个字符串，或表示为一组词的集合，也可以用一系列的语言单元如名词、短语等来表示。

文本里面含有多少信息量？和哪些因素有关？澄清这些问题将有助于对文本的有效处理。例如，在某段文本中的大部分词语都是高频词，那么可能这段文本携带的信息就很少。研究文本特征要着重考虑：不同词的频率是怎样分布的？随着文档集的增长，词汇表的增长情况如何？这些现象直接影响检索系统对文本的处理和信息检索的效果。4.1.1信息熵

信息是个很抽象的概念。我们常常说信息很多，或者信息较少，但却很难说清楚信息到底有多少。比如一本50万字的中文书到底有多少信息量。1948年香农提出了“信息熵”(informationentropy)的概念，才解决了对信息的量化度量问题。

一条信息的信息量大小和它的不确定性有直接的关系。比如说，要搞清楚一件非常非常不确定的事，或是一无所知的事情，就需要了解大量的信息。相反地，如果我们对某件事已经有了较多的了解，则不需要太多的信息就能把它搞清楚。所以，从这个角度上可以认为，信息量的度量就等于不确定性的多少。定义4-1

设词汇表中有σ个词，文本中每个词出现的频率是pi，那么该文本的熵可以定义为：(4-1)在这个公式中，词汇表中σ个词用二进制编码，所以熵的单位是比特。如果一个文本中只有一个词出现，其熵为0。

【例4-1】

设有词汇表{空格，a，b，e，o，r，s，u，y}，有如下两个文本T1=youareboy，T2=youareboys，求T1和T2的信息熵。解：

σ=9，列表求出两个文本中字符的频率如下：则根据公式(4-1)有：上面的例子中，两个文本只相差一个字母，文本的意义发生了较大的改变，相应的信息熵也发生了较显著的变化。可见，文本的信息量可以用熵来量化，熵的大小是对文本蕴涵的信息量的一个度量，依赖于每个词出现的概率(频率)。可以设想，如果一个字符在文本中频频出现，将导致熵值偏低，所携带的信息量也较少。4.1.2统计定律

为了更好地处理文本，要掌握文本的一些统计规律。本节将讨论Zipf定律和Heaps定律，分别研究不同的词在文档中的分布规律及随着文档集的增长而引起的词汇表的增长情况。

1.Zipf定律

Zipf定律，也称齐普夫定律，最初由G.K.Zipf提出[2]。齐普夫定律描述为：如果将词汇表中的词按照出现的频率由高到低排序，那么某个词出现的频率与该词所对应的序号之间有如下的简单关系：(4-2)式中：p(r)表示某个词出现的频率；r表示该词在按词频降序排列的词汇表中所对应的序号。在某种具体的分布中，α是一个正的常数，称为Zipf指数，它的大小仅取决于所描绘的词汇的具体分布，与其他参数无关。在英语中，a≈1，这时，上面的公式可以改写成：

p(r)×r=k

(4-3)

式中：k为常数。在英文中，使用频率最高的词“the”的使用频率约为1，排在第二位的“of”的使用频率约为1/2，前者的使用频率是后者的2倍。

【例4-2】

有一个英语文档包含10万个单词，假设Zipf常数k＝0.1，求出现了50次的单词，在排序词汇表中排名第几？解：再根据p(r)×r=k，得到：所以，出现50次的单词在单词表中排名序号为200。

上面这个例子中，排名第一的单词出现次数是：排名第二的单词出现次数是5000。可见，经常使用的单词在词汇表中占的比例不大。大部分词汇的使用频率很低，即很少被使用。这就是著名的“重尾分布(LongTailDistribution)”，如图4-1所示。图4-1文本词汇的重尾分布图可能会出现这样的情况，即有多个词出现的频率相同。假定rf是这些词中排位最后的那个词的序号，那么，有rf个词出现f次或多于f次，而rf+1个词出现f+1次或多于f+1次，这样可以算出仅出现了f次的单词个数：如果排在末尾(序号最高)的单词只出现了一次，那么它的排名序号为r=kN/1，仅出现了一次的单词个数为I1=kN/2。这说明：如果k趋近1，则几乎有一半的单词只出现过一次。

【例4-3】

有一个英语单词表，包含单词10万个，假设Zipf常数k＝0.1，求出现了50次的词有多少个？

解：根据公式(4-4)，得到：所以，约有4个单词出现了50次。对公式(4-2)两边取对数，为了用等号，补一个常数，得到：logp(r)=C－αlogr，令X=logr,Y(X)=logp(r)，则得到公式(4-5)：Y(X)=C－αX(4-5)可见，如果在对数坐标系里，则Zipf定律可以用一条直线表示，由于斜率是负数，故这条线是下降的。人们对许多文档集(Corpus)做了实验，证实了是吻合Zipf定律的[3-4]。图4-2显示了Brown文档的Zipf定律分布[3]。图4-2Brown文档集满足Zipf定律[3]

Zipf定律在现实世界中很常见。对Zipf定律可以解释为“最小努力原则”(principleofleasteffort)[2]，也就是说，我们的许多认识行为都有使精力支出最小化的倾向。例如人们倾向于用最少量的词来传递最大量的信息。Zipf定律给信息检索系统的设计带来了一些启示，如文本中频繁出现的词语往往是没有用的，它们对文本的内在含义表示没有实质性的意义，所以，可以删掉这部分词语，在不影响文本内容的情况下，大大减少了存储空间的使用。同时我们注意到，大多数词都是低频词(可能只出现一次)，词语之间的相关性很难分析，这对信息检索系统的设计是个不利的因素。因此，图4-1中处于上下限之间的阴影部分的词是比较有意义的，称为重要词汇(significantword)，这些词的描述能力可用一个分布(图中虚线)来表征。

2.Heaps定律

信息检索系统涉及到信息的存储，需要考虑预留存储空间的大小，而这和文档中的词汇量息息相关。一个文档里面究竟包含多少不同的单词？这个问题可以由Heaps定律[5]来问答。Heaps定律认为，一个具有n个单词的文本，它的词汇量(不同单词的数量)是：

V=Knβ=O(nβ)，0<β<1

(4-6)

其中，K和β是参数，随不同的文档而变化，典型取值通常是K在10~100之间，0<β<1。对TREC-2[6]文档集所做的实验表明[7-9]，TREC-2文档集满足Heaps定律，且β取值在0.4~0.6之间，如图4-3所示，其中ziff2、ap2、wsj2和fr2都是TREC-2文档集的子集(详见第6章的介绍)。图4-3TREC-2文档集满足Heaps定律[9]

Heaps定律描述了随着文档集的增长，词汇表的增长情况，总词库的大小随着语料库的增长而增长，这也决定了随着语料库规模的增长，词汇量并不是随之线性增长，而只是呈次线性(sublinear)增长，与文本大小的平方根成正比。这是一个可喜的现象，这也为后面的倒排索引的设计提供了理论依据。

4.2网页信息的特征

4.2.1网页结构

HTML是一种标记语言(MarkupLanguage)，其中定义了一套标签来刻画网页显示时的页面布局。因此，对于HTML网页最常用的结构表示方法是构造网页的标签树。

依据标签的作用将HTML标签分为两类：

(1)描述布局结构的标签，简称容器标签。在视觉上，网页是由若干内容块组成的，而内容块是由特定的标签规划出的。常用的容器标签有〈table〉、〈tr〉、〈td〉、〈p〉、〈div〉等等。

(2)描述显示特点的标签，简称描述标签。除了描述布局结构的标签外，HTML标准中还定义了一套标签来描述其包含的内容本身。比如〈b〉标签说明它所包含的内容要用粗体显示，〈img〉标签说明它包含的是一个图片等等。

另外还有一类标签，是超链接相关的标签。超链接是HTML文档区别于传统文本文档最明显的特点之一，表示网页之间的关系。因此，整理出超链接标签并作合理的分析可以挖掘出网页间的相关性信息。第3章介绍的〈a〉标签就是一种超链接标签。

因此，可以依据容器标签对网页进行划分，而其他类型的标签信息可以作为它所在的内容块的属性。文档对象模型(DOM，DocumentObjectModel)，是W3C制定的创建和处理XML和HTML文档结构和内容的标准接口规范[10]。DOM使得用户可以访问页面上的标准组件包括元素(element)、样式表(stylesheet)、脚本(script)等并处理它们。DOM可将整个HTML文档展现为内存中的一棵树状结构，DOM树是一种标签树，其每个节点是一个对象，其根节点为document对象，每个元素、属性都是树上的一个节点。DOM模型不仅描述了文档的结构，还定义了节点对象的行为，利用对象的方法和属性，可以方便地访问、修改、添加和删除DOM树的节点和内容。

DOM实际上有两种，HTMLDOM和XMLDOM。HTMLDOM是一种特殊的DOM，它仅支持使用getElementById()和getElementsByTagName()两种方法来进行查询，而XMLDOM则可以与XPathAPI相结合，基于正则表达式来进行查询。

HTMLDOM中常用的节点属性和方法如表4-1和4-2所示。

【例4-4】

图4-4是DOM树的一个例子。左边是HTML代码，右边是对应的DOM树。图4-4HTML代码转换为DOM树4.2.2网页类型

根据网页承载内容模式的不同，网页可以分为两大类：主题型网页(TopicPage)和导航型网页(NavigationPage)。导航型网页是通过锚文本和超链接辅助用户更好地浏览其网站内容，内容以链接为主，没有具体主题。例如，一些门户网站的首页，这类网页上分布着种类繁多的信息，并没有突出一个主题的整段文字内容，图4-5(a)所示的新浪网首页()就是典型的导航型网页。主题型网页是指网页中包含关于某个主题的整段的文字内容，如图4-5(b)所示的一篇新闻网页，图中框内的内容就是新闻内容。

由于这两种网页包含的信息模式有很大的区别，因此，它们的信息提取模式也有很大的区别。(a)导航型网页(b)主题型网页图4-5网页类型示例

4.3网页去噪

Web网页通常包含两部分内容，一部分内容体现的是网页的主题信息，比如新闻网页中的新闻部分，称之为“主题”内容。另一部分则是与主题内容无关的导航条、广告信息、版权信息以及调查问卷等内容，称之为“噪音”内容，或网页噪声。

噪音内容会导致检索到的网页常常不包含用户需要的相关内容，如果不去除原始网页中的噪音内容，检索系统必然对噪音内容也建立索引，从而导致仅仅因为查询词在某网页的噪音内容中出现，而把该网页作为结果返回，而网页的主题内容可能和这个查询词完全无关。可以看出，噪音内容不仅使索引结构的规模变大，而且还导致了检索准确性的下降。在视觉上，一张网页的页面可以划分为若干个区域，每个区域都称为一个内容块(block)。这些内容块中，有的包含主题内容，有的则包含着噪音内容。通常，一个内容块中的内容是紧密相关的，这就意味着可以以内容块为单位对网页中的内容进行取舍。基于这样的分析，网页去噪过程就是保留网页中包含主题内容的块而去掉包含噪音内容的块。

由于网页结构的复杂性和多样性，网页去噪方法很多，适用性也各不相同，以下介绍两种基本的方法。4.3.1基于网页结构的方法

基于网页结构的方法，是将一个网页表示为一个标签树或DOM树，然后依据一些启发式规则，将网页中和主题相关的信息提取出来。

例如通过观察某些网站的主题型网页，可以发现主题型网页的正文部分的标签数与非正文区域相比要少而稀疏。为了描述网页中不同区域的标签和链接的分布情况，可以分别通过每一对容器型标签中所包括的标签数与总文本数的比和锚文本数与总文本数的比，来说明网页中不同区域标签和锚文本的稠密度。由于一般主题型网页的正文部分的标签密度(标签数与总文本数的比)和锚文本密度(锚文本数与总文本数的比)比较稀疏，而非正文部分的标签密度和锚文本密度比较稠密，则可以定义启发式规则，通过判断容器型标签中标签密度和锚文本密度来区别正文信息和非正文信息。李晓明等人[11]

提出了一种HTML网页净化与元数据提取的方法，这种方法可以从一个HTML文档中自动提取网页的一些主要元素，包括网页标识、网页类型、内容类别、标题、关键词、摘要、正文、相关链接等信息，生成一个包含这些信息元素的网页表示模型，称为DocView模型。整个网页去噪过程可以分为两个步骤：网页内容的结构化表示和网页内容块的取舍。下面具体描述该方法。

1.网页的结构化表示

HTML是一种标记语言(MarkupLanguage)，其中定义了一套标签来刻画网页显示时的页面布局。因此，对于HTML网页最常用的结构表示方法是构造网页的标签树。

网页去噪是以内容块为单位进行保留和删除的，因此，可以依据容器标签来构造标签树框架，而把标签树中每个节点包含的其他类型的标签信息(包括超链接标签、图片标签等)作为它所在的内容块的属性，这样就构造了一棵标签树，对其信息作适当的分析、整理就可以得到网页去噪过程中需要的一些描述信息。例如，依据内容块中词项数与图片数和超链接数的比值可以为每个内容块设定一个类型，分为主题(topic)、超链接(hub)和图片(pic)3种。如果内容块中词项数与图片数比值小于某个阈值，该内容块就是pic类型；如果内容块中作为链接导航文字(锚文本)出现的词项数与该块中总词项数的比值小于某个阈值，该内容块就是topic类型，否则就是hub类型。这样，标签树中每个节点都有类型和属性集两组描述性信息，以及超链接集和重要标签集等数据信息。

图4-5显示了一棵完整的标签树。其中link_list表示该内容块中的超链接集合，weighty_tag_list表示该内容块中的重要标签集合。

【例4-5】

根据图4-6的网页内容，构造它对应的标签树。图4-6HTML树的结构示意图[11]为了体现重要信息标签中内容的重要性，要对重要信息标签中的内容进行加权。但重要信息标签中包含的并非都是重要内容，其中的噪音信息非常多，例如：“Tel”、“Fax”、“联系电话”、“传真”、“广告服务”、“前一页”等。因此，简单地对重要信息标签中的内容加权是不合理的，整理噪音词集合并据此集合对重要信息标签中的内容进行过滤，再对过滤后的真实重要内容加权可避免噪音的扩大化。由于网页中的标签结构是对页面布局的描述，因此不难得到这样的结论：如果某个内容块中存在真实重要信息，那么这个内容块的重要性也相对较高；如果一个内容块的重要性较高，那么这个内容块的外层嵌套块的重要性也相对较高。基于这个结论，可以给网页中每个内容块赋予一个权值，用来表示这个内容块的重要性，并采用一种内容块权值的传递规则，称为权值传递规则。由于内容块与标签树节点是一一对应的关系，以下对权值传递规则的描述统一使用标签树节点而不使用内容块。

权值传递规则如下：

(1)标签树中每个节点的初始权值为1。

(2)每个重要信息标签都有一个影响因子。如果标签树某个叶子节点中存在重要信息标签并且重要标签中的内容是真实重要内容，那么累加重要信息标签的影响因子，得到的和就是该叶子节点的影响因子。没有出现重要标签的节点的影响因子为1。

(3)对于每一个叶子节点，如果影响因子为λ且λ>1，则该叶子节点的权值变为当前值的λ倍，它的父节点以及父节点下的其他子树中的节点均变为当前值的倍，然后以该父节点为变化源，按照上述规则再向外扩展一次。每一次扩展过程中，遇到父节点为〈body〉或父节点权值超过预定上限就结束整个权值传递过程。

【例4-6】

对如图4-7(a)中的标签树，如果阴影节点的影响因子为3，请为每个节点标注重要性权值。

先将标签树中每个节点的初始权值设为1，根据权值传递规则，得到如图4-7所示的内容块权值传递过程。图4-7内容块权值传递过程[11]

2.网页内容块的取舍

网页内容块的提取主要以一组启发式规则为指导，先提取网页的正文信息，再以正文信息为基础，提取DocView模型中的其他要素(包括内容类别、标题、关键词、摘要、相关链接)。下面按照各个要素的生成过程分别描述有主题网页的信息提取过程。

(1)正文。在有主题网页中，如果一个内容块是topic类型的，则该内容块中的内容为正文的一部分。按照这个规则，深度遍历标签树并依次记录topic类型的内容块，就得到该网页的正文，也就是该网页的主题内容。

(2)关键词。关键词选取的依据是特征项的权值。对标签树中的每个正文块，如果该块中存在重要信息标签，则检查重要信息标签中的内容是否在噪音词集合中出现；如果不在噪音词集合中出现，将重要信息标签的影响因子累加到该内容块的影响因子上去；如果该内容块的影响因子大于1，则按权值传递策略在标签树中传递权值。得到每个结点都有权值的标签树后，再按公式(4-7)计算各个特征项的权值。(4-7)式中：BWeightj表示内容块j的权值，其值是由一个内容块中的重要标签来决定的；BN表示网页中内容块的总数；n表示网页中不同关键词的总数；BTfij表示关键词i出现在内容块j中的词频。得到特征项权值后，根据所有特征项权值的算术平均值avg和预先定义的阈值β，选取权值大于avg×β的特征项作为该网页的关键词。

(3)内容类别。内容类别是通过对正文分类得到的。

(4)标题。一般来说，网页的标题由〈title〉标签标识，但针对没有标题或者使用如“UntitledDocument”、“Newpage”、“欢迎访问”等无描述能力标题的网页，可从关键词中选取权值最高的作为网页的新标题。

(5)摘要。通过识别文章中不同的段落，扫描到一些关键词，就可以得到能够模拟读者浏览文章过程的摘要信息。

(6)相关链接。对于超链接的选取，可以采用两种策略，一种是基于锚文本的策略，即通过比较每个hub类型内容块中锚文本集合与正文的相似度来决定该块中链接的取舍；另一种是基于分类的策略，通过判断一个hub类型内容块中某个超链接指向的网页与本网页正文的类别是否相同，来决定该块中所有链接的内容相关性。第二种方法比第一种方法要准确，但时间开销很大。

对于hub网页和图片网页，一般是将网页中间区域的内容块作为网页的正文，对周围的内容块则通过与正文比较相似性来决定取舍。4.3.2基于模板的方法

Web规模庞大，很多网站每天都有大量新生成的网页，网站管理者不可能针对每一个新网页进行重新的排版布局。一般的方法是先开发出一套网页模板(template)，然后将要发布的信息填入这些模板，这样可大大简化网站编辑者的工作量，并可使其精力集中于网页内容的编辑。

图4-8为同一模板网页对比图。图4-8同一模板网页对比图从图4-8可以看出网站模板的一些共性：

(1)URL具有很大的相似性，通常是在同一个URL目录中；

(2)版面的编辑格式基本相同，只是内容不同；

(3)版面布局基本一致。

基于模板的方法则是利用这种性质，从一组网页中提取出相同的模板，而后利用这些模板从网页中抽取有用的信息。下面介绍一个基于模板匹配的主题信息提取算法DSE(Data-richSectionExtraction)[12]。DSE的启发思想是，同一个网站的页面结构都是相似甚至是相同的。广告和导航信息等会在页面重复出现，因此通过选择一个模板页面，将待抽取的目标页面和模板页面进行匹配，去掉相同部分(广告和导航信息等)，剩下的就是主题内容，进而达到提取网页主题内容的目的。在已经确定模板网页的前提下，DSE算法可以分为以下两个步骤：

(1)构建目标页面和模板页面的DOM树。HTML文档通过JTidy等工具解析后，可以转化为DOM树，要除去不包含结构信息的标签，如“font”、“h1”等，减少匹配计算量，标签属性只考虑“A”的“href”和“IMG”的“src”属性。

(2)匹配目标页面和模板页面的文档树，除去相同部分，提取主题。采用深度优先策略，从根节点到叶节点，逐一比较目标页面和模板页面的节点，删去相同节点。比较两个节点：如果节点是内节点，并且相同，则从右到左匹配其子节点；如果是叶节点，并且相同，则删除该节点；节点不同则返回父节点，继续比较其他兄弟节点；如果节点的子节点都被删除，则也删除此节点。

【例4-7】

以图4-9为例，TreeA是目标网页的DOM树，TreeB是模板网页的DOM树。

具体匹配过程如下(用Same()函数表示两个节点是否相同，相同为1，否则为0)：

(1)两棵树根节点Same(table，table)=1，进而进入其子节点进行匹配。

(2)第一个子节点对Same(tr，tr)=1(见上图的箭头1)，所以再进入下一级子节点。

(3)Same(td，td)=1，同样，下一步再比较Same(a1，a1)=1，并且a1是叶子节点，所以删除(a1，a1)节点。返回a1的父节点td，进而用同样的方法匹配删除节点。图4-9DSE算法示意图[12]

(3)td的子节点全部被删除，进而删除此td节点，同样删除td的父节点tr。

(4)返回根节点table，匹配其下一个子节点table，Same(table，map)=0(箭头2所示)，再进一步比较Same(table，tr)=0(箭头3所示)，tr没有右兄弟节点，返回table节点。

(5)此时最左边的(tr，tr)已经被删掉。所以比较Same(tr，map)=0(箭头4所示)。

(6)比较Same(tr，tr)=1(箭头5所示)，同样的过程，到比较Same(u1，u1)=1，进而先比较Same(a5，a6)=0(箭头6所示)，再比较Same(a5，a5)=1(箭头7所示)，删掉(a5，a5)。

(7)返回(u1，u1)，进一步匹配其子节点，此时只剩下(a6，a6)，且Same(a6，a6)=1，删除(a6，a6)。

(8)返回(u1，u1)，其子节点为空，删除(u1，u1)。

(9)返回上一级节点td，其子节点a4没有节点可以跟其匹配删除，所以保留。进而td的子节点不为空，保留td，同样保留tr和table。最后结果如图4-9的第2行所示。网页去噪和信息提取是目前热门的研究领域。许多方法综合考虑网页结构和模板的特点，例如Lin等人[13]提出的去除网页中噪音内容的方法可以根据〈table〉等标签构造网页的标签树，并依据〈table〉标签将一张网页规划为相互嵌套的内容块；然后，对于使用同一个模板做出的网页集，找出在该网页集中反复出现的内容，作为冗余内容，而在该网页集中出现较少的内容块就是有效信息块。基于视觉的网页分块算法VIPS(Vision-basedPageSegmentation)[14]则是利用页面中各元素的布局信息对页面进行划分，保留页面中间区域，而其他区域则认为是噪音。但由于网页中的视觉特征通常多样并且多变，所以造成算法实现较复杂。

由于网页结构千变万化，所以，应针对需要处理的网页的具体情况选择合适的方法，有时还需针对网站的特点加以改进，才能适用。

4.4文本处理

文本操作是指将网络爬虫搜集到的文本信息进行预处理，以便进行网络信息检索的下一个流程——索引处理。

文本预处理主要包括网页噪声去除、词汇分析、排除停用词和词干提取四个阶段。对经过噪声去除后得到的干净网页，要进行词汇分析，去除停用词，提取词干，最后得到一系列可以表达网页内容的关键词。关于词汇分析，中英文存在较大的区别，英文单词有空格分隔，易于识别，而中文文本以句子为自然分隔单位，要提取出词语来，需要复杂的分词技术。中文信息检索的相关技术在第9章介绍，本章重点介绍以英文文本为主的预处理技术。

文本处理的主要流程可以概括为如图4-10所示。图4-10HTML文档预处理流程网页经去噪后，便进入词汇分析及特征提取阶段，如图4-11所示，在这一阶段，主要完成：

(1)词汇分析：对数字、连字符、标点符号和字母的大小写进行处理，将文本分割成单词序列。

(2)排除停用词：过滤掉那些对检索来说作用不大且区分能力低的词。

(3)词干提取：把所有同根的词变成统一的词根形式。

(4)特征提取：选择可以作为关键词(索引词、索引项)的词或词组。4.4.1词汇分析

词汇分析(lexicalAnalysis)，就是把网页中的文本字符序列转换成为单词序列的过程。这些单词用来作为索引词的候选。例如，字符序列thehouseofthelord经过词汇分析后，可以得到单词序列：the、house、of、the、lord。因此词汇分析阶段的主要任务就是标识出文本中的单词。

在英文中，分割单词并不难，因为空格是英文单词的自然分割符。但是在词汇分析阶段，还有几种特殊的情况要处理：数字、连字符、标点符号和字母的大小写。对于数字来说，一般不作为索引词，因为如果没有上下文的联系，它们的含义是模糊不清的。例如，用户要查询1994年到2005年间有关信息检索方面的网页，查询中的数字1994和2005可能导致检索出只涉及这两年的网页，而遗漏这两年之间的重要网页，所以，有时候可忽略查询中的数字信息。但对于电话号码，信用卡号等数字序列，如果忽略数字，则可能查询到无意义的网页，在这种情况下，数字应该作为关键词。因此，凡与上下文密切相关的数字，我们用其作关键词，其他情况下，数字一般被忽略。对于连字符来说，也有两难的情况，一般是把连字符连接的单词分解开。例如，把“state-of-the-art”分解为“stateoftheart”。但是，有些带有连字符的单词本身是一个完整的单词，如“gilt-edged”。最恰当的方法是制定一个通用原则，指明特殊情况下的处理方法。

在词汇分析过程中，标点符号一般是要被完全去除的，但有些标点符号是单词的组成部分，去掉对检索效果的影响比较大，这种情况下又要慎重考虑是否删除标点。对于字母的大小写来说，词汇分析时通常把所有文本都转化为大写或小写的字母，但也有特殊情况，有时大小写转换会丢失语义，例如“Bank”和“bank”的语义是不同的。对这些情况，要特殊处理。

Fox在文献“Lexicalanalysisandstoplists”[15]中对词汇分析作了详细介绍。但正如Fox指出的，这些文本操作的实施没有困难，但由于对检索有深刻的影响，所以必须仔细地考虑每一种文本操作，特别是一些特殊情形下的处理。现在的很多搜索引擎都回避了文本操作，避免了文本操作带来的语义损失或误解，也简化了用户对检索任务的理解，不失为一种可取的方法。4.4.2排除停用词

出现频率很高的单词往往不具有很好的文档区分能力，比如“the”，几乎所有的文档中都频频出现这个单词，那么如果用这样的单词作关键字来检索网页的话，可能会检索到大量无用的网页，所检索出的网页中的绝大部分都不是用户想要的。在网页或文档集合中出现频率高于80%的单词通常被称为停用词(stopwords)，它们对文档的含义没有任何意义，需要被过滤、屏蔽掉。通常，冠词、介词、连词都属于停用词。英文停用词例子：a，about，above，across，after，again，against，all，almost，alone，along，already，also，although，always，among，an，and，another，any，anybody，anyone，anything，anywhere，are，area，areas，around，as，ask，asked，asking，asks，at，away，b，back，backed，backing，backs，be，because，became，and，an，by，from，of，the，with…

中文停用词例子：一、不、了、也、就、人、都、所、要、会、很、大、能、着、还、可以、最、来、所、可、为、又、将、更、才、已……

删除停用词对于信息检索来说具有重要的意义，一方面可以大大缩小索引空间，另一方面可以提高检索准确度。一般来说，停用词不仅仅有冠词、介词和连词，一些动词、副词和形容词也可能是停用词，信息检索系统可以设置一个停用词表用于过滤停用词。

虽然排除停用词可以缩小索引结构的大小，减少倒排文档的长度，但也可能会降低系统的召回率(查全率)，使得用户不能查到自己需要的网页。例如，如果用户要查找包括“tobeornottobe”的网页，排除停用词后，可能只留下了“be”，这样就很难分辨哪个文档中包含这个特定的短语，用户可能得到的是一些莫名其妙的文档。针对这个问题，有的搜索引擎会直接向用户说明系统认为用户的检索词中哪些可能是停用词，将被排除不做处理，如果用户认为有误，则可以考虑用引号将这些查询词转换为短语，这样就不会被系统排除了。4.4.3词干提取

在英文单词中，一个词干(stem)可以派生出若干的同义词，例如，单词“search”是“searched”“searching”“searches”的词干。可见，词干是单词的一部分，是去除单词的前缀和后缀后剩下的部分。词干提取就是把同词干同义的不同词语中的相同部分提取出来。使用了词干提取的检索系统，即使用

户输入的查询关键字不存在于相关文档中，也可以根据由该关键字提取到的词干为用户查找到包含含义相近的变形单词的文档。词干提取可以大大减少单词词项的数量，可以为用户查找到包含相似词的文档，从而实现改进检索性能的目的，即使如此，词干提取还是有它的缺点的，首先，词干的截取正确率不可能达到100%，可能会有误截，造成词义的改变，影响查询的结果。例如，Medical和Media被识别为Med*，并被认为是意义相近的，那就错了，查询medical的用户会得到media的不相关结果。

Frakes提出了4种词干提取方法[16]：查表法、词缀删除算法、后继变化数和N个字符列。其中查表法是最简单的一种方法，只需要创建一个单词和词干的对应表，通过该表查找单词的对应词干，但是这种方法需要很大的存储空间，所以没有太大的实际应用意义。词缀删除算法主要将单词的前缀和(或)后缀删除，只留下词干部分。后继变化数以词素边界的确定为基础，使用结构化语言学的知识，比去除词缀更加复杂。N个字符列基于二元词和三元词的确定，更像是语词的聚类过程。应用最多的，也最实际的词干提取方法是去除词缀法。Porter提出的Porter算法[17]，是最著名的词缀去除方法。

Porter算法是基于规则的词干提取方法，每一步有一组上下文无关或有关的规则用来删除后缀，或者将其转换为其他形式。上下文无关规则主要根据后缀表(或基于规则集)删除单词的后缀，如：sses→ss，ies→i，s→NULL；上下文有关规则要考虑词的其他性质，例如：happily→happi→happy，则需要定义一个上下文敏感的转换规则：如果一个词根以i结尾，i前面是p，那么将i转换为y；又如，“(*v*)：ed→NULL，ing→NULL”规则的含义是把以ed(或ing)结尾的ed(或ing)后缀去掉，同时保证留下来的词根必须包含一个元音。

详细的Porter算法可以参见文献[1]的附录。4.4.4索引词选择

如果采用全文的表示，文本中的所有词都是索引词。但这些词并非全部有用，对无用词条建立索引将浪费系统的索引空间，而且影响系统的检索性能，因此并不一定对网页中出现的所有词条都建立索引，而是选择一些比较重要的词条来建立索引。选取索引词的过程叫做索引词选择。对于一些科技刊物的检索来说，一般都是由专家来选择索引词汇的，这种方法非常准确，但需要消耗大量的人力；另一种可选的方法是通过对文档的分析来自动选择索引词，这种方法可能没有第一种方法准确，但是可以由系统自动实现。系统自动选择索引词的方法很多。一种简单的方法是选择文本中的名词作为关键词，这可以通过自动消除文本中的动词、形容词、副词、连词、冠词和代词来实现，但这要求对词的词性有一定的了解。

根据图4-1，只有出现的词频落在一定区域内的词才具有一定的描述能力。因此可以通过计算词频、信息增益(InformationGain)或互信息量(MutualInformation)等方法来选择重要的词汇，这种方法也同时用在自动分类的特征选择上，将在第11章中介绍。

4.5索引

通过上述的文本预处理操作，可以得到一组关键词序列。现在面临的问题是如何组织这些关键词，以提供快速的检索。

如果需要搜索文件，并从中找到包含一些给定单词或词组的文件，最直观的方法是采用顺序搜索，即顺序地扫描文本，直到找到给定的单词或词组为止。但这种方法只适合于规模比较小，变化频繁，对实时性要求比较高的场合，当文本规模进一步扩大时,顺序搜索的时间就会长得让人无法忍受。

建立索引，可以减少查找的时间。网络信息是大规模的、稳定的或周期性变化的，建立和维护索引具有极其重要的意义。索引是信息检索系统的核心部分，它把原始数据用一种高效率的、便于查找的方式表示出来，极大地提高了搜索的速度。把文本的原始数据转换为一个能快速进行查询的格式，这个转换过程就是建立索引(indexing)，而这一过程的输出结果称为索引(index)。索引可以看成一个数据结构，它允许对储存在其中的单词进行快速随机访问。这个概念和一本书后面的关键词索引表非常相似，它能够帮助读者比较快地找到与关键词相关的内容的页码。比如，北京：12，34页；上海：3，77页；广州：78页等，那么读者很快可以定位北京相关的内容在12页和34页，上海相关的内容在3页和77页，广州相关的内容在78页。4.5.1Trie树

Trie树是一种重要的用于索引的基础数据结构，Trie的四个字母来源于英文单词retrieval，可见这个数据结构是为信息检索而设计的。Trie树是一种多分支树结构，是一种检索效率较高的数据结构。利用Trie树进行检索时，在每层中不需要顺序查找相应的字符，就可以直接定位到要找的节点。

Trie树按照字母顺序存储字符串，其节点表示字符串的公共前缀，节点之间用边来联系，节点和边共同构成树。按照字母顺序，在树的边上标记字符串集合中的一个字符。例如，对于字符串集合S＝｛alpha，beta，bear，beast，beat｝，那么存储S的Trie树如图4-11所示，图4-11(a)是原始的Trie树，而图4-11(b)是经过整理简化的Trie树，也称为Patricia树。Patricia树是Trie树的压缩表示，所有只有一个子节点的节点都和父节点合并。图4-11Trie树在Trie树中进行检索的过程为：从根节点出发，沿着相应的指针逐层向下，直到叶节点，若节点中的关键词和给定的查询相同，则检索成功，否则检索不成功。Trie树的查找和B＋树的查找类似，查找成功时走了一条从根到叶子节点的路径，例如在图4-8中，查找关键字beast的过程为：从根节点出发，经b(a，b分支)→a(a，t分支)→s(r，s，t分支)边，最后到达叶节点beast。在Trie树中，易于进行插入和删除，只是需要相应地增加和删除一些分支节点。

4.5.2后缀树

后缀树是一种基本的数据结构。后缀索引可以处理比较复杂的查询。

定义4-2后缀。假设字符串S=s1s2…sisi+1…sn，其中，si属于输入字符集，那么Si=sisi+1…sn是S从位置i

开始的后缀。

定义4-3

后缀树。一个有m个字符的串S，它的后缀树是一棵有根的有向树，共有m个叶子，分别标号为1到m。每一条边都用S的非空子串来表示。从任一节点出来的两条边，它们必须以不同的字符开始。从根节点到叶子节点i，顺序经过的树边的串联，恰好为S从i位置开始的后缀，即Si。图4-12是字符串bopomo的后缀树示意，其中虚线的部分表示省略了若干条边。图4-12字符串bopomo的后缀树示意对于文本来说，可以以索引词为单位进行后缀树的构建。

【例4-8】

文本“Thisisatext.Atexthasmanywords.Wordsaremadefromletters”，它可以用后缀树表示为图4-13所示。图4-13样例文本的后缀树从上面两个例子可以看出，后缀树也是一种Trie树数据结构，在Trie树上表示文本的所有后缀，指向后缀的指针存储在后缀树的叶节点上。构造好后缀树之后，就可通过遍历这棵树来做检索了。

后缀树结构的主要问题是存储空间问题。后缀数组[18]提供了与后缀树相同的功能，但其空间需求远小于后缀树。后缀数组就是按照字典的顺序排列并存储所有文本后缀指针的数组，如图4-14所示。因为每个被索引的后缀只存储一个指针，其空间需求几乎与倒排文件索引相同，空间开销是原文本的30%~40%[19]。图4-14样例文本的后缀数组对于大型的后缀数组，为了提高存取效率，可以在后缀数组之上，建立上部索引来加速存取。最简单的上部索引只是给出了后缀数组的外部入口，即在外部索引中存储了每个后缀的前若干个字符及其指针。在检索时，首先在上部索引中查找，然后定位到小范围的后缀数组，进行搜索，如图4-15所示。图4-15上部索引4.5.3签名档

签名档[20](signaturefile)是一种空间开销较低(占文本大小的10%~20%)的索引技术，它是基于散列变换(hashing)的面向单词的索引结构。

利用签名档进行索引，首先把文本划分为若干块，每个块有若干个单词；然后利用散列函数，为文本块中的每个单词分配一个签名；再将块中每个单词的签名进行逐位或(OR)操作，即可得到一个位掩码；最后，所有文本块的位掩码序列构成了文本的签名档。可以简单地把文本的签名档理解为所有文本块的位掩码序列。使用签名档进行检索的主要思想是：如果某个单词出现在一个文本块中，那么置于签名档中的所有位也会置于这个文本块的位掩码中，换言之，一个查询词的位掩码中的位，假如不出现在文本块的位掩码中，那么这个查询词也不会出现在文本块中。

【例4-9】

例4-8的文本“Thisisatext.Atexthasmanywords.Wordsaremadefromletters.”被分成4个文本块(如图4-13所示)，各单词的Hash值如表4-3所示，计算各文本块的掩码和文本的签名档。解：第二个文本块中包含两个索引词text和many，通过逐位OR操作，计算第二个文本块的位掩码：同理可计算得到其他文本块的位掩码。这4个块的位掩码构成了文本串的签名档，如图4-16所示。图4-16样例文本的签名档如果要检索词“text”，先找到这个单词的Hash值(000101)，并与所有文本块的位掩码进行比较，即执行逐位与(AND)操作，可以知道存在于第一个和第二个文本中。但如果新构造一个文档只由前两个文本块组成，输入检索词“letters”(100001)，发现其位掩码存在于第二个文本块中，这就发生错误了。也就是说，可能存在这种情况：即使某个单词不存在于文本块中，其全部相应的位也可能存在于文本的位掩码中，这种情况称为误检(falsedrop)。对于签名档的设计来说，应该在保证签名档尽可能短的情况下，确保误检的可能性降到最低。

签名档的最大优点是占用空间小，组织简单，更新和删除等的维护费用较小；签名档容易生成，插入费用低。但签名档搜索速度慢(尽管比全文扫描要快)，对于顺序文件，所有的签名都必须比较；另外去除误检需要昂贵的开销。4.5.4倒排文件

1．倒排文件概述

倒排文件(invertedfile)是一种面向单词的索引机制，可以支持一些复杂的检索文件，也可以提高检索的速度，是目前为止应用最为广泛的索引技术[21-23]，开放源码的全文索引引擎Lucene[24]采用的也是倒排文件。倒排文件有时候也被称为倒排索引、倒排表、倒排文档等，内涵大同小异。

倒排文件通常由两部分组成：

(1)词汇表(vocabulary)：包括文档集合中所有不同单词的一个向量，或者文本中所有不同单词的向量。

(2)事件表(occurrence)或称置入文件(postinglist)：对于词汇表中的每个单词，都有一个包含该单词的所有文档列表，通过文档号来标识，列表存储了该单词出现的文档号，以及单词在文档中的出现位置等。

如果我们只对一个文本文件进行索引，那么事件表中的指针可以是一维的，它指向对应的单词在该文本文件中所有出现的位置。例4-5的文本“Thisisatext.Atexthasmanywords.Wordsaremadefromletters”，假设以单字为单位来标识单词的位置，其倒排索引的词汇表和事件表如图4-17所示。图4-17样例文本的倒排索引示例

从上面的单文本倒排索引可以看出，词汇表中的单词按照一定的规则进行了排序，事件表里存储的是单词出现在文本中的位置，这些位置是以单字为基本单位的，有些单词在文本中多次出现，如“text”。在这个例子中，对“this”、“is”、“a”、“has”等停用词不做索引。

倒排索引的空间占用情况如何呢？实际上，词汇表所占用的空间是相当小的，根据Heaps定律，词汇表所占的空间可以用O(nβ)来表示，这里的n是文本大小，前面提过，β一般在0.4~0.5之间。例如，对于1GB的TREC-2文档集，词汇表的大小约5MB，而且通过词干提取法、停用词排除法等技术还可以进一步减小词汇表所占用的空间。但是事件表所占用的空间相对较大，由于在事件表结构中将涉及出现在文本中的每一个单词，要保存每个单词出现在文本中的每个位置，因此所占用空间可以用O(n)表示。事实上，即使不对停用词索引，事件表所耗费的空间开销也为文本大小的30%~40%[1]。为了减小所需要的存储空间，可以采用“块寻址”技术[8]。将文本分成若干个块，事件表指向单词所在块的位置，而不是单词所在文本中的精确位置。这样不仅可以减少指针的数量，而且还可以将出现在一个块中的同一单词的所有事件压缩为一个条目。例如，仍然使用上面的例子，假设将整句话分成4个文本块，倒排索引示意图如图4-18所示。图4-18使用块寻址的倒排索引示例上面的例子反映了块寻址倒排索引的优点，同一个块中多次出现的单词的指针合并为一个，如“words”，原来是33，40，采用块寻址技术后，合并为3了。但是采用块寻址技术也有缺点，比如，查询某个单词，只能定位到某个块，如果需要精确知道它在块中的位置，还必须遍历那个块。

采用块寻址技术，主要目的是节约空间，空间节约的程度跟块的划分密切相关。表4-4是不同寻址粒度下倒排索引所占空间的比较情况[1]。注意，表4-4的数据基于文档中的如下假设：单词粒度的倒排索引指针占4个字节；每个文档大小为10KB；块的大小独立于文本的大小，块指针占1个或2个字节；还假设停用词占全部单词的45%。

从表4-4的数据可以看出：块的数量(寻址粒度)直接影响着倒排索引占用的空间大小，对于大型文档集，随着粒度的逐渐粗放，占用空间呈显著减小的趋势，但对于中小型文档集，并不是寻址粒度越粗，占用空间越小，而是需要选取适当的粒度。

2．索引的建立及检索

由于待索引的文档集中通常包含多个文本，因此需要为多文本建立倒排索引文件。倒排索引的置入文件中还必须记录索引词在哪个文件的哪个位置出现。

【例4-10】

假设有一个中文文档集，包括4个文本，分别是：

T1=南边来了个哑巴，腰里别了个喇叭

T2=北边来了个喇嘛，手里提了个獭犸

T3=喇嘛回家炖獭犸

T4=哑巴嘀嘀哒哒吹喇叭

请使用单词级细粒度进行倒排索引。解：首先进行中文分词，去掉停用词，得到词汇表，再遍历文档，得到每个单词出现的文本编号及在文本中的位置。文本编号及单词位置见表4-5，倒排索引示意如图4-19所示。图4-19中的倒排索引词汇表已经去除了“了”、“个”等停用词。从图4-16可以看到，每个文本里的每个单词，对应地在事件表中有一个索引项，每个索引项不仅包括出现该单词的文本号，还包括单词在该文本中的具体位置(以单词为基本单位)，这些信息组合构成了子块(token)，每个子块用括号分隔。而粗粒度的索引则不需要定位到单词位置，事件表中只给出现该单词的文本号即可。

图4-19多文本的倒排索引(细粒度)在实际系统中，光记录文本号和词出现的位置往往是不够的。为了支持更准确的查询，需要在置入文件中存储更多的信息，包括索引词出现的词频，属于哪个段落，是否标题(或锚文本)，该词的显示方式(是否黑体，字体颜色)等。例如Lucene中就使用了域(field)的概念，用于表达信息所在位置，如在标题中，文章中或URL中。在建立索引中，该域信息也记录在词典文件中，每个关键词都有一个field信息，因为每个关键字一定属于一个或多个field。有了域的信息后，就可以支持基于域的查询。

基于倒排索引，可以进行检索。图4-20给出了一个简单的检索算法，利用向量空间模型对找到的文档进行逻辑处理和排序，返回排序后的文档集合。图4-20基于倒排索引的检索算法

3．倒排索引的性能

倒排索引的性能主要从以下两个方面来评估：

(1)时间代价：主要取决于词汇表的组织方式。词汇表文件通常较小且比较固定，对于未登录词和数词可以按字建立索引。

(2)空间代价：主要取决于对置入文件的压缩能力。置入文件的压缩能减少IO操作，也能提高部分时间性能。

因此，为了提高索引的性能，还需要考虑以下问题。

(1)词汇表的组织方式。在大规模文本中，词汇表是很大的，因此还需要为词汇表建立索引。词汇表文件的组织方式有哈希存储、字典顺序存储或树(Trie树、B树、二分树)结构等。①哈希(Hash)存储。根据给定的关键字，用哈希函数散列成一个整数，用该整数作为词汇的访问地址。例如：如果按字索引，那么可以直接用字的编码作为访问地址，对于2字节编码只需64K地址。这种方法的优点是实现简单，速度极快，关键在于找到一个好的散列函数，减少冲突的概率。

②按字母表顺序有序存储。把词汇按照字典顺序排列，词汇的查找采用二分查找。这种方法的优点是实现简单，词汇表体积小。但索引构建和检索的效率一般，因为对于插入的文档需要反复地调用排序和查找算法，排序的时间复杂度为NlogN，这里的N是词汇表大小。检索即二分查找，时间复杂度是logN。Lucene的词汇表即采用的这种方式，如图4-21所示。图4-21Lucene的词汇表③也可以采用Trie树、B树等查找树。例如可用Trie树为样例文本的倒排索引建立词汇表，如图4-22所示。图4-22样例文本的倒排索引的词汇表Trie树

Trie树的查找时间只跟词的长度有关，而与词表中词的个数无关，词表较大时才能体现出速度优势。

(2)置入文件的压缩。置入文件必须包含如下信息：当前词出现的文档号ID，以及在文档中的位置Pos。对置入文件通常采用差值压缩(d