網(wǎng)絡(luò)搜索引擎框架和模型的研究

網(wǎng)絡(luò)搜索引擎框架和模型的研究

關(guān)鍵詞：搜索引擎，搜索引擎框架，搜索引擎模型1.引言經(jīng)過十多年的發(fā)展，WEB上的信息量已經(jīng)十分龐大并且增長勢頭依然迅猛。據(jù)統(tǒng)計(jì)，網(wǎng)絡(luò)上的靜態(tài)網(wǎng)頁有上百億，而動態(tài)和隱藏網(wǎng)頁至少是靜態(tài)的500倍。面對如此海量的信息，人們?nèi)绾慰焖贉?zhǔn)確的找到想要的信息是一大難題。而WEB搜索引擎則在很大的程度上解決了這一難題。實(shí)際上在WEB出現(xiàn)之前的1990年，加拿大蒙特利爾大學(xué)就開發(fā)出一個可以查找FTP主機(jī)上文件的軟件Archie。Archie能提供的功能就是在已知文件名的情況下能夠給出這個文件所在FTP的地址。Archie特點(diǎn)就是根據(jù)已經(jīng)有的FTP的地址和深入這些FTP主機(jī)后獲取的文件目錄信息構(gòu)建一個龐大的數(shù)據(jù)庫，然后再加上相關(guān)的檢索方法得以實(shí)現(xiàn)搜索的功能[1]。人們因此一致認(rèn)為Archie是現(xiàn)代搜索引擎的祖先。不過與自己的鼻祖相比，現(xiàn)代的以WEB網(wǎng)頁為對象的搜索引擎則有了巨大的變化。后者利用網(wǎng)頁間的鏈接關(guān)系把網(wǎng)頁一個一個抓取到本地，然后對這些網(wǎng)頁進(jìn)行處理分析，最后構(gòu)成特定的文檔表示形式以備檢索之用。所以在現(xiàn)代的WEB搜索引擎中抓取網(wǎng)頁是首先要關(guān)注的重要步驟。從而帶來的變化就是如何處理這些抓取回來的龐大的資料，如何在這個龐大的資料中查找用戶想要的信息。當(dāng)然，與上述這種以網(wǎng)頁抓取為導(dǎo)向的搜索引擎相比，現(xiàn)在還存在另外兩種不同類型的搜索引擎。一種是目錄式搜索引擎，它通過人工讀取文檔，形成摘要并將信息置于事先確定的分類框中。最后提供目錄瀏覽服務(wù)和直接檢索服務(wù)[1]。另一種則是元搜索引擎，這種搜索引擎的特點(diǎn)就是它沒有自己的數(shù)據(jù)，而是將用戶的查詢請求同時(shí)向多個搜索引擎遞交，最后綜合多個搜索引擎的結(jié)果，篩選和整理后返回給用戶，以期望提高查詢的準(zhǔn)確度和覆蓋面[2]。本文則重點(diǎn)介紹基于網(wǎng)絡(luò)爬蟲的的搜索引擎的框架和模型。2.搜索引擎的框架結(jié)構(gòu)基于網(wǎng)絡(luò)爬蟲的搜索引擎的框架從最簡單的方面來說可以分成如圖1的幾個部分。首先是從網(wǎng)絡(luò)上采集網(wǎng)頁，然后將這些原始的資料放入搜索系統(tǒng)中進(jìn)行處理并且等待查詢關(guān)鍵詞的輸入，最后根據(jù)查詢詞，這個系統(tǒng)可以給出按照文檔與查詢關(guān)鍵詞的相似度從大到小的排序查詢結(jié)果，以供用戶使用。2.1細(xì)化的搜索引擎系統(tǒng)框架通過觀察圖1，我們發(fā)現(xiàn)搜索引擎的幾乎所有奧秘都在那個搜索系統(tǒng)以及和它相關(guān)的三個接口中。所以展開這個系統(tǒng)的結(jié)構(gòu)就成為的進(jìn)一步了解搜索引擎結(jié)構(gòu)的關(guān)鍵。圖2則給出的細(xì)化的搜索系統(tǒng)的框架。這個系統(tǒng)框架重點(diǎn)展現(xiàn)了文件和查詢詞內(nèi)部處理的部分。文本框:用戶接口用戶接口廣義的文本處理查詢詞的處理建立索引查找排序形成文檔的內(nèi)部表示排序完的文檔形成查詢詞的內(nèi)部表示檢索出的文檔關(guān)鍵詞網(wǎng)頁的采集文檔用戶反饋流程圖:磁盤:搜索系統(tǒng)搜索系統(tǒng)網(wǎng)頁的采集排序結(jié)果關(guān)鍵詞用戶結(jié)果展示：這個框架我們可以發(fā)現(xiàn)搜索引擎的工作流程。第一步：網(wǎng)頁的采集。通過網(wǎng)絡(luò)爬蟲將大量的網(wǎng)頁抓到本地，形成文檔。第二步：文檔的處理。但是圖中標(biāo)明的是廣義的文本處理，而不是單純的文檔處理。這是因?yàn)槲覀儼l(fā)現(xiàn)這個廣義的文本處理過程不僅僅是處理從網(wǎng)絡(luò)上下載的網(wǎng)頁文檔，這里的文本處理還涉及到了關(guān)鍵詞的預(yù)處理操作。當(dāng)然，處理文檔和處理關(guān)鍵詞在這個文本處理關(guān)節(jié)中的內(nèi)容是相同的。具體可以包括中文分詞、停用詞消除、詞干還原等等。并且這里對于不同語言的文檔，其處理重點(diǎn)是不同的。第三步：建立索引。對于處理完的文本，系統(tǒng)就可以建立索引了?，F(xiàn)在最常用的建索引的方式莫過于全文倒排索引。它是以從文檔中切分出的單詞或分好詞的中文詞來作為標(biāo)引項(xiàng)(term)，所有不重復(fù)的標(biāo)引詞組成了一個詞庫，每個標(biāo)引項(xiàng)賦予它與每篇文檔的關(guān)系，這種關(guān)系體現(xiàn)在最重要的兩個信息上：一個是每個標(biāo)引項(xiàng)在每一篇文檔中出現(xiàn)的次數(shù)，另一個則是整個文檔中出現(xiàn)這個標(biāo)引項(xiàng)的文檔個數(shù)。這樣的兩個信息表征了每個標(biāo)引項(xiàng)與整個文檔庫中各個文檔的緊密程度。這樣的通過詞的這種信息來建立詞到文檔的“連接”方式就是倒排索引。同時(shí)從用戶處來的關(guān)鍵詞就可以看成是上述標(biāo)引項(xiàng)的組合，從而就能可以找到與關(guān)鍵詞相關(guān)度很大的文檔。當(dāng)然，關(guān)鍵詞可能是多個詞(即多個索引項(xiàng))，因此進(jìn)行查找是下一步的工作。第四步：進(jìn)行查找。從整個文檔中找出包含查詢的索引項(xiàng)的文檔。所以在查找前對關(guān)鍵詞進(jìn)行的處理也是重要的，它具體可以包括查詢擴(kuò)展和查詢重構(gòu)。前者主要是利用同義詞或近義詞對關(guān)鍵詞進(jìn)行擴(kuò)展，比如用戶查找的關(guān)鍵詞為“電腦”時(shí)，通過這步處理系統(tǒng)可以做到返回與“計(jì)算機(jī)”，“微機(jī)”等同義詞也相關(guān)的文檔，提高搜索的準(zhǔn)確度[5]。后者是指利用用戶的反饋信息對關(guān)鍵詞進(jìn)行適當(dāng)?shù)男薷摹．?dāng)然查找這一步在許多實(shí)際的系統(tǒng)中和下一步――排序，是可以同時(shí)完成的。因?yàn)椴檎页鰜淼奈臋n都已經(jīng)可以按照文檔和關(guān)鍵詞的相關(guān)度進(jìn)行排序。第五步：排序。把相關(guān)的文檔按照文檔與關(guān)鍵詞的相關(guān)度進(jìn)行整理排列。當(dāng)然相關(guān)度只是進(jìn)行排序的一種參考參數(shù)，在實(shí)際應(yīng)用中還會有進(jìn)行排序的其他附加參考參數(shù)。比如Google的PageRank算法就是對網(wǎng)頁的重要程度進(jìn)行排序。第六步：結(jié)果展示。3.搜索引擎的檢索模型從上節(jié)的分析發(fā)現(xiàn)整個搜索引擎的重點(diǎn)在于如何找到和關(guān)鍵詞相關(guān)的文檔。即檢索的這個過程。這一過程可以從圖3得到明示。所以查找的是否成功取決與文檔，查詢的內(nèi)部表示和他們之間相似度的計(jì)算。對查詢和文檔的表示統(tǒng)稱為檢索模型。它是搜索引擎中最核心的內(nèi)容之一。搜索引擎中的模型按照數(shù)學(xué)方法分類可以分成：1.基于集合論的模型：布爾模型，擴(kuò)展的布爾模型，基于模糊集的模型[3]2.基于代數(shù)論的模型：向量空間模型，潛語義索引模型[3]3.基于概率統(tǒng)計(jì)的模型：回歸模型，二元獨(dú)立概率模型4.利用語言模型建模的模型3.1布爾模型布爾模型是基于集合理論和布爾代數(shù)的一種簡單的檢索模型[3]。文檔和查詢均表示為布爾表達(dá)式。文檔表示成所有詞的“與”的關(guān)系，查詢可以由NOT，AND，OR連接起來的多個詞組成，這樣查詢可以寫成析取范式的形式。比如說，對于詞a，b，c，查詢q＝，則析取范式可化成q＝；而若文檔對于詞a，b，c可以表示為(相當(dāng)與(1，1，1))，則說明查詢和文檔匹配，而文檔對于詞a，b，c可以表示為!!(！a表示不包含a，相當(dāng)于(0，1，0))，則可直接判斷文檔與查詢無關(guān)。()abc∧∨(1，1，1)(1，1，0)(1，0，0)∨∨abc∧∧abc∧∧顯然布爾模型是一種精確的匹配方法，對于一個查詢詞，一篇文檔要么匹配要么不匹配，所以在簡單的同時(shí)也導(dǎo)致檢索的效果不太理想，也無法實(shí)現(xiàn)排序的功能。3.2向量空間模型向量空間模型是上個世紀(jì)七十年代由康乃爾大學(xué)提出的。其核心就是將文檔和查詢都轉(zhuǎn)化成由標(biāo)引項(xiàng)權(quán)重組成的向量形式，然后計(jì)算這兩個向量之間的夾角的余弦來表示兩者的相似度。如上節(jié)介紹，文檔被切分成很多個標(biāo)引項(xiàng)，即文檔是標(biāo)引項(xiàng)的集合。所有不重復(fù)的標(biāo)引詞組成了詞庫。并且假設(shè)所有不同的標(biāo)引相是相互獨(dú)立的。此時(shí)把文檔看成是由所有標(biāo)引項(xiàng)組成的向量，即文檔可用向量形式表示成d。w則是詞庫中某個詞在這篇文檔中的權(quán)重，也就是上節(jié)所說的那兩個信息(至少有這兩個)的量化表示。其中t是整個文檔庫中標(biāo)引詞的數(shù)目。同理，對于查詢詞也可以表示成所有標(biāo)引項(xiàng)組成的向量形式。這樣，文檔和查詢jd1，2，，{，...}jjjtjq1，2，，{，...}qqtqwww=qjdq都表示成了t維向量，就可以通過計(jì)算兩者的相似性來評價(jià)兩者的兩者的相似程度，這一定量關(guān)系主要通過兩個向量間的夾角余弦來表示。其中，jdq是文檔向量和查詢向量的模。因?yàn)槎际欠秦?fù)數(shù)，最后的余弦值在0到1之間，則模型不再試圖判斷文檔和查詢是否相關(guān)，而是根據(jù)文檔和查詢的相似度對文檔進(jìn)行排序，所以文獻(xiàn)和查詢僅僅部分匹配，該文獻(xiàn)也有可能被檢出。因此為余弦值設(shè)定一個閾值，大于該閾值的文檔才被檢出。這種模型的最明顯效果就是對檢出的文檔可以進(jìn)行排序，合理性比布爾模型要強(qiáng)的多，更加符合用戶的需求。3.3基于概率統(tǒng)計(jì)的模型概率檢索模型通過概率的方法將查詢和文檔聯(lián)系起來。其文檔和查詢也表示為一個個的標(biāo)引項(xiàng)。需事先計(jì)算查詢中的標(biāo)引項(xiàng)在與查詢相關(guān)以及不相關(guān)文檔中的分布概率，然后在查詢和文檔間進(jìn)行相似度計(jì)算時(shí)計(jì)算整個查詢和文檔的相似度。由于對每個查詢而言，事先無法知道相關(guān)和不相關(guān)的文檔，所以需要基于某種假設(shè)。具有代表性的是二元獨(dú)立檢索模型(BIR)。它根據(jù)用戶的查詢q，將所有文檔分為兩類，一類與查詢相關(guān)的集合R，另一類與查詢不相關(guān)R，兩者概率分別表示為:和(|)PRd(|)PRd。并假設(shè)文檔可表示為jd12(，，...，)jtd，表示第t個標(biāo)引項(xiàng)是否在文檔中，若在tx＝1，反之tx＝0。依然假設(shè)標(biāo)引相之間是獨(dú)立的。則文檔和q的相似度定義為：jd(|)(，)(|)jPRdsimdqPRd=。根據(jù)貝葉斯定義其可轉(zhuǎn)化為：(1)(，)log(1)iijiiipqsimdqxqp.=.Σ。其中()，()iiiirfpqrfr。f表示文檔集中的文檔總數(shù)，r表示集合R中文檔的個數(shù)，f表示整個文檔集中包含特征相文檔數(shù)，表示集合R中包含特征相irtX的文檔數(shù)。這種模型的優(yōu)點(diǎn)在于理論成熟，但缺陷也明顯，即它要求事先知道相關(guān)和不相關(guān)文檔的分布，還要估計(jì)參數(shù)。這種模型和向量空間模型思想逐漸融合，性能表現(xiàn)相當(dāng)。3.4利用語言模型建模的模型利用統(tǒng)計(jì)語言模型建模是由麻省理工大學(xué)于1998年提出的，它包括了查詢似然模型，翻譯模型，KL距離模型等一系列的模型。本文重點(diǎn)介紹查詢相似模型。查詢相似模型把查詢詞和文檔之間的相似度看成了文檔在已經(jīng)固定的語言下“生成”該查詢詞的可能性。這里從一個簡單的例子來理解這種模型。假設(shè)在整個文檔庫中所有詞的集合為，即整個文檔集的詞有t個。文檔D=(這是文檔詞序列，不同與向量空間模型中的)，查詢Q＝(查詢詞序列)，其中。再假設(shè)有一個有t個面的不規(guī)則的骰子，第i個面上寫著。而已知的文檔D＝意味著是拋那個不規(guī)則骰子拋了n次之后有m()個面朝上的結(jié)果(因?yàn)閮H僅是12{，，...}tVwww=12...nddd，id，ijw12...mqqq，iidqV∈iw12...ndddmn≤12...nddd個詞的序列，所以和有可能相等，。即同一個面可能出現(xiàn)多次)，現(xiàn)在的如果可以通過這個已知的信息估計(jì)出骰子拋出的概率idjd，ijn≤iwip(i)，也就是要推算出詞庫中每個詞在這個文檔的背景下出現(xiàn)的概率，有了這組t≤ip就可以輕松地算出Q＝的概率了。那么如果有N個文檔，每個文檔假設(shè)都能估計(jì)出一組互不相同的12...mqqqip，然后再用這組ip算出查詢詞在這篇文檔環(huán)境下“出現(xiàn)”的概率，這個概率值就可以區(qū)分出不同的文檔和同樣一個查詢詞的緊密關(guān)系。因此這種模型的要解決的第一個問題就是如何從一篇已知的文檔估計(jì)出那一組參數(shù)ip。這里使用的是最大似然估計(jì)法，即估計(jì)出的這組參數(shù)要使這篇文檔能夠“出現(xiàn)”查詢詞的概率最大。此模型要處理的第二個關(guān)鍵問題是數(shù)據(jù)的平滑，即如果一篇文章即便沒有出現(xiàn)詞庫中的某個詞不也能把這個詞的出現(xiàn)概率定為零。而是要通過相應(yīng)的方法給予這樣的詞以一定的概率估計(jì)。這個問題類似于一個6面的不規(guī)則骰子，若擲了10次每次都沒出現(xiàn)1同樣不能以此來估計(jì)1出現(xiàn)的概率為零。統(tǒng)計(jì)語言檢索模型具有較強(qiáng)的理論并且沒有標(biāo)引項(xiàng)獨(dú)立性假設(shè)。處于剛剛起步的統(tǒng)計(jì)語言模型為檢索技術(shù)的研究打開了新的一扇門。已經(jīng)達(dá)到并在某些程度上超過了向量模型和概率統(tǒng)計(jì)模型的性能。4.實(shí)驗(yàn)本文作者所在的實(shí)驗(yàn)室正在以研究的形式搭建一個簡易的網(wǎng)絡(luò)搜索引擎的平臺。第一階段的目標(biāo)就是在整合實(shí)驗(yàn)室以前在這方面的研究成果的基礎(chǔ)上，建成一個類似于通用網(wǎng)絡(luò)搜索引擎的一個實(shí)體。目前整個搜索引擎的大體框架如圖4所示。我們這個實(shí)驗(yàn)系統(tǒng)的兩個核心部分――組織整理和建索引查詢排序，都是實(shí)驗(yàn)室以前積累成熟的技術(shù)，所以在整個搭建過程中重點(diǎn)在于文檔的采集，用戶接口的設(shè)計(jì)以及如何條配好各個處理環(huán)節(jié)的銜接部分。采集工作主要是設(shè)計(jì)網(wǎng)絡(luò)爬蟲從網(wǎng)絡(luò)上抓取網(wǎng)頁，但是在網(wǎng)頁存儲的時(shí)候，必須要按照某個固定的結(jié)構(gòu)化形式存儲，這樣的文檔不但有利于組織整理的工作者方便的提取網(wǎng)頁的相關(guān)信息存入數(shù)據(jù)庫，而且建立索引對文檔的結(jié)構(gòu)化也有相當(dāng)?shù)囊?。我們這里采用的是類似TREC測試中數(shù)據(jù)的格式，文檔存在這樣的兩個標(biāo)簽之間，之間是文檔的id號，之間是網(wǎng)頁的鏈接地址，之間是網(wǎng)頁的標(biāo)題，此外還有不少類似的標(biāo)簽都是用來較明顯的存放重要的信息。然后在組織整理時(shí)，工作者一方面要對采集來的網(wǎng)頁文檔進(jìn)行取噪進(jìn)化，對中文網(wǎng)頁還要分詞，另一方面他們還要負(fù)責(zé)把每個網(wǎng)頁的重要信息存入數(shù)據(jù)庫，以備用戶接口的調(diào)用，比如常用的網(wǎng)頁數(shù)據(jù)有網(wǎng)頁的標(biāo)題，網(wǎng)頁的連接地址，網(wǎng)頁的大小，網(wǎng)頁被抓取的時(shí)間等。經(jīng)過組織整理的文檔就可以進(jìn)行建立索引等待查詢了。在建索引查詢時(shí)我們使用的是開源工具Lemur[4]，Lemur中有多種模型可以選擇，我們準(zhǔn)備選擇運(yùn)行效果較好的語言模型。但是Lemur在檢索結(jié)束后只提供了排序好的相關(guān)文檔的id和摘要，所以在用戶前端設(shè)計(jì)時(shí)我們還要回到底層的數(shù)據(jù)庫提取相關(guān)文檔的信息，在一定程度上影響了搜索的效率。5.總結(jié)爆炸形1:InternetInternet采集組織整理建索引查詢排序用戶接口結(jié)果展示提供查詢詞提供已排序的文檔ID和摘要