張孝祖

(華北計(jì)算技術(shù)研究所，北京 100083)

RSS聚合標(biāo)準(zhǔn)及其聚合策略

張孝祖

(華北計(jì)算技術(shù)研究所，北京 100083)

RSS是Web內(nèi)容聯(lián)合的基于XML的協(xié)議，并且用戶使用RSS訂閱源聚合器聚合RSS訂閱源。那里是幫助聚合RSS源的RSS聚合策略有效。在本文中，首先介紹RSS的出現(xiàn)和發(fā)展情況，然后介紹幾種信息聚合策略，給出具體算法，比較其算法復(fù)雜度及優(yōu)缺點(diǎn)。

web；信息聚合；RSS

0 引言

在過(guò)去幾年中，Web已經(jīng)成為廣泛的資源集合，以（靜態(tài)）文檔的形式和以服務(wù)的形式提供信息或數(shù)據(jù)。公司和個(gè)人在網(wǎng)站上發(fā)布內(nèi)容，主要搜索引擎存儲(chǔ)和索引所包含的信息。隨著互聯(lián)網(wǎng)的迅猛發(fā)展，如今的用戶不再向以前一樣面臨著信息缺乏的問(wèn)題，相反，過(guò)多的信息和大量低質(zhì)量的信息正浪費(fèi)著人們寶貴的時(shí)間和帶寬流量資源[1-3]，這種現(xiàn)象就叫做信息超載。針對(duì)這些問(wèn)題，信息聚合技術(shù)漸漸發(fā)展了起來(lái)，RSS標(biāo)準(zhǔn)的出現(xiàn)給出了聚合信息的一種簡(jiǎn)單統(tǒng)一格式，各大門(mén)戶網(wǎng)站紛紛開(kāi)始支持RSS格式的信息訂閱，涌現(xiàn)出了分類繁雜的信息訂閱源。如何聚合這些信息源的信息、如何評(píng)價(jià)聚合算法是否高效就成了值得研究的問(wèn)題。

1 簡(jiǎn)易信息聚合

RSS（也叫聚合內(nèi)容，Really Simple Syndication）是一種描述和同步網(wǎng)站內(nèi)容的格式，是目前使用最廣泛的XML應(yīng)用，是資源共享模式的延伸。RSS 0.90是Netscape在1999年設(shè)計(jì)的。在Netscape的RSS團(tuán)隊(duì)蒸發(fā)之后，RSS-DEV工作組和UserLand公司已經(jīng)獨(dú)立地在RSS上進(jìn)行標(biāo)準(zhǔn)化工作。RSSDEV工作組設(shè)計(jì)了基于RDF的RSS 1.0。UserLand基于RSS 0.90設(shè)計(jì)了RSS 2.0。

從2004年開(kāi)始，RSS聚合協(xié)議在美國(guó)等西方國(guó)家爆發(fā)式的增長(zhǎng)，隨著Web2.0時(shí)代的到來(lái)，越來(lái)越多的信息開(kāi)始分散人們的注意力，人們迫切的需要這種聚合的思想使這些碎片化信息聚合的展示給自己，讓信息在提供者與用戶之間更加有目的的流動(dòng)，讓信息的獲取變得快捷、高效、準(zhǔn)確。國(guó)內(nèi)的RSS發(fā)展也有了長(zhǎng)遠(yuǎn)的進(jìn)步，百度、騰訊、新浪等各大門(mén)戶網(wǎng)站都紛紛開(kāi)始支持這種協(xié)議，推出自己的RSS訂閱源。RSS訂閱，目前已經(jīng)成為了人們獲取信息的一種重要途徑和方法。

2 聚合策略

RSS不是在基于推送的協(xié)議下操作，而是在基于拉?。╬ull-based）的協(xié)議下操作，其中各個(gè)訂閱用戶負(fù)責(zé)自己從網(wǎng)站收集信息。RSS饋送的基本聚合和訂閱過(guò)程如圖1所示。

圖1 RSS訂閱流程Fig.1 Basic RSS feed syndication and subscription process

發(fā)布者會(huì)將內(nèi)容生成到RSS Feed中。訂閱者將RSS訂閱源地址注冊(cè)到RSS訂閱源聚合器。RSS訂閱源聚合器聚合注冊(cè)的RSS訂閱源并向訂閱者顯示內(nèi)容。RSS聚合器的角色在Web服務(wù)中變得越來(lái)越重要。隨著用戶想要預(yù)訂的RSS饋源的數(shù)量的增加，RSS聚合器必須具有的RSS饋源的數(shù)量聚集體增長(zhǎng)。此外，內(nèi)容會(huì)動(dòng)態(tài)地顯示和消失。因此，有一個(gè)良好的聚合策略，使我們能夠有效地聚合生成的內(nèi)容是至關(guān)重要的。聚合策略不僅可以確定每個(gè)RSS訂閱源的聚合數(shù)量，還需要確定發(fā)生聚合時(shí)的調(diào)度順序。

讓RSS聚合器聚合n個(gè)RSS訂閱源。最簡(jiǎn)單的聚合策略是為每個(gè)Feed提供相同的聚合數(shù)量。我們稱之為統(tǒng)一聚合策略。統(tǒng)一聚合策略效率低下，因?yàn)闊o(wú)論RSS訂閱源中存儲(chǔ)了多少發(fā)布內(nèi)容以及生成的內(nèi)容頻率，RSS聚合器都會(huì)同等數(shù)量的聚合。

2.1 最小延遲聚合策略

聚合延遲是一種廣泛接受的度量，可以評(píng)估RSS聚合策略。聚合延遲是指在RSS的發(fā)布的生成時(shí)間與聚合器的聚合時(shí)間之間的延遲時(shí)間。假設(shè)RSS源F在時(shí)間t1，…，tk生成發(fā)布p1，…，pk，并且聚合器在時(shí)間a1，…，am聚合來(lái)自F的新發(fā)布。與發(fā)布pi相關(guān)聯(lián)的延遲被定義為：

其中aj是a1，…，am的最小值，其中aj大于發(fā)布時(shí)間ti（aj≥ti）。

RSS饋源F的所有發(fā)布p1，…，pk的總聚合延遲是：

所有RSS信息源的總聚合延遲定義如下：

為了減少聚合延遲，Sia和Cho[1]提出了最小延遲聚合策略，其基于發(fā)布頻率來(lái)分配聚合數(shù)，該發(fā)布頻率是在一段時(shí)間內(nèi)的發(fā)布數(shù)量。讓RSS源Fi有發(fā)布率λi和重要性權(quán)重ωi。令M為時(shí)間T內(nèi)，信息源Fi可聚合內(nèi)容數(shù)目的最大值。然后，可以計(jì)算分配給Fi的聚集數(shù)目。

等式中的k滿足

Mi就是保證最小聚合延遲情況下，給信息源Fi分配的聚合數(shù)量。

示例：

假設(shè)存在分別具有發(fā)布頻率λ1，λ2，λ3，λ4為30，30，10，10的RSS饋送F1，F(xiàn)2，F(xiàn)3，F(xiàn)4（見(jiàn)圖2）。還假設(shè)所有RSS訂閱源具有相同的重要性權(quán)重（ωi = 1）并且M是8。

圖2 RSS源和發(fā)布率Fig.2 Feeds and posting rates

首先計(jì)算系數(shù)k

得到k約是0.46

然后計(jì)算m1到m4，結(jié)果如下表所示。

表1 示例計(jì)算結(jié)果Tab. 1 Example of the minimum delay aggregation policy

2.2 最小丟失聚合策略

在前面的方法中，聚合RSS信息源的性能標(biāo)準(zhǔn)是RSS訂閱器的總聚合延遲。該算法被設(shè)計(jì)為最小化RSS訂閱器的總聚合延遲。Young GeunHan和Sang HoLee提出了一個(gè)新的性能標(biāo)準(zhǔn)，丟失消息率。

RSS源不太可能存儲(chǔ)所有生成過(guò)的信息。相反，它們可能只存儲(chǔ)最近生成的一部分信息。所以RSS源中的一些舊的信息被刪除是很有可能的（因此不會(huì)被RSS聚合器聚合）。令Si是可以存儲(chǔ)在第i個(gè)信息源中的最大發(fā)布數(shù)量。參考圖3所示。

圖3 RSS源收集丟失Fig.3 Example of missing postings in RSS feeds

使S3和S4分別為10和5。所有10條信息都存儲(chǔ)在F3中，因此聚合器可以聚合單個(gè)聚合中的所有信息。然而，在F4中刪除了信息p1，…，p5，而生成新的信息p6，…，p10，因?yàn)镾4為5，在單次聚合中，聚合器只能聚集5個(gè)新的信息，缺少先前生成的5個(gè)信息。我們把在RSS訂閱源中生成但未由聚合器聚合（由于RSS訂閱源的存儲(chǔ)容量）的信息定義為丟失信息。

我們將在第i個(gè)RSS源Fi中的第j次聚合時(shí)聚合的信息數(shù)量表示為PPAi,j（每次聚合的信息數(shù)）。第Fi個(gè)RSS訂閱源中的總丟失信息數(shù)量被表示為MP（Fi），計(jì)算為：

然后，可以將RSS聚合器中缺少的總發(fā)布數(shù)量定義為：

我們將在第i個(gè)RSS源中的第j次聚合之后可以聚合的總信息的數(shù)量表示為T(mén)Pi,（j + 1）（目標(biāo)信息數(shù)）。然后我們有：

在聚合之前（當(dāng)j = 0時(shí)）（即，TP(i,1)）可以聚合的信息的總數(shù)是λi，因?yàn)樵赗SS源Fi中生成的總信息數(shù)量是λi。當(dāng)在RSS源Fi（當(dāng)j = mi）（即Tpi，(mi +1)）中的最后一次聚合完成時(shí)，RSS源 Fi中的待聚合信息的總數(shù)是MP（Fi），因?yàn)镸P（Fi）是λi和PPAi,j總和的差。

圖4中的算法被設(shè)計(jì)為使聚合期間丟失的信息最小化。在該算法中，具有最大PPAi,j的源的聚合數(shù)目增加1（參見(jiàn)圖8中的第18-20行），并且該過(guò)程重復(fù)M次。當(dāng)TPi,j大于Si時(shí)，作為在聚集中聚集的發(fā)布的數(shù)量的PPAi,j被設(shè)置為Si。否則設(shè)置為T(mén)Pi,j（見(jiàn)第11-16行）。注意，我們假設(shè)在聚合時(shí)間之前盡早生成新的消息（與Si一樣多）。

當(dāng)RSS聚合器聚合Fi時(shí)，存在新生成的消息發(fā)布數(shù)小于Si的情況。也就是說(shuō)，如果所有TPi,(j+1)都是0（這意味著在當(dāng)前聚合時(shí)間沒(méi)有待聚集的消息）即使存在更多要發(fā)生的聚合（即也要將所有TPi,(j+1)設(shè)置為λ（見(jiàn)第6-10行）。

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

TPi,(j+1)：第i個(gè)信息源j次收集后，還等待被收集的信息數(shù)量。

PPAi,j：第i個(gè)信息源第j次收集時(shí)收集的信息數(shù)。

3 結(jié)論

本文給出了兩種不同側(cè)重點(diǎn)的聚合策略，對(duì)于首先提到的固定聚合數(shù)目的方法，優(yōu)點(diǎn)是實(shí)現(xiàn)簡(jiǎn)單、容易操作，缺點(diǎn)是不夠靈活、沒(méi)有側(cè)重，對(duì)不同信息源一視同仁的分配聚合數(shù)目顯然是不夠精細(xì)的。相比于固定聚合數(shù)目策略，最小延遲收集策略顯然進(jìn)步了很多，它在不同信息源間加入了權(quán)重信息，在保證及時(shí)收集信息的同時(shí)對(duì)重要信息源有所側(cè)重，多分配聚合條目。最小延遲也意味著用戶能夠及時(shí)的看到更新，或得最佳的用戶體驗(yàn)并且算法也不復(fù)雜，非常適合實(shí)際使用。缺點(diǎn)在于對(duì)于固定的更新頻率，策略的更新次數(shù)是固定的，對(duì)硬件的訪問(wèn)頻率要求較高，不能自主控制聚合次數(shù)。

第三種最小丟失策略彌補(bǔ)了最小延遲策略的不足，在給定的聚合次數(shù)M中，能最小丟失的聚合信息，當(dāng)實(shí)際情況不允許頻繁發(fā)起聚合時(shí)，這種固定次數(shù)的收集算法，能保證丟失的信息最少。

實(shí)際使用中，信息以各種模式產(chǎn)生，程序設(shè)計(jì)者需要根據(jù)實(shí)際需求、硬件性能等客觀條件，靈活選擇聚合策略。

[1] 呂媛媛, 李可. 移動(dòng)端應(yīng)用設(shè)計(jì)中的響應(yīng)式實(shí)現(xiàn)方法[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網(wǎng)絡(luò)多控制器結(jié)構(gòu)的失效備援設(shè)計(jì)[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] 杜淑穎. 基于大型數(shù)據(jù)集的聚類算法研究[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] 陳峰, 熊勵(lì). 基于RSS信息服務(wù)聯(lián)盟的內(nèi)容聚合技術(shù)研究[J]. 計(jì)算機(jī)技術(shù)與發(fā)展, 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: 網(wǎng)絡(luò)信息“聚合”利器[J]. 現(xiàn)代情報(bào), 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聚合標(biāo)準(zhǔn)及其聚合策略[J]. 軟件，2016，37（12）：93-96