RSS聚合标准及其聚合策略

张孝祖

(华北计算技术研究所，北京 100083)

RSS聚合标准及其聚合策略

张孝祖

(华北计算技术研究所，北京 100083)

RSS是Web内容联合的基于XML的协议，并且用户使用RSS订阅源聚合器聚合RSS订阅源。那里是帮助聚合RSS源的RSS聚合策略有效。在本文中，首先介绍RSS的出现和发展情况，然后介绍几种信息聚合策略，给出具体算法，比较其算法复杂度及优缺点。

web；信息聚合；RSS

0 引言

在过去几年中，Web已经成为广泛的资源集合，以（静态）文档的形式和以服务的形式提供信息或数据。公司和个人在网站上发布内容，主要搜索引擎存储和索引所包含的信息。随着互联网的迅猛发展，如今的用户不再向以前一样面临着信息缺乏的问题，相反，过多的信息和大量低质量的信息正浪费着人们宝贵的时间和带宽流量资源[1-3]，这种现象就叫做信息超载。针对这些问题，信息聚合技术渐渐发展了起来，RSS标准的出现给出了聚合信息的一种简单统一格式，各大门户网站纷纷开始支持RSS格式的信息订阅，涌现出了分类繁杂的信息订阅源。如何聚合这些信息源的信息、如何评价聚合算法是否高效就成了值得研究的问题。

1 简易信息聚合

RSS（也叫聚合内容，Really Simple Syndication）是一种描述和同步网站内容的格式，是目前使用最广泛的XML应用，是资源共享模式的延伸。RSS 0.90是Netscape在1999年设计的。在Netscape的RSS团队蒸发之后，RSS-DEV工作组和UserLand公司已经独立地在RSS上进行标准化工作。RSSDEV工作组设计了基于RDF的RSS 1.0。UserLand基于RSS 0.90设计了RSS 2.0。

从2004年开始，RSS聚合协议在美国等西方国家爆发式的增长，随着Web2.0时代的到来，越来越多的信息开始分散人们的注意力，人们迫切的需要这种聚合的思想使这些碎片化信息聚合的展示给自己，让信息在提供者与用户之间更加有目的的流动，让信息的获取变得快捷、高效、准确。国内的RSS发展也有了长远的进步，百度、腾讯、新浪等各大门户网站都纷纷开始支持这种协议，推出自己的RSS订阅源。RSS订阅，目前已经成为了人们获取信息的一种重要途径和方法。

2 聚合策略

RSS不是在基于推送的协议下操作，而是在基于拉取（pull-based）的协议下操作，其中各个订阅用户负责自己从网站收集信息。RSS馈送的基本聚合和订阅过程如图1所示。

图1 RSS订阅流程Fig.1 Basic RSS feed syndication and subscription process

发布者会将内容生成到RSS Feed中。订阅者将RSS订阅源地址注册到RSS订阅源聚合器。RSS订阅源聚合器聚合注册的RSS订阅源并向订阅者显示内容。RSS聚合器的角色在Web服务中变得越来越重要。随着用户想要预订的RSS馈源的数量的增加，RSS聚合器必须具有的RSS馈源的数量聚集体增长。此外，内容会动态地显示和消失。因此，有一个良好的聚合策略，使我们能够有效地聚合生成的内容是至关重要的。聚合策略不仅可以确定每个RSS订阅源的聚合数量，还需要确定发生聚合时的调度顺序。

让RSS聚合器聚合n个RSS订阅源。最简单的聚合策略是为每个Feed提供相同的聚合数量。我们称之为统一聚合策略。统一聚合策略效率低下，因为无论RSS订阅源中存储了多少发布内容以及生成的内容频率，RSS聚合器都会同等数量的聚合。

2.1 最小延迟聚合策略

聚合延迟是一种广泛接受的度量，可以评估RSS聚合策略。聚合延迟是指在RSS的发布的生成时间与聚合器的聚合时间之间的延迟时间。假设RSS源F在时间t1，…，tk生成发布p1，…，pk，并且聚合器在时间a1，…，am聚合来自F的新发布。与发布pi相关联的延迟被定义为：

其中aj是a1，…，am的最小值，其中aj大于发布时间ti（aj≥ti）。

RSS馈源F的所有发布p1，…，pk的总聚合延迟是：

所有RSS信息源的总聚合延迟定义如下：

为了减少聚合延迟，Sia和Cho[1]提出了最小延迟聚合策略，其基于发布频率来分配聚合数，该发布频率是在一段时间内的发布数量。让RSS源Fi有发布率λi和重要性权重ωi。令M为时间T内，信息源Fi可聚合内容数目的最大值。然后，可以计算分配给Fi的聚集数目。

等式中的k满足

Mi就是保证最小聚合延迟情况下，给信息源Fi分配的聚合数量。

示例：

假设存在分别具有发布频率λ1，λ2，λ3，λ4为30，30，10，10的RSS馈送F1，F2，F3，F4（见图2）。还假设所有RSS订阅源具有相同的重要性权重（ωi = 1）并且M是8。

图2 RSS源和发布率Fig.2 Feeds and posting rates

首先计算系数k

得到k约是0.46

然后计算m1到m4，结果如下表所示。

表1 示例计算结果Tab. 1 Example of the minimum delay aggregation policy

2.2 最小丢失聚合策略

在前面的方法中，聚合RSS信息源的性能标准是RSS订阅器的总聚合延迟。该算法被设计为最小化RSS订阅器的总聚合延迟。Young GeunHan和Sang HoLee提出了一个新的性能标准，丢失消息率。

RSS源不太可能存储所有生成过的信息。相反，它们可能只存储最近生成的一部分信息。所以RSS源中的一些旧的信息被删除是很有可能的（因此不会被RSS聚合器聚合）。令Si是可以存储在第i个信息源中的最大发布数量。参考图3所示。

图3 RSS源收集丢失Fig.3 Example of missing postings in RSS feeds

使S3和S4分别为10和5。所有10条信息都存储在F3中，因此聚合器可以聚合单个聚合中的所有信息。然而，在F4中删除了信息p1，…，p5，而生成新的信息p6，…，p10，因为S4为5，在单次聚合中，聚合器只能聚集5个新的信息，缺少先前生成的5个信息。我们把在RSS订阅源中生成但未由聚合器聚合（由于RSS订阅源的存储容量）的信息定义为丢失信息。

我们将在第i个RSS源Fi中的第j次聚合时聚合的信息数量表示为PPAi,j（每次聚合的信息数）。第Fi个RSS订阅源中的总丢失信息数量被表示为MP（Fi），计算为：

然后，可以将RSS聚合器中缺少的总发布数量定义为：

我们将在第i个RSS源中的第j次聚合之后可以聚合的总信息的数量表示为TPi,（j + 1）（目标信息数）。然后我们有：

在聚合之前（当j = 0时）（即，TP(i,1)）可以聚合的信息的总数是λi，因为在RSS源Fi中生成的总信息数量是λi。当在RSS源Fi（当j = mi）（即Tpi，(mi +1)）中的最后一次聚合完成时，RSS源 Fi中的待聚合信息的总数是MP（Fi），因为MP（Fi）是λi和PPAi,j总和的差。

图4中的算法被设计为使聚合期间丢失的信息最小化。在该算法中，具有最大PPAi,j的源的聚合数目增加1（参见图8中的第18-20行），并且该过程重复M次。当TPi,j大于Si时，作为在聚集中聚集的发布的数量的PPAi,j被设置为Si。否则设置为TPi,j（见第11-16行）。注意，我们假设在聚合时间之前尽早生成新的消息（与Si一样多）。

当RSS聚合器聚合Fi时，存在新生成的消息发布数小于Si的情况。也就是说，如果所有TPi,(j+1)都是0（这意味着在当前聚合时间没有待聚集的消息）即使存在更多要发生的聚合（即也要将所有TPi,(j+1)设置为λ（见第6-10行）。

图4 RSS源最少丢失收集算法Fig.4 Minimum missing aggregation policy algorithm

TPi,(j+1)：第i个信息源j次收集后，还等待被收集的信息数量。

PPAi,j：第i个信息源第j次收集时收集的信息数。

3 结论

本文给出了两种不同侧重点的聚合策略，对于首先提到的固定聚合数目的方法，优点是实现简单、容易操作，缺点是不够灵活、没有侧重，对不同信息源一视同仁的分配聚合数目显然是不够精细的。相比于固定聚合数目策略，最小延迟收集策略显然进步了很多，它在不同信息源间加入了权重信息，在保证及时收集信息的同时对重要信息源有所侧重，多分配聚合条目。最小延迟也意味着用户能够及时的看到更新，或得最佳的用户体验并且算法也不复杂，非常适合实际使用。缺点在于对于固定的更新频率，策略的更新次数是固定的，对硬件的访问频率要求较高，不能自主控制聚合次数。

第三种最小丢失策略弥补了最小延迟策略的不足，在给定的聚合次数M中，能最小丢失的聚合信息，当实际情况不允许频繁发起聚合时，这种固定次数的收集算法，能保证丢失的信息最少。

实际使用中，信息以各种模式产生，程序设计者需要根据实际需求、硬件性能等客观条件，灵活选择聚合策略。

[1] 吕媛媛, 李可. 移动端应用设计中的响应式实现方法[J].软件, 2016, 37(02): 107-109. LV YY, LI K. A Response-based Approach to Mobile Application Design [J]. software. 2016, 37 (02): 107-109.

[2] 王钰琪, 窦伟超. SDN网络多控制器结构的失效备援设计[J]. 软件, 2016, 37(01): 71-75. DU S Y. Research on Clustering Algorithm Based on Large Data Set[J]. software. 2016, 37 (01): 132-135.

[3] 杜淑颖. 基于大型数据集的聚类算法研究[J]. 软件, 2016, 37(01): 132-135. DU S Y. Research on Clustering Algorithm Based on Large Data Set[J]. software. 2016, 37 (01): 132-135.

[4] 陈峰, 熊励. 基于RSS信息服务联盟的内容聚合技术研究[J]. 计算机技术与发展, 2009(1): 9-12. CHEN F, XIONG L. Research on Content Aggregation Technology Based on RSS Information Service Alliance [J]. Computer Technology and Development. 2009(1): 9-12.

[5] 伍玉伟. RSS: 网络信息“聚合”利器[J]. 现代情报, 2006(2): 221-222. 161-168. WU Y Y. RSS—A New Killing Weapon in Web Information [J], Modern Information 2006(2): 221-222. 161-168.

[6] SIA, K C, CHO, J, et al. Monitoring RSS Feeds Based on User Browsing Pattern [J], Boulder Colorado, March 2007: 161-168.

[7] CHO, J, GARCIA M. Synchronizing a Database to Improve Freshness, in Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data [J], Dallas Texas, May 2000: 117-128.

[8] CHO, J, GARCIA M. The Evolution of the Web and Implications for an Incremental Crawler, in Proceedings of the 26th International Conference on Very Large Data Bases [J], Cairo Egypt, September 2000: 200-209.

[9] KIM, S J, LEE. An Empirical Study on the Change of Web Pages[Z], Shanghai China, Proceedings of the Seventh Asia-Pacific Web Conference, March 2005.

RSS Aggregation Format and Its Aggregation Strategy

ZHANG Xiao-zu
(North China Institute of Computing Technology, Beijing 100083, China)

RSS is a federated XML-based format for Web content, and users aggregate RSS feeds using RSS feed aggregators. There is an RSS aggregation policy that helps aggregate RSS feeds. In this paper, the first introduction of the emergence and development of RSS, and then introduced several information aggregation strategy, given the specific algorithm to compare the algorithm complexity and advantages and disadvantages.

Web; Information aggregation; RSS

TP393.092

A

10.3969/j.issn.1003-6970.2016.12.021

张孝祖(1992-)，男，硕士，研究方向：软件分析与集成。

本文著录格式：张孝祖. RSS聚合标准及其聚合策略[J]. 软件，2016，37（12）：93-96