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