【文章內(nèi)容簡介】 技術(shù)顯示分類結(jié)構(gòu)，用戶可以只瀏覽自己感興趣的類別。d)進行站點類聚或內(nèi)容類聚，減少信息的總量。 e)讓用戶對返回結(jié)果進行選擇，進行二次查詢是一種非常有效的手段。 (4) 實現(xiàn)交叉語言的檢索 搜索引擎對多種語言的數(shù)據(jù)庫進行交叉語言信息檢索，返回能夠回 5 答用戶問題的所有語言的文檔。若配上機器翻譯，就可使返回結(jié)果以用戶熟悉的語言顯示。雖然該技術(shù)日前還處于初步研究階段，其難點在于語言之間在表達方式和語義對應(yīng)上的不確定性，但也是一種發(fā)展方向。 (5) 提供對自然語言檢索的支持 為了提高搜索引擎對用戶檢索提問的理解，就必須有一個好的檢索提問語言，為了克服關(guān)鍵詞檢索和目錄查詢的缺點，現(xiàn)在已經(jīng)出現(xiàn)了自然語言智能答詢。如 Google 有專用于回答問題的 Google Answer，微軟有 AnswerBot 等。用戶可以輸入簡單的疑問句，比如“ how can kill virus of puter?”。搜索引擎在對提問進行結(jié)構(gòu)和內(nèi)容 的分析之后，或直接給出提問的答案，或引導用戶從幾個可選擇的問題中進行再選擇。自然語言的優(yōu)勢在于，一是使網(wǎng)絡(luò)交流更加人性化，二是使查詢變得更加方便、直接、有效。就以上面的例子來講，如果用關(guān)鍵詞查詢，多半人會用“ virus”這個詞來檢索，結(jié)果中必然會包括各類病毒的介紹、病毒是怎樣產(chǎn)生的等等許多無效信息，而用“ how can kill virus of puter?”，搜索引擎會將怎樣殺病毒的信息提供給用戶，提高了檢索效率。 (6) 多媒體數(shù)據(jù)搜索 網(wǎng)絡(luò)資源豐富多彩，具有很多類型的信息，用戶需要的信息也不完全是網(wǎng)頁的形式，從用戶的角度來看，必然要求搜索引擎能夠覆蓋更多的網(wǎng)絡(luò)資源?，F(xiàn)在有很多搜索引擎已經(jīng)提供了網(wǎng)頁、新聞、圖片、音樂等資源搜索，當然范圍還可以更廣，再如可以搜索視頻、音頻等。 (7) 專業(yè)化搜索 主題搜索引擎是為了專門收錄某一行業(yè)、某一學科、某一主題和某一地區(qū)的信息而建立，非常實用，如有商務(wù)查詢、企業(yè)查詢、人名查詢、電子郵件地址查詢和招聘信息查詢等。 (8) 桌面型搜索 用戶不用打開瀏覽器，而是直接通過只要通過它就能完全實現(xiàn)搜索過程，更甚者它可以同時搜索本地、局域網(wǎng)和互聯(lián)網(wǎng)上的信息。它完全越過傳統(tǒng)的 搜索模式，越過瀏覽器，真正實現(xiàn)讓搜索無處不在。搜索引擎脫離瀏覽器是一個發(fā)展趨勢， Google、 Yahoo 等己經(jīng)推出桌面型搜索軟件，而微軟在 2020 年也同樣有了自己的桌面搜索軟件。 此外還有一些其它值得注意的技術(shù)發(fā)展，如元搜索引擎，移動代理和 XML 技術(shù)，語音檢索技術(shù)等。隨著技術(shù)的不斷發(fā)展進步，搜索引擎 6 將會在信息檢索中發(fā)揮更大的作用。 研究目的和研究內(nèi)容 互聯(lián)網(wǎng)的快速發(fā)展，對搜索引擎提出了更高的要求。巨大的使用需求推動了搜索引擎技術(shù)的發(fā)展，各種新技術(shù)紛紛應(yīng)用到搜索引擎中。搜索引擎是這些技術(shù)的基礎(chǔ)和平 臺，它決定著這些技術(shù)的開發(fā)和應(yīng)用。但一般的研究機構(gòu)不可能擁有和商業(yè)搜索引擎一樣規(guī)模的計算機資源，因此需要一種對資源要求低、體系開放的搜索引擎來作為各種新技術(shù)的平臺。 本文在深入分析網(wǎng)頁獲取、索引生成、級別系統(tǒng)、索引檢索等搜索引擎核心技術(shù)的基礎(chǔ)上，設(shè)計并實現(xiàn)互聯(lián)網(wǎng)信息檢索系統(tǒng)。該系統(tǒng)在微軟 .NET 平臺進行開發(fā)，使用 C進行代碼的編寫。采用多線程進行網(wǎng)頁數(shù)據(jù)采集并寫入數(shù)據(jù)庫；通過使用 、中文分詞、無用詞匯刪除、詞典等技術(shù)建立索引數(shù)據(jù)； Cache 技術(shù)的使用提高了用戶訪問效率 .開放的體系結(jié)構(gòu)使搜索 引擎成為相關(guān)技術(shù)可靠和靈活的平臺。 文章內(nèi)容安排 本文主要研究了搜索引擎實現(xiàn)中所涉及到的相關(guān)技術(shù)，最終實現(xiàn)一個基于 .NET 平臺下的互聯(lián)網(wǎng)信息檢索系統(tǒng)。具體內(nèi)容安排如下： 第二章：介紹了搜索引擎總體結(jié)構(gòu)，各組成部分實現(xiàn)功能及關(guān)鍵技術(shù)，相關(guān)算法，并對 Google 的體系結(jié)構(gòu)進行分析； 第三章：剖析開源的全文檢索引擎 ，分析其組織架構(gòu)，索引數(shù)據(jù)格式等，對源碼分析，二次開發(fā)應(yīng)用； 第四章：設(shè)計實現(xiàn)一個基于微軟 .NET 平臺的互聯(lián)網(wǎng)信息檢索系統(tǒng)，借助 相關(guān)技術(shù)進行實現(xiàn)，在本文 論述的理論思想基礎(chǔ)上，最終實現(xiàn)設(shè)計目標； 第五章：介紹互聯(lián)網(wǎng)信息檢索系統(tǒng)的具體實現(xiàn)，核心技術(shù)的解決方法。 第六章：對互聯(lián)網(wǎng)信息檢索系統(tǒng)進行測試，總結(jié)整個論文的完成情況，對研究工作進行總結(jié)和展望。 7 2 搜索引擎技術(shù) 搜索引擎體系結(jié)構(gòu) 典型的搜索引擎結(jié)構(gòu)一般由以下三個模塊組成：信息采集模塊(Crawler)，索引模塊 (Indexer)，查詢模塊 (Searcher)。 搜索引擎典型體系結(jié)構(gòu)如圖 21 所示。 圖 21 搜索引擎體系結(jié)構(gòu)圖 (1) Crawler 從 Web 中采集網(wǎng)頁數(shù)據(jù)； (2) Indexer 對 Crawler 采集數(shù)據(jù)進行分析生成索引； (3) Searcher 接受查詢請求，通過一定的檢索算法獲取查詢結(jié)果，排序后返回給用戶。 Crawler 日志分析器 控制器 原始數(shù)據(jù)庫 索引數(shù)據(jù)庫 Indexer Searcher 用戶接口 用戶 日志數(shù)據(jù)庫 8 Crawler Crawler 負責頁面信息的采集，它的工作實現(xiàn)基于以下設(shè)想：既然所有網(wǎng)頁都可能鏈接到其他網(wǎng)站，那么從一個網(wǎng)站開始，跟蹤所有網(wǎng)頁上的所有鏈接，就有可能檢索整個互聯(lián)網(wǎng)。 Crawler 工作原理如圖 22 所示。 圖 Crawler 工作原理圖 Crawler 首先從待訪問 URL 隊列中獲取 URL，根據(jù) URL 從 Web 中抓取網(wǎng)頁數(shù)據(jù)；然后對網(wǎng)頁進行分析，從中提取出所有的 URL 鏈接，并把它們加入到待訪問 URL 隊列中，同時將已訪問 URL 移至已訪問URL 隊列中。不斷重復上面的過程，所有采集到的網(wǎng)頁保存到頁面存儲中進行下一步處理。 Crawler 利用 HTTP 協(xié)議讀取 Web 頁面并沿著 HTML 文檔中的超鏈接自動獲取 WWW 資源。可以將 WWW 作為一個有向圖來處理，將每一個頁面看作圖中的一個節(jié)點，將頁面中的超鏈接看做圖中的有向邊。因此可以采取有向圖的遍歷算 法 (深度優(yōu)先或者廣度優(yōu)先算法 )來對WWW 進行遍歷。 由于 Web 信息具有的分布性，非結(jié)構(gòu)化，不穩(wěn)定性等特點， Crawler存在以下的關(guān)鍵問題： (1) 多線程抓取時的任務(wù)調(diào)度問題 搜索引擎會產(chǎn)生多個 Crawler 同時對網(wǎng)頁進行抓取，這里需要一個 WWW 網(wǎng)頁存儲 初始化 抓取網(wǎng)頁 獲取 URL 提取 URL 待訪問的 URL 已訪問的 URL 9 好的分布式算法，使得既不重復抓取網(wǎng)頁，又不漏掉重要的站點。 (2) 網(wǎng)頁評估 在抓取網(wǎng)頁時存在一定的取舍，一般只會抓 20%左右的網(wǎng)頁。評估算法中典型的油 Google 發(fā)明的 PgaeRank。 (3) 更新策略 每經(jīng)過一段時間， Crawler 對以抓取的數(shù)據(jù)經(jīng)行更新，保證索引 網(wǎng)頁是最新的。 (4) 壓縮算法 網(wǎng)頁抓取后，通過一定的壓縮機制保存到本地，從而減少存儲容量，同時也減少各服務(wù)器之間的網(wǎng)絡(luò)通信開銷。 Indexer 搜索引擎在完成用戶查詢請求時，并不是即時檢索 互聯(lián)網(wǎng) 上的數(shù)據(jù)，搜索的數(shù)據(jù)實際是預先采集的網(wǎng)頁數(shù)據(jù)。要實現(xiàn)對采集頁面的快速訪問，必須通過某種索引機制來完成。 頁面數(shù)據(jù)可以用一系列關(guān)鍵詞來表示，從檢索目的來說，這些關(guān)鍵詞描述了頁面的內(nèi)容。只要找到頁面，便可以找到其中的關(guān)鍵詞。反過來，如果按關(guān)鍵詞建立到頁面的索引，便可以根據(jù)關(guān)鍵詞快速地檢索到相關(guān)頁面。具 體地，關(guān)鍵詞被存儲在索引文件 (index file)中，對于每個關(guān)鍵詞，都有一個指針鏈表，該表中的每一個指針指向與關(guān)鍵詞相關(guān)的某個頁面，所有指針鏈表構(gòu)成置入文件 (posting file)。這種倒排文件的方法幾乎被當前所有的商用 IR 系統(tǒng)所采用。 Indexer 負責對 Crawler 采集的數(shù)據(jù)生成索引數(shù)據(jù)，基本結(jié)構(gòu)如圖 23所示。 圖 23 Indexer 索引數(shù)據(jù)結(jié)構(gòu)圖 Indexer 首先從頁面存儲器中獲取頁面數(shù)據(jù)，對其進行分析，通過詞典識別網(wǎng)頁中的詞， 通過停用詞 (stop words)表刪除其中的停用詞，生頁面數(shù)據(jù) 服 務(wù) 器 中間數(shù)據(jù) 索引數(shù)據(jù) 10 成檢索詞序列，并最后生成索引數(shù)據(jù)。 Indexer 中存在的問題： (1) 索引存儲 一般來講，數(shù)據(jù)量和索引量的比例接近 1:1。索引的存儲一般采用分布式策略，檢索的數(shù)據(jù)分布在不同的服務(wù)器上。 Google 存儲索引的服務(wù)器大概有 1000 多臺。 (2) 索引更新 頁面數(shù)據(jù)更新時，索引數(shù)據(jù)必須相應(yīng)的更新。更新策略一般采用增量索引方式。 (3) 索引壓縮 索引也存在數(shù)據(jù)壓縮的問題。索引壓縮是通過對具體索引格式的研究實現(xiàn)壓縮。 (4) 網(wǎng)頁相似性支持 索引的結(jié)構(gòu)還必 須為網(wǎng)頁相似性分析提供支持。 (5) 多語言，多格式支持 網(wǎng)頁數(shù)據(jù)具有多種編碼格式，通過 Unicode，索引支持多種編碼查詢。同時索引還必須有對 Word， Excel 等文件格式進行分析的功能。 Searcher Searcher 是直接與用戶進行交互的模塊，在接口上有多種實現(xiàn)方式，常見的主要是 Web 方式，另外還可以通過無線接入方式 (如手機 )進行查詢。 Searcher 基本結(jié)構(gòu)如圖 24 所示。 圖 24 Searcher 基本結(jié)構(gòu)圖 Searcher 通過某種接口方式，接收用戶查詢，對查詢進行分詞Searcher 索引數(shù)據(jù) 頁面數(shù)據(jù) 用戶接口 11 (stemming)處理，獲取查詢關(guān)鍵字。通過 Indexer 獲取與查詢關(guān)鍵字匹配的網(wǎng)頁數(shù)據(jù)，經(jīng)過排序后返回給用戶。 Searcher 中存在的問題： (1) 檢索結(jié)果的排序 由于搜索引擎返回結(jié)果非常多，檢索結(jié)果是否按用戶預期的順序排列是評價搜索引擎的重要指標之一。一些新的嘗試，比如對用戶偏好的分析技術(shù)都可以運用到這里，對不同的用戶采用不同的排序策略。 (2) 排序結(jié)果排重 排重可以提高結(jié)果數(shù)據(jù)的質(zhì)量。檢索結(jié)果的數(shù)量給排重帶來資源上的開銷及速度上的影響。搜索引 擎需要在其中作出權(quán)衡。 (3) 檢索結(jié)果的相似性分析 主要用在類似網(wǎng)頁功能中，需要在索引結(jié)構(gòu)中提供支持。 (4) 檢索的速度 主要依賴索引結(jié)構(gòu)的設(shè)計。同時在體系結(jié)構(gòu)上還有很多技術(shù)可以用來提升速度。如： Cache，負載均衡等。 搜索引擎的性能指標 我們可以將 Web 信息的搜索看作一個信息檢索問題，即在由 web網(wǎng)頁組成的文檔庫中檢索出與用戶查詢相關(guān)的文檔。所以我們可以用衡量傳統(tǒng)信息檢索系統(tǒng)的性能參數(shù)一召回率 (recall)和精度 (pricision)衡量一個搜索引擎的性能。 召回率是檢索出的相關(guān)文檔數(shù)和 文檔庫中所有的相關(guān)文檔數(shù)的比率，衡量的是檢索系統(tǒng) (搜索引擎 )的查全率；精度度是檢索出的相關(guān)文檔數(shù)與檢索出的文檔總數(shù)的比率，衡量的是檢索系統(tǒng) (搜索引擎 )的查準率。對于一個檢索系統(tǒng)來講，召回率和精度不可能兩全其美，召回率高時，精度低，精度高時，召回率低。對于搜索引擎系統(tǒng)來講，因為沒有一個搜索引擎系統(tǒng)能夠搜集到所有的 Web 網(wǎng)頁，所以召回率很難計算。目前的搜索引擎系統(tǒng)都非常關(guān)心精度。 影響一個搜索引擎系統(tǒng)性能和精度有很多因素，最主要的是信息檢索模型，包括文檔和查詢的表示方法、評價文檔和用戶查詢相關(guān)性的匹配策略、查詢 結(jié)果的排序方法和用戶進行相關(guān)度反饋的機制。 12 提高搜索引擎精度的關(guān)鍵是研究最優(yōu)的頁面優(yōu)先度算法，提供具有較高用戶相關(guān)度的網(wǎng)頁頁面優(yōu)先度排序。研究搜索引擎的頁面優(yōu)先度算法，需要從客觀和主觀兩方面進行研究。客觀上，從網(wǎng)頁頁面本身的信息和鏈接情況分析，提高信息量大、鏈接度高的網(wǎng)頁頁面的優(yōu)先度排序 。主觀上，從互聯(lián)網(wǎng)用戶使用搜索引擎的行為模式分析，提高用戶點擊率高和瀏覽時間長的網(wǎng)頁頁面的優(yōu)先度排序。 中文分詞算法 眾所周知，英文是以詞為單位的，詞和詞之間是靠空格隔開，而中文是以字為單位，句子中所有的字連起來才 能描述一個意思。例如，英文句子“ I am a student” ，用中文則為：“我是一個學生”。計算機可以很簡單通過空格知道 student 是一個單詞，但是不能很容易明白“學”、“生”兩個字合起來才表示一個詞。把中文的漢字序列切分成有意義的詞，就是中文分詞，有些人也稱為切詞。 基于字符串匹配的分詞方法 這種方法又叫做機械分詞方法，它是按照一定的策略將待分析的漢字串與一個“充分大的”機器詞典中的詞條進行匹配，若在詞典中找到某個字符串，則匹配成功 (識別出一個詞 )。按照掃描方向的不同，串匹配分詞方法可以 分為正向匹配和逆向匹配；按照不同長度優(yōu)先匹配的情況，可以分為最大 (最長 )匹配和最小 (最短 )匹配；按照是否與詞性標注過程相結(jié)合，又可以分為單純分詞方法和分詞與標注相結(jié)合的一體化方法。 常用的幾種機械分詞方法如下： (1) 正向最大匹配法 (由左到右的方向 ) 首先將待拆分的字符串從左向右進行分詞，然后將分詞與機器字典中的詞條進行匹配，若在詞典中找到某個字符串，則匹配成功。 實現(xiàn)流程如圖 25 所示。 13