（计算机科学与技术专业论文）基于xml的动态信息触发机制的研究.pdf

国簖科学疆术人葶磷究生陵学位论文 摘要 随着w e b 数据的r 黼增长，警丽i n t e r n e t 信息供求存在两个突出问题： 1 ) 用户能够访问的信息过于庞大而个体信息需求相对有限，怎样从浩如烟海的信息中 绥速援至爝户感兴趣懿内容。2 ) 妊俺菠缮碍户吴青对信惑变纯酶合理的牒踪麓力。 为此，系统至少需要具备两种能力。一种是给定个信息单元，系统能够通过分析 熟道哪些耀户对其中豹 嘉患感兴趣，然后将运些毽怠瑷会逶黪越菠秘形式发送绘糖 应的用户。另一种是系统能够在合理的时间间隔内完成相关信息的刷新，通过分析 知道哪些用户对其中的变化感兴趣+ 并最终将这些变化发送给相关的用户。这两手巾 麓力本质上都是鬟建立一释双信感或者信息的变化到用户意向的关联机制，称为信 ，留触发机制。信息触发机制分为静态触发和动态触发两种形式，本文重点研究基于 x 跹兹动态信患触发襁裁。 首先，本文以变化检测和意向匹配为核心技术，提出了基于x m l 的动态信息触 发规剖的系统挺架，目的蓬于能够每天鉴控 n e r n e t 范隧内大靓模兹x 弧文挡驰 菝敬，并褥时支褥大规模的用户慧向，使键系统能够校掇糟户的需求对获得的x m l 文档进行过滤，并将其中的内容以合适的粒度和途径发给相关的用户。 在系统挺絮设诗懿基键上，论文重轰磷究x 魏文档蕺变伲捡溯技术捌x 弧交毯 的意向匹配技术。 对于瓣孝，赞霁雩已有算法太多铱藏非鬻耗时鼹缝点签襞，荠虽算法过疆复杂熬 问题，本文提出了一种文档变化检测的处理方法，该方法利用文档固有信息建立特 征参照体系，通过特征路径楣关的系列概念的引入，将传统标号树匹配闷题转化 为无重复路径的称号树睡酝问题，育效造解决了路径等价黉眈较的问题，筒化了x 帆 文档的比较。 在特砭耱径褪关橇念熬基磁上，本文捷出了逶合无_ l 芋模式文秣沈较兹k f 一if f 算法。在算法复杂艘上从先前的多项式时间提高到0 ( n o g r i ) ，其中i 7 为文档结点数。 浚簿法熊够捡璎l 所商豹移动操络，搜缛匹憩环节鲍教率缛别提骞，题时提嬲7 过滤 能力并能得到高质量的解。该算法的问题是只能适合中小土篼模的应用。 为适应大规模应用的需要，本文提出了直接利用特征路径避行文档比较的 f d i f f + 繇法，嗣蠢亨适于鸯序露无序两释筷式，在鞋寸闻复杂度上献先前的0 ( n o g n ) 提高到0 ( 廊，更加适合i n t e r n ec 舰模的应用。 在转缎蹙经礁关戆诗箕孛，本文 ；入凝固半结枣鼋鼗据麓k e y 约束思想，并基铮 对先| j 判定算法过于复杂的问题，提出了凑于多实例结点集合的k e y 约束的概念以 及相关的处理方法，在一定程度上简化了计算。在此基础上，本文婀述了k e y 约震 辐关的路铰稻容傻潮定问麓，给崮了稆应的推导溉鲻以及剐定算法，同时阐述了k e y 约束相关的满足与隐含问题，给出了相关的推导舰则、判定算法以及相应的算法分 拆。 对于艏哲，针对先前研究存在的问题，本文酋先提出丁抽象文档模式空问的概 国防科学技术人学研究生院学位论文 念，从模式空间有限超集的层次上将有模式定义文档和无模式定义文档的处理统一 起来。在此基础上，本文提出了两级意向关联模型( 模式级意向关联和文档级意向 关联) 。不仅有效地压缩了候选意向的规模，而且提高了计算过程的共享和重用。 在意向关联模型的基础上，本文提出了增量式的意向匹配算法，能够充分地利用先 前的计算过程来实现意向匹配状态的连续推演，从而实现状态级计算共享。 另外，由于在意向匹配过程中涉及大量索引问题，为此针对先前研究在处理基 于相对路径的意向表示上存在的问题，本文提出了一种基于相容关系的索引模式， 利用系统抽象数据拓扑结构进行相对路径到绝对路径的转换，通过基于相容关系的 数字方式编码，能够快速确定对应结点的依赖关系，同时提出了新的路径转换算法， 将时问复杂度由过去的平方时间变为线性。 论文所描述的内容已经在原型系统x f d s 中得到部分实现，实验证明系统在大 规模意向的情况下能够达到较高的文档处理能力，尤其在文档变化率相对较低的情 况下，效果更为显著。这对于以变化为中心的f n t e r n e t 规模) ( m l 应用具有重要意 义。 关键字：x m l ，k e y ，变化检测，意向，索引，触发 国防科学技术大学研究生院学倪论文 a b s t r a c t t h e r ea r en e wr e q u i r e m e n t so fu s e r sw i t ht h ec o n s t a n t l yi n c r e a s i n go ft h ed a t a p u b l i c a t i o no nt h ew e b w h i c hb r i n g so nt w or e m a r k a b l ep r o b l e m s 1 ) i nf a c eo ft h e h u g ea m o u n to fi n f o r m a t i o no nt h ew e b ，h o wc a l lt h eu s e r sg e te x a c t l yw h a tt h e y r e a l l yw a n t ，w h i l em o s to f t h ei n f o r r n a t i o nt h e yd on o tc a r e 2 1h o w t on o t i f yt h eu s e r s w h e nt h ei n f o r m a t i o nt h e ya r ei n t e r e s t e di sc h a n g e d t os o l v et h ep r o b l e m s ，t h es y s t e mn e e d st w ok i n d so fc a p a b i l i t i e s 0 n ei st h a tf o r ag i v e ni n f o r m a t i o nu n i t ，t h es y s t e mc a nf i l t e ri ta g a i n s tt h eu s e rp r o f i l e sf i r s t l y , a n d t h e nd e l i v e rt h eu s e f u ii n f o r m a t i o ni nr i g h tg r a n u l a r i t ya n df o r n lt ot h eu s e r s a n o t h e r i st h a tt h es y s t e ms h o u l di d e n t i f yt h ec h a n g eo ft h ei n f o r m a t i o na tp r o p e ri n t e r v a l s ， a n dn o t i f yt h eu s e r si n t e r e s t e di nt i m e e s s e n c i a l l y , t h ec a p a b i l i t i e sd e s c r i b e da b o v e i m p l i et oe s t a b l i s ht h ea s s o c i a t i o nb e t w e e ni n f o r m a t i o na n dt h eu s e rp r o f i l e s ，d e n o t e d b yt h ei n f o r m a t i o nt r i g g e rm e c h a n i s m t h ei n f o r m a t i o nt r i g g e rm e c h a n i s mc a nh e d i v i d e di n t ot w ok i n d so ff o r m s ，o n ej ss t a t i cf o 肿，a n da n o t h e ri sd y n a m i cf o r m n ef o c u so f t h i st h e s i si sm a i n l yg i v e nt ot h el a r e ro n e t h et h e s i sp r e s e n t saf r a m e w o r kn a m e dx f d s o nt h eb a s i so fc h a n g ed e t e c t i o n t e c h n o l o g ya n ds u b s c r i p t i o nm a t c h i n gt e c h n o l o g y n ef r a m e w o r ki sd e s i g n e dt o m o n i t o rt h ef e t c h i n go fm i l l i o n so fx m ld o c u m e n t sp e rd a y , w h i l es u p p o r t i n g m i l l i o n so f s u b s c r i p t i o n s b a s e do nt h ex f d s ，o f t h et h e s i sa d d r e s s e st w ob o t t l e n e c k s ：c h a n g ed e t e c t i o no f x m ld o c u m e n t sa n ds u b s c r i p t i o nm a t c h i n g t ot h ef o r m e ro n e ，s i n c em o s tp r e v i o u sw o r kd e p e n d so nt h es i g n a t u r eo fn o d e s ， w h i c h w o u l db ec o s t l yt ob ec o m p u t e d ，an e ww a yi sp r o p o s e dt od i s c r i m i n a t et h o s e n o d e st h a th a v et h es a n l ep a t h si nt h ei n t r i n s i cp r o p e r t i e so ft h ex m ld o c u m e n t t o w a r d st h i se n d ，t h et h e s i si n t r o d u c e sas e r i e so fn o t i o n sr e l a t e dt ot h ek e yp a t h ， w h i c hm a k et h ec h a n g ed e t e c t i o no f x m ld o c u m e n te a s i e r b a s e do nt h en o t i o n s ，ac h a n g ed e t e c t i o n “g o f i t h r nn a m e dk f d i f ri sp r e s e n t e d w h i c hi st a i l o r e dt ou n o r d e r e dt r e e s t h ec o m p l e x i t yo fk f d i f ri so ( n l o g n ) w h i l en i st h en u m b e ro ft h en o d e si nt h et r e e v s p o l y n o m i a lt i m ef o rp r e v i o u sa l g o r i t h m s k f d i f fm a k e sp r o g r e s si nt h em a t c h i n gs t e pa n dt h ef i l t e r i n gs t e p ，a n dc a np r o d u c e f a i r l yg o o dr e s u l t s i na d d i t i o n ，k f d i f fc a l ld e t e c ta l lk i n d so fm o v eo p e r m i o n s y e t ， k f d i f fi sn o te f f i c i e n te n o u g ht ob eu s e di nt h ee n t e r p r i s ea p p l i c a t i o n s t os o l v et h ep r o b l e m t h et h e s i sp r o p o s e sah i g h l ye m c i e n ta l g o r i t h mn a m e d k f d i 斛n l ea l g o r i t h mt r a n s f o r i l l st h et r a d i t i o n a lt r e e t o t r e ec o r r e c t i o ni n t ot h e c o m p a r i n go ft h ek e yt r e e s ，w h i c ha r es u b s t a n t i a l l yl a b e lt r e e sw i t h o u td u p l i c a t ep a t h s t h u s ，t h ea l g o r i t h ma c h i e v e sh i g he f f i c i e n c yw i t ht h ec o m p l e x i t yo f0 ( n ) ，w h e r eni s t h et o t a ln u m b e ro fn o d e si nt h et r e e s w h i c hi s s i g n i f i c a n tt ot h el a r g es c a l e d a p p l i c a t i o n s d i f f e r e n tf r o mt h ep r e v i o u sw o r k k f d i 骨 i st a i l o r e dt ob o t ho r d e r e d t r e e sa n du n o r d e r e dt r e e s 。 w h i l ed e a l i n gw i t ht h ek e yp a t h ，t h en o t i o no ft h ek e yc o n s t r a i n tf o r s e m i - s t r u c t u r ed a t aa n dt h en o t i o no ft h em u l t i i n s t a n c eb a s e dk e y sa r ei d e n t i f i e d ， 国防科学技术大学研究生院学位论文 w h i c hw i l lg r e a t l ys i m p l i f yt h ec o m p l e x i t yo ft h ea l g o r i t h m t h et h e s i sa d d r e s s e st h e p r o b l e m sa s s o c i a t e dw i t ht h ek e yc o n s t r a i n t ，s u c ha ss a t i s f i a b i l i t ya n di m p l i c a t i o ne t c ， a n df u r t h e r m o r eg i v e ss o m ei n f e r e n c er u l e s ，p r o p o s e sd e t e r m i n a n ta l g o r i t h m sa n d a n a l y s e st h ea l g o r i t h m sa c c o r d i n g l y t oi m p l e m e n tt h es u b s c r i p t i o nm a p p i n g ，t h ea b s t r a c tm o d e ls p a c eo ft h e d o c u m e n t si si d e n t i f i e da tf i r s t w h i c hc a nb et a i l o r e dt od o c u m e n t sw i t ho rw i t h o u t s c h e m a 1 1 1 e n ，t h et h e s i sp r e s e n t sas c h e m ab a s e dt w o 1 e v e la s s o c i a t e dm o d e l ，w h i c h d r a m a t i c a l l yr e d u c e st h en u m b e ro ft h ec a n d i d a t es u b s c r i p t i o n s i na d d i t i o n ，a n i n c r e m e n t a ls u b s c r i p t i o nm a t c h i n ga l g o r i t h mi sp r o p o s e dt o e f f i c i e n t l ym a t c h i n g e v e n t sf o rm i l l i o n ss u b s c r i p t i o n s f u r t h e r m o r e ，s i n c ei n d e x i n gi sv e r yi m p o r t a n tt ot h es y s t e m t h ei n d e x i n g s c h e m ef o rx m ld a t ai sd e f i n e db a s e do nt h ec o n t a i n m e n tr e l a t i o n s h i p ，w h i c hc a nb e m o r ee f f i c i e n tt od e a lw i t hr e l a t i v ep a t h st h a np r e v i o u sm e t h o d s t h ek e yp r o p e r t i e so f t h em o d e la r ec o n c l u d e da sf o l l o w s i tt r a n s f o r m sr e l a t i v ep a t h st oa b s o l u t ep a t h s b yu s i n gt h et o p o l o g i c a ls t r u c t u r eo ft h ex m ld o c u m e n t si n s t e a do fd t d o rx m l s c h e m a 2 ) i ta p p l i e san u m b e r i n gs c h e m et ot h et o p o l o g i c a ls t r u c t u r e ，w h i c hc a n q u i c k l yd e t e r m i n e st h ea n c e s t o r - d e s c e n d a n tr e l a t i o n s h i pb e t w e e ne l e m e n t si nt h e h i e r a r c l a y b e s i d e s w ep r e s e n tan e wa l g o r i t h mr u n si ni i n e a rt i m ev s q u a d r a t i ct i m e f o rp r e v i o u sa l g o r i t h m s t h ew o r kd e s c r i b e dh e r eh a sp a r t l yb e e ni m p l e m e n t e da n di n t e g r a t e dt ot h e x f d ss y s t e m e x p e r i m e n ts h o w st h a tx f d sc a nh a n d l ex m ld o c u m e n t sa te x t r e m e s p e e d ，a n dc a ns u p p o r taf l o wo fm i l l i o n so fa l e r t sp e rd a yw i t hm i l l i o n so f s u b s c r i l o t i o n s ，e s p e c i a l l yi nt h ec a s eo f m i n o rc h a n g e k e y w o r d ：x m l ，k e y , c h a n g ed e t e c t i o n ，s u b s c r i p t i o n ，i n d e x ，t r i g g e r 独创性声明 本人声明所曼交的学位论文是我本人在导师搬导下进行的研究工作及取提 的研究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 箕他人已经发表和撰写遗的研究成果，也不包含为获得国防科学技术大学或其它 教弯提旃麴学位或证书委使霜运载糖瓣。与我一爱王搏蟓弱态惑本磺兖翳敲蕊任 何贡献均已在论文中作了明确的说明并表示谢意。 学位论文题目： 基至l 墼塑勉奎垡蛊越发扭制丝盟寇 学位论文幸# 暂签名：! 全塑!蟊襄：枷。j 警，。月妒疆 学位论文版权使用授权书 本入宠全了辩匿跨辩掌技术夫学有关缳瞽、使j ；学位论文翡裁定。本人授权 瞬防科学技术大学可以保鼯并囱圜家有关部门或机构送交论文的复露件和电子 文档，允许论文被查阅和偕阔；可以将学位论文的全部或部分内容编入有关数据 瘁进行检索，可以采用影印、缩印或扫描替复镧手段保存、汇编学位论文。 ( 缳密学位论文在群密君适蔑零授数_ 亭。) 学位论文题目：基ix 墼鲤动盔焦! 暨越塞拯劐煎盟筮 学位论文作者签名：猃堡塑 作者稽导教洚签名釜些缝 日期：撕，年，o 月铲日 珂翔：跏乞年 。月日 国防科学技术犬学研究生院学传论文 第一耄绪论 黼着i n t e m e t 信息的持续增长，问益庞大的数据舰模使得如1 可有效管理这些信 惑成为当篱秘研究熬点。搴章介缓论文的漂瑟背景，阐述灏骛景下信息管理需求的 变化，荠爻孽当装磺究存在滋润题遘行7 努轿，最后奔绍沦文静研究目标、研究内容 以及论文的组织。 l 。l 课题背黉i ： 1 1 。1滔髓i n t e m e t 傧息辫求的蜷点 随糟w e b 数据的日虢增长，其信息规模与增长潜力褥到越柬越多的羌注。落避 认为十年之内人类信息资源豹主体褥会以w e b 形式存在f l 】。一方面任挥人任俺 嚣寸候可以在w e b 羔独立谶发布信患，使得信息总薰持续膨胀。弱一方面每个用户都 会鹰不阉壤发豹结惠霰求( 为表述懿方澄，我们将描述孀户狺崽浠求静袭示形式猕 为爝户的慧彝) 。出于怒户可以独立、叁崮遗选择访阏其中静经露篷接，绩得个天 信息拥有量的增长几乎同步于信息总量的增长。这葺中情? 咒最终罢敬用户农捌毒越激 越多可访翘蔷恿的弱对，也西晒蓉信息过璧戆困扰。缀显然，对一般愆户嚣言，无 选择遗谈受全部信恩凡乎蹩不可能的。此外，权碱研究簸示【2 】，w e b 信息系统除 了疑煮搜索、套诲戮及僖惑获敬豹缆力之舞，逐应该其有擒挺w e b 薅患静动态突亿 驻及基于这罩孛变亿避露逶鸯静筑力。出越霹见，蠹对焦患黪曩蠡膨涨，鼯弼建立信 息发布与用户傣息需求之阃的商效关联的闽题变姆越发重受。 总体寒说，当 l 誊i n t e m e t 信息震求舆存以下几个德点f l ，3 ，4 ：1 ) 蠲户对信 息的兴趣量现不均匀分布。也就是说，对任意嗣户而亩，其信息需求通常主要集中 奁为数不多豹领域范围之鸯，遮主要是密簿个人其蠢豹区剐予能人豹特联( 出于生 理与最壤懿不瓣嚣器致戆愁辏行为赫特殊 雯) 掰决定静。2 ) 髑户髂息需求具裔选 择性。送种选撵波现在用户的缤熙攥求遴攀是缀尽体毂，或喾熨为难确迭淡，_ 肄l 户 的箔息需袭其露不弱豹粒凄要求。镄始，霄薅可旋霭要熬个页蕊，祷对也可能只蒜 要一个熏体的德。3 ) 用户信息需求常常是基于变化甚掇是基于状态的。基于变化 体璇在糟户常常鬻簧反复访闫褶同的箔怠链接，蓉这些页螽豹内容是谮发生了变 纯+ 蓦予状态裂表瑗在翔户可麓不缓需蒹豁道页藩避否襞，圭了变亿，而鬣需要知道 燮藤是签撵变化的。4 ) 不仅单一瞒户熬瞧患需袋里理不均匀分露，就整 奉丽善， 用户信息需求约分蠢也不均匀。俐魏掌鬻出瑗蛰遍受到关注的热 j 站点。 通过以上的分析可以看出，目前基于i n t e m e t 的信息供求存在以下灏个圭簧矛 蒋： ) 个a 倍感访两能力与个人信感需求鼢矛盾h 。这一矛露主要在予个人所能 涛鞠戆僖患过予庞大，褥个a 信意需求鄢裙对有限，怎样胰浩如涸海的信息中快速 找到用户感兴趣黔爨容愚鬓耱敬继患管理辨亟需解决懿瓣题。2 ) 倍意变纯频度每 镣j 页 国防科学技术大学研究生院学位论文 用户信息跟踪能力之问的矛盾 1 】。这一矛盾主要表现在，在线w e b 信息通常会不 断变化，用户要想把握这种变化过程，就必须时刻不停地反复访问相关的信息。理 论上，当信息变化超过用户信息跟踪g 力时，用户会因刷新的不及对丽丢失信息： 反之当信息变化频度很低时，用户会因大量没有意义的重复访问而浪费资源。事实 上更为普遍的情况是，由于用户无法知道信息变化的频度，因而为避免无休止的冗 余访问通常会使得用户丧失信息跟踪的能力。因此，如何使得用户具有对信息变化 的合理的跟踪能力也是需要解决的问题。 为解决上述问题，需要信息管理系统具备两种能力。一种是给定一个信息单元， 系统能够通过分析知道哪些用户对其中的信息感兴趣，然后将相应的信息按照合适 的粒度和形式发送给相关的用户。另一种是系统能够在合理的时间间隔内完成相关 信息页面( 文档) 的刷新，通过分析知道哪些用户对其中的变化感兴趣，并最终将 这些变化发送给相关的用户。 这两种能力本质上都是要建立种从信息或者信息的变化到用户意向的关联 机制，我们称这种机制为信息触发机制。 1 1 2 信息触发机制 信息触发机制主要解决信息以及信息变化的过滤问题和分发问题，而过滤和分 发的依据则是用户的意向。信息触发机制按照处理模式的不同可以分为两类静 态信息触发机制和动态信息触发机制。 1 ，1 2 1 静态信息触发机制 静态信息触发机制是指当一个信息单元到来时，系统仅仅根据该信息单元当前 的内容迸行基于用户意向的过滤与分发，而不考虑该信息单元先前的状态。 i 1 2 2 动态信息触发机制 动态信息触发机制是指当一个信息单元到来时，系统首先通过该信息单元先前 状态与当前状态之间的比较，知道自上一处理时刻到现在该信息单元发生了哪些变 化。然后针对这些变化进行分柝，看哪些用户对其中的变化感兴趣。最后将相应的 变化发送给相关的用户。 动态信息触发机制本身又包含两种形式，一种是基于绝对比较的信息触发形 式，另一种是基于褶对比较的信息触发形式。绝对比较指将信息项的当日f 状态与状 态无关的条件相匹配，如果满足则意味着该信息项与用户的意向存在关联，否则， 则说明没有用户对该信息项的内容感兴趣。例如，假设用户对价格在1 0 0 0 0 元以上 的相机感兴趣则当个信息单元包含相机的信息项时，就会将相机的价格与用户 意向中的条件( 1 0 0 0 0 ) 进行比较。如果满足，则说明该信息项包含了用户需要的 国防科学技术火学研究生院学忙论文 信息。相对比较则指信息项的匹配条件是状态相关的情况。这里的状态相关是指用 户意向中的条件不仅与信息项当前状态相关，而且还与信息项历史状态相关。例如， 假设用户对收盘价格涨幅在2 5 以上的股票感兴趣，则在对包含股票信息的信息项 进行匹配时，无法仅就当前的价格信息做出判断，而必须将该信息项当f i i 的收盘价 格值与前一处理时刻的收盘价格值进行比较，只有在满足指定的涨幅情况下，才能 说匹配成功。 1 1 3 信息触发机制相关技术 随着基于i n t e m e t 的操作级的交互能力以及数据级交互能力的日益增强，信息 触发机制越来越成为n t e m c t 信息服务中不可或缺的形式。 信息触发机制的研究由来已久，也出现了许多相关的技术，例如信息获取技术、 主动数据库、视图技术、t r i g g e r 技术、连续查询技术、基于消息的中问件、s d i 技 术、x m l 技术以及文档比较技术等等。 信息触发机制研究的数据形式可分为结构化数据、半结构化数据以及非结构化 数据三种。结构化数据是指结构特征严格遵循良定的语法规范的数据形式。例如传 统关系数据库中的记录，每一介记录必须并且只能包含规定的子项，同时每一个子 项必须严格遵循数据类型的约定。非结构化数据则指那些没有良定的语法特征的数 据形式。例如普通的文本文档，其结构组织没有固定的框架，内含的数据没有相应 的元信息描述。正因为这类数据缺乏反映数据单元之间依赖关系的特征信息，使得 信息内容的获取变得相对困难。传统信息获取技术在这方面进行了大量的研究，然 而由于非结构信息获取时间、空间复杂性的限制，使得很多问题至今没有得到根本 的解决。也正是因为人们意识到非结构化数据处理的困难，意识到元信息对于数据 处理的重要程度，才使得半结构化数据逐渐成为数据表示和信息交换的主流格式。 半结构化数据介于结构化数据与非结构化数据之间，在保留结构化数据的结构特征 的基础上，提供了非常灵活的表示能力。正是这种灵活性使得半结构化数据能够表 示传统结构化数据不适合表示的信息形式，从而为在i n t e m e t 范围内实现语义级的 数据管理提供了手段。 1 i 3 i 信息获取技术 信息获取技术重点研究非结构数据特别是文本数据的信息获取，目的在于从非 结构化文档或者文档的非结构化部分中获取感兴趣的内容。信息获取所研究的数据 不仅包括静态的文档集合，也包括动态的信息流。信息获取的标准是反映用户意向 的查询，而这种查询可以是非结构化的( 例如一个句子甚至一个文档) 形式，也可 以是结构化的( 例如布尔表达式) 形式5 1 。 信息获取技术从处理模式上大体分为两种：查询方式和路由方式f 6 】。前者针对 相对固定的文档集合以及任意变化的查询，根据不同的查询在整个文档集合中提取 满意的信息；后者则相反，先有相对固定的查询( 通常以一组主题的形式存在) ， 第3 页 国防科学技术人学研究生院学位论文 然后以信息流的方式处理动态变化的信息单元，并将信息单元路由到与单元内容匹 配的主题所对应的分类当中。这两种方式最大的区别在于：在路由方式中，训练是 可以预先完成的，或者说，路由方式可以对相对静态的查询进行预处理，而查询方 式则可以对相对静态的文档进行预处理。 信息获取技术从方法上也可分为两类：基于统计的方法和基于语义的方法。基 于统计的方法是信息获取技术研究的主流。这类方法中，信息获取的处理以及相关 程度的判定都依靠统计的手段。例如典型的方法有：基于布尔关系的方法，基于扩 展布尔关系的方法，基于矢量空间的方法以及基于概率的方法等等。基于语义的方 法则试图直接通过语法、语义分析或者说依靠自然语言。处理( n a t u r a ll a n g u a g e p r o c e s s i n gn l p ) 的方式去解析文档的结构和语义，挖掘感兴趣的内容。这类方法 通常作为基于统计的方法的补充。 另外，在信息获取过程中，为提高处理效率，还经常使用分簇( c l u s t e r i n g ) 的 方法。分簇的目的在于根据内在的特征将文档分类存放，使得特征相近的文档能够 被集中处理。并且这些特征往往是查询相关的重要依据，在一定程度上能够提高文 档意向匹配的效率。基于分簇的文档处理从流程上可以分为自顶而下和自下而上两 种方式，从算法实现上可以分为静态分簇模式以及增量式动态分簇模式两种。 从根本上讲，本文研究的内容应该属于信息获取技术研究的范畴，因为二者实 质上都是要分析一个信息单元中有哪些用户感兴趣的内容，都是要建立信息实体到 用户意向的某种形式的关联。然而，本文研究的内容与传统意义上的信息获取技术 又有着明显的区别。首先，信息获取技术尽管不排斥结构化数据或者半结构化数掘， 但是其研究重点在于非结构化数据上面，而本文则重点研究半结构化( x m l ) 数据。 第二，由于二者关注的数据形态不同，使得传统信息获取技术的研究成果大多无法 直接用于我们的研究当中。然而这并不代表信息获取技术与论文的内容毫不相关， 相反，我们在研究过程中，汲取借鉴了很多信息获取技术中的概念、方法以及处理 问题的思路。例如，文档划分的思路、基于统计的处理方式、路由方式的处理方法 等等。 1 1 3 2 主动数据库 主动数据库 7 】重点研究结构化形式的信息触发机制，其处理过程简单说就是当 数据库状态发生变化时，依据定的规则，采取相应的动作。其实质是建立事件 条件一动作( e c a ) 之间的关联，并且这种关联的实现依赖数据库系统的支持。 主动数据库实质上是在数掘库的系统框架内研究结构化数据的信息触发机制。 1 1 3 3 视图技术 视图技术在数据库技术中侧重于研究查询上的优化，多适用于集中数掘库环 境，实质上是在一组原本独立的状态集合之上建立逻辑与物理的关联，从而提高查 询效率。视图技术与信息触发机制的关联主要体现在视图的更新上面，不过严格地 讲，二者相关的程度非常有限。 1 1 3 4 t r i g g e r 技术 在概念上况，一个数据库t r i g g e r 【8 】是一个事件- 条件一动作( e c a ) 规则的限制 形式。因而在这个意义上t r i g g e r 技术与主动数据库没有本质的区别。为适应用户的 需求，商业数据库大多支持不同级别的t r i g g e r ，然而由于机制上的原因，这些t r i g g e r 往往具有不同程度的限制。 在数据库中，当一个作用在数据库上的操作发生时，t r i g g e r 系统需要根据谓词 的内容对变化的数据项与当前数据库的状态进行比较，这种实现方式使得t r i g g e r 系 统的规模受到限制。因为如果t r i g g e r 系统面对大规模查询时，每次数据库修改的事 件都会导致所有查询条件与当前数据库状态的匹配，这显然在效率上是行不通的。 另外，当前的t r i g g e r 系统在支持信息触发的能力上也有明显的限制，例如触发条件 只能局限于一个表内等等。 t r i g g e r 技术与本文研究内容的主要共同点在于都是研究动态信息触发机制的 实现技术。然而前者研究的范围局限于数据库系统内部，研究内容局限于结构化数 据，而后者则主要研究广域环境下半结构数据的动态意向关联。 1 1 3 5 连续查询技术 连续查询技术使得用户不必反复发送相同的请求就可以得到意向相关的最新 结果。连续查询技术与主动数据库技术有着紧密的联系，其数据触发方式从根本上 是一致的。不同之处主要有以下几点：1 ) 连续查询技术逻辑上独立于数据库系统， 也就是说，不像主动数据库或t r i g g e r 技术那样依赖数据库系统的支持，因而适用 于广域环境下对持续变化信息的查询。2 ) 正因为连续查询技术独立于数据库系统， 使得连续查询技术能够摆脱数据库系统本身对信息触发的条件上和规模上的限制， 从而提高系统的可扩展性。3 ) 连续查询技术能够覆盖全部三种数据形式( 结构、 半结构和非结构) ，这使得连续查询技术能够用于i n t e m e t 范围内各种异构信息资源 的查询处理。4 ) 连续查询技术除了支持基于信息变化的触发，还支持基于时间的 触发形式。 为了实现连续查询，常常需要具备对一定范围内相关信息的连续监控能力。需 要指出的是，基于w e b 的变化监测目益重要。一些搜索引擎( 例如n e t m i n df 9 1 、 n o t h e ml i g h tf l o l 等) 已经提供了h t m lw e b 页面的变化监测能力。用户只要提交 意向，系统就可以通过e m a i l 将相关的变化通告给用户。 从用户的观点来看，变化监测过程包括两个重要的方面。一是需要自动知道页 面何时发生变化，而不用无休止地反复访问相同的链接。另一个方面是需要知道页 面是如何变化的。因为当用户感兴趣的页面多到一定程度时，对于每一个新到的页 面，要记住其原来的细节十分困难，为此需要系统告诉用户页面是如何变化的，也 就是说，系统需要持续不断地监测获取的页面文档流，将每个新到的文档与系统保 第5 页 国防科1 学技术人学研究生院学忙论文 留的该文档上一时刻的版本进行比较，发现其中的变化，并根据变化对用户意向的 影响采取相应的动作。要在广域环境下建立这样的系统，最大的挑战在于可扩展性 和效率。这要求系统尽可能地支持更多的文档获取和更多的用户，并且在高负载的 情况下仍有较好的响应能力。 连续查询技术与本文的内容关系密切，相似之处在于二者都关注信息的变化以 及基于变化的条件匹配。然而从整体上说，二者又有不同的研究重点。前者注重研 究查询方式的优化，而后者主要研究路由方式下意向匹配的效率问题。 1 1 3 6 基于消息的中间件技术 很多基于查询的事件通告服务已经被集成到各种中问件( 例如消息中间件 m o m 、c o r b a 中间件等) 当中，用来耦合分布式应用系统。多数消息中间件都将 属性和值作为事件的基本组成部分，新近的m o m 系统研究基于x m l 的消息交换。 基于消息的中问件通常对被处理的消息仅仅进行基于主题( 或者基于地址) 的分类， 而不像其它技术那样关注信息的内容，因而无论是意向表示还是意向匹配都要相对 简单。 1 1 3 7 p s 技术 出版( p u b l i s h ) 订阅( s u b s c r i b e ) ( 简称p s ) 模式主要研究信息( 文档) 发布 与信息需求之间的关联。通常p s 系统主要关注大规模文档数据与大规模意向之间 的高效匹配。由于意向匹配最终目的在于根据用户意向对文档数据进行过滤，并将 满足条件的信息发给相关的用户，因此这方面的研究也被称为有选择的信息分发 ( s e l e c t i v e d i s s e m i n a t i o n o f i n f o r m a t i o n s d i ) 。对于在广域环境下建立信息到用户 意向的关联，信息分发是一种直观而有效的模式。一个信息分发系统，通常是用户 向系统提交长期的意向，以说明需要什么样的信息；系统则在不断搜集新的信息的 同时，根据用户的意向对这些信息进行过滤，然后将相关的内容发给对应的用户。 p s 系统包括两种主要类型：基于主题的p s 系统和基于内容的p s 系统【1 1 】。 基于主题的p s 系统直接对事件进行分组，并且依靠这种分组来进行事件的过滤。 基于内容的p s 系统则提供更为精密的过滤机制。例如，事件可以根据属性值束进 行匹配。与前者相比，基于内容的p s 系统能够为用户提供更强的意向表达能力， 特别是基于x m l 的p s 系统，利用x m l 独特的自描述能力，用户能够实现对海量 数据信息的细粒度把握。 p s 技术研究的重点在于意向匹配，特别是当考虑到系统要面对大规模( 上百 万) 的用户意向和大规模( 上千万) 的数据文档时，意向匹配的效率则变成决定性 的因素。p s 技术与本文研究的内容关系密切，相似之处在于二者都注重研究信息 与意向的匹配：不同之处在于传统p s 技术主要研究静念意向匹配，而本文则主要 研究基于信息变化的动态意向匹配。 第6 页 国防科学技术人学研究生院。学位论文 1 1 3 8x m l 技术 近年来，由于通信体系结构的嗣益丰富，例如i n t e m e t 、i n t r a n e t 、无线与卫星 网络、宽带入户以及第三代移动网络( 3 gu m t s ) 的潜在增长等等，使得越来越多 的用户与越来越多的信息提供商( 例如股票、交通信息、电子报纸以及娱乐等等) 被连接起来。这使得建立i n t e m e t 规模的信息供求关联的需求日益强烈。同时，面 对广域环境下越来越多的信息提供商、系统以及用户之1 8 j 的互操作问题，不仅需要 技术层面的统一，而且需要语义层面的统一。x m l 的出现为这种需要的满足提供 了可能，并且必然会对i n t e r n e t 信息管理产生根本的影响。 随着x m l 1 2 逐渐成为i n t e m e t 主流的数据交换与数据格式的标准，其影响几 乎遍及所有的领域，支持几乎所有的语义相关的互操作j ；= 节( 例如w e b 站点表示、 无线访问以及移动语音访问等等) 。目前的x m l 规范已经全面支持基于i n t e m e t 的 x m l 信息查询，就像现有的搜索引擎能够查询基于w e b 的h t m l 文档一样，x m l 的最终目标是使i n t e m e t 成为一个巨大的分布式x m l 数据库。x m l 数据可以通过 包括数据库系统、文件系统、应用系统在内的任何形式存储在i n t e m e t 的任何地方， x m l 搜索引擎通过对x m l 数据的访问，能够提供比传统搜索引擎更为强大、更为 精确的查询能力。 毫无疑问，随着越来越多的数据变成x m l 的形式，相关的模式定义(