1、第4章 网页文本处理和索引第4章 网页文本处理和索引4.1 文本的特性4.2 网页信息的特征4.3 网页去噪4.4 文本处理4.5 索引4.6 小结思考题第4章 网页文本处理和索引4.1 文本的特性文本的特性一般来讲，文本由有限的字母符号构成1。它既可以表示为一个字符串，或表示为一组词的集合，也可以用一系列的语言单元如名词、短语等来表示。文本里面含有多少信息量？和哪些因素有关？澄清这些问题将有助于对文本的有效处理。例如，在某段文本中的大部分词语都是高频词，那么可能这段文本携带的信息就很少。研究文本特征要着重考虑：不同词的频率是怎样分布的？随着文档集的增长，词汇表的增长情况如何？这些现象直接影响
2、检索系统对文本的处理和信息检索的效果。第4章 网页文本处理和索引4.1.1 信息熵信息熵信息是个很抽象的概念。我们常常说信息很多，或者信息较少，但却很难说清楚信息到底有多少。比如一本50万字的中文书到底有多少信息量。1948 年香农提出了“信息熵”(information entropy)的概念，才解决了对信息的量化度量问题。一条信息的信息量大小和它的不确定性有直接的关系。比如说，要搞清楚一件非常非常不确定的事，或是一无所知的事情，就需要了解大量的信息。相反地，如果我们对某件事已经有了较多的了解，则不需要太多的信息就能把它搞清楚。所以，从这个角度上可以认为，信息量的度量就等于不确定性的多少。第
3、4章 网页文本处理和索引定义定义4-1 设词汇表中有个词，文本中每个词出现的频率是pi，那么该文本的熵可以定义为：(4-1)12logiiippE在这个公式中，词汇表中个词用二进制编码，所以熵的单位是比特。如果一个文本中只有一个词出现，其熵为0。【例例4-1】设有词汇表空格，a，b，e，o，r，s，u，y，有如下两个文本T1=you are boy，T2=you are boys，求T1和T2的信息熵。解：解：=9，列表求出两个文本中字符的频率如下：第4章 网页文本处理和索引则根据公式(4-1)有：916.2(-0.447)3.315)0(5 112lb1123111lb1115 lb911i
4、iiTppE087.3 )431.0(3)299.0(6 122lb1223121lb1216 lb912iiiTppE第4章 网页文本处理和索引上面的例子中，两个文本只相差一个字母，文本的意义发生了较大的改变，相应的信息熵也发生了较显著的变化。可见，文本的信息量可以用熵来量化，熵的大小是对文本蕴涵的信息量的一个度量，依赖于每个词出现的概率(频率)。可以设想，如果一个字符在文本中频频出现，将导致熵值偏低，所携带的信息量也较少。第4章 网页文本处理和索引4.1.2 统计定律统计定律为了更好地处理文本，要掌握文本的一些统计规律。本节将讨论Zipf定律和Heaps定律，分别研究不同的词在文档中的分布
5、规律及随着文档集的增长而引起的词汇表的增长情况。第4章 网页文本处理和索引1.Zipf定律定律Zipf定律，也称齐普夫定律，最初由G.K.Zipf提出2。齐普夫定律描述为：如果将词汇表中的词按照出现的频率由高到低排序，那么某个词出现的频率与该词所对应的序号之间有如下的简单关系：rrp1)(4-2)式中：p(r)表示某个词出现的频率；r表示该词在按词频降序排列的词汇表中所对应的序号。在某种具体的分布中，是一个正的常数，称为Zipf指数，它的大小仅取决于所描绘的词汇的具体分布，与其他参数无关。在英语中，a1，这时，上面的公式可以改写成：第4章 网页文本处理和索引p(r)r=k (4-3)式中：k为
6、常数。在英文中，使用频率最高的词“the”的使用频率约为1，排在第二位的“of”的使用频率约为1/2，前者的使用频率是后者的2倍。【例例4-2】有一个英语文档包含10万个单词，假设Zipf常数k0.1，求出现了50次的单词，在排序词汇表中排名第几？Nfrp总单词量出现次数)(解：解：再根据p(r)r=k，得到：200501000001.0,rfNkrkrNf第4章 网页文本处理和索引所以，出现50次的单词在单词表中排名序号为200。上面这个例子中，排名第一的单词出现次数是：10000rNkf排名第二的单词出现次数是5000。可见，经常使用的单词在词汇表中占的比例不大。大部分词汇的使用频率很低，
7、即很少被使用。这就是著名的“重尾分布(Long Tail Distribution)”，如图4-1所示。第4章 网页文本处理和索引图4-1 文本词汇的重尾分布图第4章 网页文本处理和索引可能会出现这样的情况，即有多个词出现的频率相同。假定rf是这些词中排位最后的那个词的序号，那么，有rf个词出现f次或多于f次，而rf+1个词出现f+1次或多于f+1次，这样可以算出仅出现了f次的单词个数：)1(11ffkNfkNfkNrrIfff如果排在末尾(序号最高)的单词只出现了一次，那么它的排名序号为r=kN/1，仅出现了一次的单词个数为I1=kN/2。这说明：如果k趋近1，则几乎有一半的单词只出现过一次
8、。第4章 网页文本处理和索引【例例4-3】有一个英语单词表，包含单词10万个，假设Zipf常数k0.1，求出现了50次的词有多少个？解解：根据公式(4-4)，得到：3.9)150(501000001.0 )1(1ffkNrrIfff所以，约有4个单词出现了50次。对公式(4-2)两边取对数，为了用等号，补一个常数，得到：logp(r)=C logr，令X=logr,Y(X)=logp(r)，则得到公式(4-5)：Y(X)=CX (4-5)可见，如果在对数坐标系里，则Zipf定律可以用一条直线表示，由于斜率是负数，故这条线是下降的。人们对许多文档集(Corpus)做了实验，证实了是吻合Zipf定
9、律的3-4。图4-2显示了Brown文档的Zipf定律分布3。第4章 网页文本处理和索引图4-2 Brown文档集满足Zipf定律3第4章 网页文本处理和索引Zipf定律在现实世界中很常见。对Zipf定律可以解释为“最小努力原则”(principle of least effort)2，也就是说，我们的许多认识行为都有使精力支出最小化的倾向。例如人们倾向于用最少量的词来传递最大量的信息。Zipf定律给信息检索系统的设计带来了一些启示，如文本中频繁出现的词语往往是没有用的，它们对文本的内在含义表示没有实质性的意义，所以，可以删掉这部分词语，在不影响文本内容的情况下，大大减少了存储空间的使用。同时
10、我们注意到，大多数词都是低频词(可能只出现一次)，词语之间的相关性很难分析，这对信息检索系统的设计是个不利的因素。因此，图4-1中处于上下限之间的阴影部分的词是比较有意义的，称为重要词汇(significant word)，这些词的描述能力可用一个分布(图中虚线)来表征。第4章 网页文本处理和索引2.Heaps定律定律信息检索系统涉及到信息的存储，需要考虑预留存储空间的大小，而这和文档中的词汇量息息相关。一个文档里面究竟包含多少不同的单词？这个问题可以由Heaps定律5来问答。Heaps定律认为，一个具有n个单词的文本，它的词汇量(不同单词的数量)是：V=Kn=O(n)，01 (4-6)其中，
11、K和是参数，随不同的文档而变化，典型取值通常是K在10100之间，01，则该叶子节点的权值变为当前值的倍，它的父节点以及父节点下的其他子树中的节点均变为当前值的倍，然后以该父节点为变化源，按照上述规则再向外扩展一次。每一次扩展过程中，遇到父节点为body或父节点权值超过预定上限就结束整个权值传递过程。第4章 网页文本处理和索引【例例4-6】对如图4-7(a)中的标签树，如果阴影节点的影响因子为3，请为每个节点标注重要性权值。先将标签树中每个节点的初始权值设为1，根据权值传递规则，得到如图4-7所示的内容块权值传递过程。第4章 网页文本处理和索引图4-7 内容块权值传递过程11第4章 网页文本处
12、理和索引2.网页内容块的取舍网页内容块的取舍网页内容块的提取主要以一组启发式规则为指导，先提取网页的正文信息，再以正文信息为基础，提取DocView模型中的其他要素(包括内容类别、标题、关键词、摘要、相关链接)。下面按照各个要素的生成过程分别描述有主题网页的信息提取过程。(1)正文。在有主题网页中，如果一个内容块是topic类型的，则该内容块中的内容为正文的一部分。按照这个规则，深度遍历标签树并依次记录topic类型的内容块，就得到该网页的正文，也就是该网页的主题内容。第4章 网页文本处理和索引(2)关键词。关键词选取的依据是特征项的权值。对标签树中的每个正文块，如果该块中存在重要信息标签，则
13、检查重要信息标签中的内容是否在噪音词集合中出现；如果不在噪音词集合中出现，将重要信息标签的影响因子累加到该内容块的影响因子上去；如果该内容块的影响因子大于1，则按权值传递策略在标签树中传递权值。得到每个结点都有权值的标签树后，再按公式(4-7)计算各个特征项的权值。(4-7)2BN11BN1BTfBWeightBTfBWeightijjjniijjjiw第4章 网页文本处理和索引式中：BWeightj表示内容块j的权值，其值是由一个内容块中的重要标签来决定的；BN表示网页中内容块的总数；n表示网页中不同关键词的总数；BTfij表示关键词i出现在内容块j中的词频。得到特征项权值后，根据所有特征项
14、权值的算术平均值avg和预先定义的阈值，选取权值大于avg的特征项作为该网页的关键词。(3)内容类别。内容类别是通过对正文分类得到的。(4)标题。一般来说，网页的标题由title标签标识，但针对没有标题或者使用如“Untitled Document”、“New page”、“欢迎访问”等无描述能力标题的网页，可从关键词中选取权值最高的作为网页的新标题。第4章 网页文本处理和索引(5)摘要。通过识别文章中不同的段落，扫描到一些关键词，就可以得到能够模拟读者浏览文章过程的摘要信息。(6)相关链接。对于超链接的选取，可以采用两种策略，一种是基于锚文本的策略，即通过比较每个hub类型内容块中锚文本集合
15、与正文的相似度来决定该块中链接的取舍；另一种是基于分类的策略，通过判断一个hub类型内容块中某个超链接指向的网页与本网页正文的类别是否相同，来决定该块中所有链接的内容相关性。第二种方法比第一种方法要准确，但时间开销很大。对于hub网页和图片网页，一般是将网页中间区域的内容块作为网页的正文，对周围的内容块则通过与正文比较相似性来决定取舍。第4章 网页文本处理和索引4.3.2 基于模板的方法基于模板的方法Web规模庞大，很多网站每天都有大量新生成的网页，网站管理者不可能针对每一个新网页进行重新的排版布局。一般的方法是先开发出一套网页模板(template)，然后将要发布的信息填入这些模板，这样可大
16、大简化网站编辑者的工作量，并可使其精力集中于网页内容的编辑。图4-8为同一模板网页对比图。第4章 网页文本处理和索引图4-8 同一模板网页对比图第4章 网页文本处理和索引从图4-8可以看出网站模板的一些共性：(1)URL具有很大的相似性，通常是在同一个URL目录中；(2)版面的编辑格式基本相同，只是内容不同；(3)版面布局基本一致。基于模板的方法则是利用这种性质，从一组网页中提取出相同的模板，而后利用这些模板从网页中抽取有用的信息。下面介绍一个基于模板匹配的主题信息提取算法DSE(Data-rich Section Extraction)12。DSE的启发思想是，同一个网站的页面结构都是相似甚
17、至是相同的。广告和导航信息等会在页面重复出现，因此通过选择一个模板页面，将待抽取的目标页面和模板页面进行匹配，去掉相同部分(广告和导航信息等)，剩下的就是主题内容，进而达到提取网页主题内容的目的。在已经确定模板网页的前提下，DSE算法可以分为以下两个步骤：第4章 网页文本处理和索引(1)构建目标页面和模板页面的DOM树。HTML文档通过JTidy等工具解析后，可以转化为DOM树，要除去不包含结构信息的标签，如“font”、“h1”等，减少匹配计算量，标签属性只考虑“A”的“href”和“IMG”的“src”属性。(2)匹配目标页面和模板页面的文档树，除去相同部分，提取主题。采用深度优先策略，从
18、根节点到叶节点，逐一比较目标页面和模板页面的节点，删去相同节点。比较两个节点：如果节点是内节点，并且相同，则从右到左匹配其子节点；如果是叶节点，并且相同，则删除该节点；节点不同则返回父节点，继续比较其他兄弟节点；如果节点的子节点都被删除，则也删除此节点。第4章 网页文本处理和索引【例例4-7】以图4-9为例，Tree A是目标网页的DOM树，Tree B是模板网页的DOM树。具体匹配过程如下(用Same()函数表示两个节点是否相同，相同为1，否则为0)：(1)两棵树根节点Same(table，table)=1，进而进入其子节点进行匹配。(2)第一个子节点对Same(tr，tr)=1(见上图的箭
19、头1)，所以再进入下一级子节点。(3)Same(td，td)=1，同样，下一步再比较Same(a1，a1)=1，并且a1是叶子节点，所以删除(a1，a1)节点。返回a1的父节点td，进而用同样的方法匹配删除节点。第4章 网页文本处理和索引图4-9 DSE算法示意图12第4章 网页文本处理和索引(3)td的子节点全部被删除，进而删除此td节点，同样删除td的父节点tr。(4)返回根节点table，匹配其下一个子节点table，Same(table，map)=0(箭头2所示)，再进一步比较Same(table，tr)=0(箭头3所示)，tr没有右兄弟节点，返回table节点。(5)此时最左边的(t
20、r，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)。第4章 网页文本处理和索引(8)返回(u1，u1)，其子节点为空，删除(u1，u1)。(9)返回上一级节点td，其子节点a4没有节点可以跟其匹配删除，所以保留。进而td的子节点不为空，保
21、留td，同样保留tr和table。最后结果如图4-9的第2行所示。第4章 网页文本处理和索引网页去噪和信息提取是目前热门的研究领域。许多方法综合考虑网页结构和模板的特点，例如Lin等人13提出的去除网页中噪音内容的方法可以根据table等标签构造网页的标签树，并依据table标签将一张网页规划为相互嵌套的内容块；然后，对于使用同一个模板做出的网页集，找出在该网页集中反复出现的内容，作为冗余内容，而在该网页集中出现较少的内容块就是有效信息块。基于视觉的网页分块算法VIPS(Vision-based Page Segmentation)14则是利用页面中各元素的布局信息对页面进行划分，保留页面中间
22、区域，而其他区域则认为是噪音。但由于网页中的视觉特征通常多样并且多变，所以造成算法实现较复杂。由于网页结构千变万化，所以，应针对需要处理的网页的具体情况选择合适的方法，有时还需针对网站的特点加以改进，才能适用。第4章 网页文本处理和索引4.4 文本处理文本处理文本操作是指将网络爬虫搜集到的文本信息进行预处理，以便进行网络信息检索的下一个流程索引处理。文本预处理主要包括网页噪声去除、词汇分析、排除停用词和词干提取四个阶段。对经过噪声去除后得到的干净网页，要进行词汇分析，去除停用词，提取词干，最后得到一系列可以表达网页内容的关键词。关于词汇分析，中英文存在较大的区别，英文单词有空格分隔，易于识别，
23、而中文文本以句子为自然分隔单位，要提取出词语来，需要复杂的分词技术。中文信息检索的相关技术在第9章介绍，本章重点介绍以英文文本为主的预处理技术。文本处理的主要流程可以概括为如图4-10所示。第4章 网页文本处理和索引图4-10 HTML文档预处理流程第4章 网页文本处理和索引网页经去噪后，便进入词汇分析及特征提取阶段，如图4-11所示，在这一阶段，主要完成：(1)词汇分析：对数字、连字符、标点符号和字母的大小写进行处理，将文本分割成单词序列。(2)排除停用词：过滤掉那些对检索来说作用不大且区分能力低的词。(3)词干提取：把所有同根的词变成统一的词根形式。(4)特征提取：选择可以作为关键词(索引
24、词、索引项)的词或词组。第4章 网页文本处理和索引4.4.1 词汇分析词汇分析词汇分析(lexical Analysis)，就是把网页中的文本字符序列转换成为单词序列的过程。这些单词用来作为索引词的候选。例如，字符序列the house of the lord经过词汇分析后，可以得到单词序列：the、house、of、the、lord。因此词汇分析阶段的主要任务就是标识出文本中的单词。在英文中，分割单词并不难，因为空格是英文单词的自然分割符。但是在词汇分析阶段，还有几种特殊的情况要处理：数字、连字符、标点符号和字母的大小写。第4章 网页文本处理和索引对于数字来说，一般不作为索引词，因为如果没有
25、上下文的联系，它们的含义是模糊不清的。例如，用户要查询1994年到2005年间有关信息检索方面的网页，查询中的数字1994和2005可能导致检索出只涉及这两年的网页，而遗漏这两年之间的重要网页，所以，有时候可忽略查询中的数字信息。但对于电话号码，信用卡号等数字序列，如果忽略数字，则可能查询到无意义的网页，在这种情况下，数字应该作为关键词。因此，凡与上下文密切相关的数字，我们用其作关键词，其他情况下，数字一般被忽略。第4章 网页文本处理和索引对于连字符来说，也有两难的情况，一般是把连字符连接的单词分解开。例如，把“state-of-the-art”分解为“state of the art”。但是
26、，有些带有连字符的单词本身是一个完整的单词，如“gilt-edged”。最恰当的方法是制定一个通用原则，指明特殊情况下的处理方法。在词汇分析过程中，标点符号一般是要被完全去除的，但有些标点符号是单词的组成部分，去掉对检索效果的影响比较大，这种情况下又要慎重考虑是否删除标点。第4章 网页文本处理和索引对于字母的大小写来说，词汇分析时通常把所有文本都转化为大写或小写的字母，但也有特殊情况，有时大小写转换会丢失语义，例如“Bank”和“bank”的语义是不同的。对这些情况，要特殊处理。Fox在文献“Lexical analysis and stoplists”15中对词汇分析作了详细介绍。但正如Fo
27、x指出的，这些文本操作的实施没有困难，但由于对检索有深刻的影响，所以必须仔细地考虑每一种文本操作，特别是一些特殊情形下的处理。现在的很多搜索引擎都回避了文本操作，避免了文本操作带来的语义损失或误解，也简化了用户对检索任务的理解，不失为一种可取的方法。第4章 网页文本处理和索引4.4.2 排除停用词排除停用词出现频率很高的单词往往不具有很好的文档区分能力，比如“the”，几乎所有的文档中都频频出现这个单词，那么如果用这样的单词作关键字来检索网页的话，可能会检索到大量无用的网页，所检索出的网页中的绝大部分都不是用户想要的。在网页或文档集合中出现频率高于80%的单词通常被称为停用词(stopword
28、s)，它们对文档的含义没有任何意义，需要被过滤、屏蔽掉。通常，冠词、介词、连词都属于停用词。第4章 网页文本处理和索引英文停用词例子：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
29、，be，because，became，and，an，by，from，of，the，with中文停用词例子：一、不、了、也、就、人、都、所、要、会、很、大、能、着、还、可以、最、来、所、可、为、又、将、更、才、已 删除停用词对于信息检索来说具有重要的意义，一方面可以大大缩小索引空间，另一方面可以提高检索准确度。第4章 网页文本处理和索引一般来说，停用词不仅仅有冠词、介词和连词，一些动词、副词和形容词也可能是停用词，信息检索系统可以设置一个停用词表用于过滤停用词。虽然排除停用词可以缩小索引结构的大小，减少倒排文档的长度，但也可能会降低系统的召回率(查全率)，使得用户不能查到自己需要的网页。例如，如
30、果用户要查找包括“to be or not to be”的网页，排除停用词后，可能只留下了“be”，这样就很难分辨哪个文档中包含这个特定的短语，用户可能得到的是一些莫名其妙的文档。针对这个问题，有的搜索引擎会直接向用户说明系统认为用户的检索词中哪些可能是停用词，将被排除不做处理，如果用户认为有误，则可以考虑用引号将这些查询词转换为短语，这样就不会被系统排除了。第4章 网页文本处理和索引4.4.3 词干提取词干提取在英文单词中，一个词干(stem)可以派生出若干的同义词，例如，单词“search”是“searched”“searching”“searches”的词干。可见，词干是单词的一部分，是
31、去除单词的前缀和后缀后剩下的部分。词干提取就是把同词干同义的不同词语中的相同部分提取出来。使用了词干提取的检索系统，即使用户输入的查询关键字不存在于相关文档中，也可以根据由该关键字提取到的词干为用户查找到包含含义相近的变形单词的文档。第4章 网页文本处理和索引词干提取可以大大减少单词词项的数量，可以为用户查找到包含相似词的文档，从而实现改进检索性能的目的，即使如此，词干提取还是有它的缺点的，首先，词干的截取正确率不可能达到100%，可能会有误截，造成词义的改变，影响查询的结果。例如，Medical和Media被识别为Med*，并被认为是意义相近的，那就错了，查询medical的用户会得到med
32、ia的不相关结果。第4章 网页文本处理和索引Frakes提出了4种词干提取方法16：查表法、词缀删除算法、后继变化数和N个字符列。其中查表法是最简单的一种方法，只需要创建一个单词和词干的对应表，通过该表查找单词的对应词干，但是这种方法需要很大的存储空间，所以没有太大的实际应用意义。词缀删除算法主要将单词的前缀和(或)后缀删除，只留下词干部分。后继变化数以词素边界的确定为基础，使用结构化语言学的知识，比去除词缀更加复杂。N个字符列基于二元词和三元词的确定，更像是语词的聚类过程。应用最多的，也最实际的词干提取方法是去除词缀法。Porter提出的Porter算法17，是最著名的词缀去除方法。第4章
33、网页文本处理和索引Porter算法是基于规则的词干提取方法，每一步有一组上下文无关或有关的规则用来删除后缀，或者将其转换为其他形式。上下文无关规则主要根据后缀表(或基于规则集)删除单词的后缀，如：ssesss，iesi，sNULL；上下文有关规则要考虑词的其他性质，例如：happily happi happy，则需要定义一个上下文敏感的转换规则：如果一个词根以i结尾，i前面是p，那么将i转换为y；又如，“(*v*)：edNULL，ing NULL”规则的含义是把以ed(或ing)结尾的ed(或ing)后缀去掉，同时保证留下来的词根必须包含一个元音。详细的Porter算法可以参见文献1的附录。第
34、4章 网页文本处理和索引4.4.4 索引词选择索引词选择如果采用全文的表示，文本中的所有词都是索引词。但这些词并非全部有用，对无用词条建立索引将浪费系统的索引空间，而且影响系统的检索性能，因此并不一定对网页中出现的所有词条都建立索引，而是选择一些比较重要的词条来建立索引。选取索引词的过程叫做索引词选择。对于一些科技刊物的检索来说，一般都是由专家来选择索引词汇的，这种方法非常准确，但需要消耗大量的人力；另一种可选的方法是通过对文档的分析来自动选择索引词，这种方法可能没有第一种方法准确，但是可以由系统自动实现。第4章 网页文本处理和索引系统自动选择索引词的方法很多。一种简单的方法是选择文本中的名词
35、作为关键词，这可以通过自动消除文本中的动词、形容词、副词、连词、冠词和代词来实现，但这要求对词的词性有一定的了解。根据图4-1，只有出现的词频落在一定区域内的词才具有一定的描述能力。因此可以通过计算词频、信息增益(Information Gain)或互信息量(Mutual Information)等方法来选择重要的词汇，这种方法也同时用在自动分类的特征选择上，将在第11章中介绍。第4章 网页文本处理和索引 4.5 索索 引引通过上述的文本预处理操作，可以得到一组关键词序列。现在面临的问题是如何组织这些关键词，以提供快速的检索。如果需要搜索文件，并从中找到包含一些给定单词或词组的文件，最直观的方
36、法是采用顺序搜索，即顺序地扫描文本，直到找到给定的单词或词组为止。但这种方法只适合于规模比较小，变化频繁，对实时性要求比较高的场合，当文本规模进一步扩大时,顺序搜索的时间就会长得让人无法忍受。建立索引，可以减少查找的时间。网络信息是大规模的、稳定的或周期性变化的，建立和维护索引具有极其重要的意义。索引是信息检索系统的核心部分，它把原始数据用一种高效率的、便于查找的方式表示出来，极大地提高了搜索的速度。第4章 网页文本处理和索引把文本的原始数据转换为一个能快速进行查询的格式，这个转换过程就是建立索引(indexing)，而这一过程的输出结果称为索引(index)。索引可以看成一个数据结构，它允许
37、对储存在其中的单词进行快速随机访问。这个概念和一本书后面的关键词索引表非常相似，它能够帮助读者比较快地找到与关键词相关的内容的页码。比如，北京：12，34页；上海：3，77页；广州：78页等，那么读者很快可以定位北京相关的内容在12页和34页，上海相关的内容在3页和77页，广州相关的内容在78页。第4章 网页文本处理和索引4.5.1 Trie树树Trie树是一种重要的用于索引的基础数据结构，Trie的四个字母来源于英文单词retrieval，可见这个数据结构是为信息检索而设计的。Trie树是一种多分支树结构，是一种检索效率较高的数据结构。利用Trie树进行检索时，在每层中不需要顺序查找相应的字
38、符，就可以直接定位到要找的节点。第4章 网页文本处理和索引Trie树按照字母顺序存储字符串，其节点表示字符串的公共前缀，节点之间用边来联系，节点和边共同构成树。按照字母顺序，在树的边上标记字符串集合中的一个字符。例如，对于字符串集合Salpha，beta，bear，beast，beat，那么存储S的Trie树如图4-11所示，图4-11(a)是原始的Trie树，而图4-11(b)是经过整理简化的Trie树，也称为Patricia树。Patricia树是Trie树的压缩表示，所有只有一个子节点的节点都和父节点合并。第4章 网页文本处理和索引图4-11 Trie树第4章 网页文本处理和索引在Tri
39、e树中进行检索的过程为：从根节点出发，沿着相应的指针逐层向下，直到叶节点，若节点中的关键词和给定的查询相同，则检索成功，否则检索不成功。Trie树的查找和B树的查找类似，查找成功时走了一条从根到叶子节点的路径，例如在图4-8中，查找关键字beast的过程为：从根节点出发，经b(a，b分支)a(a，t分支)s(r，s，t分支)边，最后到达叶节点beast。在Trie树中，易于进行插入和删除，只是需要相应地增加和删除一些分支节点。第4章 网页文本处理和索引4.5.2 后缀树后缀树后缀树是一种基本的数据结构。后缀索引可以处理比较复杂的查询。定义4-2 后缀。假设字符串S=s1s2sisi+1sn，其
40、中，si属于输入字符集，那么Si=sisi+1sn是S从位置i 开始的后缀。定义定义4-3 后缀树。一个有m个字符的串S，它的后缀树是一棵有根的有向树，共有m个叶子，分别标号为1到m。每一条边都用S的非空子串来表示。从任一节点出来的两条边，它们必须以不同的字符开始。从根节点到叶子节点i，顺序经过的树边的串联，恰好为S从i位置开始的后缀，即Si。图4-12是字符串bopomo的后缀树示意，其中虚线的部分表示省略了若干条边。第4章 网页文本处理和索引图4-12 字符串bopomo的后缀树示意第4章 网页文本处理和索引对于文本来说，可以以索引词为单位进行后缀树的构建。【例例4-8】文本“This i
41、s a text.A text has many words.Words are made from letters”，它可以用后缀树表示为图4-13所示。图4-13 样例文本的后缀树第4章 网页文本处理和索引从上面两个例子可以看出，后缀树也是一种Trie树数据结构，在Trie树上表示文本的所有后缀，指向后缀的指针存储在后缀树的叶节点上。构造好后缀树之后，就可通过遍历这棵树来做检索了。后缀树结构的主要问题是存储空间问题。后缀数组18提供了与后缀树相同的功能，但其空间需求远小于后缀树。后缀数组就是按照字典的顺序排列并存储所有文本后缀指针的数组，如图4-14所示。因为每个被索引的后缀只存储一个指针
42、，其空间需求几乎与倒排文件索引相同，空间开销是原文本的30%40%19。第4章 网页文本处理和索引图4-14 样例文本的后缀数组第4章 网页文本处理和索引对于大型的后缀数组，为了提高存取效率，可以在后缀数组之上，建立上部索引来加速存取。最简单的上部索引只是给出了后缀数组的外部入口，即在外部索引中存储了每个后缀的前若干个字符及其指针。在检索时，首先在上部索引中查找，然后定位到小范围的后缀数组，进行搜索，如图4-15所示。第4章 网页文本处理和索引图4-15 上部索引 第4章 网页文本处理和索引4.5.3 签名档签名档签名档20(signature file)是一种空间开销较低(占文本大小的10%
43、20%)的索引技术，它是基于散列变换(hashing)的面向单词的索引结构。利用签名档进行索引，首先把文本划分为若干块，每个块有若干个单词；然后利用散列函数，为文本块中的每个单词分配一个签名；再将块中每个单词的签名进行逐位或(OR)操作，即可得到一个位掩码；最后，所有文本块的位掩码序列构成了文本的签名档。第4章 网页文本处理和索引可以简单地把文本的签名档理解为所有文本块的位掩码序列。使用签名档进行检索的主要思想是：如果某个单词出现在一个文本块中，那么置于签名档中的所有位也会置于这个文本块的位掩码中，换言之，一个查询词的位掩码中的位，假如不出现在文本块的位掩码中，那么这个查询词也不会出现在文本块
44、中。【例例4-9】例4-8的文本“This is a text.A text has many words.Words are made from letters.”被分成4个文本块(如图4-13所示)，各单词的Hash值如表4-3所示，计算各文本块的掩码和文本的签名档。第4章 网页文本处理和索引第4章 网页文本处理和索引解解：第二个文本块中包含两个索引词text和many，通过逐位OR操作，计算第二个文本块的位掩码：同理可计算得到其他文本块的位掩码。这4个块的位掩码构成了文本串的签名档，如图4-16所示。第4章 网页文本处理和索引图4-16 样例文本的签名档第4章 网页文本处理和索引如果要检
45、索词“text”，先找到这个单词的Hash值(000101)，并与所有文本块的位掩码进行比较，即执行逐位与(AND)操作，可以知道存在于第一个和第二个文本中。但如果新构造一个文档只由前两个文本块组成，输入检索词“letters”(100001)，发现其位掩码存在于第二个文本块中，这就发生错误了。也就是说，可能存在这种情况：即使某个单词不存在于文本块中，其全部相应的位也可能存在于文本的位掩码中，这种情况称为误检(false drop)。对于签名档的设计来说，应该在保证签名档尽可能短的情况下，确保误检的可能性降到最低。签名档的最大优点是占用空间小，组织简单，更新和删除等的维护费用较小；签名档容易生
46、成，插入费用低。但签名档搜索速度慢(尽管比全文扫描要快)，对于顺序文件，所有的签名都必须比较；另外去除误检需要昂贵的开销。第4章 网页文本处理和索引4.5.4 倒排文件倒排文件1 倒排文件概述倒排文件概述倒排文件(inverted file)是一种面向单词的索引机制，可以支持一些复杂的检索文件，也可以提高检索的速度，是目前为止应用最为广泛的索引技术21-23，开放源码的全文索引引擎Lucene24采用的也是倒排文件。倒排文件有时候也被称为倒排索引、倒排表、倒排文档等，内涵大同小异。倒排文件通常由两部分组成：(1)词汇表(vocabulary)：包括文档集合中所有不同单词的一个向量，或者文本中所
47、有不同单词的向量。第4章 网页文本处理和索引(2)事件表(occurrence)或称置入文件(posting list)：对于词汇表中的每个单词，都有一个包含该单词的所有文档列表，通过文档号来标识，列表存储了该单词出现的文档号，以及单词在文档中的出现位置等。如果我们只对一个文本文件进行索引，那么事件表中的指针可以是一维的，它指向对应的单词在该文本文件中所有出现的位置。例4-5的文本“This is a text.A text has many words.Words are made from letters”，假设以单字为单位来标识单词的位置，其倒排索引的词汇表和事件表如图4-17所示。第4
48、章 网页文本处理和索引图4-17 样例文本的倒排索引示例第4章 网页文本处理和索引 从上面的单文本倒排索引可以看出，词汇表中的单词按照一定的规则进行了排序，事件表里存储的是单词出现在文本中的位置，这些位置是以单字为基本单位的，有些单词在文本中多次出现，如“text”。在这个例子中，对“this”、“is”、“a”、“has”等停用词不做索引。倒排索引的空间占用情况如何呢？实际上，词汇表所占用的空间是相当小的，根据Heaps定律，词汇表所占的空间可以用O(n)来表示，这里的n是文本大小，前面提过，一般在0.40.5之间。例如，对于1 GB的TREC-2文档集，词汇表的大小约5 MB，而且通过词干
49、提取法、停用词排除法等技术还可以进一步减小词汇表所占用的空间。但是事件表所占用的空间相对较大，由于在事件表结构中将涉及出现在文本中的每一个单词，要保存每个单词出现在文本中的每个位置，因此所占用空间可以用O(n)表示。事实上，即使不对停用词索引，事件表所耗费的空间开销也为文本大小的30%40%1。第4章 网页文本处理和索引为了减小所需要的存储空间，可以采用“块寻址”技术8。将文本分成若干个块，事件表指向单词所在块的位置，而不是单词所在文本中的精确位置。这样不仅可以减少指针的数量，而且还可以将出现在一个块中的同一单词的所有事件压缩为一个条目。例如，仍然使用上面的例子，假设将整句话分成4个文本块，倒
50、排索引示意图如图4-18所示。第4章 网页文本处理和索引图4-18 使用块寻址的倒排索引示例第4章 网页文本处理和索引上面的例子反映了块寻址倒排索引的优点，同一个块中多次出现的单词的指针合并为一个，如“words”，原来是33，40，采用块寻址技术后，合并为3了。但是采用块寻址技术也有缺点，比如，查询某个单词，只能定位到某个块，如果需要精确知道它在块中的位置，还必须遍历那个块。采用块寻址技术，主要目的是节约空间，空间节约的程度跟块的划分密切相关。表4-4是不同寻址粒度下倒排索引所占空间的比较情况1。第4章 网页文本处理和索引第4章 网页文本处理和索引注意，表4-4的数据基于文档中的如下假设：单
