信息获取模型Modeling-I.ppt

《信息获取模型Modeling-I.ppt》由会员分享，可在线阅读，更多相关《信息获取模型Modeling-I.ppt（71页珍藏版）》请在装配图网上搜索。

1、1 2.信息获取模型 Modeling I 基本概念 经典的 IR模型 结构化文本检索模型 浏览模型 2 Review of Last Week 信息检索简介 将用户的信息需求转变到查询 匹配查询和存储的文档信息 评价查询结果与用户需求的匹配程度 以下概念的区别 Data retrieval and information retrieval 初步介绍了索引技术 倒排索引 为什么使用倒排索引？ 倒排索引的结构如何？ 一些压缩技术，包括 词表压缩 出现位置压缩 齐普夫率 Zipfs Law 提出了信息检索中存在的一些问题 3 前言 本周主要介绍 IR系统的一些模型 为什么要建模 ? 方便深入地分

2、析比较和预测 什么是建模 ? 通过理论方法描述系统的本质，忽略一 些无关紧要的方面 IR系统的一个核心问题就是预测或计算出 文档集中哪些与用户查询是相关的、哪些 是无关的 4 文档 文档是由文本构成的逻辑单元 记录的单元 (由文本或其他一些东西组成 ) 能够被存储、检索、显示出的单元实体 用来表达某种语义的实体单元 units of text grouped together for a purpose 也可能是完全无结构的文本 Text as written by authors of documents 5 文档模型 文档应当以一种可以被计算机识别的格式 或结构来处理和表达 文档由文本组成

3、 并非文本中的每一个词对于搜索都有意义 文档本身往往并不包含可识别的元数据信息， 比如作者和文档的标题 6 文档的表现形式 文档应该能够被处理，文档的表达方式能够帮助 用户从系统中识别和接受信息 识别作者和标题 识别文章主题 提供总结 /摘要 对文档进行主题分类 7 查询处理 IR 系统通常采用关键词 /索引词来处理查询 索引词 文档关键词或一些被选定来表达文档内容的词 文档中的任何词 (更一般意义上讲 ) 对于文档可能进行词根处理 connect: connecting, connection, connections 中文也有词根处理，如：高高兴兴 高兴 根据选定的索引词建倒排索引，以便查

4、询使用 8 Docs Information Need Index Terms doc query Ranking match 9 结果排名 结果排名是指对检索到的文档进行排序， 这个顺序反映了文档与用户需求之间的相 关程度 排序基于相关度计算的一些基本假设进行 查询和文档关键词共享同一个词的集合 如何定义相关度 不同的相关性定义导致不同的 IR模型 10 结果排名 在索引词层次的匹配是不精确的 用户经常对搜索结果不满意 大多数用户并不知道如何正确使用查询的语法， 因此查得的结果就会更糟糕 Web用户经常会感到不满意 如何能够形成好的排名对于 IR系统来说至关重要 11 Retrieval:

5、Ad Hoc and Filtering Ad hoc retrieval自由式查询 Collection “Fixed Size” Q2 Q3 Q1 Q4 Q5 12 Retrieval: Ad Hoc and Filtering Filtering过滤式查询（比如股票信息） Documents Stream User 1 Profile User 2 Profile Docs Filtered for User 2 Docs for User 1 13 IR 模型 Non-Overlapping Lists Proximal Nodes Structured Models Retrieva

6、l: Adhoc Filtering Browsing U s e r T a s k Classic Models boolean vector probabilistic Set Theoretic Fuzzy Extended Boolean Probabilistic Inference Network Belief Network Algebraic Generalized Vector Latent Semantic Index Neural Network Browsing Flat Structure Guided Hypertext 14 IR模型、文档逻辑视图、用户任务之间

7、的关联 Index Terms Full Text Full Text + Structure Retrieval Classic set theoretic Classic algebraic Classic probabilistic Classic set theoretic Classic algebraic Classic probabilistic Structured Browsing Flat Flat Hypertext Structure Guided Hypertext LOGICAL VIEW OF DOCUMENTS U S E R T A S K 15 IR系统的形

8、式化描述 (MIR p. 23) IR模型是一个四元组 D 是文档集中文档的逻辑表示形式 Q 是用户需求的逻辑表示形式，亦可理解为查询 F 是一种机制，用于构建文档表示、查询以及它们之 间关系的模型 R(qi, dj) 是排名函数，该函数输出一个与查询 qi Q和 文档表示 dj D有关的实数，从而在文档之间根据查询 qi定 义一个顺序 16 框架 F的含义 对于经典布尔模型而言，框架由文档集合 和作用在这个集合上的标准运算（与、或、 非）组成 对于经典向量模型而言，框架由 t维向量空 间和作用在向量上的标准线性代数运算组 成 对于经典概率模型而言，框架由集合、标 准概率运算和贝叶斯 Baye

9、s理论组成 17 经典 IR模型 -基本概念 每个文档可用一组有代表性的关键词集合来描述 索引项 index terms往往是文档中的一个词，这个 词有助于表达或记载该文档的主题 索引项 index terms通常是名词，因为名词本身具 有语义 对于一个全文检索系统来说，也可以假设所有的 词都是索引项 例如，一些 web search engines 18 经典 IR模型 -基本概念 不同关键词在描述文档内容时的作用是不尽相同 的，较少出现的词往往能够表征出较少的文档集 合 索引项 index term的重要性由权重来表示，设 ki 是一个索引项 index term dj 是一个文档 doc

10、ument wij 是 (ki,dj) 之间的权重 权重 wij 定量描述了某关键词 ki对于描述文档 dj的 重要程度 19 经典 IR模型 符号表示 ki 索引项 index term dj 文档 document t 系统中索引项的数目 K = (k1, k2, , k t) 是所有索引项的集合 wij 0 是索引项 ki在文档 dj中的权重 wij = 0 表明某词并不属于某文档，或词与文档 无关 vec(dj) = (w1j, w2j, , w tj) 是与文档 dj相关的词 的权重向量 gi(vec(dj) = wij 返回 vec(dj)中第 i个向量的函数 20 集合 (直观描

11、述 ) 具有某种属性的对象总体 (通常用大写字母 表示，如 A,B)，这些对象称为其元素 (通常 用小写字母表示，如 x, y) x是 A的元素记为： x A x不是 A的元素记为： xA 集合的基本特性是，对于给定的集合 A，任何对 象 x, x A与 xA中有且只有一个成立 21 集合的并运算和交运算 集合 A与 B的并是由 A或 B的所有元素组成的 集合 , 记为 A B, 即 A B=x | x A或 x B 集合 A与 B的交是由所有 A和 B的公共元素组 成的集合 , 记为 AB, 即 AB=x | x A且 x B 22 布尔代数 布尔变量：只有“真”、“假”取值的变量 如命题“

12、一篇文档中存在世界杯这个词”，其结果变量就是 一个布尔变量 (存在则取真，否则取假 ) 计算机中常常用 1表示“真” true， 0表示“假” false 布尔操作 (关系 ) 与 (AND)： (A AND B) = true if A=true and B=true 或 (OR) ： (A OR B) = true if A=true OR B=true 非 (NOT) ： (NOT A) = true if A=false 布尔表达式：多个布尔变量之间通过布尔操作组成的表达 式 如： A AND (B OR C) AND NOT D 蕴含：两个布尔表达式 P、 Q，如果 P为 true，

13、那么 Q也为 true，则称 P蕴含 Q，记为 P Q 23 布尔模型 基于集合论和布尔代数的简单模型 查询以布尔表达式的方式出现，表示为多个合取向量的析取 精确的语义，简洁的表达方式 q = ka (kb kc) qdnf 表示查询 q的析取范式， qcc 表示 qdnf 的任意合取向量 词在文档中要么出现要么不出现，因此 , wij 0,1 Consider q = ka (kb kc) 析取范式 qdnf = (1,1,1) (1,1,0) (1,0,0) qcc = (1,1,0) 是一个合取子项 24 布尔模型 (1,1,1) (1,0,0) (1,1,0) Ka Kb Kc 0,0

14、,10,1,11,1,1 cba KKKq 1 | ,( , ) 0 c c c c d n f i i j i c c j i f q q q k g d g qs i m d q o t h e r w i s e 任何一个布尔表达式都可以转化成析取范式 以上将布尔查询转化成析取范式 25 布尔模型的缺陷 没有部分匹配的概念 不提供排名先后，没有相似度计算 判断 要么文档与查询匹配，要么不匹配 更接近一个数据库系统而不是一个信息检索系统 信息需求必须被翻译为布尔表达式，然而很多用户发现自 己对布尔表达式并不熟悉，很难用来表达自己的需求 用户所采用的布尔查询往往过于简单 直接导致的结果是布尔

15、模型返回的查询结果要么太多，要 么太少 26 课堂思考题 想查关于 2009年快女 6进 5 比赛的新闻，用 布尔模型怎么构造查询？ 27 参考答案 (2009 OR 今年 ) AND (快乐女声 OR 快女 ) AND (6进 5 OR 六进五 OR 六 AND 进 AND 五 ) 表达式相当复杂，构造困难 不严格的话结果过多，而且很多不相关； 非常严格的话结果会很少，漏掉很多 28 布尔模型的优缺点 优点： 简单：现代很多搜索引擎中仍然包含布尔模型的思想， 如 Google的高级检索 自我保护功能：降低用户对搜索系统的期望，使自己 不在责任方，检索结果不好的原因在于用户构造查询 不好 缺点

16、： 只能严格匹配 (得分不是 0就是 1)，不能近似或者部分 匹配，多个结果无法排序 一般用户构造查询不是很容易，构造不利可能造成结 果过多或者过少 29 向量模型 布尔模型二值权值的权重表示方式限制太大 非二值权值的权重能够实现部分匹配，可计算用 户查询与文档之间的相似度 这种相似度有利于用户判断文档与自己需求的贴 近程度 30 向量 向量 (矢量， vector)：既有大小又有方向的量，通 常用有向线段表示 考虑从空间坐标系原点出发 (其他向量可以平移到 原点出发 )的向量，终点坐标为 ，我 们称之为一个 n维向量 向量的运算：加、减、倍数、内积 nn yxyxyxyx , . . . ,

17、 2211 nxxxx , . . . , 21 nn yxyxyxyx , . . . , 2211 31 向量的模、距离和夹角 向量的模 (大小 )： 向量的 (欧氏 )距离 夹角 22221 . nxxxxx 2222211 .),( nn yxyxyxyxd i s t yx yx c o s 32 向量空间模型 向量空间模型 (Vector Space Model， VSM)是康 奈尔大学 Salton等人上世纪 70年代提出并倡导， 原型系统 SMART* *可从 ftp:/ftp.cs.cornell.edu/pub/smart/下载全部源码和相 关语料 Term独立性假设： T

18、erm在文档中的出现是独立、 互不影响的 查询和文档都可转化成 Term及其权重组成的向量 表示，都可以看成空间中的点，向量之间通过距 离计算得到查询和每个文档的相似度 33 向量模型 定义 : wij 0 whenever ki dj wiq = 0 associated with the pair (ki,q) vec(dj) = (w1j, w2j, ., wtj) vec(q) = (w1q, w2q, ., wtq) 每一个关键词 ki 都代表一个向量 vec(i) 向量 vec(i) 和 vec(j) 之间是独立的 (i.e., 假设关键词在文档中出现是相 互独立的 ) 假设各关键

19、词的出现是独立的，那么 t 个向量 vec(i) 形成了 t维空间的 正交基 在这个 t维空间，查询和文档都是权重构成的向量 34 向量模型： Cosine Similarity Since wij = 0 and wiq = 0, 0 = sim(q,dj) =1 引入了在 0和 1之间的相似度，一个文档即使是与查询部分匹 配也能够被检索 t2 t1 dj q , 1 22 , 11 , c o s t i j i q j i j tt j i j i q ii ww qd si m q d qd ww 35 向量模型 Term的选择 Term能代表文档内容的特征 Term粒度： Term可

20、以是字、词、短语或者某种语义单元 (比如：所有同义词作为 1维 )，最简单的是采用全文标引 (full text indexing)，即用文档中出现的所有的字或词作为 标引词 降维： VSM中向量的维数很大 (以中文词索引为例，向量 维数会上 10万 )时，往往也同时引入了很多噪音。因此， 实际应用中，会采用一些降维策略 (如：去停用词、对英 文进行词干还原、只选择名词作为 Term、将 Term聚成的 不同类作为一个个 Term、选择出现次数较多的词作为 Term等等 ) 36 向量模型的权重计算： tf vs idf 如何计算 wij 和 wiq ? 一个好的权重必须考虑两方面因素 : 词

21、的频率 (term frequency, tf)，通常称为 tf因子：词对文档的重要性 或相关程度 tf factor, the term frequency within a document 逆文档频率（ inverse document frequency, idf)，通常称为 idf因子： 词对于区分不同文档所起的作用 idf factor, the inverse document frequency wij = tf(i,j) * idf(i) , 1 22 , 11 , c o s t i j i q j i j tt j i j i q ii ww qd si m q d qd

22、 ww 37 向量模型 设 , N 集合中文档的总数量 ni 集合中包含 ki的文档的数量 freq(i,j) 表示 ki 在 dj中出现的次数 归一化的 tf因子计算如下： f(i,j) = freq(i,j) / max(freq(l,j) max(freq(l,j) 代表在文档 dj中出现频度最高的词出现的频率 idf 因子计算如下： idf(i) = log (N/ni) 取 log 是使得 tf和 idf之间具有可比性，也可以把 idf理解为关键词 ki的信息量 38 向量模型 目前为止最好的权重机制如下所示： wij = f(i,j) * log(N/ni) the strateg

23、y is called a tf-idf weighting scheme 对于计算查询的权重，通常按如下公式计算： wiq = (0.5 + 0.5 * freq(i,q) / max(freq(l,q) ) * log(N/ni) 对于一般集合而言， tf-idf 权重的向量模型是一个比较好 的排名机制，比较简单而且易于计算 39 向量模型 优点： 词权重改进了结果集的质量 部分匹配允许检索出与查询接近的文档 cosine ranking排名机制根据文档与查询之间的相似 度对文档进行排序 缺点： 理论上不够：基于直觉的经验性公式 标引项之间的独立性假设与实际不符：实际上， Term的出现之

24、间是有关系的，不是完全独立的。如： “王励勤”“乒乓球”的出现不是独立的 40 向量模型 : 例 1 k1 k2 k3 q dj d1 1 0 1 2 d2 1 0 0 1 d3 0 1 1 2 d4 1 0 0 1 d5 1 1 1 3 d6 1 1 0 2 d7 0 1 0 1 q 1 1 1 d1 d2 d3 d4 d5 d6 d7 k1 k2 k3 41 向量模型 : 例 2 d1 d2 d3 d4 d5 d6 d7 k1 k2 k3 k1 k2 k3 q dj d1 1 0 1 4 d2 1 0 0 1 d3 0 1 1 5 d4 1 0 0 1 d5 1 1 1 6 d6 1 1

25、0 3 d7 0 1 0 2 q 1 2 3 42 向量模型 : 例 3 d1 d2 d3 d4 d5 d6 d7 k1 k2 k3 k1 k2 k3 q dj d1 2 0 1 5 d2 1 0 0 1 d3 0 1 3 11 d4 2 0 0 2 d5 1 2 4 17 d6 1 2 0 5 d7 0 5 0 10 q 1 2 3 43 概率统计初步 随机试验与随机事件 概率和条件概率 乘法公式、全概率公式、贝叶斯公式 随机变量 随机变量的分布 44 随机试验和随机事件 随机试验：可在相同条件下重复进行；试 验的可能结果不止一个，但能确定所有的 可能结果；一次试验之前无法确定具体是 哪种结

26、果出现 掷一颗骰子，考虑可能出现的点数 随机事件：随机试验中可能出现或可能不 出现的情况叫“随机事件” 掷一颗骰子， 4点朝上 45 概率和条件概率 概率：直观上来看，事件 A的概率是指事件 A发生的可能性，记为 P(A) 掷一颗骰子，出现 6点的概率为多少？ 条件概率：已知事件 A发生的条件下，事件 B发生的概率称为 A条件下 B的条件概率， 记作 P(B|A) 30颗红球和 40颗黑球放在一块，请问第一次抽取 为红球的情况下第二次抽取黑球的概率？ 46 乘法公式、全概率公式和贝叶斯公式 乘法公式 ： P(AB) P(A)P(B|A) P(B)P(A|B) P(A1A2A n) P(A1)P

27、(A2|A1).P(An|A1A n 1) 全概率公式： A1A2A n是整个样本空间的一个划 分 贝叶斯公式： A1A2A n是整个样本空间的一个划 分 n i ii ABPAPBP 1 | nj ABPAP ABPAP BAP n i ii jj j ,. . .,1, | | | 1 47 事件的独立性 两事件独立：事件 A、 B，若 P(AB)=P(A)P(B)，则 称 A 、 B独立 三事件独立：事件 A B C，若满足 P(AB)=P(A)P(B), P(AC)=P(A)P(C), P(BC)=P(B)P(C), P(ABC)=P(A)P(B)P(C)，则称 A、 B、 C独立 多

28、事件独立：两两独立、三三独立、四四独立 . 48 随机变量 随机变量：若随机试验的各种可能的结果 都能用一个变量的取值（或范围）来表示， 则称这个变量为随机变量，常用 X、 Y、 Z来 表示 (离散型随机变量 )：掷一颗骰子，可能出现的点 数 X (可能取值 1、 2、 3、 4、 5、 6) (连续型随机变量 )：北京地区的温度 (-1545) 49 概率模型 通过概率的方式来描述和刻画 IR problem 理想结果集：给定一个用户查询，存在一个文献集合，该 集合只包含完全相关的文献而不包括其他不相关的文献 把构造查询的过程看成详细描述理想结果集属性的过程 这些属性是什么呢？在开始时并不确

29、切知道，因此需要努 力猜测是什么 初始的猜测允许我们形成一个初步的对理想结果集的概率 描述，用于检索出初始的文献集 在改进理想结果集的概率描述这一目标指引下，叠代改进 假设最初查出一些文档 用户查看这些文档，找到那些有用的文档 IR系统使用这些信息来优化理想结果集的描述 重复以上过程，结果集会越来越好 50 假设：概率原则 给定一个用户查询 q 以及一个文档 dj ，概率模型尽力去估计用户对 文档 dj感兴趣的概率 (i.e., relevant) ，并认为文档和查询相关的概率 仅依赖于查询和文档的表示 模型模型假设在文献集合中存在一个子集，且用户倾向于把该子集作 为查询 q 的结果集，该理想

30、的结果集用 R 表示；对于用户来说，它应 该能够使得总体的相关概率最大；集合 R中的文献与查询相关，不在 集合中的文献则不相关 那么如何计算相关的概率呢？ 51 排名计算 概率排名相似度计算公式如下： sim(q,dj) = P(dj relevant-to q) / P(dj non-relevant-to q) 这就是文档 dj 与查询 q相关的判断标准 以此为准则能够最小化误判发生的概率 定义： wij 0,1， wiq 0,1 R表示已知的相关文档集（或最初的猜测集）， R 表示 R的补集 P(R|dj ) ： 文档 dj 与查询 q相关的概率 P(R|dj ) ：文档 dj 与查询

31、q不 相关的概率 52 排名计算 P(dj|R) ：从相关文档集 R中随机选取 dj 的概率 P(R) ：从整个集合中随机选择一个文档是相关的概率 P(dj| R) ：从补集中随机选取 dj 的概率 P(R) ：从整个集合中随机选择一个文档是不相关的概率 |( , ) | j j j P R ds im d q P R d 根据贝叶斯定理： | | | | ( , ) | | j j j j j jj jj P d R P R P d R P R P d R P R P d R P R si m d q P d R P R P d R P R P d R P R P d R P R 对文档集中

32、的每一个文档来说， P(R)和 P(R)都是一样的 ： |( , ) | j j j P d Rs im d q P d R 53 排名计算 Assume the independence of index terms 10 10 | ( , ) | | i j i j i j i j iig d g dj j j ii g d g d P k R P k RP d R si m d q P d R P k R P k R P(ki | R) ：表示索引词 ki 在集合 R的某篇文档中随机出现的概 率 P( ki | R) ：表示索引词 ki 不在集合 R的某篇文档中随机出现 的概率 对于集合

33、 R ，相应的概率具有相似的含义 54 排名计算 where P(ki | R) = 1 - P(ki | R) P(ki | R) = 1 - P(ki | R) 10 10 , , , , 11 , , , , 1 | ( , ) l og | l og | 1 l og 1 | l og | 1 i j i j i j i j ii g d g d j ii g d g d tt i q i j i i q i j i ii t i q i j i i q i j i P k R P k R sim d q P k R P k R w w P k R w w P k R w w P k

34、R w w 1 , 1 l og 1 | | 1 | l og l og 1 | | t i i t ii i q i j i ii P k R P k R P k R ww P k R P k R 两边对对数，忽略在相同查询背景下对所有文献恒定不 变的因子，则 55 初始排名计算 概率 P(ki | R) 和 P(ki | R) 如何计算 ? 在没有任何检出的文档时，基于以下假设来估算： P(ki | R) = 0.5 P(ki | R) = ni /N where ni 是包含 ki 的文档数， N表示集合中的文献总数 用这个最初的猜想来获取最初排名 在最初排名基础上不断改进 RkP Rk

35、P RkP RkPwwqds i m i i i i t i jiqij | |1l o g |1 |l o g),( 1 , 56 Improving the Initial Ranking Let V ：用概论模型初步检出并经过排序的文档的一个子集 Vi ： V中包含 ki的文档集合 重新估算： ,1 | 1 |( , ) l og l og 1 | | t ii j i q i j i ii P k R P k Rsi m d q w w P k R P k R i i iv n v|v N viiP k R P k R 递归计算 57 Improving the Initial Ran

36、king 为了避免 V=1 and Vi=0 在实际中引发的问题，可在公式 中加入调整因子： P(ki | R) = Vi + 0.5 V + 1 P(ki | R) = ni - Vi + 0.5 N - V + 1 调整因子恒等于 0.5并不能总是令人满意，可用分数 ni/N作 为调整因子： P(ki | R) = Vi + ni/N V + 1 P(ki | R) = ni - Vi + ni/N N - V + 1 RkP RkP RkP RkPwwqds i m i i i i t i jiqij | |1l o g |1 |l o g),( 1 , 58 优缺点 优点 : 文档依概

37、率相关排序 良好的数学模型，便于理论分析 缺点 : 需要猜测初始值 P(ki | R) 没有考虑 tf and idf factors 假设索引词相互独立 59 经典模型之间的比较 布尔模型不提供部分匹配功能，被认为是最弱的模型 Salton and Buckley 作了相当的试验表明对于通常的数 据集来说 vector model 要好于 probabilistic model 60 结构化文本检索模型 假设一个用户回忆起来某个感兴趣的文档包含这样一页，其中字符串 “ Polluted Water” 围绕一幅图出现，这幅图的标签包含 “ earth” 用经典的信息检索模型，该查询可表示为：“

38、 Polluted Water” and “earth” 一种更为丰富的表达方式可能是： same-page (near(Polluted Water Figure(label(earth) 有的信息检索模型能够将文本的信息与结构化信息联合起来查询，我 们称之为结构化文本检索 (structured text retrieval, STR)模型 往往搜索所有符合查询条件的文档 合适的结果排名目前仍然是一个未能解决的研究问题 往往是在查询语言的表现力和效率之间进行折中 应用场景有限，往往是小的数据集，良好的结构 相关概念 Match point 匹配点，表示文本中与用户查询相匹配的词串的位置 R

39、egion 区域，表示文本中连续的局域部分 Node 节点，表示文献的结构化单元 61 基于非重叠链表的模型 将整个文本划分成若干非重叠的文本区域，并用链表连接起来 划分方法有多种，会产生多个链表（彼此独立，有不同的数据 结构）；每个链表对应一个独立的倒排文档，每个结构单元作 为索引中的一个项，与每项相关的是一个文本区域链表 与传统倒排表良好兼容 查询简单 Chapter Sections Subsections Pages L1 L2 L3 L4 62 基于临近节点的模型 Chapter Sections Subsections Subsubsections holocaust 10 256

40、 48324 在文档上定义独立分层索引结构，每个索引都有严格的层次结构，即由章、节、段、 页、行组成 每个 Node都与一个文本区域相关；两个不同的层次结构可能会指向同一个 Region 对涉及不同层次结构的用户查询而言，结果只能由来自一个层次的所有 Node形成， 目的是允许以较少的表达获得较快的查询处理 对结构部分分层索引，对词平坦索引；在查找的时候根据倒排表中节点临近情况 返回查找结果 63 结构化索引以方便查询处理 Query: (*section) with (holocaust) which search for section, subsection and subsubsect

41、ion 最简单直白的处理方法 遍历倒排列表，对每个出现的 holocaust 都在层次索引中查 找包含该词的节、子节、子子节 一个更为复杂的查询处理机制 对 holocaust 链表中的第一项，搜索层次索引，找到最内层 的匹配单元，即最下层的节点 看临近出现的 holocaust是否也在此节点中 不需要对层次索引逐个从上到下遍历结构树，只依靠 邻近节点 (Proximal Nodes)即可快速查找出现章节。 64 浏览模型 有时用户的兴趣并不在提出查询获得结果，而是 希望通过对查询结果文档进行浏览以获得感兴趣 的内容 对于一个浏览任务来说，用户的目的性并不像一 般搜索任务那么明确 三种浏览模型

42、： 扁平（ flat） 结构导向（ structure guided) 超文本（ hypertext） 65 扁平式 (flat)浏览 文档空间平坦组织，并未结构化组织 在相邻文档中查找相关文档，并通过浏览这些文 档来修改原始查询以获得更好的查询结果 以平坦式方法浏览单个文档 缺陷：在给定的页面或屏幕上，可能没有关于用 户所处上下文情况的任何提示 66 结构化引导的浏览 目录，即类的层次结构，将文献按照相关主题来 分类和组织 用户浏览在目录结构指引下进行，可以变焦的方 式上下查看这些层次，并保持上下文的线索 界面也可以提供一些其他工具如历史地图，用来 指明最近访问过的类 67 Web Page

43、 目录结构 Open Directory Project The Open Directory Project 是最大、最具综合性、人工 编辑的网站目录，它是由大量志愿者来构建和维护的 Google, Baidu, Yahoo! 网站分类 68 69 70 71 超文本模型 超文本是一个允许以非顺序方式在计算机屏幕上浏览文本 的高层交互式导航 navigational结构 超文本实质上是由结点和链组成，结点之间的关系用链表 示，结点和链构成一个有向图结构 超文本的导航过程可以被理解成遍历一个有向图的过程 关于 web 准确的讲， web并不是一个严格意义上的超文本，因为它缺少 基本的数据模型，缺乏导航计划，而且缺乏设计统一的用户界 面