【文章內(nèi)容簡(jiǎn)介】 樂信息搜索引擎的設(shè)計(jì)建立一個(gè)基本框架。第三章，垂直搜索引擎的關(guān)鍵算法，重點(diǎn)論述垂直搜索引擎設(shè)計(jì)與實(shí)現(xiàn)的一些獨(dú)特的信息識(shí)別方法，提出音樂信息搜索引擎所采用的一些關(guān)鍵算法。第四章，面向音樂領(lǐng)域的垂直搜索引擎的總體設(shè)計(jì)，根據(jù)前文的理論分析和當(dāng)前搜索引擎技術(shù)的發(fā)展現(xiàn)狀，按照軟件工程的方法，重點(diǎn)論述音樂信息搜索引擎的總體設(shè)計(jì)過程，包括需求分析、網(wǎng)站的功能規(guī)劃和總體結(jié)構(gòu)等內(nèi)容。第五章，面向音樂領(lǐng)域的垂直搜索引擎技術(shù)的具體實(shí)現(xiàn)，在前面總體設(shè)計(jì)的基礎(chǔ)上，選定系統(tǒng)的開發(fā)環(huán)境和開發(fā)工具，通過編碼實(shí)現(xiàn)設(shè)計(jì)階段的各種算法和具體功能。結(jié)論。主要對(duì)論文的研究工作進(jìn)行總結(jié)，提出系統(tǒng)的創(chuàng)新之處存在的問題。針對(duì)以上幾點(diǎn)，本課題做了大量的工作，開發(fā)的平臺(tái)具有較好的通用性，可擴(kuò)展性。西安工業(yè)大學(xué)畢業(yè)設(shè)計(jì)（論文）7第 2 章 搜索引擎實(shí)現(xiàn)原理由于垂直搜索引擎是通用搜索引擎的細(xì)分和延伸，因此，在基本原理和工作過程方面，與通用搜索引擎基本相同。本章將在重點(diǎn)論述通用搜索引擎的基本原理，作為開發(fā)音樂信息搜索引擎的基礎(chǔ)。 通用搜索引擎的工作流程盡管當(dāng)前對(duì)于各種搜索引擎的分類不同，但從原理上看，搜索引擎主要是指那些使用網(wǎng)頁(yè)爬行軟件，按照一定的策略將 Web 文檔采集到本地?cái)?shù)據(jù)庫(kù)，然后對(duì)這些網(wǎng)頁(yè)進(jìn)行自動(dòng)分析并建立索引數(shù)據(jù)庫(kù)，進(jìn)而對(duì)用戶提出的檢索請(qǐng)求在數(shù)據(jù)庫(kù)中進(jìn)行搜索，找出匹配的文檔或者鏈接，返回給用戶的網(wǎng)絡(luò)軟件。搜索引擎系統(tǒng)一般由蜘蛛（也叫網(wǎng)頁(yè)爬行器） 、切詞器、索引器、查詢器幾部分組成。蜘蛛負(fù)責(zé)網(wǎng)頁(yè)信息的抓取工作，一般情況下切詞器和索引器一起使用，它們負(fù)責(zé)將抓取的網(wǎng)頁(yè)內(nèi)容進(jìn)行切詞處理并自動(dòng)進(jìn)行標(biāo)引，建立索引數(shù)據(jù)庫(kù)。查詢器根據(jù)用戶查詢條件檢索索引數(shù)據(jù)庫(kù)并對(duì)檢索結(jié)果進(jìn)行排序和集合運(yùn)算，如并集、交集運(yùn)算，再抽取網(wǎng)頁(yè)簡(jiǎn)單摘要信息反饋給查詢用戶 [11]。搜索引擎從功能上同樣分為三大部分：網(wǎng)頁(yè)爬行、標(biāo)引入庫(kù)和用戶查詢 [12]。網(wǎng)頁(yè)爬行主要負(fù)責(zé)網(wǎng)頁(yè)的抓取，由 URL 服務(wù)器、爬行器、存儲(chǔ)器、分析器和 URL 解析器組成, 爬行器是該部分的核心；標(biāo)引入庫(kù)主要負(fù)責(zé)對(duì)網(wǎng)頁(yè)內(nèi)容進(jìn)行分析，對(duì)文檔進(jìn)行標(biāo)引并存儲(chǔ)到數(shù)據(jù)庫(kù)里，由標(biāo)引器和分類器組成，該模塊涉及許多文件和數(shù)據(jù)，有關(guān)于桶的操作是該部分的核心；用戶查詢主要負(fù)責(zé)分析用戶輸入的檢索表達(dá)式，匹配相關(guān)文檔，把檢索結(jié)果返回給用戶，由查詢器和網(wǎng)頁(yè)級(jí)別評(píng)定器組成，其中網(wǎng)頁(yè)等級(jí)的計(jì)算是該部分的核心。其總體系統(tǒng)結(jié)構(gòu)圖 21 所示。西安工業(yè)大學(xué)畢業(yè)設(shè)計(jì)（論文）7圖 搜索引擎的工作流程搜索引擎的主要工作流程是：首先從蜘蛛開始，蜘蛛程序每隔一定的時(shí)間（象google 一般是 28 天）自動(dòng)啟動(dòng)并讀取網(wǎng)頁(yè) URL 服務(wù)器上的 URL 列表，按深度優(yōu)先或廣度優(yōu)先算法，抓取各 URL 所指定的網(wǎng)站，將抓取的網(wǎng)頁(yè)分配一個(gè)唯一文檔ID(DocId)，存入文檔數(shù)據(jù)庫(kù)。一般在存入文檔數(shù)據(jù)庫(kù)之前進(jìn)行一定的壓縮處理。并將當(dāng)前頁(yè)上的所的超連接存入到 URL 服務(wù)器中。在進(jìn)行抓取的同時(shí)，切詞器和索引器將已經(jīng)抓取的網(wǎng)頁(yè)文檔進(jìn)行切詞處理，并按詞在網(wǎng)頁(yè)中出現(xiàn)的位置和頻率計(jì)算權(quán)值，然后將切詞結(jié)果存入索引數(shù)據(jù)庫(kù)。整個(gè)抓取工作和索引工作完成后更新整個(gè)索引數(shù)據(jù)庫(kù)和文檔數(shù)據(jù)庫(kù)，這樣用戶就可以查詢最新的網(wǎng)頁(yè)信息。查詢器首先對(duì)用戶輸入的信息進(jìn)行切詞處理，并檢索出所有包含檢索詞的記錄，通過計(jì)算網(wǎng)頁(yè)權(quán)重和級(jí)別對(duì)查詢記錄進(jìn)行排序并進(jìn)行集合運(yùn)算，最后從文檔數(shù)據(jù)庫(kù)中抽取各網(wǎng)頁(yè)的摘要信息反饋給查詢用戶。 網(wǎng)頁(yè)信息采集技術(shù)和軟件當(dāng)前的網(wǎng)頁(yè)信息采集技術(shù)，主要依賴自動(dòng)采集軟件，也稱機(jī)器人 robot，蜘蛛 URL服 務(wù) 器 爬 行 器 存 儲(chǔ) 服 務(wù) 器 資 源 庫(kù) 頁(yè) 級(jí) 別 評(píng) 定 器 URL解 析 器 標(biāo) 引 器 查 詢 器 分 類 器 錨 庫(kù) 詞 典 庫(kù) 索 引 庫(kù) 鏈 接 庫(kù) 桶 桶 桶 桶 桶 桶 Web頁(yè)搜索 標(biāo)引入庫(kù) 用戶查詢 西安工業(yè)大學(xué)畢業(yè)設(shè)計(jì)（論文）8spider 或者爬蟲 crawler，利用 Web 文檔內(nèi)的超級(jí)鏈接遞歸訪問新網(wǎng)頁(yè)。其主要功能是自動(dòng)從 inter 上的各 Web 站點(diǎn)抓取 Web 文檔并從 Web 文檔中撮一些信息來描述該 Web 文檔 [13]；為搜索引擎站點(diǎn)的數(shù)據(jù)庫(kù)服務(wù)器追加和更新數(shù)據(jù)提供原始數(shù)據(jù)，這些數(shù)據(jù)包括 HTML、標(biāo)題、長(zhǎng)度、文件建立時(shí)間、HTML 文件中的各種鏈接等 [14]。 蜘蛛(即 Web Spider)，實(shí)際上是一個(gè)基于 HTTP 協(xié)議的網(wǎng)絡(luò)應(yīng)用程序。網(wǎng)絡(luò)蜘蛛是通過網(wǎng)頁(yè)的鏈接地址來尋找網(wǎng)頁(yè)，從網(wǎng)站某一個(gè)頁(yè)面（通常是首頁(yè)）開始，讀取網(wǎng)頁(yè)的內(nèi)容，并抽取出網(wǎng)頁(yè)中的其它超鏈接地址，然后通過這些鏈接地址尋找下一個(gè)網(wǎng)頁(yè)，這樣一直循環(huán)下去，直到把這個(gè)網(wǎng)站所有的網(wǎng)頁(yè)都抓取完為止 [15]。在抓取網(wǎng)頁(yè)的時(shí)候，spider 通常將 Web 作為一個(gè)有向圖來處理，將每一個(gè)頁(yè)面看作圖的一個(gè)節(jié)點(diǎn)，將頁(yè)面中的超鏈接看作圖中的有向邊。因此，可以使用有向圖的遍歷算法來對(duì) Web 進(jìn)行遍歷 [16]。當(dāng)前流行的遍歷算法包括以下幾種。（1）IP 地址搜索策略先賦予 spider 一個(gè)起始地址的 IP，然后根據(jù) IP 遞增的方式搜索本 IP 段后的每一個(gè) WWW 地址中的文檔，它完全不考慮各文檔中指向其他 Web 站點(diǎn)超鏈接地址。這種算法搜索全面，能夠發(fā)現(xiàn)沒有被其他文檔引用的新文檔信息源，但效率較低，不適合大規(guī)搜索。（2）深度優(yōu)先算法從起始頁(yè)面 P0 出發(fā)沿 P0 上的某一個(gè)鏈接一直搜索到某個(gè)不包含任何鏈接的文件為止，這樣形成一條完整的鏈。再返回 P0 繼續(xù)選擇其他鏈接進(jìn)行相似的訪問。訪問結(jié)束的標(biāo)志是不再有其他超鏈接可以搜索。這種算法的優(yōu)點(diǎn)是在理論上能夠遍歷一個(gè) Web 站點(diǎn)下所有深層嵌套的頁(yè)面，但如果遇到深度很大的搜索樹，有陷入一個(gè)分支當(dāng)中或者進(jìn)入循環(huán)狀態(tài)的危險(xiǎn)，因而不具有完備性和最優(yōu)性。（3）廣度優(yōu)先算法先搜索完一個(gè) Web 頁(yè)中所有的鏈接，再繼續(xù)下一層的搜索，直到最底層為止。它克服了深度優(yōu)先算法所不具備的完備性和最優(yōu)性的缺點(diǎn)，保證一個(gè)服務(wù)器上至少有一篇文檔加入到索引數(shù)據(jù)庫(kù)，能降低同一服務(wù)器被訪問的頻度，但時(shí)間復(fù)雜度和空間復(fù)雜度較大。（4）深度——廣度結(jié)合算法 [1718]這是一種綜合深度優(yōu)先算法和廣度優(yōu)先算法的優(yōu)點(diǎn)，并克服兩者缺點(diǎn)的算法。使用這種算法的 spider 每到達(dá)一個(gè)新的頁(yè)面后能對(duì)該頁(yè)面的后續(xù)鏈接（即引用該頁(yè)西安工業(yè)大學(xué)畢業(yè)設(shè)計(jì)（論文）9面的鏈接）進(jìn)行統(tǒng)計(jì)，并對(duì)該頁(yè)面進(jìn)行檢索，將檢索結(jié)果返回給用戶。接著對(duì)所獲得的一組 URL 重復(fù)上述步驟。這種算法查全率高，但當(dāng)同一時(shí)間檢索的用戶過多時(shí)可能造成服務(wù)器負(fù)擔(dān)過重或者信息阻塞現(xiàn)象。垂直搜索引擎 spider 和網(wǎng)頁(yè)庫(kù)的 spider 相比應(yīng)該是更加專業(yè)，可定制化。可定向性的采集和垂直搜索范圍相關(guān)的網(wǎng)頁(yè)忽略不相關(guān)的網(wǎng)頁(yè)和不必要的網(wǎng)頁(yè)，選擇內(nèi)容相關(guān)的以及適合做進(jìn)一步處理的網(wǎng)頁(yè)深度優(yōu)先采集、對(duì)頁(yè)面有選擇的調(diào)整更新頻率……，采集可通過人工設(shè)定網(wǎng)址和網(wǎng)頁(yè)分析 url 方式共同進(jìn)行。根據(jù)抓取過程蜘蛛主要分為三個(gè)功能模塊:一個(gè)是網(wǎng)頁(yè)讀取模塊主要是用來讀取遠(yuǎn)程 Web 服務(wù)器上的網(wǎng)頁(yè)內(nèi)容，另一個(gè)是超鏈分析模塊，這個(gè)模塊主要是分析網(wǎng)頁(yè)中的超鏈接，將網(wǎng)頁(yè)上的所有超鏈接抽取出來，放入到待抓取 URL 列表中，再一個(gè)模塊就是內(nèi)容分析模塊，這個(gè)模塊主要是對(duì)網(wǎng)頁(yè)內(nèi)容進(jìn)行分析，將網(wǎng)頁(yè)中所有超標(biāo)志去掉只留下網(wǎng)頁(yè)文字內(nèi)容。蜘蛛的主要工作流程如圖 所示：首先蜘蛛讀取抓取站點(diǎn)的 URL 列表，取出一個(gè)站點(diǎn) URL，將其放入未訪問的 URL列表（UVURL 列表）中，如果 UVURL 不為空則從中取出一個(gè) URL 判斷是否已經(jīng)訪問過，若沒有訪問過則讀取此網(wǎng)頁(yè)，并進(jìn)行超鏈分析及內(nèi)容分析，并將這些頁(yè)存入文檔數(shù)據(jù)庫(kù)，而那些 URL 則放入已訪問 URL 列表（VURL 列表） ，直到 UVRL 為空為止，此時(shí)再抓取其他站點(diǎn)，依次循環(huán)直到所有的站點(diǎn) URL 列表都抓取完為止。西安工業(yè)大學(xué)畢業(yè)設(shè)計(jì)（論文）10創(chuàng)建蜘蛛讀取站點(diǎn) URL 列表站點(diǎn) URL 列表是否空結(jié)束是否將 URL 放入 UVURL 列表UVURL 為空 ？讀取此 URL 網(wǎng)頁(yè)超鏈分析內(nèi)容分析存入文檔庫(kù)刪除此 URL 并加入VURL取出一 URL是否已訪問？否否是是說明UVURL：為當(dāng)前站點(diǎn)未訪問的 URLVURL：為當(dāng)前站點(diǎn)已訪問的 URL圖 spider 的工作流程西安工業(yè)大學(xué)畢業(yè)設(shè)計(jì)（論文）11 索引器索引操作是所有搜索引擎的核心概念：為了進(jìn)行快速查找，就需要把數(shù)據(jù)處理成一種高效的、可交叉引用的查找表格式。為了快速搜索大量的文本文件，首先必須為文件建立索引，就像是為一本書建立目錄，然后把文本轉(zhuǎn)換成你能夠快速搜索到的格式，而不是使用慢速順序掃描的處理方法。我們把這個(gè)轉(zhuǎn)換過程稱為索引操作。因此索引器是搜索引擎系統(tǒng)必須也是很關(guān)鍵的一個(gè)環(huán)節(jié)，它主要完成將切詞形成的順排檔文檔組織成倒排檔索引數(shù)據(jù) [1921]。倒排檔索引文件分三個(gè)文件保存，一個(gè)是存放各詞條索引文件，另一個(gè)是各文檔索引文件，再一個(gè)就是各詞在文檔中出現(xiàn)的位置信息文件。1)、順排檔結(jié)構(gòu)順排檔文檔是以 DocID 為主序的，每一文檔下存放各自出現(xiàn)的詞的 ID 及各詞所出現(xiàn)的次數(shù)和具體位置信息，各數(shù)據(jù)項(xiàng)的存儲(chǔ)長(zhǎng)度固定。Hits(位置)占 16 位DocID WordID 出現(xiàn)次數(shù) hit ……. hit…….. ………. … ……. …WordID 出現(xiàn)次數(shù) hit ……. hitDocID WordID 出現(xiàn)次數(shù) hit ……. hit…….. ………. … ……. …WordID 出現(xiàn)次數(shù) hit ……. hit西安工業(yè)大學(xué)畢業(yè)設(shè)計(jì)（論文）12圖 23 順排檔結(jié)構(gòu)2） 、倒排檔結(jié)構(gòu)圖 24 倒排檔結(jié)構(gòu)1） 、一級(jí)索引：一級(jí)索引文件屬于記錄式文件，每一記錄大小固定，共有三個(gè)數(shù)據(jù)項(xiàng)構(gòu)成，WordID、文檔數(shù)、第一個(gè)文檔開始位置。其中 WordID 是詞典中詞條的ID，文檔數(shù)是指這個(gè)詞總共在多少個(gè)文檔中出現(xiàn)，文檔開始位置是一個(gè)文件指針指向二級(jí)索引中出現(xiàn)當(dāng)前詞的文檔集中的第一個(gè)文檔存儲(chǔ)位置，這個(gè)指針是一個(gè)長(zhǎng)整形值相當(dāng)于指明了是二級(jí)索引文件中的第幾條記錄，因?yàn)楦饔涗涢L(zhǎng)度也是固定大小。通過這個(gè)指向可以直接定位到二級(jí)索引文件讀取位置，然后讀取 nDocs 個(gè)記錄即可，因?yàn)樗鼈兪谴娣旁谶B續(xù)的地址空間上。2） 、二級(jí)索引：二級(jí)索引也是一種記錄式文件，每一記錄有三個(gè)數(shù)據(jù)項(xiàng)組成，DocID、出現(xiàn)次數(shù)、第一個(gè) Hit 位置。其中 DocID 是文檔的 ID，出現(xiàn)次數(shù)指的是當(dāng)前文檔中某一個(gè)詞出現(xiàn)的次數(shù)，第一個(gè) Hit 位置也是一個(gè)指針，指向 Hits 文件中的某一位置。通過這個(gè)指針就可以直接定位到 Hits 位置中的讀取位置，這樣連續(xù)讀取hitWordID nDocs 文檔開始位置WordID nDocs 文檔開始位置WordID nDocs 文檔開始位置hithithithithitDocID 出現(xiàn)次數(shù) 首次出現(xiàn)位置DocID 出現(xiàn)次數(shù) 首次出現(xiàn)位置DocID 出現(xiàn)次數(shù) 首次出現(xiàn)位置DocID 出現(xiàn)次數(shù) 首次出現(xiàn)位置DocID 出現(xiàn)次數(shù) 首次出現(xiàn)位置DocID 出現(xiàn)次數(shù) 首次出現(xiàn)位置…………………….…………………….hithithithit一級(jí)索引 二級(jí)索引 Hits西安工業(yè)大學(xué)畢業(yè)設(shè)計(jì)（論文）13nHits 個(gè)記錄就可以將所有當(dāng)前詞在當(dāng)前文檔中的出現(xiàn)的位置信息都讀入。些文件將屬于同一 WordID 下的所有文檔記錄按其詞在整個(gè)文檔的權(quán)值從大到小排列。3） 、Hits 位置信息文件：些文件每一記錄只有一個(gè)數(shù)據(jù)項(xiàng)，即 Hit 位置信息，只記錄了各詞在文檔中出現(xiàn)的位置。將同一詞在同一文檔中的出現(xiàn)位置按出現(xiàn)的先后排列。這樣在讀取文檔并抽取摘要時(shí)只需對(duì)字符串從頭到尾掃描一邊即可，不需要來回掃描。1） 、以文檔為單位處理先將切分結(jié)果處理為順排檔并存入到外部數(shù)據(jù)庫(kù)。在此過程中計(jì)算各詞的權(quán)值，主要考慮了出現(xiàn)的次數(shù)和出現(xiàn)的位置，若出現(xiàn)在網(wǎng)頁(yè)的鏈接文字和 title 上則其權(quán)值比普通位置高一個(gè)數(shù)量級(jí)將其設(shè)為 ，若在其它位置上出現(xiàn)，則每出現(xiàn)一次將其權(quán)值加 。2） 、將順排檔文件按多種關(guān)鍵字排序，首先按 WordID 從小到大排序，再按詞的權(quán)值從大到小排序，最后按各詞的出現(xiàn)的先后順序排序。這樣基本形成了倒排檔文件結(jié)構(gòu)，再分組統(tǒng)計(jì)各詞出現(xiàn)的文檔數(shù)及各文檔中同一詞出現(xiàn)的次數(shù)，最后寫到索引文件里即可。 （注：這里的權(quán)值是同一詞在同一文檔中所有出現(xiàn)位置的權(quán)值之和） 網(wǎng)頁(yè)存儲(chǔ)器與分析索引器Web頁(yè)面被抓取回來后需要暫時(shí)地存儲(chǔ)起來，進(jìn)行索引分析，一般由頁(yè)面存儲(chǔ)器和索引軟件來完成這些功能。具體說，頁(yè)面存儲(chǔ)器執(zhí)行的是雙重接口的功能：提供接口供spider存儲(chǔ)抓取的頁(yè)面，提供應(yīng)用程序接口供索引器和分析器獲取頁(yè)面。頁(yè)面存儲(chǔ)器的設(shè)計(jì)中需要考慮規(guī)模、訪問模式和頁(yè)面數(shù)據(jù)更新以及過期頁(yè)面的刪除等問題。這里，我們重點(diǎn)分析索引數(shù)據(jù)庫(kù)的建立和標(biāo)引技術(shù)。Spider將頁(yè)面從Web頁(yè)面上抓取回來并存儲(chǔ)于頁(yè)面存儲(chǔ)器中后，分析索引軟件對(duì)這些信息進(jìn)行自動(dòng)分析和標(biāo)引，建立可供查詢的索引數(shù)據(jù)庫(kù)。標(biāo)引方法因不同的系統(tǒng)而異，但大多數(shù)均采用自動(dòng)標(biāo)引技術(shù)。有的建立WWW頁(yè)面內(nèi)容的全文索引，即對(duì)Web頁(yè)面中的每一個(gè)單詞進(jìn)行標(biāo)引；有的則從頁(yè)面中按分類或特征對(duì)信息進(jìn)行抽取。這些分類或特征包括：網(wǎng)頁(yè)標(biāo)題、網(wǎng)址、