【正文】 寫的基礎(chǔ)。 數(shù)據(jù)流分析。其次是對數(shù)字的壓縮，數(shù)字只保存與上一個值的差值，這樣可以減小數(shù)字的長度，從而減少保存該數(shù)字需要的字節(jié)數(shù)。為了減小索引文件的大小。索引數(shù)據(jù)存儲方面，、出現(xiàn)頻率、出現(xiàn)位置分別作為詞典文件(Term Dictionary)、頻率文件(frequencies)、位置文件(positions)保存?；旧隙裕且粋€倒排索引，比如使用索引/信息文件的方式，從文件安排的形式上提高查找的效率。這樣，整個段的索引信息就通過這些文檔有機(jī)的組成。這樣，域集合和項(xiàng)集合不僅僅聯(lián)系起來，而且其中的文件之間也互相聯(lián)系起來。由于索引信息是靜態(tài)存儲的，域集合與項(xiàng)集合中的文件組采用了一種類似的存儲方法：一個小型的索引文件，運(yùn)行時載入內(nèi)存；一個對應(yīng)于索引文件的實(shí)際信息文件，可以按照索引中指示的偏移量隨機(jī)訪問；索引文件與信息文件在記錄的排列順序上存在隱式的對應(yīng)關(guān)系，即索引文件中按照“索引項(xiàng)索引項(xiàng)2…”排列，則信息文件則也按照“信息項(xiàng)信息項(xiàng)2…”排列。.fnm各個域的名字信息.frq詞元（term）的頻率信息.prxterm在文檔中的位置信息.tis包含term數(shù)據(jù)信息，指向位置文件與頻率文件的指針.tii，.tvd保存有document信息，用詞元向量（TermVector）方式保存field的信息，同它包含一個指針表，deletable包含要刪除的文檔信息保存了相關(guān)段的信息每個段的文件中，主要記錄了兩類的信息：域集合和項(xiàng)集合。每個段包含一組文件，它們的文件擴(kuò)展名不同，但是文件名均稱為記錄在文件segments中段的名字。從概念上映射到結(jié)構(gòu)中，索引被處理為一個目錄(文件夾)，其中含有的所有文件即為其內(nèi)容，這些文件按照所屬的段不同分組存放，同組的文件擁有相同的文件名，不同的擴(kuò)展名。域是一個關(guān)聯(lián)的元組，由一個域名和一個域值組成，域名是一個字符串，域值是一個項(xiàng)，比如將“標(biāo)題”和實(shí)際標(biāo)題的項(xiàng)組成的域。(index)由若干段(segment)組成，每一段由若干的文檔(document)組成，每一個文檔由若干的域(field)組成，每一個域由若干的項(xiàng)(term)組成。，以字節(jié)為基礎(chǔ)，定義了數(shù)據(jù)類型，由于它們都以字節(jié)為基礎(chǔ)定義而來，因此保證了平臺無關(guān)的特性。 索引文件分析，、組織結(jié)構(gòu)、命名規(guī)范等等內(nèi)容，但是它僅僅是一個規(guī)范說明，并沒有從實(shí)現(xiàn)者的角度來衡量這個規(guī)范的實(shí)現(xiàn)。，而不是做為一個單獨(dú)的索引服務(wù)器存在。在每個局部細(xì)節(jié)上，比如某些常用的數(shù)據(jù)結(jié)構(gòu)與算法上。從面向?qū)ο蟮挠^點(diǎn)來考察，：引入額外的抽象層以降低耦合性。Search(搜索)。Storage(存儲)模塊也提供了2種保存索引方式，一種將索引信息存放在內(nèi)存中，一種針對索引信息存放在物理磁盤中。一種為搜索提供訪問，另一種協(xié)議為維護(hù)索引提供服務(wù)。需要對被索引的文件進(jìn)行分析，對于搜索過程而言，用戶輸入的查詢條件，也需要通過解析(Analysis)，通過相同的解析過程后，用戶的查詢信息才能和從文本解析出的信息相匹配，才能返回給用戶正確的結(jié)果。語料庫為Analysis模塊提供了訪問協(xié)議，Analysis通過該協(xié)議得到料庫的內(nèi)容。每一模塊從邏輯上又可以再劃分為2部分：交互協(xié)議部分與具體實(shí)現(xiàn)部分。各個模塊之間保持固定的協(xié)議，將實(shí)現(xiàn)方法隱藏起來。，如圖32所示。 系統(tǒng)結(jié)構(gòu)組織，其系統(tǒng)結(jié)構(gòu)具有強(qiáng)烈的面向?qū)ο蟮奶匦?。它的功能與Lucene一樣，都是用來提供一組API，讓開發(fā)人員能快速開發(fā)自己的搜索引擎。Lucene在應(yīng)用程序中的使用情況如圖31所示。提供了完整的查詢引擎和索引引擎，部分文本分析引擎(英文與德文兩種西方語言)。3 Apache Lucene是一個高性能(highperformance)的全能的全文檢索(fullfeatured text search engine)的搜索引擎框架庫，由Java編寫。通過檢索倒排索引獲取匹配關(guān)鍵字的網(wǎng)頁集合。Sorter讀取barrels中內(nèi)容，重新排序后產(chǎn)生以關(guān)鍵字(worded)為索引的倒排索引(inverted index)。鏈接文本被放入順排索引中，并與鏈接文本所指向的docID建立關(guān)聯(lián)。Indexer同時分析了網(wǎng)頁中所有的鏈接，并將鏈接文本(Anchor Text）、URL等重要信息存入稱為Anchors的結(jié)構(gòu)中。這也是Google區(qū)別其他搜索引擎的特點(diǎn)之一，Google更多的挖掘了網(wǎng)頁中內(nèi)容信息以改善檢索排名的結(jié)果。解壓后的頁面數(shù)據(jù)被轉(zhuǎn)換成一組稱為hits的結(jié)構(gòu)。數(shù)據(jù)索引數(shù)據(jù)索引由Indexer模塊，URL Resolver模塊和Sorter模塊共同完成。每個網(wǎng)頁都有一個獨(dú)一無二的docID，在Google早期設(shè)計(jì)中，docID被定義為32位的整數(shù)，也即意味著最多能保存40億個網(wǎng)頁數(shù)據(jù)，Google現(xiàn)在的數(shù)據(jù)量已經(jīng)達(dá)到了80億，如此規(guī)模的數(shù)據(jù)量也是Google設(shè)計(jì)者始料未及的。Crawler根據(jù)獲取URL列表進(jìn)行網(wǎng)頁抓取，已抓取的網(wǎng)頁被送往Store Server進(jìn)行保存。URL數(shù)據(jù)由URL Server模塊負(fù)責(zé)維護(hù)。 Google的工作過程Google工作流程可以分為信息采集，數(shù)據(jù)索引，查詢請求三個方面進(jìn)行分析：因?yàn)樾实木壒蔊oogle使用C和C++實(shí)現(xiàn)大部分模塊。 實(shí)際系統(tǒng)研究下面通過Google實(shí)現(xiàn)流程說明搜索引擎的具體工作過程。但這種方法也有一定的局限性，會經(jīng)常抽出一些共現(xiàn)頻度高、但并不是詞的常用字組，例如“這一”、“之一”、“有的”、“我的”、“許多的”等，并且對常用詞的識別精度差，時空開銷大。當(dāng)緊密程度高于某一個閾值時，便可認(rèn)為此字組可能構(gòu)成了一個詞。定義兩個字的互現(xiàn)信息，計(jì)算兩個漢字X、Y的相鄰共現(xiàn)概率。因此字與字相鄰共現(xiàn)的頻率或概率能夠較好的反映成詞的可信度。由于漢語語言知識的籠統(tǒng)、復(fù)雜性，難以將各種語言信息組織成機(jī)器可直接讀取的形式，因此目前基于理解的分詞系統(tǒng)還處在試驗(yàn)階段。在總控部分的協(xié)調(diào)下，分詞子系統(tǒng)可以獲得有關(guān)詞、句子等的句法和語義信息來對分詞歧義進(jìn)行判斷，即它模擬了人對句子的理解過程。其基本思想是在分詞的同時進(jìn)行句法、語義分析，利用句法信息和語義信息來處理歧義現(xiàn)象。另一種方法是將分詞和詞類標(biāo)注結(jié)合起來，利用豐富的詞類信息對分詞決策提供幫助，并且在標(biāo)注過程中又反過來對分詞結(jié)果進(jìn)行檢驗(yàn)、調(diào)整，從而極大地提高切分的準(zhǔn)確率。實(shí)際使用的分詞系統(tǒng)，都是把機(jī)械分詞作為一種初分手段，還需通過利用各種其它的語言信息來進(jìn)一步提高切分的準(zhǔn)確率。統(tǒng)計(jì)結(jié)果表明，單純使用正向最大匹配的錯誤率為1/169，單純使用逆向最大匹配的錯誤率為1/245。由于漢語單字成詞的特點(diǎn)，正向最小匹配和逆向最小匹配一般很少使用。S是否為單字S2=S2+S+”/”S1=S1S是是是否否否帶切分字符 S1，輸出字符 S2最大詞長 MaxLenS1是否為空輸出 S2最大詞長 MaxLen從S1右側(cè)開始，取出候選字符串S，S的長度不大于MaxLan查看字典，判斷S是否在字典中將S最左邊一個字去掉最大詞長 MaxLen開始結(jié)束圖26逆向最大匹配法實(shí)現(xiàn)流程圖(3) 最少切分(使每一句中切出的詞數(shù)最小)。S是否為單字S2=S2+S+”/”S1=S1S是是是否否否帶切分字符 S1，輸出字符 S2最大詞長 MaxLenS1是否為空輸出 S2最大詞長 MaxLen從S1左側(cè)開始，取出候選字符串S，S的長度不大于MaxLan查看字典，判斷S是否在字典中將S最右邊一個字去掉最大詞長 MaxLen開始結(jié)束圖25正向最大匹配法實(shí)現(xiàn)流程圖(2) 逆向最大匹配法(由右到左的方向)首先將待拆分的字符串從右向左進(jìn)行分詞，然后將分詞與機(jī)器字典中的詞條進(jìn)行匹配，若在詞典中找到某個字符串，則匹配成功。常用的幾種機(jī)械分詞方法如下：(1) 正向最大匹配法(由左到右的方向)首先將待拆分的字符串從左向右進(jìn)行分詞，然后將分詞與機(jī)器字典中的詞條進(jìn)行匹配，若在詞典中找到某個字符串，則匹配成功。 基于字符串匹配的分詞方法這種方法又叫做機(jī)械分詞方法，它是按照一定的策略將待分析的漢字串與一個“充分大的”機(jī)器詞典中的詞條進(jìn)行匹配，若在詞典中找到某個字符串，則匹配成功(識別出一個詞)。計(jì)算機(jī)可以很簡單通過空格知道student是一個單詞，但是不能很容易明白“學(xué)”、“生”兩個字合起來才表示一個詞。 中文分詞算法眾所周知，英文是以詞為單位的，詞和詞之間是靠空格隔開，而中文是以字為單位，句子中所有的字連起來才能描述一個意思?？陀^上，從網(wǎng)頁頁面本身的信息和鏈接情況分析，提高信息量大、鏈接度高的網(wǎng)頁頁面的優(yōu)先度排序。提高搜索引擎精度的關(guān)鍵是研究最優(yōu)的頁面優(yōu)先度算法，提供具有較高用戶相關(guān)度的網(wǎng)頁頁面優(yōu)先度排序。目前的搜索引擎系統(tǒng)都非常關(guān)心精度。對于一個檢索系統(tǒng)來講，召回率和精度不可能兩全其美，召回率高時，精度低，精度高時，召回率低。所以我們可以用衡量傳統(tǒng)信息檢索系統(tǒng)的性能參數(shù)一召回率(recall)和精度(pricision)衡量一個搜索引擎的性能。如：Cache，負(fù)載均衡等。(4) 檢索的速度主要依賴索引結(jié)構(gòu)的設(shè)計(jì)。搜索引擎需要在其中作出權(quán)衡。(2) 排序結(jié)果排重排重可以提高結(jié)果數(shù)據(jù)的質(zhì)量。Searcher中存在的問題：(1) 檢索結(jié)果的排序由于搜索引擎返回結(jié)果非常多，檢索結(jié)果是否按用戶預(yù)期的順序排列是評價搜索引擎的重要指標(biāo)之一。Searcher索引數(shù)據(jù)頁面數(shù)據(jù)用戶接口圖24 Searcher基本結(jié)構(gòu)圖Searcher通過某種接口方式，接收用戶查詢，對查詢進(jìn)行分詞(stemming)處理，獲取查詢關(guān)鍵字。 SearcherSearcher是直接與用戶進(jìn)行交互的模塊，在接口上有多種實(shí)現(xiàn)方式，常見的主要是Web方式，另外還可以通過無線接入方式(如手機(jī))進(jìn)行查詢。(5) 多語言，多格式支持網(wǎng)頁數(shù)據(jù)具有多種編碼格式，通過Unicode，索引支持多種編碼查詢。索引壓縮是通過對具體索引格式的研究實(shí)現(xiàn)壓縮。更新策略一般采用增量索引方式。Google存儲索引的服務(wù)器大概有1000多臺。Indexer中存在的問題：(1) 索引存儲一般來講，數(shù)據(jù)量和索引量的比例接近1:1。Indexer負(fù)責(zé)對Crawler采集的數(shù)據(jù)生成索引數(shù)據(jù)，基本結(jié)構(gòu)如圖23所示。具體地，關(guān)鍵詞被存儲在索引文件(index file)中，對于每個關(guān)鍵詞，都有一個指針鏈表，該表中的每一個指針指向與關(guān)鍵詞相關(guān)的某個頁面，所有指針鏈表構(gòu)成置入文件(posting file)。只要找到頁面，便可以找到其中的關(guān)鍵詞。要實(shí)現(xiàn)對采集頁面的快速訪問，必須通過某種索引機(jī)制來完成。(4) 壓縮算法網(wǎng)頁抓取后，通過一定的壓縮機(jī)制保存到本地，從而減少存儲容量，同時也減少各服務(wù)器之間的網(wǎng)絡(luò)通信開銷。評估算法中典型的油Google發(fā)明的PgaeRank。由于Web信息具有的分布性，非結(jié)構(gòu)化，不穩(wěn)定性等特點(diǎn)，Crawler存在以下的關(guān)鍵問題：(1) 多線程抓取時的任務(wù)調(diào)度問題搜索引擎會產(chǎn)生多個Crawler同時對網(wǎng)頁進(jìn)行抓取，這里需要一個好的分布式算法，使得既不重復(fù)抓取網(wǎng)頁，又不漏掉重要的站點(diǎn)?？梢詫WW作為一個有向圖來處理，將每一個頁面看作圖中的一個節(jié)點(diǎn)，將頁面中的超鏈接看做圖中的有向邊。不斷重復(fù)上面的過程，所有采集到的網(wǎng)頁保存到頁面存儲中進(jìn)行下一步處理。Crawler工作原理如圖22所示。Crawler日志分析器控制器原始數(shù)據(jù)庫索引數(shù)據(jù)庫IndexerSearcher用戶接口用戶日志數(shù)據(jù)庫圖21 搜索引擎體系結(jié)構(gòu)圖(1) Crawler從Web中采集網(wǎng)頁數(shù)據(jù)；(2) Indexer對Crawler采集數(shù)據(jù)進(jìn)行分析生成索引；(3) Searcher接受查詢請求，通過一定的檢索算法獲取查詢結(jié)果，排序后返回給用戶。2 搜索引擎技術(shù) 搜索引擎體系結(jié)構(gòu)典型的搜索引擎結(jié)構(gòu)一般由以下三個模塊組成：信息采集模塊(Crawler)，索引模塊(Indexer)，查詢模塊(Searcher)。具體內(nèi)容安排如下：第二章：介紹了搜索引擎總體結(jié)構(gòu)，各組成部分實(shí)現(xiàn)功能及關(guān)鍵技術(shù)，相關(guān)算法，并對Google的體系結(jié)構(gòu)進(jìn)行分析；第三章：，分析其組織架構(gòu)，索引數(shù)據(jù)格式等，對源碼分析，二次開發(fā)應(yīng)用；第四章：，在本文論述的理論思想基礎(chǔ)上，最終實(shí)現(xiàn)設(shè)計(jì)目標(biāo)；第五章：介紹互聯(lián)網(wǎng)信息檢索系統(tǒng)的具體實(shí)現(xiàn)，核心技術(shù)的解決方法。采用多線程進(jìn)行網(wǎng)頁數(shù)據(jù)采集并寫入數(shù)據(jù)庫；、中文分詞、無用詞匯刪除、詞典等技術(shù)建立索引數(shù)據(jù)；。本文在深入分析網(wǎng)頁獲取、索引生成、級別系統(tǒng)、索引檢索等搜索引擎核心技術(shù)的基礎(chǔ)上，設(shè)計(jì)并實(shí)現(xiàn)互聯(lián)網(wǎng)信息檢索系統(tǒng)。搜索引擎是這些技術(shù)的基礎(chǔ)和平臺，它決定著這些技術(shù)的開發(fā)和應(yīng)用。 研究目的和研究內(nèi)容互聯(lián)網(wǎng)的快速發(fā)展，對搜索引擎提出了更高的要求。此外還有一些其它值得注意的技術(shù)發(fā)展，如元搜索引擎，移動代理和XML技術(shù)，語音檢索技術(shù)等。它完全越過傳統(tǒng)的搜索模式，越過瀏覽器，真正實(shí)現(xiàn)讓搜索無處不在。(7) 專業(yè)化搜索主題搜索引擎是為了專門收錄某一行業(yè)、某一學(xué)科、某一主題和某一地區(qū)的信息而建立，非常實(shí)用，如有商務(wù)查詢、企業(yè)查詢、人名查詢、電子郵件地址查詢和招聘信息查詢等。(6) 多媒體數(shù)據(jù)搜索網(wǎng)絡(luò)資源豐富多彩，具有很多類型的信息，用戶需要的信息也不完全是網(wǎng)頁的形式，從用戶的角度來看，必然要求搜索引擎能夠覆蓋更多的網(wǎng)絡(luò)資源。自然語言的優(yōu)勢在于，一是使網(wǎng)絡(luò)交流更加人性化，二是使查詢變得更加方便、直接、有效。用戶可以輸入簡單的疑問句，比如“how can kill virus of puter?”。(5) 提供對自然語言檢索的支持為了提高搜索引擎對用戶檢索提問的理解，就必須有一個好的檢索提問語言，為了克服關(guān)鍵詞檢索和目錄查