批量圖片器設(shè)計(jì)論文

1、 第iii頁mass picture downloader圖片批量下載器 摘 要批量下載圖片可以方便用戶從一個(gè)網(wǎng)站下載大量圖片，節(jié)省用戶時(shí)間，給用戶帶來便利。本文設(shè)計(jì)和實(shí)現(xiàn)一個(gè)基于正則表達(dá)式的圖片批量下載器。本文首先在分析網(wǎng)上現(xiàn)有的圖片下載器的工作原理及運(yùn)行結(jié)果的基礎(chǔ)之上，針對(duì)原有的爬蟲搜索所有url的下載方式所存在的不合理性與盲目性，基于正則表達(dá)式對(duì)url進(jìn)行判定和解析，設(shè)計(jì)了新的圖片下載器的總體架構(gòu)，且該架構(gòu)主要包括爬蟲模塊和正則表達(dá)式自動(dòng)產(chǎn)生模塊兩個(gè)部分。本文對(duì)爬蟲模塊的設(shè)計(jì)和實(shí)現(xiàn)原理進(jìn)行了詳細(xì)闡述。爬蟲模塊設(shè)計(jì)新的下載方式，要求用戶指定的正則表達(dá)式為圖片url的提取標(biāo)準(zhǔn)，使得程序可以更

2、快搜索并下載下來圖片。程序根據(jù)用戶指定的正則表達(dá)式再結(jié)合爬蟲程序來提取出一個(gè)網(wǎng)頁中的地址，直到到達(dá)指定層數(shù)，最后執(zhí)行下載。在分析url的同時(shí)，程序亦建立網(wǎng)站層次樹，以便用戶查看那些未下載成功的圖片在網(wǎng)站上的確切位置，從而可以選擇重新下載。本文詳細(xì)介紹了正則表達(dá)式自動(dòng)模塊的設(shè)計(jì)和實(shí)現(xiàn)，該模塊通過用戶輸入的，從而得到一個(gè)比較高效的正則表達(dá)式，以供圖片批量下載器使用。并且程序?qū)σ粋€(gè)正規(guī)的圖片網(wǎng)站執(zhí)行下載，運(yùn)行結(jié)果表明，該程序能夠快速準(zhǔn)確的完成用戶指定的下載任務(wù)，且使用較為方便，大大節(jié)省了用戶的時(shí)間。論文最后對(duì)全文做出了總結(jié)，并對(duì)未來研究方向進(jìn)行了展望。關(guān)鍵詞：圖片下載，正則表達(dá)式，爬蟲程序，動(dòng)態(tài)規(guī)劃

3、算法，規(guī)范 ，javamass picture downloaderabstractmass picture downloader is a software that can save users time by downloading thousands of pictures from a website automatically.this thesis is about the design and the realization of the mass picture downloader.a new architecture of the software has been bu

4、ilt，which includes two parts called crawler and regular expression generator.basing on the analysis of the working mechanism and the results of existent mass picture downloaders，this thesis describes a new way that is different from traditional blindly search on urls using a crawler.the new way is b

5、ased on the analysis to the urls by using regular expression.this thesis describes the design and the realization of the crawler in detail.a new way has been designed for the crawler part.in the new way，a regular expresssion appointed by the user is used to extract the urls from a webpage，which，inde

6、ed，make the search and downloading much faster.the program extracts a url from a webpage according to the regular expression，then gets the content of the webpage indexed by the extracted url，and then analyzes the content of the webpage by using the regular expresssion next layer，until reaches the de

7、signated layer count.during the analysis of the urls，a websitetree is being built，in order to do the users a favor when they want to see the address of the downloading-unfinished pictures.this thesis also describes the design and the realization of the regular expression generator in detail. the reg

8、ular expression generator provides regular expression that generated through the urls input by the users to the crawler to make it work.then the program is put into practice-download pictures from a large picture website，the result shows that the program works well.at last，this thesis makes a summar

9、y about the program，and gives an expectation about the future.key words: picture downloader，regular expression，crawler，dynamic programming，url specification，java目 錄圖片批量下載器ii摘 要iiabstractiii1 緒論11.1 課題研究背景及意義11.1.1 研究背景11.1.2 研究意義21.2 國(guó)內(nèi)研究現(xiàn)狀21.3 研究的主要內(nèi)容31.4 論文組織結(jié)構(gòu)31.5 本章小結(jié)42 圖片批量下載器的總體架構(gòu)設(shè)計(jì)52.1 總體設(shè)計(jì)52

10、.2 關(guān)鍵模塊簡(jiǎn)介52.2.1 爬蟲模塊52.2.2 正則表達(dá)式自動(dòng)產(chǎn)生器模塊62.3 本章小結(jié)63 爬蟲程序的整體設(shè)計(jì)和實(shí)現(xiàn)及相關(guān)技術(shù)要點(diǎn)73.1 爬蟲程序的整體設(shè)計(jì)和實(shí)現(xiàn)73.2 相關(guān)技術(shù)要點(diǎn)133.2.1 檢查重復(fù)url133.2.2 將相對(duì)地址轉(zhuǎn)化為絕對(duì)地址143.2.3 將一張圖片下載下來的函數(shù)163.3 本章小結(jié)174 正則表達(dá)式自動(dòng)產(chǎn)生器184.1 基于動(dòng)態(tài)規(guī)劃的最優(yōu)字符串比對(duì)算法184.1.1 字符串比對(duì)定義184.1.2 字符串比對(duì)問題的動(dòng)態(tài)規(guī)劃解法184.2 正則表達(dá)式自動(dòng)產(chǎn)生器總體設(shè)計(jì)和實(shí)現(xiàn)224.2.1 假設(shè)和規(guī)定224.2.2 自動(dòng)產(chǎn)生正則表達(dá)式的問題分析和基本思路2

11、24.2.3 正則表達(dá)式自動(dòng)產(chǎn)生器設(shè)計(jì)和實(shí)現(xiàn)254.3 程序測(cè)試結(jié)果324.4 本章小結(jié)345 結(jié)論與展望355.1 工作總結(jié)355.2 工作展望35致謝36參考文獻(xiàn)37附錄a38 第49頁1 緒論1.1 課題研究背景及意義1.1.1 研究背景目前，隨著多媒體技術(shù)的發(fā)展，對(duì)信息的表現(xiàn)形式逐步趨向多元化，其中數(shù)字圖片是信息傳遞的主要形式之一。對(duì)于喜歡收藏各種精美數(shù)字圖片的人而言，下載少量圖片可以通過瀏覽器簡(jiǎn)單的右鍵保存到本地硬盤，但是如果要下載一個(gè)網(wǎng)站上成千上萬張圖片，手工一張一張保存，已經(jīng)是不可能的事，更何況目前大多數(shù)圖片網(wǎng)站，一張圖片要點(diǎn)擊平均3-4次才能得到真正想要的圖片。于是針對(duì)該種狀況

12、，設(shè)計(jì)一款圖片批量下載工具，方便用戶批量下載網(wǎng)站的圖片，節(jié)省用戶時(shí)間。目前，互聯(lián)網(wǎng)上圖片網(wǎng)站都具有如下特征：1.網(wǎng)站排版很有規(guī)則，網(wǎng)站的層次結(jié)構(gòu)鮮明且固定，比如：用戶從進(jìn)入一個(gè)網(wǎng)站到看到他所想要的圖片，所要點(diǎn)擊的次數(shù)都是固定的，這就成為可以采用正則表達(dá)式層來進(jìn)行url匹配的前提條件。2.目前絕大多數(shù)網(wǎng)站，都沒有采用反盜鏈技術(shù)，這就使得爬蟲程序能夠運(yùn)行成為可能。3.絕大多數(shù)網(wǎng)站，如果從用戶每一次深層次的點(diǎn)擊角度來看待，那么處于同一層的多個(gè)url具有相似性，這就使正則表達(dá)式的精確匹配成為可能。4.幾乎所有網(wǎng)站，表示下一頁的方式都是固定不變的，比如：一個(gè)網(wǎng)站的下一頁都用一個(gè)按鈕，或者一個(gè)文字超鏈接等

13、等，這就使遞歸的分析下一頁成為可能。5.網(wǎng)頁上鏈接重復(fù)的情況，目前看來，全部發(fā)生在同一層里面，也就是說，僅有同一層才可能出現(xiàn)重復(fù)url的情況。在上述背景下，論文將對(duì)如何設(shè)計(jì)爬蟲程序和如何正確的提取出正則表達(dá)式進(jìn)行研究，詳細(xì)闡述可行方案和實(shí)現(xiàn)機(jī)制，旨在探求能夠高效方便的批量下載圖片的方法。1.1.2 研究意義圖片在目前的信息傳輸過程中起到重要的作用，豐富多彩的圖片能夠更加直觀，更加有效的表達(dá)出信息，本課題的研究意義就在于能夠幫助用戶高效的，批量的從大型圖片網(wǎng)站上搜集各種精美圖片，整個(gè)搜集過程要實(shí)現(xiàn)自動(dòng)化后臺(tái)操作，從而使用戶擺脫重復(fù)而繁重的右擊保存操作，節(jié)約用戶寶貴的時(shí)間。1.2 國(guó)內(nèi)研究現(xiàn)狀目前

14、網(wǎng)上流傳的圖片下載器種類繁多，技術(shù)也比較成熟，基本上都是基于傳統(tǒng)爬蟲技術(shù)，比較好的例如：globalfetch圖片下載器，picture downloader 等等。picture downloader是一款功能齊全的圖片下載軟件，可以新建下載任務(wù)，輸入給定的可用url，圖片大小，關(guān)聯(lián)網(wǎng)址級(jí)數(shù)及網(wǎng)址url所具有的特征文件夾名和特征后綴名，就可以開始下載任務(wù)，根據(jù)用戶指定的關(guān)聯(lián)網(wǎng)址級(jí)數(shù)，該工具從當(dāng)前網(wǎng)頁搜索指定深度的網(wǎng)頁。該軟件還可以與百度搜索引擎相關(guān)聯(lián)，將用戶提交的圖片搜索信息以表單形式提交給百度，然后在其內(nèi)置瀏覽器中顯示結(jié)果。globalfetch也有類似的功能。但是美中也有不足之處，具體情

15、況如下：1. 目前我所見到的幾款圖片下載器，基本上都是基于類似于搜索引擎一樣，搜索所有圖片鏈接，然后將所有圖片統(tǒng)統(tǒng)下載下來，然而，有可能這么多圖片并不是用戶所想要的，用戶的需求可能是，用戶只對(duì)網(wǎng)站上的一個(gè)系列或其中的某個(gè)人物的圖片感興趣，所以我想在針對(duì)某一主題進(jìn)行特定下載方面進(jìn)行改進(jìn)。2. 目前我所見到的幾款圖片下載器，雖然設(shè)定了限制條件，但還是有按鈕圖片等被批量下載下來，存在錯(cuò)誤下載格式的問題，所以我想在針對(duì)某一主題進(jìn)行特定下載方面進(jìn)行對(duì)此改進(jìn)。3. 目前我所見到的幾款圖片下載器，都是基于分析網(wǎng)頁上url地址，根據(jù)特征來提取網(wǎng)址，但是，目前非常多的網(wǎng)站采用反盜鏈功能，讓分析網(wǎng)頁鏈接這一方法完

16、全失效，如果圖片下載器遇到這種網(wǎng)站，根本不會(huì)下載任何東西。4.也有一些軟件自帶批量下載功能，比如迅雷中的下載全部鏈接功能，以及qq瀏覽器中的提取圖片功能，但以上都只能單純的提取當(dāng)前網(wǎng)頁的圖片，無法對(duì)網(wǎng)站進(jìn)行深層次的搜索。參考文獻(xiàn)1指出：文件偽裝是目前采用的最多的反盜鏈技術(shù)，一般會(huì)結(jié)合服務(wù)器端的動(dòng)態(tài)腳本(jsp)。實(shí)際上，用戶請(qǐng)求的文件地址，只是一個(gè)經(jīng)過偽裝的腳本文件，這個(gè)腳本文件會(huì)對(duì)用戶的請(qǐng)求作出認(rèn)證，一般會(huì)檢查session，cookie或 http_referer作為判斷是否為盜鏈的依據(jù)。而真實(shí)的文件隱藏在用戶不能夠訪問的地方，只有用戶通過驗(yàn)證后才會(huì)返回該用戶。目前有許多網(wǎng)站采用反盜鏈技術(shù)

17、，這一技術(shù)的采用，使得一般的爬蟲程序無法正常運(yùn)行，由于反盜鏈?zhǔn)沟门老x無法獲得可用鏈接，就需要采用其它方法。1.3 研究的主要內(nèi)容本文研究的主要內(nèi)容包括爬蟲程序的構(gòu)建和如何根據(jù)用戶輸入的url來提取出準(zhǔn)確的正則表達(dá)式兩大內(nèi)容。最后，把程序應(yīng)用于一個(gè)大型圖片網(wǎng)站中，實(shí)現(xiàn)批量下載，從而驗(yàn)證模型和算法是合理的、有效的。1.4 論文組織結(jié)構(gòu)全文共分為四章，其中：第1章 是緒論部分，首先簡(jiǎn)單概括了課題的來源和背景，然后論述了國(guó)內(nèi)研究現(xiàn)狀，最后根據(jù)來源和背景提出了程序研究的主要問題和內(nèi)容，并闡述了程序的意義以及論文的組織結(jié)構(gòu)。第2章 介紹了圖片下載器的總體架構(gòu)設(shè)計(jì)。第三章主要論述了程序主體爬蟲程序的總體設(shè)計(jì)

18、方案。首先討論了程序需求并根據(jù)程序需求分析提出了程序總體解決方案。隨后，詳細(xì)描述了在爬蟲程序執(zhí)行過程中要解決的關(guān)鍵問題的設(shè)計(jì)和實(shí)現(xiàn)，包含如何防止重復(fù)下載，如何通過正則表達(dá)式提取出url，如何構(gòu)建網(wǎng)站層次樹等等。第四章主要論述了程序附屬正則表達(dá)式產(chǎn)生器的總體設(shè)計(jì)方案。首先描述了正則表達(dá)式產(chǎn)生器需求分析提出了程序總體解決方案。隨后，詳細(xì)描述了提取正則表達(dá)式過程中要解決的關(guān)鍵問題的設(shè)計(jì)和實(shí)現(xiàn)。第四章最后針對(duì)實(shí)際圖片網(wǎng)站給出了程序測(cè)試結(jié)果，以驗(yàn)證程序的正確性。第五章總結(jié)全文，并展望了未來發(fā)展方向。1.5 本章小結(jié)本章詳細(xì)描述了本課題的所處的背景，由于這些背景因素的存在，使得本課題的實(shí)現(xiàn)成為可能。本章接

19、著提出了本課題的研究意義，分析了國(guó)內(nèi)的研究現(xiàn)狀和所取得的研究成果，并列舉出相關(guān)示例加以闡述，最后提出了本文的主要研究?jī)?nèi)容及論文的結(jié)構(gòu)。2 圖片批量下載器的總體架構(gòu)設(shè)計(jì)2.1 總體設(shè)計(jì)圖片批量下載器主要由網(wǎng)站爬蟲程序和正則表達(dá)式自動(dòng)產(chǎn)生程序組成，正則表達(dá)式產(chǎn)生程序負(fù)責(zé)從用戶統(tǒng)計(jì)輸入的url中提取出這些url的特征正則表達(dá)式，然后加入到爬蟲程序的正則表達(dá)式隊(duì)列中，作為提取某一層后臺(tái)頁面的url的標(biāo)尺。爬蟲程序就是根據(jù)正則表達(dá)式隊(duì)列中的url正則表達(dá)式對(duì)一個(gè)網(wǎng)站進(jìn)行一層一層的剝離，直到正則表達(dá)式隊(duì)列指定的層數(shù)。圖片批量下載器的總體架構(gòu)設(shè)計(jì)如圖2-1所示。圖2-1 圖片批量下載器的總體架構(gòu)設(shè)計(jì)2.2

20、關(guān)鍵模塊簡(jiǎn)介2.2.1 爬蟲模塊爬蟲程序是本課題的主體程序，該模塊工作時(shí)首先接受用戶輸入的一個(gè)入口頁，然后再接受用戶通過正則表達(dá)式自動(dòng)產(chǎn)生器得到的一層url的正則表達(dá)式，用戶輸入完畢之后，爬蟲程序開始根據(jù)用戶輸入的每一層的正則表達(dá)式提取出下一層url，接著在下一層，這樣循環(huán)，直到指定層數(shù)。2.2.2 正則表達(dá)式自動(dòng)產(chǎn)生器模塊該模塊是專門針對(duì)上述爬蟲程序開發(fā)的模塊，此模塊的功能主要是根據(jù)用戶統(tǒng)計(jì)輸入的url進(jìn)行特征提取，最后得到一個(gè)較為準(zhǔn)確的url正則表達(dá)式，然后再提供給爬蟲程序使用。2.3 本章小結(jié)本章通過系統(tǒng)總體協(xié)作圖簡(jiǎn)要介紹了圖片下載器的整體架構(gòu)，以及兩個(gè)關(guān)鍵模塊的主要功能。3 爬蟲程序的

21、整體設(shè)計(jì)和實(shí)現(xiàn)及相關(guān)技術(shù)要點(diǎn)爬蟲程序是本課題的主體程序，本章詳細(xì)闡述了如何根據(jù)1.1.1 的背景條件來有效設(shè)計(jì)爬蟲程序，并詳細(xì)描述了其實(shí)現(xiàn)。其他關(guān)鍵技術(shù)要點(diǎn)也給出了響應(yīng)的設(shè)計(jì)與實(shí)現(xiàn)。3.1 爬蟲程序的整體設(shè)計(jì)和實(shí)現(xiàn)傳統(tǒng)爬蟲從一個(gè)或若干初始網(wǎng)頁的url開始，獲得初始網(wǎng)頁上的url，在抓取網(wǎng)頁的過程中，不斷從當(dāng)前頁面上抽取新的url放入隊(duì)列，直到滿足系統(tǒng)的一定停止條件。本程序的爬蟲基于傳統(tǒng)爬蟲的設(shè)計(jì)理念，但是由于本程序的需求的具有特殊性，即：用戶登陸一個(gè)圖片網(wǎng)站，大多數(shù)情況下，用戶不可能想要下載該網(wǎng)站上的所有圖片，更多的情況是下載其中的一類，那么，如果采用傳統(tǒng)的爬蟲，就會(huì)嚴(yán)重影響搜索速度，而且下載

22、下來的并不一定是用戶所想要的。基于這個(gè)情況，可行的解決辦法是：程序運(yùn)行之前，用戶首先輸入一系列的正則表達(dá)式，每一個(gè)正則表達(dá)式能夠代表該層要提取的url的特征，用戶進(jìn)入入口頁之后， 根據(jù)當(dāng)前層的正則表達(dá)式提取出url，然后再以提取出的url為基礎(chǔ)，應(yīng)用第二層正則表達(dá)式，這樣，直到正則表達(dá)式層數(shù)結(jié)束，也就提取出了最終的圖片url。但是，基本上所有的圖片網(wǎng)站的某一個(gè)主題都不止一頁，有可能向后有100頁，那么在運(yùn)行上述爬蟲的時(shí)候，程序中間還要檢測(cè)當(dāng)前分析頁是否存在下一頁的鏈接，如果存在，那么還要將下一頁當(dāng)作同一級(jí)的網(wǎng)頁來處理，直到一個(gè)網(wǎng)頁中沒有下一頁的地址，或者該地址指向自身。在爬蟲程序遞歸分析網(wǎng)頁的

23、同時(shí)，可以同步構(gòu)造出網(wǎng)頁的層次結(jié)構(gòu)，即：在分析當(dāng)前url指示的網(wǎng)頁里面的內(nèi)容的時(shí)候，如果發(fā)現(xiàn)了子url，那么就將該子url加入到arraylist websitetree里面，并將該子url在websitetree里的位置加入到當(dāng)前url的子節(jié)點(diǎn)位置數(shù)組里面，然后將該子url的父節(jié)點(diǎn)的位置設(shè)為當(dāng)前url在websitetree里的位置，如此循環(huán)反復(fù)，就完成了網(wǎng)站層次結(jié)構(gòu)的構(gòu)建。由上述，從而得到如下算法：關(guān)鍵變量，類和方法的聲明：class treenodeint father;/此變量保存此節(jié)點(diǎn)的父節(jié)點(diǎn)在數(shù)組中的位置int selfrealpos;/此變量保存此節(jié)點(diǎn)本身在數(shù)組中的位置urlva

24、lue=0;/所保存的url字符串里面的字符相加得到的整數(shù)值string address;/該節(jié)點(diǎn)保存的url字符串a(chǎn)rraylist childrenpos;/該節(jié)點(diǎn)的所有孩子節(jié)點(diǎn)在數(shù)組中的位置class repeatedtreenodetreenode follower;/后來的重復(fù)節(jié)點(diǎn)treenode victim;/原來的節(jié)點(diǎn)arraylist websitetree;/網(wǎng)站層次樹arraylist layeraddresscontainer;/保存一層的全部url節(jié)點(diǎn)arraylist regularexpression;/正則表達(dá)式層arraylist repeatedinfo;/

25、存儲(chǔ)重復(fù)節(jié)點(diǎn)arraylistlinskarray;/臨時(shí)變量，保存下一層所有urlint layercount;/記錄現(xiàn)在處于第幾層stack path;/此棧記錄了深度爬蟲算法里面的路徑函數(shù)recursionanalyzer()用來根據(jù)給定的url和正則表達(dá)式層來遞歸得出下一層所有的url，并返回arraylist類型參數(shù)算法1：根據(jù)一個(gè)輸入的url得到該url對(duì)應(yīng)的網(wǎng)頁上下一層所有url，即函數(shù) arraylistrecursionanalyzer(入口頁節(jié)點(diǎn)，表示下一頁的字符串，layercount，regularexpression，repeatedinfo，websitetree)

26、讀入入口頁指定的url的網(wǎng)頁內(nèi)容;if(有下一頁)同時(shí)檢測(cè)是否存在重復(fù)url，如果下一頁與前面的url沒有重復(fù)說明下一頁有效;根據(jù)layercount所指定的正則表達(dá)式層里的正則表達(dá)式找有沒有匹配的url;if(有匹配的url)同時(shí)檢測(cè)是否存在重復(fù)url;if(沒有重復(fù))將該節(jié)點(diǎn)加入到linskarray里面;將該節(jié)點(diǎn)加入到websitetree里面，構(gòu)建網(wǎng)頁目錄層次;else 根據(jù)棧的內(nèi)容將重復(fù)url的層次地址打印出來，并打印出與哪個(gè) url重復(fù)，并打印出那個(gè)url的層次地址;如果有下一頁，遞歸調(diào)用recursionanalyzer(下一頁的地址節(jié)點(diǎn)，表示下一頁的字符串，layercount

27、，regularexpression，repeatedinfo，websitetree，repeatedinfo)對(duì)下一頁所指的網(wǎng)頁進(jìn)行分析;return linskarray;算法2：廣度爬蟲算法輸入：入口頁輸出：所有圖片的url簡(jiǎn)要算法邏輯：首先初始化各變量;while(layercountregularexpression.size()for(int i=0;ilayeraddresscontainer.size();i+)arraylisttemp=a.recursionanalyzer(參數(shù)略);/該函數(shù)返回分析第一層的結(jié)果，也就是第二層的所有url打印出每個(gè)url的層次地址if(r

28、epeatedinfo.size()0)/意味著有重復(fù)情況處理重復(fù)的情況;將temp里面的內(nèi)容在存儲(chǔ)到layeraddresscontainer里面，供下次循環(huán)使用;layercount+;算法3：深度爬蟲算法輸入：入口頁輸出：下載圖片簡(jiǎn)要算法邏輯：首先初始化各變量;public void core_depth_first_fetching(入口頁地址，正則表達(dá)式層，layercount等參數(shù))if(layercount=regularexpression.size()/所有層都已分析完畢，遞歸出口對(duì)地址進(jìn)行預(yù)處理;根據(jù)棧的內(nèi)容打印出層次地址;開始下載;以上兩算法：深度優(yōu)先爬蟲算法和廣度優(yōu)先爬

29、蟲算法，是本程序?qū)崿F(xiàn)下載的兩種方式。廣度優(yōu)先爬蟲算法在搜索的時(shí)候以廣延性為首要目標(biāo)，它的好處顯而易見，在分析一個(gè)網(wǎng)站的時(shí)候，可以讓用戶實(shí)時(shí)的了解每個(gè)網(wǎng)頁的情況，比如，該網(wǎng)頁上有多少個(gè)用戶所關(guān)心的鏈接url地址等等，用戶還可以清晰的看到整個(gè)網(wǎng)站的組織結(jié)構(gòu)。但是，廣度優(yōu)先爬蟲算法也存在嚴(yán)重的缺點(diǎn)，就是占據(jù)存儲(chǔ)容量很大，這也是構(gòu)建網(wǎng)站結(jié)構(gòu)的代價(jià)。深度優(yōu)先爬蟲算法在搜索的時(shí)候以縱深搜索為首要目標(biāo)，這種方式無需保存整個(gè)網(wǎng)站層次結(jié)構(gòu)，每次遞歸運(yùn)行，僅僅需要保存縱深路徑上的節(jié)點(diǎn)個(gè)數(shù)。但是這種方式，在與用戶交互性方面不如廣度優(yōu)先爬蟲算法，用戶在下載過程中不能全面了解網(wǎng)站的結(jié)構(gòu)。下面是對(duì)兩種搜索方式的占據(jù)空間數(shù)

30、值比較：前提條件：一個(gè)入口頁，上面有s個(gè)超鏈接，并有a頁，每一個(gè)鏈接點(diǎn)進(jìn)去之后，出來的網(wǎng)頁上面仍有s個(gè)超鏈接，也是有a頁，這樣以此類推。用戶需要點(diǎn)擊n次才可以看到最終的圖片。廣度優(yōu)先爬蟲算法由于要保存前一層的超鏈接以用來分析下一層的超鏈接，所以要要同時(shí)保存兩層的url，又由于要確保分析下一層url時(shí)不會(huì)加入重復(fù)url，平衡二叉樹需要保存下一層的所有url，所以，采用廣度優(yōu)先爬蟲算法分析第k層時(shí)，內(nèi)存在任意時(shí)刻最多要保存?zhèn)€url記錄。深度優(yōu)先爬蟲算法以縱深搜索為首要目標(biāo)，所以每次只保存一條url記錄，直到到達(dá)最底層。由于廣度優(yōu)先爬蟲算法是以層為目標(biāo)，所以里面的重復(fù)檢查時(shí)，avl樹里面只要保存一層

31、的內(nèi)容，等到一層分析完畢，就可以將avl樹清空，以便進(jìn)行下一次的重復(fù)檢查，與之不同的是深度優(yōu)先爬蟲算法無所謂一層是否結(jié)束，不到最后，任何層都無法結(jié)束。所以深度優(yōu)先爬蟲算法avl樹要保存所有的url節(jié)點(diǎn)，不存在清空的情況。所以，采用深度優(yōu)先爬蟲算法，分析的時(shí)候需要保存n條url記錄，正常情況下，深度優(yōu)先爬蟲算法avl樹占用空間在分析最后一個(gè)url的時(shí)候達(dá)到最大值，也就是avl樹保存了所有的url，這時(shí)內(nèi)存要保存*a個(gè)url記錄，遠(yuǎn)小于廣度優(yōu)先時(shí)內(nèi)存占用最大值 。以上分析了爬蟲程序的核心算法，爬蟲程序核心是作為公有類picfetchmanners里面的公有方法breadth_first_fetch

32、ing()和depth_first_fetching()兩個(gè)函數(shù)實(shí)現(xiàn)。兩種算法具體實(shí)現(xiàn)核心代碼參見附錄a。3.2 相關(guān)技術(shù)要點(diǎn) 3.1節(jié)詳細(xì)闡述了本課題的主體程序-爬蟲程序的整體設(shè)計(jì)和實(shí)現(xiàn)，并探討了兩種爬蟲方式的優(yōu)缺點(diǎn)，本程序?qū)煞N爬蟲方式均給予了實(shí)現(xiàn)，在實(shí)現(xiàn)過程中，遇到了很多技術(shù)難點(diǎn)，這一節(jié)，將在上一節(jié)的基礎(chǔ)之上，詳細(xì)介紹重要技術(shù)點(diǎn)的設(shè)計(jì)思路和實(shí)現(xiàn)，并會(huì)給出相應(yīng)偽代碼。3.2.1 檢查重復(fù)url首先進(jìn)行關(guān)鍵變量聲明：arraylist repeatedinfo /保存所有的產(chǎn)生重復(fù)的u rl節(jié)點(diǎn)class repeatedtreenodetreenode follower;/后來的與前面某個(gè)

33、節(jié)點(diǎn)重復(fù)的節(jié)點(diǎn)treenode victim;/受害者節(jié)點(diǎn)一個(gè)網(wǎng)頁上難免存在許多相同的url指向相同的內(nèi)容，如果不進(jìn)行重復(fù)判斷，爬蟲程序?qū)⒅貜?fù)分析許多url，重復(fù)下載許多圖片，浪費(fèi)了網(wǎng)絡(luò)帶寬，增加了程序運(yùn)行時(shí)間。本程序采用了avl樹來對(duì)每個(gè)url節(jié)點(diǎn)進(jìn)行檢查，由于avl樹的平衡性，使得查找的速度非常迅速。設(shè)計(jì)：對(duì)于一個(gè)url字符串，通過將其里面的字符全部相加，得到一個(gè)整數(shù)值urlvalue，urlvalue就作為avl樹每個(gè)節(jié)點(diǎn)的數(shù)值，此外，avl樹的每個(gè)節(jié)點(diǎn)還有一個(gè)鏈表urltreenodearray，用來保存urlvalue相同的所有節(jié)點(diǎn)。如果一個(gè)新的節(jié)點(diǎn)到達(dá)，那么首先用avl樹二分查找，

34、如果沒有找到，則new一個(gè)新的節(jié)點(diǎn)并插入到avl樹里面;如果找到，接著遍歷urltreenodearray，如果urltreenodearray里不存在，就將該節(jié)點(diǎn)插入到urltreenodearray，如果urltreenodearray里已經(jīng)存在，說明這個(gè)url已經(jīng)產(chǎn)生重復(fù)，將此url加入到repeatedinfo里面，添加節(jié)點(diǎn)的形式為：new repeatedtreenode(重復(fù)的節(jié)點(diǎn)，在avl樹中的已經(jīng)存在的節(jié)點(diǎn));如此構(gòu)造的目的是，如果產(chǎn)生重復(fù)，程序要立即打印出與哪個(gè)節(jié)點(diǎn)重復(fù)，該節(jié)點(diǎn)的層次地址，而這些信息都存儲(chǔ)在avl樹中的已經(jīng)存在的節(jié)點(diǎn)里面。向avl樹插入節(jié)點(diǎn)在整體上耗費(fèi) o(l

35、og n) 時(shí)間，搜索avl樹亦消耗 o(log n) 時(shí)間，然后對(duì)每個(gè)節(jié)點(diǎn)中urltreenodearray的搜索消耗o(k)，所以上述設(shè)計(jì)總的時(shí)間代價(jià)最多o(log(n+k)。檢查重復(fù)url作為公有類bst類里面的bstinsert()函數(shù)實(shí)現(xiàn)。3.2.2 將相對(duì)地址轉(zhuǎn)化為絕對(duì)地址 制作網(wǎng)站時(shí)，為了網(wǎng)頁的通用性，普遍采用了相對(duì)地址來指示網(wǎng)頁的位置，爬蟲程序無法使用單純的相對(duì)地址，必須將相對(duì)地址轉(zhuǎn)換為絕對(duì)地址。為了使正則表達(dá)式在提取url的時(shí)候有更準(zhǔn)確的界限，用戶輸入的正則表達(dá)式往往是以href=或者src=這樣開頭，這樣就不會(huì)造成地址界限確定不準(zhǔn)的情況。算法4：相對(duì)地址轉(zhuǎn)絕對(duì)地址算法輸入：

36、任何地址輸出：絕對(duì)地址簡(jiǎn)要算法邏輯：關(guān)鍵變量聲明：url fullpathcontainstem;/這個(gè)url指示了包含相對(duì)地址的那個(gè)網(wǎng)頁string tem;/表示任何類型的地址string transform_a_relativepath_to_absolutepath(string tem，url fullpathcontainstem)首先判斷給地址是否是 href= 或者是 src=的類型地址如果是，就將里面真正的地址完全提取出來，且不含引號(hào);/下面就是判斷是否是絕對(duì)路徑;if(不是絕對(duì)路徑，那就是相對(duì)路徑)/相對(duì)路徑的情況如果開頭是以 /，那么表示這個(gè)路徑是根目錄，直接在前面加上f

37、ullpathcontainstem主機(jī)名和協(xié)議名即可，并賦給tem;如果包含././等，則表示取fullpathcontainstem表示的url的上面幾級(jí)目錄，然后再加上tem的文件名并賦給tem;如果不以/或者是./開頭，而是ima/tt.htm這種，或直接tt.htm，那么就表示這樣的目錄和這樣的文件在fullpathcontainstem相同的工作目錄中，只要將fullpathcontainstem的文件部分替換成ima/tt.htm，或tt.htm即可，其余部分不變，并賦給tem;return tem;/這時(shí)的tem，已經(jīng)變成了可以直接使用的絕對(duì)路徑了將相對(duì)地址轉(zhuǎn)化為絕對(duì)地址的功能

38、是作為公有類recursionsearchthewebpage的transform_a_relativepath_to_absolutepath()方法實(shí)現(xiàn)。這樣，就可以將相對(duì)地址轉(zhuǎn)化為絕對(duì)地址，具體實(shí)現(xiàn)參見附錄a。3.2.3 將一張圖片下載下來的函數(shù)本程序最基本的方法是下載一張圖片的方法，首先要對(duì)圖片的url進(jìn)行分解，得到圖片的文件名，然后檢測(cè)該文件名在當(dāng)前文件夾中是否已經(jīng)存在，一般來說，在已經(jīng)避免重復(fù)下載的情況下，能夠下載下來相同文件名的圖片的情況非常少見，如果文件名相同，圖片內(nèi)容也可能不同，比如許多網(wǎng)站的文件名僅僅以數(shù)字命名:1.jpg，2.jpg等等，這樣就容易造成上述情況，所以，在下

39、載前，如果檢測(cè)到該文件名已經(jīng)存在，那么本程序采用的方法是，取當(dāng)前系統(tǒng)時(shí)間作為字符串加到該文件名后面，這樣，就避免了以后再出現(xiàn)重復(fù)的情況。下面開始下載，基本方法是：url url = new url(urlname);urlconnection connection = url.openconnection();connection.connect();bufferedimage image=imageio.read(url);該過程要拋出3種異常：ioexception 無法從網(wǎng)絡(luò)讀取數(shù)據(jù)異常;illegalargumentexception 用戶輸入的url或者本地路徑名格式非法異常;自定義

40、sizeexception 圖片分辨率異常，由于圖片分辨率過小產(chǎn)生的異常;下載單圖片函數(shù)作為公有類explicitdownloadmanners里的downloadsingleimg()方法實(shí)現(xiàn)。3.3 本章小結(jié)本章首先介紹了爬蟲程序的整體設(shè)計(jì)思路，并詳細(xì)描述了兩種爬蟲深度爬蟲和廣度爬蟲的偽代碼實(shí)現(xiàn)，然后比較了兩種方式的優(yōu)缺點(diǎn)。從第二小節(jié)開始，介紹了爬蟲算法實(shí)現(xiàn)中遇到的主要技術(shù)點(diǎn)，本文對(duì)每個(gè)技術(shù)點(diǎn)的設(shè)計(jì)和實(shí)現(xiàn)都進(jìn)行了精要的描述。4 正則表達(dá)式自動(dòng)產(chǎn)生器4.1 基于動(dòng)態(tài)規(guī)劃的最優(yōu)字符串比對(duì)算法4.1.1 字符串比對(duì)定義為字符集上的兩個(gè)序列。a與b的序列比對(duì)是一個(gè)在中2*k字符矩陣m(k=m，n)

41、，使得m中沒有列完全有短橫線組成，并且對(duì)m中的第一行和第二行的全部短橫線進(jìn)行移動(dòng)而得到的結(jié)果序列分別與a和b相同。例如：如果a=abcd和b=cbd，他們的一個(gè)可能的比對(duì)是：a b c - d- - c b d同樣這樣的兩個(gè)序列的另一個(gè)可能的比對(duì)是：a b c dc b - d4.1.2 字符串比對(duì)問題的動(dòng)態(tài)規(guī)劃解法 定義得分函數(shù)設(shè)兩個(gè)字符，令表示x與y的比對(duì)得分，如果x，y相同，那么=2;如果x與y不相同但是都不是 - ，=1;如果x或者y是 - ，那么=-1。 問題的數(shù)學(xué)模型a和b 的2序列比對(duì)問題描述為找到具有最多得分的兩序列最優(yōu)比對(duì)。采用遞歸公式可將此問題公式化。令整數(shù)表示與之間的最優(yōu)

42、比對(duì)對(duì)應(yīng)的最高得分，其中1im，1jn。那么，可以表示如下：表示兩個(gè)空字符串相比較，得分為0; 表示字符串與一個(gè)為空的b進(jìn)行比對(duì)，那么比對(duì)只有如下情況： - - - - 。 表示如果和比對(duì)可以產(chǎn)生最高得分，那么必須在和之間要產(chǎn)生最優(yōu)比對(duì)。表示如果 和 - 比對(duì)可以產(chǎn)生最高得分，那么必須在和之間要產(chǎn)生最優(yōu)比對(duì)。 表示如果和 - 比對(duì)可以產(chǎn)生最高的得分，那么必須在和之間產(chǎn)生一個(gè)最優(yōu)比對(duì)。有了上面的聲明，下面得到字符串比對(duì)問題解法的遞歸式： 算法5：尋找字符串比對(duì)算法輸入：兩個(gè)url字符串輸出：兩者的最優(yōu)比對(duì)簡(jiǎn)要算法邏輯：根據(jù)上面遞歸式，于是得到了兩字符串比對(duì)解法的偽代碼:得分函數(shù):int f(ch

43、ar a，char b)int score;if(a=- | b =-)score=-1;else if(a=b)score=2;else score=1;return score;比對(duì)函數(shù)：highestscore(x，y)m-lengthx;n-lengthy;for i-1 to mdo ci，0 -0for j-0 to ndo c0，j -0for i-1 to mfor j=max)max= aij-1+f(-，yj);bij=;if(ai-1j+f(xi，-)=max)max= ai-1j+f(xi，-);bij=; return c and b;下面是通過回溯數(shù)組b來將x和y的

44、最優(yōu)比對(duì)打印出來打印x的比對(duì)：tracebackprint(b，x，i，j)if i=0 or j=0 then returnif bi，j= then tracebackprint(b，x，i-1，j-1) print xielse if bi，j= then tracebackprint(b，x，i-1，j)else tracebackprint(b，x，i，j-1) print -同理可得：打印y 的比對(duì)tracebackprint(b，y，i，j)if i=0 or j=0 then returnif bi，j= then tracebackprint(b，y，i-1，j-1) pri

45、nt yielse if bi，j= then tracebackprint(b，y，i-1，j) print -else tracebackprint(b，y，i，j-1)4.2 正則表達(dá)式自動(dòng)產(chǎn)生器總體設(shè)計(jì)和實(shí)現(xiàn)4.2.1 假設(shè)和規(guī)定為了簡(jiǎn)化本程序的編程工作，不讓程序過于復(fù)雜，現(xiàn)在做如下假設(shè)：輸入到本程序中的url的模式為：href|src=協(xié)議名:/主機(jī)名：端口號(hào)/路徑部分/頁名及一些請(qǐng)求參數(shù)為了稱呼方便，做如下名稱規(guī)定：href|src 部分稱作前綴部分，該部分可有可無;其后的引號(hào)稱作引號(hào)部分，該部分可有可無;包含網(wǎng)頁名和url請(qǐng)求過程中的參數(shù)的部分稱作最后部分，該部分可有可無;一個(gè)待

46、比對(duì)的正則表達(dá)式和上一步產(chǎn)生的正則表達(dá)式的各個(gè)部分比對(duì)之后產(chǎn)生的結(jié)果稱作正則表達(dá)式雛形。該正則表達(dá)式雛形一直由由特殊字符和比對(duì)雙方的公共部分組成，直到最后用戶輸入ok要結(jié)果時(shí)，程序才會(huì)通過把特殊字符所代表的內(nèi)容將其從正則表達(dá)式雛形狀態(tài);路徑部分如果是相對(duì)路徑形式，協(xié)議部分、主機(jī)名部分一定不存在，路徑部分一定存在;路徑部分如果是絕對(duì)路徑形式，協(xié)議部分、主機(jī)名部分一定存在，路徑部分可以不存在，即一個(gè)網(wǎng)頁屬于默認(rèn)頁，例如：4.2.2 自動(dòng)產(chǎn)生正則表達(dá)式的問題分析和基本思路 用戶在使用爬蟲程序的時(shí)候，需要自行輸入正則表達(dá)式來作為提取網(wǎng)頁url的依據(jù)，用戶提取正則表達(dá)式的過程如下： 先搜集足夠的網(wǎng)頁ur

47、l，然后人工比較url的前綴部分，協(xié)議部分，主機(jī)名部分，路徑部分以及包含網(wǎng)頁文件名或其他條件參數(shù)的最后一部分。在比較的過程中抽取出不同url的同一部分的相同點(diǎn)，不相同的點(diǎn)，就用正則表達(dá)式語法中的特殊字符來替代，最后將各部分的結(jié)果加起來，就得到了最終的正則表達(dá)式。 在構(gòu)造正則表達(dá)式時(shí)，要堅(jiān)持以下原則： (1)正則表達(dá)式首先要構(gòu)造正確; (2)正則表達(dá)式構(gòu)造時(shí)要根據(jù)用戶需要的精度來操作，正則表達(dá)式構(gòu)造應(yīng)分為模糊模式和精確模式，兩種模式的差別就在于對(duì)52個(gè)英文字符的處理方式上，精確模式下的正則表達(dá)式要足夠精確，以便減少正則表達(dá)式引擎對(duì)所產(chǎn)生的正則表達(dá)式的匹配次數(shù)，提高正則表達(dá)式的解析效率，例如： 如

48、果(a-z)或者(k|a|x)同時(shí)可選，精確模式要選更加精確的(k|a|x)，但是如果用戶指定要用模糊模式，那么要選(a-z); 如果一個(gè)字符存在有或者沒有兩種情況，該正則表達(dá)式有兩種表達(dá)方式：(a-z)*，(a-z)?，那么一定要選(a-z)?; 如果一個(gè)正則表達(dá)式可以寫作：(a-z)*，同時(shí)也可以寫作:(a-z)0-5，那么精確模式一定要選后者，而模糊模式要選前者; (3)正則表達(dá)式要有很強(qiáng)的可讀性，正則表達(dá)式可讀性高，可以讓人更容易理解該正則表達(dá)式的意義，使程序更好維護(hù); 有了上述問題分析，此問題就可以歸結(jié)為一個(gè)n個(gè)字符串比對(duì)的問題，但是此問題又不能簡(jiǎn)單的直接利用上述字符串比對(duì)的解決方案

49、，原因如下： (1)3.1.2的解決方案為后向匹配，即后面有符合條件的，將會(huì)覆蓋先前符合條件的。對(duì)于僅僅存在兩個(gè)字符串url的情況，如果直接利用3.1.2的解決方案，非常容易造成構(gòu)造正則表達(dá)式不夠準(zhǔn)確，可讀性混亂。比如兩個(gè)url字符串: /ftpz/p/sxhxxcom/a.html ftp:/用3.1.2的解決方案，他們的比對(duì)是：/ftpz/p/sxhxxcom/a.html-ftp:- /-/-/s. 如果最后能夠提取出正則表達(dá)式，那么ftp的url的協(xié)議和主機(jī)名之間的/，主機(jī)名部分，都已經(jīng)走位，不僅造成產(chǎn)生的正則表達(dá)式無法讓人理解，

50、而且會(huì)造成正則表達(dá)式本身就是錯(cuò)誤的。 (2)如下兩個(gè)url字符串： 如果直接利用3.1.2的解決方案，將產(chǎn)生比對(duì)： 這個(gè)比對(duì)將路徑中完整的一層king拆分開來與另一個(gè)url進(jìn)行比對(duì)，這種比對(duì)方式產(chǎn)生的正則表達(dá)式的king區(qū)域?yàn)?k(/)?i(/)?n(/)?g，這個(gè)正則表達(dá)式可讀性相當(dāng)混亂，作為用戶更希望看到的king區(qū)域的結(jié)果是：(k|i|n|g)+/)+，后者的可讀性遠(yuǎn)遠(yuǎn)高于前者。 鑒于以上兩點(diǎn)原因，3.1.2的解決方案不能直接用于此問題。 本程序?yàn)榱吮苊馍鲜鰡栴}，采用了如下解決方案： 處理url之前，首先通過預(yù)處理函數(shù)，將url的前綴部分，協(xié)議部分，主機(jī)名部分，路徑部分里的每一個(gè)小部分，

51、及最后部分均拆分開。每個(gè)小部分調(diào)用3.1.2的解決方案和其他根據(jù)3.1.2算法衍生出來的針對(duì)arraylist進(jìn)行比對(duì)的算法進(jìn)行處理，這樣就會(huì)大大提高產(chǎn)生的正則表達(dá)式的精確性和可讀性。圖4-1 正則表達(dá)式自動(dòng)產(chǎn)生器的基本思路 如果遇到兩個(gè)以上的url，可以采用如下處理方式： 對(duì)第一和二個(gè)url進(jìn)行提取之后，首先進(jìn)行各部分拆分，對(duì)于每一部分，其共有元素不變，加入到正則表達(dá)式雛形里面，但是不相同元素要用某種特殊字符來替代，然后將該特殊字符加入到正則表達(dá)式雛形里面，并把特殊字符代表的內(nèi)容保存;或者用新的特殊字符替換掉原來的正則表達(dá)式雛形里面對(duì)應(yīng)位置的特殊字符，然后將原來特殊字符代表的內(nèi)容加入到新的特殊字符代表的內(nèi)容里面，并保存。把這個(gè)提取出來的正則表達(dá)式雛形再與下一個(gè)url的各個(gè)部分相比較，如此循環(huán)反復(fù)。正則表達(dá)式自動(dòng)產(chǎn)生器的基本思路如圖4-1所示。4.2.3 正則表達(dá)式自動(dòng)產(chǎn)生器設(shè)計(jì)和實(shí)現(xiàn)基于上述的基本思想和4.1.2的解決方案，本小節(jié)闡述如何將該問題的解決具體化。本文計(jì)劃采用自頂向下，逐步求精的描述方式來描述該小節(jié)。算法6：正則表達(dá)式提取總體流程輸入：用戶輸入的url字符串輸出：正則表達(dá)式關(guān)鍵方法聲明：extractregularexpressionfro