[發(fā)明專(zhuān)利]一種從維基百科半結(jié)構(gòu)化數(shù)據(jù)自動(dòng)構(gòu)建分類(lèi)樹(shù)的方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201410040234.9
• 申請(qǐng)日: 2014-01-27
• 公開(kāi)（公告）號(hào): CN103778238A
• 公開(kāi)（公告）日: 2014-05-07
• 發(fā)明（設(shè)計(jì)）人: 劉均;魏筆凡;馮博琴;鄭慶華;馬健;王晨晨;吳蓓
• 申請(qǐng)（專(zhuān)利權(quán)）人: 西安交通大學(xué)
• 主分類(lèi)號(hào): G06F17/30
• 分類(lèi)號(hào): G06F17/30
• 代理公司: 西安通大專(zhuān)利代理有限責(zé)任公司 61200
• 代理人: 蔡和平

技術(shù)領(lǐng)域

本發(fā)明涉及知識(shí)獲取技術(shù)領(lǐng)域，特別涉及一種利用維基百科半結(jié)構(gòu)化數(shù)據(jù)自動(dòng)構(gòu)建分類(lèi)樹(shù)的方法。

背景技術(shù)

互聯(lián)網(wǎng)促使信息數(shù)字化的進(jìn)程加速，其上信息以指數(shù)增長(zhǎng)。目前數(shù)字信息已呈現(xiàn)數(shù)量龐大、類(lèi)型繁多、更新迅速等發(fā)展趨勢(shì)。著名的Web搜索引擎Google索引的網(wǎng)頁(yè)數(shù)量目前已經(jīng)達(dá)到500億。信息時(shí)代帶來(lái)了海量的數(shù)字化文本，日益積累的數(shù)據(jù)使得信息的獲取越來(lái)越困難。

在數(shù)量巨大的頁(yè)面中含有人工編輯的半結(jié)構(gòu)化數(shù)據(jù)，這些數(shù)據(jù)散落在不同的頁(yè)面中，造成人們無(wú)法從大量頁(yè)面中迅速而準(zhǔn)確地找到這些有用的半結(jié)構(gòu)化信息。

維基百科(www.wikipedia.org)是目前訪問(wèn)量最大的十個(gè)網(wǎng)站之一，維基百科頁(yè)面由志愿者共同編輯，含有大量高質(zhì)量的半結(jié)構(gòu)化數(shù)據(jù)，這些半結(jié)構(gòu)化數(shù)據(jù)中蘊(yùn)藏著大量的上下位關(guān)系，因而需要自動(dòng)化的抽取方法從這些半結(jié)構(gòu)化數(shù)據(jù)中獲取上下位關(guān)系，并進(jìn)行融合最終形成分類(lèi)樹(shù)。

現(xiàn)有技術(shù)中尚未找到有關(guān)從維基百科半結(jié)構(gòu)化數(shù)據(jù)中抽取上下位關(guān)系抽取及構(gòu)建分類(lèi)樹(shù)的專(zhuān)利或者文獻(xiàn)；只檢索到了一篇與本專(zhuān)利相關(guān)的已授權(quán)專(zhuān)利：一種基于Web數(shù)值表格抽取的數(shù)據(jù)挖掘方法[專(zhuān)利號(hào)：ZL200910084507.9]；該專(zhuān)利的發(fā)明人基于領(lǐng)域知識(shí)庫(kù)，提出一種從Web數(shù)值表格抽取數(shù)值知識(shí)元庫(kù)的方法。該專(zhuān)利所述方法依賴領(lǐng)域知識(shí)庫(kù)，且只能處理數(shù)值表格，無(wú)法識(shí)別表格中字符串表示的實(shí)體及實(shí)體間的關(guān)系。

發(fā)明內(nèi)容

本發(fā)明的目的是提供一種從維基百科半結(jié)構(gòu)化數(shù)據(jù)自動(dòng)構(gòu)建分類(lèi)樹(shù)的方法，通過(guò)分析半結(jié)構(gòu)化數(shù)據(jù)中的模式和實(shí)體，自動(dòng)抽取出半結(jié)構(gòu)化數(shù)據(jù)中的實(shí)體及它們間的上下位關(guān)系，從而可以大大減少計(jì)算量，降低計(jì)算復(fù)雜度。所述實(shí)體是指維基百科頁(yè)面的標(biāo)題及結(jié)構(gòu)化數(shù)據(jù)中的最小處理單元。所述實(shí)體間的上下位關(guān)系是指實(shí)體間內(nèi)在的分類(lèi)關(guān)系。

為達(dá)到以上目的，本發(fā)明是采取如下技術(shù)方案予以實(shí)現(xiàn)的：

一種從維基百科半結(jié)構(gòu)化數(shù)據(jù)自動(dòng)構(gòu)建分類(lèi)樹(shù)的方法，包括以下步驟：

第1步、半結(jié)構(gòu)化數(shù)據(jù)的抽取：通過(guò)分析獲取到頁(yè)面的HTML，識(shí)別出含有半結(jié)構(gòu)化數(shù)據(jù)的頁(yè)面，所述半結(jié)構(gòu)化數(shù)據(jù)指維基百科目錄頁(yè)面及維基百科條目頁(yè)面中的導(dǎo)航表格；

第2步、半結(jié)構(gòu)化數(shù)據(jù)中上下位關(guān)系的抽取：抽取維基百科目錄頁(yè)面中上下位關(guān)系和導(dǎo)航表格中上下位關(guān)系；

第3步、源于不同半結(jié)構(gòu)化數(shù)據(jù)的上下位關(guān)系融合：依據(jù)抽取到的上下位關(guān)系集構(gòu)建向有向無(wú)權(quán)簡(jiǎn)單圖，然后基于圖的深度優(yōu)先遍歷算法生成分類(lèi)樹(shù)。

本發(fā)明進(jìn)一步的改進(jìn)在于：第1步具體包括以下步驟：

第1.1步：從維基百科網(wǎng)站首頁(yè)www.wikipedia.org開(kāi)始，通過(guò)解析頁(yè)面的超鏈接逐層爬取所有頁(yè)面，依據(jù)頁(yè)面URL前綴“http://en.wikipedia.org/wiki/”獲取條目頁(yè)面，依據(jù)URL前綴“http://en.wikipedia.org/wiki/Category:”獲取目錄頁(yè)面，每個(gè)頁(yè)面對(duì)應(yīng)一個(gè)實(shí)體，頁(yè)面標(biāo)題為該實(shí)體的名字；

第1.2步：根據(jù)條目頁(yè)面是否含有HTML標(biāo)簽<table?class＝″navbox″>，篩選出含有導(dǎo)航表格的條目頁(yè)面。

本發(fā)明進(jìn)一步的改進(jìn)在于：第1步具體包括以下步驟：

1)：通過(guò)Web頁(yè)面爬取工具爬取維基百科首頁(yè)http://www.wiki?pedia.org/并進(jìn)行解析，然后依據(jù)HTML標(biāo)簽<a>和</a>找出該頁(yè)面中的所有匹配模式http/:∨∨[a-z]+/.wikipedia/.org∨的超鏈接，記為{head_link_i}_n’其中n表示所有不同語(yǔ)言的維基子網(wǎng)站數(shù)目；每個(gè)這樣的超鏈接heaad_linnk_i對(duì)應(yīng)一種語(yǔ)言的維基百科子網(wǎng)站，并且是該子網(wǎng)站的首頁(yè)，枚舉每個(gè)維基子網(wǎng)站首頁(yè)的超鏈接head_link_i;

2)：構(gòu)建空的哈希表，該哈希表用來(lái)記錄某個(gè)頁(yè)面是否已經(jīng)被爬取過(guò)，使用頁(yè)面的URL地址來(lái)標(biāo)識(shí)不同的頁(yè)面；

3)：設(shè)置當(dāng)前爬取頁(yè)面地址為當(dāng)前維基子網(wǎng)站首頁(yè)，current_link＝head_link_i;

4)：在HashSet查詢curre?nt_link，如果命中，表明頁(yè)面已經(jīng)被爬取過(guò)，則不再爬取跳轉(zhuǎn)到第8步；如果該頁(yè)面沒(méi)有爬取過(guò)，則通過(guò)Web頁(yè)面爬取工具爬取該頁(yè)面，并將該鏈接加入到HashSet中，即執(zhí)行HashSet.add(current_link)；