WEB上超文本数据导航方法的研究，本文主要内容关键词为：超文本论文,方法论文,数据论文,WEB论文，此文献不代表本站观点，内容供学术参考，文章仅供参考阅读下载。
1 引言
网上Web页面一般都由多媒体数据组成，有文本、图形、图像、声频、视频、动画等。由于 多媒体系统具有把各种媒体数据与设施统一组织、存放、合成和演播的集成性，用户作用、 加工和控制信息的交互性，以及处理媒体信息严格的时序要求和实时性等特点[1]，使多媒 体系统具有越来越广泛的应用价值。在网上多媒体页面之间加上表示相互联系的超链，可形 成超媒体Web页面。一般情况下，超文本和超媒体都具有超媒体的含义，往往不加分别，但 有时也需要区别对待。
由于Web的迅速发展，人们才真正地感觉到信息时代的到来。据估计，Web已经拥有3亿页面 ，而且仍以每4至6个月翻一倍的速度增加[2]。在Web上浏览各种信息，并对这些信息进行加 工和利用已成为人们工作和日常生活中必不可少环节。但由于超文本数据模型中存在迷路问 题，需要使用导航方法[3，4]。因此，必须研究建立、浏览、检索和维护Web页面的有关技 术，Web上超文本数据的导航方法就是其中之一。
2 超文本数据的迷路问题
超文本数据模型是一种新型的数据组织方法，由节点和链组成的网络构成。网络中的每个 节点是以多媒体形式表示的一个信息单位（文本、图形、图像、声频、视频、动画等媒体的 集成），其链表示节点之间的关系。图1给出了一个简单的超文本数据的组织方式。从该图中 可以看到，数据网络中维持各个节点之间关系的只有节点之间的超文本链。恰恰是这种链蕴 藏了超文本数据的迷路问题。
在超文本系统中浏览数据时，主要靠超文本数据的内在特性进行，即使用网络中各节点的 数据时，主要靠跟踪超文本节点之间的链来确定当前位置。如果超文本网络中的节点非常多 （例如几百个以上），而且各节点之间的链接关系复杂（网络图中的边非常多），导致网络关系 复杂。用户在这样的网络中浏览航行时，会遇到两个问题[3]：(1)不知道当前所处节点的具 体位置；(2)不知道怎样才能到达想要去的节点。这就是所说的“迷路”问题。因此，在超 文本系统中必须设法避免或减少迷路情况发生，其最有效、最实际的做法就是引入“导航” 机制。Web页面作为超文本系统最广泛的应用之一，其导航方法研究十分重要。
3 Web导航方法
为了讨论Web导航方法，需要把Web页面对应到超文本网络图。假设Web的每个页面文档对应 超文本网络图的节点，页面之间的联系对应该图中的有向边，网络中各服务器上的Web页面 就构成了有向图。页面之间的联系用超文本外链链接，简称为外链；页面内部之间的联系用 超文本内链链接，简称为内链。超文本外链和内链统称为超链，简称为链。由于内链是同一 个文档（Web页面）内部的链接关系，对迷路问题的影响较小，除非特殊说明，本文讨论的链 接关系均指外链。
除了利用超文本数据模型固有的特点，由用户利用Web页面节点之间的“超链”关系选择航 行地点以外，Web导航机制主要有以下几种方法：
(1)导游线路方法。把一串页面节点利用超链连接在一起，形成一个“导游”线路。用户通 过选择导游线路进行导航。利用这种导航方法可以完成某种固定的任务，用户一旦选择了导 游线路以后，导航就一直进行，可以避免迷路问题。但该方法适应性太弱，往往不能满足用 户不断变化的需求，其应用价值较小。
(2)导航图方法。导航图是解决超文本数据迷路问题最有效的方法。该方法是将Web服务器 上的Web页面的网络图用示意图方法表示出来（当然也包括节点和链的一些属性），用户需要 访问哪个页面时，可以直接选中示意图上对应的节点。由于示意图的直观性较好，其导航速 度快、效果好，但生成和显示节点导航图不很容易。
首先，网上Web服务器很多，其Web页面数以亿计，生成一个完全的节点图是不可能的，其 时间、空间都不允许。其次，由于一个用户（或一个用户的某一次网上浏览）的任务是一定的 ，没有必要对所有的Web服务器进行浏览，对浏览的Web服务器也只关心其中与自己任务相关 的页面。所以，实际操作时只需要对一部分（实际上是一小部分）站点的部分页面产生导航图 。此外，为了更好地导航，可以使用导航树、全局/局部导航图、分级框架导航图和鱼眼图 等导航图技术。
(3)自动超链接技术。由于网上信息量很大，用人工产生所有的超链既不方便，时间上也不 允许。根据各媒体（现在主要是文本）的意义、权重等可以通过计算得出其映射关系，自动产 生超链。这种导航方法能引导用户方便地找到比较有用的页面。
(4)利用搜索引擎导航。网络搜索引擎也是一种实用的导航方法。网络搜索引擎一般由信息 收集软件、索引数据库和查询接口三部分组成。搜索引擎可分成基于目录的搜索、基于机器 人的搜索、基于客户的搜索、元搜索和分布式搜索等几类[5]。由于搜索引擎的研究也是一 个非常重要的研究课题，本文对它不做过多的探讨，关于搜索引擎的现状分析可见文献[5] 和文献[6]。
(5)其他导航方法。一般浏览器中都具有的一些导航方法，例如回溯、前进、历史列表和书 签 等。这些导航方法非常容易学习、掌握和实现，不是导航方法研究的主要任务。
从以上的介绍和分析可见，导航方法中使用价值最大、最有研究意义、也是最难掌握的导 航方法是导航图法和自动超链接技术，下边将重点研讨这两类导航方法。
4 利用导航图导航的方法
4.1
鱼眼图
由于用户只关心与自己的任务有关的节点的信息，没有必要对所有的Web页面生成导航图。 有资料表明，用户使用超文本系统时，一般只对自己当前所处节点的“周围环境”最感兴趣 ，离当前节点越远，其注意力越少[3]。于是，其导航图可以采用一种“粗细”不均匀的显 示方式，即离当前节点越近的节点其显示越“细”（放大显示），越远的节点显示越“粗”（ 粗略显示），这种导航图就是鱼眼图。可见，鱼眼图是一种对用户关注程度的描述。为了能 定量地描述用户的关注程度，引入D[,DOI]函数，其定义为D[,DOI] (x｜y)=I(x)-D(x，y)，其中I(x) 表示节点x的重要程度，D(x，y)表示x与y之间的距离，D[,DOI] (x｜y)表示用户位于节点y时，对 节点x感兴趣的程度。预先设定一个阈值d，导航图中只显示那些D[,DOI]的值大于d的节点。
4.2 导航树技术
由于树型属于层次结构，比网络结构易操作，其浏览方式也比较简便，所以超文本系统的 导航图经常使用树型导航图——导航树。导航树中每个节点代表一个超文本页面，每一条边 相当于一条（或多条）超链。由于超文本世界的链接结构一般都是网状结构，把这种网状图转 化成树状图时需要去掉那些会产生网状图的一些不重要的链。这种导航树的结构类似于超媒 体文献模型[7，8]，非常适合于作为超媒体教材、文章和产品介绍等的导航图。目前关于导 航树的研究比较深入。
除了手工产生导航图以外，自动导航图技术也是热点课题之一，前边介绍的鱼眼图的产生 就需要这种技术。自动产生导航树也具有很大的实际意义。文献[3]介绍了一种将超文本网 状有向图转化为导航树的方法。
该方法需要定义网状有向图G的距离矩阵D(G)=(d[,ij])，其中d[,ij]是节点i到节点j之间的路径 长度。图G的转换距离矩阵C(G)=(c[,ij])，如果d[,ij]≠∞，c[,ij]=d[,ij]，否则c[,ij]=k，其中k是转换 常数。一个节点的转换出距C[,cod]是C(G)中它所对应的行的总和，表示该节点在图中的中心度 。网络G的转换距离C[,cd]是该图转换距离矩阵中所有项之和。一个节点的相对出中心度R[,ROCi]=C[,cd]/C[,CODi]，该值表示该节点是否靠近中心位置。
对G的层次化可以从选择导航树的根节点开始。可以看出，应选择具有较大的R[,ROC]值的节点 作为树根，因为从这样的节点出发比较容易访问图中的其他节点。至于导航树的生成过程可 以使用广度优先算法。
4.3 分级框架导航图
鱼眼图实际上是一种最简单的分级结构的导航图。作为一种扩充，可以将阈值用向量表示 ，例如设两个阈值d[,1]＞d[,2]。对D[,DOI]大于d[,1]的节点放大显示，对D[,DOI]小于或等于d[,2]的节点只 显示其轮廓，对D[,DOI]大于d[,2]并且小于或等于d[,1]的节点显示其主干框架。这样，就形成了三 级框架导航图。如果阈值向量中的分量增多，所分的级别也越多。当然，导航图分级不一定 非使用D[,DOI]，也可根据具体需要选择其他量。作为这种分级框架的另一种简化形式，可以采 用全局/局部导航图方法。
全局/局部导航图法对全局图一般采用概括（或折叠）显示，对局部图采用放大（或精确）显示 。以树型导航为例，文献[7]采用了类似于Windows资源管理器中对文件夹/文件等资源的树 型显示结构。对非树叶节点，节点前的+或-号可以提示用户可以打开或关闭（折叠）从该节点 开始的子导航树。这样，用户可以根据需要显示全局或局部导航图。这种导航方法与鱼眼图 是不同的，因为鱼眼图一般只显示当前节点附近（超过阈值的）节点，而全局/局部导航图可 以 同时显示所关心的节点的全图（可以概括显示，如果需要也可以精确显示），显示局部图时其 全图也在显示窗口中，只不过大部分都概括或折叠了。如果仔细观察，这两种导航方法之间 还有其他不同之处。
5 自动超链接技术
5.1 自动产生超文本链的方法
在互联网世界里，Web服务器和页面很多，采用人工方法建立导航图不很方便，往往采用自 动产生超文本链的导航技术。此处介绍一个基于语义相似性的超文本链的自动生成方法[9] 。
先引入词法链的概念。词法链是一个文本中语义上相关的词的序列。例如，一个文本中如 果包含apple和fruit，它们就会出现在同一个词法链中，因为apple是一种fruit。该方法需 要先建立词汇网数据库(WordNet)，该库由同义词集合(synset)组成，每个synset包含一个 或多个有相同或相近意义的词，一个词可以出现在多个synset中。根据synset之间的相互关 系，一些synset之间可被链接起来。
synset之间的链有三种方向：向上链（又称上链）对应概括，例如，从apple到fruit的上链 表示fruit比apple更具一般性，即apple是一种fruit；向下链（又称下链）对应特殊性，例如 ，从fruit到apple的下链表示fruit中包括一种特定的apple；水平链说明链接synset的意义 ， 例如，WordNet中的ANTONYMY关系可用水平链表示。
词与词之间的链有三种：特强链、强链和正常链，它们分别表示三种关系。特强链只存在 于同一个词的副本之间。在同一个synset中的词（即同义词）之间存在强链，例如图2(a)的pe rson和someone；在synset之间有简单的水平链的词之间也有强链，例如图2(b)中的success or和predecessor；使synset之间的单词有简单的IS-A或INCLUDES关系的也有强链，例如图2 (c)中的private school和school。如果两个词所在的synset之间具有允许长度的路径时（一 般允许路径长度为4），这两个词之间存在正常链。图3给出了apple和carrot之间的正常关系 链 。
有了synset和链的叙述以后，就可以用它们自动产生超链。以建立文档的超链为例，首先 需要把文档分成各个部分，假设按其自然表达功能划分为段，把划分后得到的段作为超文本 中的节点。然后，把各个段中具有实际意义的词（或词组）划分到相应的词法链中，并标记这 些词法链中各个单词在该文档所有的段中出现的次数。另外，还要求出每个段中涉及的各个 词法链编号的集合。定义段p中词法链c的密度为d[,c,p]=W[,c,p]/W[,p]，其中W[,c,p]是词法链c 中的单词在段p中出现的次数，W[,p]是p中有内容单词的数目。对所有的段计算各个词法链 的密度，可以得到相应的密度表。由于一个文档的某些部分相关时，这些部分将趋向于包含 同样的词法链。因此，通过密度表可以计算出各段（节点）之间的相似性，相似性较大的节点 之间应建立超链。使用相应的方法，可以计算链的相似性，从中得出两个文档之间的相关 性，决定两文档之间是否需要建立超链。
5.2 超文本结构的优化
5.1介绍了利用已有文档中所蕴涵的语义相似性建立超文本链的方法。对于已经建立了超文 本 页面网络的系统应做什么工作呢？对导航来说主要是页面超链的优化问题。
优化最简单的方法是手工调整超文本链，这当然不是最佳的。文献[10]介绍了一种利用页 面的流行性调整Web页面的链接结构，是系统获得更好的访问效果的方法。
假设系统中的Web页面按树型结构链接（如果不是树结构可以按4.2中或其他方法转化为树） ，为了计算页面的流行性，需要引入几个参数：AA表示页面的绝对访问次数；RA表示页面的 相对访问次数；PT表示平均页面时间（一个用户在一个特定页面停留的时间）；UT表示平均用 户时间（一个用户在服务器上每次从进站到出站用多长时间）；NP表示平均页面次数（一个用 户每次从进站到出站访问了多少不同的页面）；a表示系数，并且定义RA=a*AA；d表示页面深 度（从主页，也就是从树根到页面间路径中的边数）；n表示具有相同深度的页面数目；r表示 页面被链接数（从该服务器到此页面的超链数）。
由于页面i的系数a[,i]与d[,i]、n[,i]和r[,i]有关，可以假设a[,i]=F(d[,i]，n[,i]，1/ r[,i])。F的设定主要基于这样的考虑：页面的深度能降低页面的流行性，故系数a与页面深 度d成正比；如果同一深度的页面越多，一个被浏览了的页面就越有流行价值，故a与页面所 在深度的页面数n成正比；从其他页面链接到本页面的超链越多，该页面被访问的机会也越 大，这可能不是页面的流行性产生的，所以a与链接到本页面的超链数r成反比。最简单时， 可简化F为a[,i]=d[,i]+n[,i]/r[,i]。假设根据运行日志文件已知一段时间内页面的AA，用 户在各个页面浏览的时间等运行数据以及d[,i]，n[,i]和r[,i]等基础数据，就可以计算出 每个节点的RA、PT等值。构造一个节点交换算法，对树中所有有父子关系的节点对比较它们 的PT值，如果父节点的PT值小，则交换它们的位置，直到所有的父节点的PT值都比其子孙节 点 的PT值大或相等为止。显然，把用户比较喜欢浏览的页面放到深度较浅的地方更能吸引用户 驻留在该服务器的页面上。文献[10]的实验已经验证了这一结论。
5.3 超媒体导航方法
5.1自动建立超链是基于对文本的语义相似性的研究进行的，5.2的讨论对所有的超媒体页 面都有效，因为它不涉及页面的内容，只是根据页面被访问的次数、时间等统计信息计算页 面的流行性，由此调整各个页面在树结构中的深度，使比较流行的页面放在较浅的层次上。
对于一般的超媒体数据应如何处理导航问题呢？文献[11]叙述了视频在时间和空间上的制作 和导航的方法。
该文提出的超视频模型的语法由镜头(scene)、故事序列(narrative sequence)、导航(nav igation)、链接机会(link opportunity)和导航桥(navigational bridge)组成。其中的镜 头是超视频的最小单位，故事序列表示通过链接一组视频镜头得到的一条路径，图3是两个 故事序列共享同一个镜头的例子。为了导航故事序列之内和之间的超视频镜头需要基于时间 的链接机会，而传统的超链只隐含在静态关联中。这种（时间或空间）动态链接机会的出现， 促使系统必须基于当前镜头的内容并提供与镜头相关的导航路径。这种链接机会可分成时间 机会、时间超文本和空间机会几种。导航桥能提供从视频镜头到视频镜头过渡的连续镜头， 使一个故事序列内镜头的结构达到和谐。为了制作和导航超视频，系统还提供了超视频引擎 、交互制作工具、镜头描述器等功能，使用户能利用已有的超视频镜头和超文本等素材，按 自己的愿望制作故事序列，使用导航桥和按时间、空间等动态方式导航。
6 Web导航技术的发展展望
Web导航技术虽然有很大的发展，但与人们的期望值还差得很远。例如，网络导航的查准率 很差，更不用说查全率了，导航自动化技术还无法满足网上要求，智能化水平不高等。可以 预测，Web页面导航技术将从以下几个方面发展：
(1)自动导航技术研究。现在的自动导航技术，无论是导航图导航还是超链自动生成技术， 其实际导航效果与用户期望值还有距离，明显的是查准率很差，往往把许多意思相近（也有 一些根本与被查内容无关）的内容全提交给用户，甚至经常把许多重复的内容提交给用户（出 现很高的查重率），使用户无法知道这一大堆信息中哪些是主要的，浪费了大量的浏览、下 载时间，实际上导致了新的迷路现象。寻找比较准确的Web自动导航办法将是未来最重要的 课题之一，其难度也是很大的。
(2)搜索引擎研究。主要有研究能充分表达用户查询要求的查询语言，索引数据库的组织和 管理，提高检索的查准率以及信息的自动加工等[5]。此外，去重功能也是提高检索性能的 必要条件之一[6]。
(3)优化超链结构。对已有的Web页面的超链进行分析、统计和重组的技术，通过超链的优 化重组，提高页面的被浏览率。
(4)Web数据库技术研究。散放在各个Web站点的WWW页面实际上已经构成了分布式超媒体数 据库。这种数据库的数据模型（数据结构、数据操作和完整性约束）的研究十分必要，特别需 要商品化的成型产品。此外，把原来已有的数据库移植到Web上也是十分有意义的课题，需 要一些成熟、有效的技术和方法[12，13]。
(5)智能化页面研究。把Web技术与人工智能技术相结合，可开发出具有智能的Web站点或页 面以及能提供智能化检索的工具[14]，为用户提供更高级的服务。
(6)Web数据挖掘技术。Web具有几乎可称作“无限世界”的资源，在这些资源上进行数据挖 掘一定能发现许多知识。当然，Web数据挖掘是一个很难的新课题，已经引起了各方的重视 。目前，基于文本的Web数据挖掘研究得比较多[15～17]，对其他媒体的挖掘技术研究十分 具有诱惑力。
通过本文的研究，可以看到Web页面导航是一个非常有意义的课题，其研究成果十分丰富， 也取得了一定的实用效果。可以预计在未来一段时间内，Web导航技术仍然会有很大的发展 ， 必将取得突破性进展。