Web站點(diǎn)拓?fù)浣Y(jié)構(gòu)獲取方法研究

潘慶和，徐耀群，趙星馳

(1. 哈爾濱商業(yè)大學(xué) 計(jì)算機(jī)與信息工程學(xué)院，哈爾濱 150028；2. 哈爾濱科學(xué)技術(shù)職業(yè)學(xué)院 外語系，哈爾濱 150300)

Web站點(diǎn)拓?fù)浣Y(jié)構(gòu)獲取方法研究

潘慶和1，徐耀群1，趙星馳2

(1. 哈爾濱商業(yè)大學(xué) 計(jì)算機(jī)與信息工程學(xué)院，哈爾濱 150028；2. 哈爾濱科學(xué)技術(shù)職業(yè)學(xué)院 外語系，哈爾濱 150300)

提出了一種使用深度優(yōu)先遍歷方式實(shí)現(xiàn)的Web站點(diǎn)拓?fù)浣Y(jié)構(gòu)獲取策略，使用Python語言實(shí)現(xiàn)，并可擴(kuò)展成用于數(shù)據(jù)采集的爬蟲.利用這種方式可以對目標(biāo)網(wǎng)站進(jìn)行拓?fù)涮綔y，了解其內(nèi)部組織結(jié)構(gòu)，為進(jìn)一步的研究提供基礎(chǔ).

站點(diǎn)拓?fù)浣Y(jié)構(gòu)；深度優(yōu)先遍歷；Python；爬蟲

1 Web站點(diǎn)拓?fù)浍@取的意義

當(dāng)前，互聯(lián)網(wǎng)已經(jīng)成為人們工作生活不可或缺的一部分.截至2014年9月，全球互聯(lián)網(wǎng)網(wǎng)站數(shù)量已超過10.6億[1]，我國在2014年就開通新網(wǎng)站95.2萬個，平均每月7.9萬余個[2]，至2014年底，我國網(wǎng)站數(shù)量已經(jīng)達(dá)到364.7多萬個.這些網(wǎng)站所提供的信息不盡相同，類型各異，比如新聞類，電商類，論壇類，咨詢類等等，而每種類別又可以進(jìn)一步地細(xì)化分類，通過這種內(nèi)容的分類，可以對我國互聯(lián)網(wǎng)發(fā)展得到更加客觀和深入的認(rèn)識，無論對于網(wǎng)絡(luò)政策的制定，還是未來網(wǎng)絡(luò)發(fā)展的規(guī)劃，都具有十分重要的意義.本研究也是對網(wǎng)絡(luò)中的各類網(wǎng)站進(jìn)行分析和研究，但研究對象不是針對互聯(lián)網(wǎng)各網(wǎng)站的內(nèi)容，而是對各網(wǎng)站的拓?fù)浣Y(jié)構(gòu)進(jìn)行研究分析，并提出了一種切實(shí)可行的技術(shù)來獲得各網(wǎng)站的拓?fù)浣Y(jié)構(gòu).網(wǎng)站拓?fù)浣Y(jié)構(gòu)本質(zhì)上就是網(wǎng)站的內(nèi)容層次結(jié)構(gòu)，除去了具體內(nèi)容的含義，從抽象的角度研究網(wǎng)站的層次結(jié)構(gòu).這種研究具有十分重要的意義，比如說通過對一個網(wǎng)站拓?fù)浣Y(jié)構(gòu)的獲取，可以有效地了解網(wǎng)站在運(yùn)行過程中關(guān)鍵的信息節(jié)點(diǎn)，這些節(jié)點(diǎn)往往是性能瓶頸存在的位置;可以進(jìn)一步對關(guān)鍵節(jié)點(diǎn)進(jìn)行評測，從而設(shè)計(jì)合理的安全 防護(hù)策略.另外，在對網(wǎng)站拓?fù)涮綔y的同時，如果同時保留了所探測的頁面信息，可實(shí)現(xiàn)對網(wǎng)站整體信息的抓取.本研究設(shè)計(jì)的拓?fù)浍@取策略即可達(dá)到這種效果.

2 站點(diǎn)拓?fù)浣Y(jié)構(gòu)獲取方法

本文設(shè)計(jì)了一種基于深度優(yōu)先遍歷的網(wǎng)站拓?fù)浣Y(jié)構(gòu)獲取方法.基本思想如下:從網(wǎng)站的根路徑對應(yīng)的首頁面開始，依次逐個訪問該頁面中所包含的鏈接，這些鏈接因?yàn)槎荚谑醉撝校虼硕继幱谙嗤膶哟?，可認(rèn)為是根路徑的下一個層次.在每一個鏈接對應(yīng)的頁面中，再次重復(fù)這個步驟，如果一個頁面中所包含的鏈接全部都被訪問過，那么返回上一層次，在上一層次中找到?jīng)]有被訪問過的鏈接，繼續(xù)依照這種模式進(jìn)行訪問.在這個過程中，未訪問鏈接的數(shù)量會越來越少，當(dāng)網(wǎng)站所有的鏈接都被訪問后，就認(rèn)為任務(wù)結(jié)束，根據(jù)訪問過程中保留下來的線索信息即可生成網(wǎng)絡(luò)的拓?fù)?該思想的示意圖如圖1所示.

圖1 網(wǎng)絡(luò)拓?fù)渖疃缺闅v過程示意圖

圖1給出了前面設(shè)計(jì)思想的示意.圖中使用樹來描述獲取網(wǎng)站拓?fù)涞倪^程.樹的根節(jié)點(diǎn)為Root，對應(yīng)待探測網(wǎng)站的入口鏈接，一般該鏈接指向網(wǎng)站的首頁.樹中的每個節(jié)點(diǎn)均代表鏈接，比如Root下的A1，A2，A3，...，Am表示點(diǎn)擊Root鏈接所到達(dá)的頁面中包含的未訪問鏈接.B1的子節(jié)點(diǎn)C1，C2，C3表示點(diǎn)擊鏈接B1后到達(dá)的頁面中所包含的未訪問鏈接.C1沒有子節(jié)點(diǎn)，表示點(diǎn)擊鏈接C1后，到的頁面中已無未訪問鏈接.箭頭描述了拓?fù)浒l(fā)現(xiàn)的執(zhí)行方向，箭頭上的數(shù)字為執(zhí)行的順序.可以看出沿著1->2->3->4->5->6->7->8->9->10->11->12的路徑，恰好是前面描述的思想所對應(yīng)的執(zhí)行路徑.帶有“X”標(biāo)志的箭頭表示不沿著該箭頭所示方向進(jìn)行探索，通常這種情況一般表示探索的鏈接將指向其他網(wǎng)站，一般來講對網(wǎng)站拓?fù)涞奶綔y發(fā)現(xiàn)過程將只涉及到該網(wǎng)站自身，并不涉及到其他網(wǎng)站.盡管并不對鏈接到的外部網(wǎng)站進(jìn)行探索，但為了保存相應(yīng)的信息，仍把外部網(wǎng)站的根節(jié)點(diǎn)信息作為網(wǎng)站拓?fù)浣Y(jié)構(gòu)的一部分，比如對于圖中帶有“X”標(biāo)志的箭頭所指向的那個灰色節(jié)點(diǎn)，也作為網(wǎng)站拓?fù)涞囊徊糠直４?從上圖的形式看，這種拓?fù)涞奶綔y發(fā)現(xiàn)十分類似于數(shù)據(jù)結(jié)構(gòu)中樹的深度優(yōu)先遍歷所給出的形式，這正是我們提出的基于深度遍歷的Web站點(diǎn)拓?fù)浣Y(jié)構(gòu)獲取策略名稱的由來.在對于樹的深度遍歷過程中，通常使用遞歸的方式進(jìn)行，因此可以將上面的拓?fù)浒l(fā)現(xiàn)策略抽象為遞歸過程.下面給出這種策略思想的簡單描述，由于使用了遞歸形式，因此策略的描述十分簡潔.

Algorithm: Get topology structure of a website

get_site_map(link，exclusive_links)

Input:

1) root_url of a website; #網(wǎng)站的根url鏈接；

2) exclusive_links; #無需進(jìn)一步遍歷的網(wǎng)站鏈接列表，比如圖1中其他網(wǎng)站的根鏈接將在此列表中.Output:

網(wǎng)站拓?fù)浣Y(jié)構(gòu)(用恰當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)或圖形表示).

Steps:

Step1. 如果link沒有被探測，則得到link所指向頁面中包含的鏈接列表link_list，列表中不應(yīng)包含link和 exclusive_link所包含的鏈接，同時將該link加入到已探測訪問過得鏈接列表visited_link_list中;如果link已經(jīng)被探測過，則不在對其探測，返回；

Step2. 對于link_list中的每個元素a，繼續(xù)調(diào)用 get_site_map(a， exclusive_links).

應(yīng)該指出的是，這種形式的策略與網(wǎng)絡(luò)爬蟲的工作方式十分相似.網(wǎng)絡(luò)爬蟲是一個十分形象的名稱.通常來講網(wǎng)絡(luò)爬蟲可以分為兩類，一類是像搜索引擎提供商所設(shè)計(jì)的爬蟲，這類爬蟲會不斷地在互聯(lián)網(wǎng)中利用鏈接跳轉(zhuǎn)，采集頁面信息，返回后供搜索引擎建立相應(yīng)的索引，這樣當(dāng)我們在引擎中輸入文字進(jìn)行搜索時，引擎就會根據(jù)輸入對爬蟲曾經(jīng)得到的信息進(jìn)行檢索，找到接近我們搜索文字的相關(guān)內(nèi)容并返回.另一種爬蟲是對明確指定的網(wǎng)站進(jìn)行抓取的，這是最常見的一類爬蟲.利用這類爬蟲可以對具體的目標(biāo)網(wǎng)站進(jìn)行數(shù)據(jù)抓取，獲得所需要的信息.這些信息通常都是可以公共訪問的，利用程序設(shè)計(jì)爬蟲來抓取的主要原因是可以節(jié)省人工瀏覽并保存信息的工作量.比如，對于各類大型電商網(wǎng)站商品信息，房地產(chǎn)領(lǐng)域住房信息，各種機(jī)械，電子領(lǐng)域的部件信息，都可以設(shè)計(jì)爬蟲有目的的抓取.大數(shù)據(jù)時代，這種獲取也是自建大數(shù)據(jù)集的一種有效手段.本研究對網(wǎng)站拓?fù)浍@取所使用的技術(shù)，工作方式上類似于第二類爬蟲.

3 拓?fù)浍@取策略的實(shí)現(xiàn)

對于已給出的策略，在實(shí)施上有很多問題需要考慮.比如：

1)如何獲得一個頁面內(nèi)所包含的所有鏈接的列表?

2)如何跟蹤探測一個鏈接?在html頁面中通常使用a標(biāo)簽表示一個鏈接，一般來講a的href屬性就是需要進(jìn)一步探測的鏈接，獲得這個屬性值后，就可以根據(jù)它進(jìn)行適當(dāng)?shù)奶D(zhuǎn)；另一種常見的情況是，一個鏈接的跳轉(zhuǎn)是通過點(diǎn)擊它，觸發(fā)相關(guān)的js代碼實(shí)現(xiàn)的，那么如何設(shè)計(jì)一種探測方法同時兼顧這兩種方式，是一個值得研究的技術(shù)問題，這將使我們設(shè)計(jì)的程序更具一般性，適應(yīng)更加廣泛的場合.

3)在step1和step2的描述中，只給出了一般的探測策略，但為了最后得到整個網(wǎng)站的拓?fù)浣Y(jié)構(gòu)的詳細(xì)信息，必須在step1和step2的執(zhí)行過程中同時將探測到的信息記錄下來，那么采用何種數(shù)據(jù)結(jié)構(gòu)或存儲機(jī)制更為合適?

4)如何直觀地展示拓?fù)浣Y(jié)構(gòu)?如何將探測到的網(wǎng)站拓?fù)浣Y(jié)構(gòu)以圖形的方式表示出來，獲得更加直觀的認(rèn)識，也是一個十分值得研究的問題.

以上的4個問題是將要關(guān)注的主要問題，但并不是全部問題，在實(shí)現(xiàn)的過程，還有會遇到很多其他的問題需要解決.對與上面列出的幾個問題，都是從程序設(shè)計(jì)角度提出的，因此接下來就需要結(jié)合某種語言來解決這些問題，實(shí)現(xiàn)相應(yīng)的功能.Java，C#，C++，C等主流語言都可以作為選擇，本研究中使用Python[3]作為實(shí)現(xiàn)語言，主要原因是Python的動態(tài)語法機(jī)制更加靈活簡潔，同時Python有強(qiáng)大的支持庫可以方便地調(diào)用，加快開發(fā)的效率.本研究所提供的拓?fù)浍@取策略并不依賴于具體的語言，其他動態(tài)類型腳本語言如PHP和Ruby等也可作為實(shí)現(xiàn)語言，方式也都類似.下表1給出了利用Python實(shí)現(xiàn)時，上述四個問題所涉及的解決技術(shù).在拓?fù)淇梢暬矫妫褂昧薌raphviz[4]作為工具，將Python探測到的拓?fù)湫畔@示出來.

表1 針對各問題的解決方案

解決方案說明 問題1Beautifulsoup[5](Python)使用該庫可以方便地根據(jù)需求提取頁面中的信息．問題2Selenium[6](Python)一個可以模擬各種瀏覽器的庫，利用該庫可以利用模擬點(diǎn)擊的方式來進(jìn)行鏈接的探測，有效地解決了問題2．問題3Python面向?qū)ο蠹夹g(shù)(Python)在跟蹤拓?fù)湫畔⒌臅r候，可以設(shè)計(jì)鏈接類，對每一個鏈接都用一個鏈接對象來表示，利用對象的屬性保存相應(yīng)的信息，達(dá)到保留拓?fù)浣Y(jié)構(gòu)線索的作用，有效地解決了問題3．問題4Graphviz在運(yùn)行結(jié)束時，可將各鏈接對象的信息抽取出來，然后把這些信息組成字符串，供Graph?viz作圖．

需要說明的是，對于問題3中鏈接類的設(shè)計(jì)涉及了許多的細(xì)節(jié)，比如每個鏈接對象都需要保存其父節(jié)點(diǎn)鏈接，保存其子鏈接列表，而鏈接類還要有變量來保存全局已經(jīng)訪問過的鏈接和鏈接對象，這樣當(dāng)拓?fù)浍@取完成時，可以根據(jù)對象間的這些鏈接線索穿成一條線，完成對整體拓?fù)浣Y(jié)構(gòu)的獲取.

4 實(shí) 驗(yàn)

本節(jié)應(yīng)用上節(jié)所設(shè)計(jì)的程序進(jìn)行網(wǎng)站拓?fù)涞墨@取，目標(biāo)是哈爾濱商業(yè)大學(xué)的官方網(wǎng)站.圖2是網(wǎng)站的首頁.

圖2 網(wǎng)站首頁內(nèi)容

該網(wǎng)站是一個以新聞咨詢?yōu)橹鞯木W(wǎng)站，網(wǎng)站包含很多鏈接跳轉(zhuǎn)到學(xué)校的各個職能部門，對于這些部門的網(wǎng)站都是獨(dú)立的，因此在拓?fù)浍@取的過程中將只記錄這些部門首頁的鏈接，將其作為整體拓?fù)涞囊徊糠?對于各部門內(nèi)部的拓?fù)鋵⒉辉偬綔y追蹤.如果對這些子部門內(nèi)部的拓?fù)浣Y(jié)構(gòu)也感興趣，則可繼續(xù)探測，將探測到的拓?fù)浣Y(jié)構(gòu)和整體拓?fù)淅檬醉撴溄酉噙B接即可.

將實(shí)現(xiàn)前面拓?fù)洳呗缘某绦蛭募麨間et_site_map.py.使用的方式是利用Windows命令行CMD程序或Linux的終端，進(jìn)入到該文件的目錄，然后輸入命令python get_site_map.py http://www.hrbcu.edu.cn/啟動即可.其中，python將啟動本機(jī)安裝的python解釋器，get_site_map.py 是文件名稱，參數(shù)”http://www.hrbcu.edu.cn/”是待探測網(wǎng)站的主頁鏈接. 程序?qū)⑦\(yùn)行一段時間，在程序最后，為了可視化地展示拓?fù)浣Y(jié)構(gòu)，將得到的拓?fù)湫畔⒔M織成了graphviz繪圖程序所能識別的結(jié)構(gòu)形式，這將生成一個dot文件，里面包含有網(wǎng)站拓?fù)浣Y(jié)構(gòu)的信息，比如可命名文件為graph.dot.文件內(nèi)容如下.

digraph G {

"http://www.hrbcu.edu.cn/"->"http://3w.hrbcu.edu.cn/";

"http://www.hrbcu.edu.cn/"->"http://en.hrbcu.edu.cn/";

"http://www.hrbcu.edu.cn/"->"/Category_28/Index.aspx";

"http://www.hrbcu.edu.cn/"->"/Category_40/Index.aspx";

"http://www.hrbcu.edu.cn/"->"/Category_41/Index.aspx";

"http://www.hrbcu.edu.cn/"->"/Category_93/Index.aspx";

"http://www.hrbcu.edu.cn/"->"/Category_117/Index.aspx";

"http://www.hrbcu.edu.cn/"->"/Category_118/Index.aspx";

"http://www.hrbcu.edu.cn/"->"/Category_38/Index.aspx";

…

}

然后同樣在命令行或終端環(huán)境下，導(dǎo)航到文件所在目錄，運(yùn)行g(shù)raphviz -Tjpeg graph.dot -o graph.jpg便可在相同目錄下生成grapg.jpg，這個圖片就是網(wǎng)站的拓?fù)浣Y(jié)構(gòu)圖，圖3中給出了部分截圖.

從圖3中可以清楚的看到，網(wǎng)站形式為三級層次，這和一般的新聞咨詢類網(wǎng)站風(fēng)格是一致的.該圖中有兩個鏈接“http://djgz.hrbcu.edu.cn”和”http://kxfz.hrbcu.edu.cn/”分別跳轉(zhuǎn)至不同的子部門，因此只保留了入口鏈接而并沒有繼續(xù)的探測.如果需要可進(jìn)一步探測，然后將獲得到的拓?fù)浣Y(jié)構(gòu)信息在上述鏈接處和整體結(jié)構(gòu)相鏈接即可.同時可以看到，有的二級節(jié)點(diǎn)連接著大量的三級子節(jié)點(diǎn)，這些二級樞紐節(jié)點(diǎn)在提升網(wǎng)絡(luò)性能和提高安全性的角度都是需要關(guān)注的對象.

圖3 網(wǎng)站拓?fù)浣Y(jié)構(gòu)部分截圖

前面提到過，在探測的過程中如果將頁面信息同時保存下來，即可實(shí)現(xiàn)網(wǎng)絡(luò)爬蟲的功能.對于本實(shí)驗(yàn)也可在探測拓?fù)鋾r同時保存所探測的網(wǎng)頁.圖4給出了保存網(wǎng)頁文件夾的截圖，其中每一個網(wǎng)頁文件的名稱為時間戳加上兩個隨機(jī)數(shù)字，利用下劃線相連接，這是因?yàn)槿绻綔y速度過快，可能導(dǎo)致同一個時間戳對應(yīng)多個頁面的情況，因此利用時間戳加上兩個隨機(jī)數(shù)的形式，可以最大可能地避免這個問題.如果將網(wǎng)頁文件名作為鏈接對象的一個屬性值保存，也可建立起這些文件間的關(guān)聯(lián).

圖4 抓取到的網(wǎng)頁文件

5 結(jié) 語

本文給出了一種Web站點(diǎn)拓?fù)浍@取的策略，并利用Python語言加以實(shí)現(xiàn)，得到了一種通用的，適合于各種類型網(wǎng)站的拓?fù)浍@取方法.通過使用拓?fù)浍@取的方式對網(wǎng)站進(jìn)行研究，可以在網(wǎng)站分類，性能評測，安全性防護(hù)方面給出有價值的建議.文中使用selenium進(jìn)行鏈接的追蹤是一種通用性的考慮，因?yàn)橥ㄟ^模擬點(diǎn)擊追蹤鏈接的方式，可以無需關(guān)心鏈接的具體形式.如果不考慮通用性，有的站點(diǎn)可以使用asyncio，aiohttp[7]等進(jìn)行快速地探測和抓取.文本設(shè)計(jì)的拓?fù)浍@取程序，經(jīng)過簡單地改動可以變成一個爬蟲，在探測拓?fù)涞耐瑫r保存相關(guān)的網(wǎng)頁，為進(jìn)一步分析提供基礎(chǔ).

[1] 法新社. 全球互聯(lián)網(wǎng)網(wǎng)站數(shù)量破10億[J]. 中國教育網(wǎng)絡(luò), 2014(10): 4.

[2] 國家互聯(lián)網(wǎng)應(yīng)急中心.中國互聯(lián)網(wǎng)站發(fā)展?fàn)顩r及其安全報(bào)告(2015) [EB/OL]. http://www.isc.org.cn/zxzx/ywsd/listinfo-31792.html, 2015-03-20.

[3] MARK J J. A Concise Introduction to Programming in Python [M]. United Kingdom: Chapman & Hall/CRC Textbooks in Computing, 2012.

[4] JOHN E, EMDEN G, LEFTERIS K,etal. Graphviz—Open Source Graph Drawing Tools [J]. Graph Drawing Lecture Notes in Computer Science, 2002, 2265: 483-484.

[5] VINEETH G N. Getting Started with Beautiful Soup [M]. Birmingham: Packt Publishing, 2014.

[6] BURNS D. Selenium 2 Testing Tools: Beginner's Guide [M]. Birmingham: Packt Publishing, 2012.

[7] JAN P. Parallel Programming with Python [M]. Birmingham: Packt Publishing, 2014.

Research on acquisition method of Web site topology

PAN Qing-he1, XU Yao-qun1, ZHAO Xing-chi2

(1. School of Computer and Information Engineering, Harbin University of Commerce, Harbin 150028, China;2. Department of Foreign Languages, Harbin Vocational College of Science and Technology, Harbin 150300, China)

In this paper, the strategy on the obtainment of website topology structure was put forward based on depth first traversal. The Python language was used to implement this strategy and the program can be extended to construct a web crawler. By obtaining web site topology structure it could detect and understand the internal organizational structure of the website and would provide a basis for further research.

website topology structure; depth first traversal; Python; crawler

2015-01-27.

黑龍江省自然科學(xué)基金資助(F201035)

潘慶和(1981-)，男，博士，講師，研究方向：大數(shù)據(jù)分析，數(shù)據(jù)抓取，數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)，數(shù)據(jù)可視化.

TP393

A

1672-0946(2015)05-0573-05