（计算机科学与技术专业论文）网络信息自适应发布模型及算法的研究.pdf

摘要 摘要：随着当今社会进入网络化信息化时代，网络信息作为一种新兴的信息资源 而急剥增长。在其发布过程中，由于信息发布硬件设备的不同，各终端承载能力 的差异，会导致相同信息在不同终端上可能无法以适当的形式表示出来，甚至不 能准确地表达出其原意，而不利于人们识别。若运用适当的算法处理信息，使其 以层次化结构表示，便可以达到信息对终端设备种类和承载能力的自适应发布， 从而大大减少信息的失真程度。 基于上述问题，本文设计并提出了网络信息皇适应发奄的简化模型与一系列 算法，将其优化，并运用实验证明其可行性。 本文首先根据网络信息重构的基本概念，结合实际需要，提燃信息翻适应发 布的简化模型，即层次化模型，并针对该模型进行叶结点覆盖集分析，提出初步 的最优解算法。继而从时间和空间复杂度方面对最优解算法进行分析，采用动态 规划原理为理论依据，对初步的最优解算法进行适当改进，并提出基于动念规划 的改进算法。然后从解决方案的质量和可行性角度出发，提出次优解算法，并将 相关算法进行比较。最后麸实际应用惫度出发，将层次化模型从二叉树表示扩展 成为n 叉树表示，并结合x h t m l ，提出正式的语法定义，同时扩展上述算法并进 行研究比对。 本文提出的网络信息自适应发布的简化模型与算法，可以有效地使网络信息 根据不同终端需求来实现自适应的发布。能够对网络信息资源进行有效提炼，并 以适当的形式表示，尽可能减少信息失真程度，从而达到信息有效传递和交流的 目的。 关键词：圈络信息：融适应；层次化模型；叶结点覆盖集 分类号：t p 3 9 3 4 a b s t r a c t a b s t r a c t ：w i t ht h es o c i e t ye n t e r i n gt h ee r ao fn e t w o r ka n di n f o r m a t i o n ，a san o v e l k i n d o fi n f o r m a t i o nr e s o u r c e , t h ew e bi n f o r m a t i o ni s g r o w i n gr a p i d l y d u r i n gi t s p r o c e d u r eo fi s s u a n c e ，d u et ot h ed i f f e r e n c eo fh a r d w a r ee n v i r o n m e n tc a p a c i t ya n d v a r i o u st e r m i n a ll o a d s ，t h es a m ei n f o r m a t i o nm a yn o tb ee x p r e s s e di na p r o p e rf o r mo n d i f f e r e n t t e r m i n a l s ，r e s u l t i n gi n i n c o r r e c te x p r e s s i o no fi t s o r i g i n a lm e a n i n ga n d p e o p l e sm i s u n d e r s t a n d i n g h o w e v e r , t h e r ei so n ep o s s i b l ea p p r o a c ht oi n f o r m a t i o n s a u t o m a t i ca d a p t a t i o nt od i f f e r e n tk i n d sa n dc a p a c i t yo ft e r m i n a l sa n dr e d u c t i o no f i n f o r m a t i o n si n c o r r e c tp r e s e n t a t i o n , t h a ti s ，t oe m p l o yp r o p e ra l g o r i t h mt op r o c e s st h e i n f o r m a t i o na n dd e s c r i b ei ti nah i e r a r c h i c a ls t r u c t u r e b a s e do nt h ep r o b l e m sa b o v e ，t h i st h e s i sp r o p o s e sa n d d e v e l o p sas i m p l i f i e dm o d e l f o rt h ea u t o a d a p t e di s s u a n c eo fw e bi n f o r m a t i o na n d c o r r e s p o n d i n ga l g o r i t h m s ， o p t i m i z e st h e m ，a n dp r o v e st h e i rf e a s i b i l i t yw i t he x p e r i m e n t s a c c o r d i n gt ot h eb a s i cc o n c e p t so fw e bi n f o r m a t i o nr e c o n s t r u c t i o na n dp r a c t i c a l r e q u i r e m e n t ，t h i st h e s i s f i r s tp r o p o s e st h e s i m p l i f i e dm o d e lf o rt h ea u t o a d a p t e d i s s u a n c eo fw e bi n f o r m a t i o n ，v i z ，t h eh i e r a r c h i c a lm o d e l ，a n a l y z e st h ec o v e rs e t so ft h e m o d e l ，a n dd e s i g n st h ec r u d ea l g o r i t h mf o ro p t i m a ls o l u t i o n s a f t e rt h a t ，t h et h e s i s a n a l y z e st h ea l g o r i t h mf o ro p t i m a ls o l u t i o n sw i t hr e s p e c tt ot i m ea n ds p a c ec o m p l e x i t y a n di m p r o v e si tb a s e do nt h et h e o r yo fd y n a m i cp l a n n i n g ，t h e ni t b r i n g so u tt h e a l g o r i t h mf o rs e c o n d b e s ts o l u t i o n sf r o mt h ep e r s p e c t i v eo fq u a l i t yo fs o l u t i o n sa n d t h e i rv i a b i l i t y , a n dc o m p a r e st h o s er e l e v a n ta l g o r i t h m s f i n a l l y , c o n s i d e r i n gp r a c t i c a l r e q u i r e m e n t ，i te x t e n d st h eh i e r a r c h i c a lm o d e lf r o mb i n a r yt r e e st on a r yt r e e s ，d e f i n e s t h ef o r m a ls y n t a xo fa u t o - a d a p t a t i o nw e bl a n g u a g eb a s e do nx h t m l ，a n dc o m p a r e si t w i t ht h et h e o r e t i c a lr e s u l t s t h es i m p l i f i e dm o d e lf o ra u t o a d a p t a t i o no fw e bi n f o r m a t i o ni s s u a n c ed e v e l o p e d i n t h i st h e s i sc a nr e a l i z et h ep r a c t i c a ln e e do fw e bi n f o r m a t i o nt ob e i s s u e d a u t o a d a p t i v e l ya c c o r d i n gt od i f f e r e n tt e r m i n a l s i tc a nd i s t i l lt h ew e bi n f o r m a t i o n r e s o u r c ee f f e c t i v e l ya n de x p r e s si ti na p p r o p r i a t ef o r m 。 k e y w o r d s ：w 曲i n f o r m a t i o n ；a u t o a d a p t a t i o n ；h i e r a r c h i c a lm o d e l ；l e a f - n o d e c o v e rs e t c i a s s n o ：t p 3 9 3 4 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取德的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书 磊使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中律 了明确的说明并表示了谢意。 学位论文作者签名；着榕 签字隧期： 2 护矽年厂月侈瑟 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 提供阅览服务，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。 同意学校向圈家有关部f 1 或机构送交论文酶复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：荔 导师签名： 签字目期：2 节年夕冀f 踟 签字匿期： 娥参 撕海芒戮t 岛鼠 致谢 首先，我要衷心感谢我的导师魏慧琴副教授。在读研期间，魏老师不但指导 我完成各项研究，而且在生活中给予我很大的帮助。在学习生活中，魏老师宽厚 的为人、渊蹲的知识、，程谨求实的和追求创新的治学态度使我受益匪浅，使我获 得宝贵的精神财富。本论文的工作是在我的导师魏慧琴副教授的悉心指导下完成 的，她的谆谆教诲使我在各个方面的素质得到檄大提高，在此衷心感谢两年来魏 老师对我无微不至的关心和指导。 在这里我还要感谢贾卓生老师，贾老师对予我的科研工作和论文都提出了许 多的宝贵意见，在此表示衷心的感谢。同时，贾老师在平时的学习和实验室项目 的歼发中给我提出了很多指导性建议，使我能够更好地完成各项任务。唐宏老师、 高勃老师在项目中也给予我很大的帮助，使我动手能力和专业知识的应用能力得 到了很大的提高，在此向各位老师表示深深的谢意。 在撰写论文期阉，周筠同学霹我的研究工作给予了热情帮助。弱时，特别感 谢我的哥哥，英国杜伦大学的罗晨光，在日常工作及课题研究过程中，为我提供 了一系歹l 的建议，并向我推荐了很多很有建设意义的书籍，对我研究工作起到了 至关重要的作用。在此向他们表达我的感激之情。 最后，我要感谢我的父母和家人，他们多年来默默付出给予我继续学习的机 会，从精神到物质一直支持着我，我能够顺利完成学业，与他们的理解和支持密 不可分，在这里对他们致以最崇高的敬意和感谢。 序 随着互联网的不断发展，信息资源的交流和共享更加便捷，网络信息作为一 种新兴的信患资源，在人们日常生产和生活中发挥着重要的作用，为人们提供了 一个更为广阔的信息检索和利用空间。但其带来巨大便利的同时，网络信息资源 又存在无序、优劣混杂，缺乏统一的组织与控制的缺点。随着当今社会网络纯信 息化的程度不断提高，网络信息资源的急剧增长，使其自身缺乏有效组织且信息 检准率较低，资源分数，缺乏深层次的开发等缺点日益明显。尤其在不两终端设 备查找使用过程中，面临着数量大、类型多、分散性、信息质量不稳定等特点， 只有对其进行积极有效的再次组织和开发，才能带来真正有序的信息空间，实现 信息资源效用的最大化。 由于各种信息发布硬件设备的能力不同，相同的信息在不同的终端上可能无 法以适当的形式表示搬来，甚至不能乖确地反映原意，丽不便被人们识剐。如果 信息能够以层次化的结构的形式进行自适应发布，就可以根据终端设备的种类和 承载能力，以适当的形式来表示，放藤大大减少其失真程度。本选题“瓣络信息 自适应发布模型及算法的研究将就信息自适应发布的问题以及对该问题求解等 进行研究讨论。 1 1引言 1 绪论 随着网络技术的迅速发展和普及，互联网成为一个庞大的分布异构资源库， 从网络中获取知识已经成为入们r 常学习、工作和生活中不可或缺的一部分。互 联网的广泛应用与迅猛发展，使信息资源的交流和共享更加便捷。 网终信息资源有汉下特点：分散性、互动性、潜在性、信息质量不稳定性。 其应用现状存在很多问题：一是网络信息资源缺乏有效组织；二是信息检准率较 低，网上信息资源分散、无序现象加测；三是网络信息资源缺乏深层次的开发。 尤其在不同终端设备查找使用过程中，面临着数量大、类型多、分散性、信息质 量不稳定等特点，只有对其进行积极有效地深层次组织和开发，才能带来真正有 序的信息空间，实现信息资源利用的最大化。 同时随着各种信息发布终端的出现，一个极其重要且现实的问题初现端倪： 出于各种硬件设备的承载能力不同，相同信息在不同终端上可能因设备差异两无 法以适当形式表达，甚至不能正确地反映信息原意，从而对人们识别信息造成巨 大的不便。因丽，各类信息缝蚕在各种终端上正确表示和发布邑成为人们进行信 息交流过程中至关重要的问题，同时也成为信息高速发展中的“瓶颈问题”。 例如一个网页，在计算机的屏幕上可以几近完美地发布和显示，但在一个屏 幕相对较小的p d a ( p e r s o n a ld i g i t a la s s i s t a n t ) 上显示效果就不那么尽如人意，浏 览者必须不断拖动屏幕四周的滚动条力能浏览全部内容。若将终端设备换成手机 就更不理想：由于屏幕大小，分辫率和彩色数隧的限制，该网页所包含的信息则 可能不能正确地表示出来，即使文字能够币常地显示，浏览全部信息对于有限的 手机屏幕来说也是一种负担。 这一切都是由于网页不能针对发布信息的终端设备进行自适应发柿而导致 的。假设使用上述三种设备浏览另一个有设备国适应能力的网页，当用户通过计 算机网络向该网页发出访问请求时，网页将会以最完整最清晰的形式进行发布， 甚至会自动识别用户终端的屏幕分辨率，并据此做出必要的调整；如果用户终端 是台p d a ，则网页会相应地简化发匆内容，例如压缩文字容量，降低图片数目 和质量，等等；如果用户采用手机进行浏览，则网页只需发布相关文字，包括对 原来网页中文字於浓缩和圈片的文本搦述以及说臻等，给用户以阏页全貌的概览 【l 】。 结合上述事实，若能使信息通过臼适应的网页进行发布，就可以根据终端设 备的种类和承载能力，以适当的形式表示，从丽大大减少其失真程度，并有效地 组织、管理和应用信息资源。本选题“网络信息自适应发布模型及算法的研究” 将就信息自适应发布的问题以及求解方法等进行深入研究讨论。 1 2 本文研究背景 目日 ，国内外针对不同终端的网络信息自适应发布往往通过改造硬件设备来 实现，但并未有统一的标准。现在的研究也有通过建立智能信息亿网络来屏蔽潮 络的复杂性。通过把数据、视频、语音、安全、存储等各种企业的需求集成到一 个设备中，柬解决管理的难度。 现在使用较为广泛的技术是通过i pn g n ( n e x tg e n e r a t i o nn e t w o r k ) 分段实施， 包括建立智能网络，然后由服务感知型网络提供应用感知型服务。这种基于i p 的 智能n g n 为电信运营商提供了新的商枧，邵通过任意类型的连接提供先进的个性 化多媒体服务。由于智能i p 在应用、服务和网络三个网络层次上提供融合，因而 将成为实现n g n 转变的技术基础，但投入成本巨大，并不适合普通用户使用【2 】。 然而，专门针对网络信息发布进行的研究相对较少。由此可见，目前的网络 信息发布技术并不能很好地满足当今数字化时代各异终端设备的广泛应用以及需 求。因此，本论文将此作为研究课题具有创新思想和实际意义。 本选题是基于笔者先前发表的网络信息自适应发靠的p l c h 二叉树模型 等一系列楣关论文的基础上，迸一步深入研究并发掘完善。本文从网络信息资源 角度出发，针对网络信息自适应发布问题进行讨论，建立信息层次化模型并进行 分析研究，根据终端对信息承载能力的不同要求，提出并改进檩关算法，使其麓 够更为有效地针对网络信息资源进行提炼，广泛应用于根据终端设备的种类以及 承载能力差异面对网络信息资源进行的自适应性发布，尽量减少信息失真程度， 从而达到便于信息传递和交流的目的。 1 3本文主要研究内容 本文就网络信息融适应发布的问题进行讨论，主要工作氢含以下几个方面： 1 根据网络信息重构的基本概念，结合现实需要，提出信息自适应发布的简 化模型，即信息层次化模型。在对信息发赢问题研究的基础上，针对层次化模型 进行叶结点覆盖集分析，提出该问题的求解方案。 2 提文基于直接套找的最优解算法。该算法具有较强的理论研究意义。 2 3 从算法复杂度以及实用性角度对最优解算法进行分析，使用动态规划原理， 对最优解算法进行适当改进，提出改进最优解算法，通过实验证明该算法在应用 中有着良好的表现。 4 从解决方案的质量和可行性角度出发，提出次优解算法，并通过实验分析， 对其与先前求最优解的算法进行比较，讨论各个算法的优缺点。在应用过程中， 可根据实际需要，选择不同算法进行操作。 5 针对实际需要，将层次化模型进霉亍扩展，与x h t m l 结合，提出正式的语 法定义，对上述三种算法的实际应用性进行研究，通过对网页信息自适应发布的 实验，发现层次化模型以及算法在网络信息发奄中有着较强的适媚性。 圭4 本文的组织与结构 本文由七章内容和参考文献构成。七章的内容安排分别如下： 第一章：绪论。 介绍本选题的研究背景、论文所做的主要工作、研究内容以及全文的组织结 构。 第二章：网络信息综述。 通过已有概念，对网络信息进彳亍全面介绍，主要讨论现有的网络信息分类、 网络信息发稚功能、组织方式以及网络信息资源的特点等综合情况。 第三章：网络信息自适应发布的基本理论与简化模型。 粳据信息资源重构与自适应发毒的基本概念，对发布问题进行详细分析，将 其抽象为具体数学问题表达，提出信息自适应发布的简化模型，即信息层次化模 型。同时针对该模型进行研究，以叶结点覆盖集分析的方式对信患自适应发布闻 题进行简化求解。 第四章：算法求解与改进。 通过对先前的模型进行分析，提出最优解算法，通过对最优解算法的深入研 究，结合动态规划原理，对最优解算法改进，并提出改进算法。从解决方案的质 量和时间复杂度角度溅发考虑，提出次优解算法。并对上述算法进行分析比对。 第五章：层次化模型的扩展。 从实际疲用熊度艇发，将宠翦的层次化模型由二叉瓣扩展成为n 一义树模型， 并根据该模烈，对直接查找最优解算法，动态规划最优解算法以及次优解算法进 行分析毙对。 第六章：层次化模型关于x h t m l 的适应性扩展。 根据x h t m l 的特点，将层次模型应用到x h t m l ，并提出正式的语法定义， 3 对其进行执行实例验证。 第七章：结论。 对本文的工作进行总结和概括，并对未来所需开展的工作进行展望。 4 2 网络信息综述 网络在人类信息交流与沟通过程中起着至关重要的作用，其突出贡献在于将 以往各行其道的文本信息、图像信息、声音信息和多媒体信息汇集在同媒体f 网 络) 上，人们可以同时查询各种不同来源、不同状态、不同内容的信息。 网络信息资源与传统载体的信息资源有着本质区别，它是以数据的形式将文 字、图像、声音、动画等多种形式的信息存放在光磁等非印刷质载体中，通过网 络通信传播并在计算机上显现出来的信息资源。它将原本相互独立、分布于世界 各地的数据库、信息中心、文献中心等联结在一起，形成一个内容与结构全新的 信息整体p j 。 网络信息资源的主体是能够在互联网上传播和交流的信息集合，并特指其中 能满足人们信息需求，在互联网上可见的信息赘源部分。这部分信息集合是网络 信息资源管理的直接对象。因此，网络信息资源可以理解为以阏络为纽带联结起 来的信息资源和以网络为主要存贮、传播、交流方式的信息资源，是通过计算机 网络可以利用薛各种信息资源的总和。 从信息资源建设的角度出发，网络信息资源不再是一个物理概念，也不再是 相互分割的独立存在的实体，瓶是一个跨国家、跨地区的信息空间。其瓷源和服 务大大超出传统意义上的馆藏文献库或独立的数据库系统，它是与全国乃至全球 相互连接的信息资源网络系统，为人们建立了快速、便捷、有效的联系，提供了 崭新的信息交流环境淤】。 2 1网络信息的分类及特点 2 1 1 网络信息分类 网络信患的分类从基于实践的角度出发，目前国内外比较流行的分类方案基 本分为以下种类【5 】： 1 按信息的表现形态，将网络信息瓷源分为文本信息、图像信息、声音信息 以及多媒体信息。 2 按信息交流的方式，将网络信息资源分为非正式出版信息、半f 式出版信 息耪诿式出舨信息。 其中正式出版信息又分为一次出版信息、二次出版信息和三次出版信息。 5 次出版信息包括电子图书、电子期刊、电子报纸等；二次出版信息包括搜索引擎、 检索数据露、网络导航等；三次出版信息包括网络述评、参考数据库、网站推荐 等。 3 基于传统的信息资源分类体系，将与之对应的网络信息资源划分为图书馆 馆藏目录、电子书刊、参考工具书、数据库等。 4 按信息的组织存放方式，网络信息资源划分成邮件型、交互型、公告牌型、 广播型、图书馆型、书蠢型等。 5 按信息资源的时效性分类，可将其分为电子报纸、动态信息、全文信息和 书謦数据库等睡大类。 6 按文件组织影式分为自由文本和规范文本两大类。 2 1 2 网络信息资源的特点 网络信息资源具有下列特点f 3 】豳： 1 存储数字化 信息资源出纸张上文字变为磁性会质上的电磁信号或者光介质上的光信怠， 是信息的存储和传递。通过该处理过程，使信息查询更加方便，而且所存储的信 息密度高，容量大，可以无损耗地被重复使用。以数字化形式存在的信息，既可 以在计算机内高速处理，又可以通过信息网络进行远距离传送。 2 表现形式多样化 传统信息资源主要是以文字或数字形式表现出来的信息，两网络信息资源则 可以是文本，图像，音频，视频，软件，数据库等多种形式存在的。涉及领域从 经济，科研，教育，艺术，到具体的行业和个体，包含酌文献类型从电子报刊， 电子工具书，商业信息，新闻报道，书目数据库，文献信息索引到统计数据，图 表，电子地燃等。 3 以网络为传播媒介 传统的信息存储载体为纸张，磁带，磁盘，而在网络时代，信息的存在是以 嘲络为载体，以虚拟化的姿势状态展示的。人们得到的是尉络上的信息，而不必 过问信息是存储在磁盘上还是磁带上的，体现了网络资源的社会性和共享性。 4 。数量匿大，增长迅速 中国互联网络信息中一i l , ( c n n i c ) - - 年两次发布的中因互联网络发展状况统计 报告，全面反映和分析了中豳互联阏络发展状况，以其权威性著称。2 0 0 9 年0 1 月1 3 日，c n n i c 在北京发布了第2 3 次中国互联网络发展状况统计报告。报告 显示，我国网民数达到2 9 8 亿，我国互联网普及率以2 2 6 的比例首次超过2 1 9 6 的全球平均水平：宽带网民数达到2 7 亿，国家c n 域名数达1 3 5 7 2 万，三项指标 继续稳居世界排名第一，显示出中国互联网的规模价值范在同益放大f 死。 5 传播方式的动态性 网络环境下，信息的传递和反馈快速灵敏，具有动态性和实时性等特点。信 息在网络中的流动毪非常迅速，电子流取代纸张和邮政的物流，加上电磁信号和 卫星通讯技术的充分运用，上传到网上的任何信息资源，都只需要短短的数秒时 问就能传递到世界各地的每一个角落。 6 信息源复杂 网络的共享性与开放性使得人人都可以在互联网上获取和存放信息，由予没 有质量控制和管理机制，这些信息没有经过严格编辑和整理，良莠不齐，各种不 良和无用的信息大量充斥在网络上，形成了一个纷繁复杂的信息世界，给用户选 择，利用网络信息带来了障碍。 2 2网络信息发布功能 信息在阙上发蠢，可以理解力是一种网上戡版，利用w e b 技术，使得这种意 义上的出版比传统意义上的出版容易得多，任何个人或组织只要在网上拥有一席 之地就可以内网上发布信息，这秘信息少到一句话、二幅图片，或多到成百上千 g b 的庞大数据库，均可称为w e b 出版。这种出版通常也拥有传统出版概念的大 多数权力和义务瞵】。 目前的w e b 出版可以分为两种形式，一种是应用h t m l 语言在网上建立一个 站点( w e b s i t e ) 并发布若干页h t m l 文件或文本型数据库。文件内部可以看作h t m l 链接，亦可以从文件漆链接到外部酶其他站点或其他文锋，如个人主页、机构篱 介、事件描述和现期报刊等均可用这种形式发布。由于这种发布方案在各种技术 上实现起来比较容易，所以w e b 的网上信息量以空前的速度和数量迅速膨胀。 另一类网络发布则较为复杂，要求的设备和技术条件都较高，通常馥l 具有一 定实力的机构所建。这种形式往往是通过服务器扩展程序( 网关c g i ，a p i 以及环 境变量滋明、模板程序) 将w e b 技术系统与传统的结构型数据库系统连接起来。用 户通过浏览器以h t m l 格式向系统作信息检索提问，数据库检索结果向用户以 h t m l 格式传回，遥过服务器扩展程序转换。 因此，传统上按w e b 发布的方式，其产生的信息就可粗略地划分为简单h t m l 文件型和较为复杂的h t m l 数据库型鼹大类雕潮。 2 3网络信息组织方式 7 所谓网络信息的组织是指人们根据网络信息本身的特点( 或属性) 运用各种工 具和方法，对网络信息进行加工、整理、排列、组合，使之有序化、系统化、规 律化，从而有利于网络信息资源的存储、传播、利用，以满足人们对网络信息的 需求。网络信息的完善组织是一项长期而又不断演进的需求。 根据网络信息应用方式的不同，主要有以下几种方式陶【珏】： 1 文件方式 文件方式是瘸络资源比较原始的组织方式，它可以存储大璧菲结构化信息。 优点是简单便捷，缺点是数据冗余，文件之间缺乏联系，难以有效控制结构复杂 的信意，只能是信息资源管理的辅助形式。 2 主题树方式 主题树方式采用“主题子主题 方式把网络信息资源分成若干范畴，每个主 题范畴再分为若干子主题。此种方式提供了一个基于树型浏览的简单易用的网络 信息检索与利用界面，具有较强的专题性和科学性，可以进行任一层次的检索。 但利用主题树方式必须事先建立一套完整的主题目录分类体系，用户需要对分类 体系有一定的认识，不宜于建立大型的综合性网络资源系统，仅适于建立专业性 或示范性的网络信息瓷源体系。 3 数据库方式 数据库系统能够有效地克服文件系统缺陷，提供对数据更高级、更有效的管 理，它将要处理的数据经合理分类和旒范化处理后，以记录的形式存储于计算机 中。关系型数据库从规范化的数据中抽取出相应的字段建立表，以“主键”的形 式束连接各表。 利用数据库技术组织信息资源可以极大地提高信息的有序性、完整性、可理 解性和安全性，数据冗余嗳显减少，实现了数攥共享，为用户提供方便的客户接 口，是目前网络信息凌源组织的主要形式。 但是数据库方式对非结构化信息的处理困难较大，更重要的是它不能提供数 据信息之间的知识关联，现有的关系数据库( r d 8 ) 和面向对象数据库( o o d b ) 在不 同程度上都存在对相互联系的多媒体信息缺乏表达能力的问题，无法有效处理结 构目益复杂的信息单元，同时缺乏直观性和入机交互性1 1 2 1 。 4 超媒体方式 超媒体( h y p e rm e d i a ) 方式是超文本( h y p e r t e x t ) 与多媒体技术的结合，以 超链接( h y p e rl i n k ) 的方式将位于不同页面上的文字、表格、声音、图像、视频等 多媒体信息以超文本形式组织起来。 以超媒体技术组织信息，可使信息系统得到任意收缩，具有良好的包容性和 可扩充性；可突破传统信息组织的线性结构，灾现文本内外的信息组合，熊够充 8 分表达各种信息之间内在的联系；超越了媒体类型对信息组织与检索的限制，避 免了检索语言的复杂性。由于超媒体技术的上述优势，它已成为互联网上占主流 地位的信息组织方式。超媒体技术主要应用子办公自动化系统、大型文献资料信 息库以及综合数据库系统。 但是，当礴络过于庞大时，使用超媒体技术进行信息资源的有序化整理和组 织就有较大的难度，用户难以迅速而准确地定位，导致“迷航现象。 综合分析数据库技术和超媒体技术的优缺点，较为理想的网络信息资源组织 方式是数据库技术和超媒体技术的结合，建立新型的数据库系统。这样既可以有 效解决关系数据库对多媒体信息的表达能力，又可以您决超文本系统的存储管理 等问题。 5 大众标注方式 大众标注是w e b 2 0 环境下信息组织的一种新的理念，也是- f - j 新兴的技术方 法。具体来说就是网络资源的利用者为了便于自己或他人获取和利用某一数字资 源，丽对该资源赋予标签( t a g ) 的过程或结采。髑标签侔为元数据，代替关键词的 功能，是大众标注组织网络信息的原理。另外，可将标注与其他资源描述、组织 工具或方法进行整合，共| 司完成对资源的组织和检索。 数字和网络环境为标注这一古老而传统的事物赋予了新的生命力，使之具有 使用成本低、篱单、可扩展等优势，但也存在标签滥用、标准缺乏、信息检索效 率低等问题，只有关注并有效地解决目前标注所存在的问题，才能更有效地实现 标注的价值。 2 4信息资源层次 在组织模式方面，按信息资源层次划分可以分为一次网络信息，二次网络信 息，以及多次网络信息f l 引。 1 一次网络信息 所谓网络一次网络信息，是指网上传输的原始数字化信息资源，是没有被加 工处理的第一手信息资源。一次信息柬源广泛、种类繁多、内容复杂。这些信息 的组织模式通常有文件组织模式、超文本超媒体模式、网站网页组织模式、非结 构化数据库组织模式。 1 1 以超文本组织方式的众多互联网信息 超文本技术是一种新墅的信息组织方式。该技术的特薤就是将信息单元按其 之间的内在联系组织成一个有机统一体，它表现为状的非线性结构。信息表达形 式的多种多样，超文本信息可以是文字、图形、图像、声音、动燕等。可在网上 9 从一个站点链接到其他站点，从一个网页链接到其他网页都是一种基于超文本组 织方式和信息资源。常用的互联网信息组织的语言工具有h t m l ( h y p e rt e x t m a r k u pl a n g u a g e ，超文本置标语言) 、x m l ( e x t e n s i b l em a r k u pl a n g u a g e ，可扩展 置标语言) 、x h t m l ( e x t e n s i b l eh y p e rt e x tm a r k u pl a n g u a g e , 可扩展超文本标记语 言) 等。 2 ) 以f t p 文件传输协议方式管理和组织的网络文件型信息 如上所述，互联网上大量存在的f t p 文件，就是以其独特的文件系统来管理 和组织的网络信息资源。f t p 文件传输协议就是用来帮助用户利用那些以文件形 式保存和组织的信息资源，此类信息资源可以是程序、豳形、匿像、图表、音频、 视频等非结构化信息。 3 1 以规范化数据来进行管理的数据库型信息 数据库型信息在网络上出现的数量庞大，传统的各类结构型数据信息纷纷在 网上发布。现在更多的网站在站内也设立自己的动态数据库，许多有价值的信息 正因为“隐藏”在数据库墨，方便用户再次使用时可以获取其所需的“深层”信 息。 钠j # 结构他数据库组织模式 随着网络技术的迅速发展，半结构化数据和非结构化数据在网络上得以大量 的应用，非结构化数据库可根据其的特殊性进行存储和管理，在管理机制上超越 了传统结构化关系数据库对于信息采取定长和结构化定义的局限，与w e b 技术结 合，可实现非结构化数据库型信息资源的直接网上发布与全文检索【1 4 】。 2 二次网络信息 一次信息入网后，用户希望快速、高效地从浩如烟海、急剧增长的网上一次 信息中找到所需要的信息。因此产生了对这些信息进行重新组织使之达到初步穿 化的需求。将一次网络信息资源进行描述、揭示、分析和存储后，形成的有序化、 系统化的网络信息资源称之为二次网络信息资源。二次网络信息资源的组织模式 通常有：搜索引擎模式、主题目录组织模式、虚拟图书馆模式、数字图书馆模式f 1 5 】。 1 ) 搜索引擎模式 搜索引擎的出现是为了解决网上用户不断增长的信息需求和网上信息的无序 状态之间的矛盾而产生的，其实质是一种报道、存储网上信息的检索工具，起剑 网络导航的作用。搜索孳| 擎的工作过程是派出“圈页搜索程序 搜索w e b 服务器 信息并进行索引。加入到网页数据库中，对信息进行分类、整理，建立搜索引擎 数据库，通过w e b 服务器端软锋，检索智能代理将用户提闷与数据库记录楣匹配， 根据相关程度为用户提供所需信息。 搜索引擎是一类专门提供信息查询服务的网站。如g o o g l e 、天网、a l t a v i s t a l o 等。其信息组织原理是利用被称作r o b o t ，s p i d e r ，w o r m 等名称的网络搜索机器 人，定期或不定期地在网上自动搜寻网络中公开区域的每一个站点，采集网络信 息资源然后自动对这些资源进行标引、著录，创建一个详尽的w e b 页索引数据库 以供用户进行关键词及其组配检索，当用户通过检索界面进行检索时即会得到含 有相关信息的大量网站涌过所提供的超链接即可访阀这些网站。搜索弓| 擎在一定 程度上避免了用户网络信息浏览的盲目性，而给用户的信息搜索带来很大的便利 1 1 6 1 o 2 ) 主题目录组织模式 主题垦录又可称为匿录式搜索引擎，其组织网络信息资源的方法是将网络信 息资源按照某种事先确定的概念体系分门别类地逐层加以组织，也就是将与各主 题有关的一次网络信息资源的网址和有关描述信息以主题目录的形式组织起来供 用户选择用户先通过浏览的方式层层遍历，直到找到所需信息的线索，再通过信 息线索链扭到相应的网络信息资源。网上许多著名的网络检索工具如y a h o o 、s o h u 、 i n f o s e e k 等都是采用该模式组织信息资源的。 3 ) 指示数据库类信息模式 指示数据库存贮的是有关网上一次信息的网址以及相关信息的播述，即对蹰 上的信息资源进行分类编目。编目人员在对网上信息资源进行组织时，按照_ 定 的格式，对其进行描述，以帮助用户获得和查找。这种方式的优点是每条记录都 经过了严格的选择，具有较强的针对性和较高的可靠性，因此指示数据库常用来 组织专题资源或专用的网上二次信息1 1 7 j 。 4 虚拟图书模式 由于大多数搜索引擎和主题目录都是综合性的，并且还带有商业性质，针对 学术信息的检索的查准率和查全率都难如人愿。因此针对于某一学科的学术信息 组织而言，对一次学术信息进行再次组织的虚拟图书馆应运而生。虚拟图书馆是 组织剐络信息资源的一种有效褥经济的形式。它根据选定的学科领域在庞大的霹 络信息群中对有关的一次网站网页信息进行搜索和收集，并加以鉴定核实，对核 实后的网址进行合理组织，使之成为特定分类的阅链接的信息集合，供用户进行 浏览和检索，弥补了搜索弓| 擎检索结果冗余量过大、检准率不高的不足，有助子 专业用户在本领域中获得“所得即所要的信息。 5 ) 数字图书馆模式 数字图书馆是伴随着计算机技术在图书馆中的应用而出现的，其采用先进的 信息技术对现有的馆藏资源进行数字化、网络化使之成为网终信息资源。并对璃 络信息进行描述和组织。以供用户检索、查询和利用。与传统图书馆相比，数字 图书馆主要应用其信息资源存敬自由化和结构连接化的优势来满足用户曰益增长 的信息需求，为用户提供更周到的服务。由于数字图书馆的资源是对已有的序化 数字化信息进行组织和整理丽得，因此其资源是相对集中、有序规范以及有质量 保证的信息瓷源。 3 多次网络信息 为帮助用户快捷、高效地找到适合自己使用的搜索引擎，主题目录和虚拟图 书馆，以进一步提高检索效率和网络信息资源开发利用水平，可以对二次网络信 息资源进行搜集和再次组织，透过这种方式形成酶信息被称为多次网络信息，。 多次网络信息多用元搜索引擎目录组织模式。元搜索引擎又称为多元搜索引 擎，它与传统搜索引擎的最大区别在予：通过调用多个独立搜索弓| 擎的检索功能 来实现网络信息资源的查询。元搜索引擎一般没有搜索引子的网页搜寻机制，也 没有一个自己独立的索引数据库，它将多个独立搜索引擎集成在一起，并为用户 提供一个统一的检索界面。当用户键入检索提阀词时，系统将该提问提交给多个 独立搜索引任，并对后者返回的结果进行整理，然后反馈给用户 1 8 j 。 元搜索葶| 擎霉录组织模式首先可按搜索弓| 擎曩录模式将所有集中起来的搜索 引擎按类型组织成目录，便于用户选择，再借鉴元搜索引擎的思想针对各类型的 搜索弓| 擎提供统一的检索界面，实现出多个独立搜索引擎的统一检索。 2 5本章小结 本章介绍了网络信息资源的基本概念、分类、特点以及功能和组织方式等相 关内容。针对网络信息数量巨大，信息源复杂等特点，为更好的组织利用信息资 源，满足不同用户的需要，应对其进行重构，以便网络信息发布。 1 2 3 网络信息自适应发布的基本理论与简化模型 在上文中已经对网络信息阀题进行了初步的介绍。本章的主要目的就是要把 信息自适应发布问题结合相关概念形式化，模型化，并进行必要的简化，最终得 到可以求解的数学模型。 3 1信息资源重构的基本概念 由于网络信息受资源承载能力以及各类终端发布能力的限制，会导致相同信 息在不同终端发布时会出现楣异的效栗。 性，因而信息价值的实现也是有条件的。 并且蠢于信息的分布与流通存在不均衡 为了实现信息发布的硬件资源无关性与 自适应性，就必须对信息的结构进行调整，需要在有限的资源上对信息实现有效 地重构，以针对各类的终端情况采用不同级别的内容进行发布，尽量减少信息失 真程度。 信息资源重构的霹的是以最为恰当的形式，对原信息进行提炼和压缩，充分 利用有限资源，尽可能表达出原信息的正确内容【1 9 】。 3 2信息资源自适应发布的基本理论 为实现信息发布的硬件无关性与自适应性，就必须对信息的结构进行调整， 针对不同的硬件情况采取不同的内容进行发布。因而，信息资源自适应发布的理 论有如下定义： 定义1 信息的自适应发布：是指相同信息在不同硬件终端上，能够自动地以 最为恰当的形式反映其中所包含的内容，并消除不确定性的因素。 这里“最为恰当的形式，意为信息表现形式会随着不同的硬件而有所改变， 其目的在于充分利用有限的终端资源，在对信息内容正确表示的前提下，进行尽 可能全面的表达。 3 3信息资源发布的问题分析 本节锋对信息资源发布的相关闩题进行讨论，曩的在于使信息表示结构化， 层次化，利于其自适应发布，并由此导出信息层次结构的数学模型。 1 3 一条具体的信息表现形式( 即消息) ，通常只适应于在某种特定的环境下进行发 布。例如一个网页，其内容可能比较丰富，从丽使其只适合在计算机屏幕等终端 设备上进行浏览。如果要同时使之能够在表达能力较差的终端上发布，则必须对 其中的内容进行提炼和压缩。一种具体方法为：将此消息分为2 一个信息段，假设每 段发布时所占用的设备资源均相同。再依次将这2 稽个信息段中每两个相邻信息段的 内容进行提炼与合并，得到2 肛1 个信息段( 不妨假设这里的每个信息段占用的发布资 源小于原信息的两个信息段之和，此时消息已经被压缩了) 。再次重复以上的过程， 不断产生新的消息，巍到整条消息被压缩成为一个信息段为止。 实际上，在以上的压缩过程中已经产生了一个层次化的信息结构，即每一次 信息压缩产生新的信息段的集合为一个层次，一共有+ 1 ) 个层次的信息。这样在 信息需要自适应发布时就可以充分利用各种设备的能力来进行选择。即在发布能 力强，资源较多的设备上，采用层次较低的信息段集合进行发布；而在发布能力 弱，资源相对较为有限的设备上，采用层次较高的信息段集合进行发布。这样各 种设备都可以准确方便地反映感信息全貌，信患自适应发毒的目的也就基本上达 到了。 3 4自适应发布的问题表达 下面假设在以上的信息分段过程中，每两段相邻信息所占用的发布资源要大 于其压缩后所得到的和。则问题可以转化为如下的形式： 定义2 设m ，, n ，若n = 2 m + 1 或n = 2 m + 2 ，则称m 为聆的前驱。 定义3 设m ，力n ，若存在序列m ，m lm 2 ，m ，z ，其中前一个为后一个的前 驱，则称m 秀斑的祖先。 根据以上的两个定义，原先的问题转化成为：给定- - nw o ，嗽。，满足 w 2 。+ 2 + 。+ 3构造集合s 0 1 ，2 。- 2 ，使得对于 v 2 扣1 一l a 2 。一2 ，3 b s ，有b = a 或b 为a 的祖先，同时罗 的路径上有且仅有一个 结点n ，s 。 通过建立p l c h z 叉树模型，待发