基于Tag-Tree模板的結(jié)構(gòu)化論壇信息提取

文/程倩楠

基于Tag-Tree模板的結(jié)構(gòu)化論壇信息提取

文/程倩楠

結(jié)構(gòu)化的論壇網(wǎng)站多采用動態(tài)網(wǎng)頁生成技術，將后臺數(shù)據(jù)庫的記錄信息加入HTML模板，以動態(tài)地顯示在網(wǎng)頁上。與此過程對稱，本文首先將不同BBS網(wǎng)站的大量網(wǎng)頁解析為Tag-Tree，然后計算樹的相似度與構(gòu)建代價生成多類Tag-Tree模板，同時得到每個模板所對應的網(wǎng)頁，尋找模板的重復模式確定記錄邊界。最后，利用模板解析相應網(wǎng)頁得到非模板內(nèi)容，進而采用啟發(fā)式規(guī)則提取結(jié)構(gòu)信息與記錄內(nèi)容。

相似度 構(gòu)建代價 Tag-Tree模板記錄邊界 啟發(fā)式規(guī)則

當今網(wǎng)頁信息提取大多采用人工編制的Tag-Tree模板程序?qū)W(wǎng)頁進行解析，提取過程過于繁瑣。本文針對傳統(tǒng)方式的弊端，提出一種基于Tag-Tree模板的結(jié)構(gòu)化論壇信息提取方法。

1 將網(wǎng)頁解析為Tag-Tree

網(wǎng)頁Tag-Tree包括標簽、文本、注釋三類結(jié)點。其中，文本只能作為Tag-Tree的葉子結(jié)點，而標簽作為普通結(jié)點擁有子節(jié)點和屬性集。一對標簽內(nèi)的文本與標簽作為此標簽的子結(jié)點，且這類標簽具有結(jié)束標簽。當網(wǎng)頁中一個標簽以“/>”結(jié)束時，我們認為該標簽是自結(jié)束的?；谝陨蠘?gòu)造規(guī)則，我們將網(wǎng)頁解析為Tag-Tree。

2 Tag-Tree模板的生成

定義Tag-Tree B，根節(jié)點為J，J的屬性集為S，其子節(jié)點為X，表示為B（J，X，S）。

2.1 定義Tag-Tree模板

樹B與模板B'的根節(jié)點相同，屬性集S'為S的子集，子節(jié)點X'為X的子集，以X'中節(jié)點為根節(jié)點的樹也是其對應X中節(jié)點為根節(jié)點的樹的模板。Tag-Tree模板的集合表示如下：

2.2 提取兩個Tag-Tree的模板

算法1：提取兩個Tag-Tree的公共子樹作為模板

輸入：兩個Tag-Tree

輸出：公共子樹

（1）將兩個Tag-Tree根節(jié)點作為公共子樹根節(jié)點。

（2）若兩個Tag-Tree對應節(jié)點的子節(jié)點存在多對相同結(jié)點，進行步驟3-4，否則進行步驟4。

（3）驗證哪對相同結(jié)點才是相對應的，可以通過計算每對結(jié)點樹的相似度，選擇最大相似度的子節(jié)點作為公共結(jié)點。

（4）將相同結(jié)點插入模板。

（5）重復上述1-4過程，直到所有結(jié)點判斷完畢，生成模板。

2.3 計算Tag-Tree相似度

為了得到Tag-Tree的構(gòu)建代價，首先計算Tag-Tree結(jié)點構(gòu)建代價T,其中默認葉子結(jié)點構(gòu)建代價為1，父節(jié)點構(gòu)建代價為自身代價1加上子節(jié)點代價的加權和，即

設Tag-tree D與Tag-Tree E提 取 的 模板為B,則D與E的相似度L為B的構(gòu)建代價在D和E中構(gòu)建代價的比例相乘，即提取模板的算法需要計算樹的相似度，而相似度的計算也要利用公共模板，這是一種迭代關系。

2.4 從不同網(wǎng)站提取多類模板

本文定義了模板提取過程中所需要的一種度量Minimal Template Portion簡記做MTP。如圖1所示。

提取多個網(wǎng)站不同網(wǎng)頁的各類公共模板我們的思路是，首先，將網(wǎng)頁解析為Tag-Tree,分別與模板集合中存在的各模板提取公共模板，計算新模板的MTP，選取具有最大MTP值的新模板代替原模板，加入模板集合中，并將Tag-Tree對應到此模板中。如果最大MTP小于臨界值ε，則創(chuàng)建新模板類，將此Tag-Tree置為模板及模板對應的第一個標簽樹。采用上述方法，得到最終的Tag-Tree模板集合及各模板所對應的網(wǎng)頁。

圖1

3 確定記錄邊界提取各類信息

Tag-Tree模板為多個網(wǎng)頁共有的部分，于此我們認為每個網(wǎng)頁所獨有的信息隱藏在Tag-Tree的非模板內(nèi)容中。由于BBS網(wǎng)頁中可能存在多個帖子，我們首先需要在模板上尋找子樹的重復模式，來確定記錄邊界。然后，利用生成的模板解析Tag-Tree,從而得到模板之外的非模板內(nèi)容。最后，利用啟發(fā)式規(guī)則及信息表達規(guī)則發(fā)現(xiàn)記錄內(nèi)不同字段的描述，進而得到不同的記錄信息。

4 結(jié)語

基于Tag-Tree模板的結(jié)構(gòu)化論壇信息提取方法，通過解析網(wǎng)頁得到Tag-Tree并計算樹的相似度，采用聚類思想完成不同類型BBS網(wǎng)站Tag-Tree模板的自動提取，用于解析HTML的非模板內(nèi)容，過濾了網(wǎng)頁中的廣告等噪音信息，較準確提取非模板內(nèi)的各種記錄信息。

[1]王璟琦.基于內(nèi)容單元的網(wǎng)頁解析與內(nèi)容提取[D].黑龍江：哈爾濱工業(yè)大學,2008(12).

[2]吉向文.標簽樹模板在網(wǎng)頁關鍵信息抽取及話題識別中的應用[D].上海：復旦大學,2009(04).

作者單位 山東師范大學信息科學與工程學院 山東省濟南市 250000

程倩楠（1997-），女，山東省泰安市人。山東師范大學信息科學與工程學院本科在讀。主要研究方向為計算機信息技術。