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