[發(fā)明專利]基于頻繁子樹來導出記錄模板的方法

有效

• 申請?zhí)枺?/td>: 201110245084.1
• 申請日: 2011-08-16
• 公開（公告）號: CN102955796A
• 公開（公告）日: 2013-03-06
• 發(fā)明（設計）人: 徐鵬;陳正
• 申請（專利權）人: 微軟公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 上海專利商標事務所有限公司 31100
• 代理人: 胡利鳴;陸嘉

1.一種用于從網(wǎng)頁中導出數(shù)據(jù)記錄模板(data?record?template)的方法，所述方法包括：

從網(wǎng)頁中挖掘最大頻繁子樹(maximal?frequent?subtree)和閉合頻繁子樹(closed?frequent?subtree)，包括：

計算頻繁1-子樹(frequent-1subtree)，所述頻繁1-子樹是網(wǎng)頁的文檔對象模型DOM(document?object?model)樹中僅具有一個節(jié)點的頻繁子樹；

基于所述頻繁1-子樹，通過最右擴展來枚舉按頻繁排序的導出的子樹，所述最右擴展包括通過迭代地將新的子樹附加到頻繁子樹的最右分支上的節(jié)點來增長頻繁子樹；

將所有導出的子樹區(qū)分為最大頻繁子樹和閉合頻繁子樹，其中導出的子樹按頻繁排序；

對從網(wǎng)頁挖掘出的最大頻繁子樹和閉合頻繁子樹進行分組；

在分組內(nèi)標識模板子樹(TEN)，所述模板子樹是僅包括所有必要節(jié)點的模板，基于模板子樹來標識可選節(jié)點并消除噪音；以及

基于模板子樹從各個節(jié)點中抽取結構化數(shù)據(jù)，以導出數(shù)據(jù)記錄模板。

2.如權利要求1所述的方法，其特征在于，所導出的數(shù)據(jù)記錄模板是針對所述網(wǎng)頁的主數(shù)據(jù)記錄列表的數(shù)據(jù)記錄模板。

3.如權利要求1所述的方法，其特征在于，消除噪音進一步包括消除數(shù)據(jù)記錄列表周圍的噪音。

4.如權利要求1所述的方法，其特征在于，對從網(wǎng)頁挖掘出的最大頻繁子樹和閉合頻繁子樹進行分組進一步包括基于最大頻繁子樹和閉合頻繁子樹之間的所屬關系進行分組，使得各個分組包括一最大頻繁子樹和多個閉合頻繁子樹。

5.如權利要求4所述的方法，其特征在于，在分組內(nèi)標識模板子樹進一步包括對分組內(nèi)的各個最大頻繁子樹和閉合頻繁子樹計算一加權度量，其中具有最高加權度量的最大頻繁子樹或閉合頻繁子樹被標識為所述模板子樹。

6.如權利要求1所述的方法，其特征在于，所述可選節(jié)點包括最大頻繁子樹中的下述節(jié)點：所述模板子樹內(nèi)不具有與該節(jié)點相匹配的節(jié)點。

7.如權利要求5所述的方法，其特征在于，基于模板子樹從各個節(jié)點中抽取結構化數(shù)據(jù)進一步包括將其分組內(nèi)的具有最大加權度量的頻繁子樹是相同的最大頻繁子樹對齊來標識從中可抽取結構化數(shù)據(jù)的節(jié)點。

8.如權利要求7所述的方法，其特征在于，所述從中可抽取結構化數(shù)據(jù)的節(jié)點包括在頻繁子樹內(nèi)具有相同的兄弟節(jié)點和父節(jié)點但從不在一起出現(xiàn)來作為DOM樹中的節(jié)點的子節(jié)點的可選節(jié)點。

9.一種用于挖掘子樹結構的方法，所述方法包括：

計算頻繁1-子樹，所述頻繁1-子樹是網(wǎng)頁的文檔對象模型DOM樹中僅具有一個節(jié)點的頻繁子樹；

基于所述頻繁1-子樹，通過最右擴展來枚舉按頻繁排序的導出的子樹，所述最右擴展包括通過迭代地將新的子樹附加到頻繁子樹的最右分支上的節(jié)點來增長頻繁子樹；

將所有導出的子樹區(qū)分為最大頻繁子樹和閉合頻繁子樹，其中導出的子樹按頻繁排序。

10.如權利要求9所述的方法，其特征在于，計算頻繁1-子樹進一步包括使用標簽路徑來計算頻繁1-子樹，其中樹中一節(jié)點的標簽路徑是從該樹的根部到該節(jié)點的一系列節(jié)點。

11.如權利要求9所述方法，其特征在于，將所有導出的子樹區(qū)分為最大頻繁子樹和閉合頻繁子樹進一步包括使用基于出現(xiàn)的支持來區(qū)分一頻繁子樹是閉合頻繁子樹還是最大頻繁子樹。

12.一種用于從子樹結構得出數(shù)據(jù)記錄模板的方法，所述方法包括：

對從網(wǎng)頁挖掘出的最大頻繁子樹和閉合頻繁子樹進行分組；

在分組內(nèi)標識模板子樹(TEN)，所述模板子樹是僅包括所有必要節(jié)點的模板，基于模板子樹來標識可選節(jié)點并消除噪音；以及

基于模板子樹從各個節(jié)點抽取結構化數(shù)據(jù)，以得出數(shù)據(jù)記錄模板。

13.如權利要求12所述的方法，其特征在于，最大頻繁子樹和閉合頻繁子樹是從所述網(wǎng)頁的文檔對象模型DOM樹中挖掘的。

14.如權利要求12所述的方法，其特征在于，消除噪音進一步包括消除數(shù)據(jù)記錄列表周圍的噪音。