搜索引擎基本原理及實(shí)現(xiàn)技術(shù)——索引

1、搜索引擎基本原理及實(shí)現(xiàn)技術(shù)索引技術(shù)網(wǎng)絡(luò)爬蟲(chóng)辛辛苦苦的把網(wǎng)頁(yè)爬回來(lái)之后預(yù)處理系統(tǒng)主要工作信息抽取分詞分類(lèi)等處理工作生成正排發(fā)送 到索引系統(tǒng)生成倒排索引。信息抽取去標(biāo)簽和去噪去標(biāo)簽構(gòu)造 DOM 樹(shù)。，Jsoup；tinyHTML，htmlParser去噪去掉與正文不相關(guān)的廣告或者其他信息。如廣告，評(píng)論，導(dǎo)航條，版權(quán)信息，友情鏈接等等。分詞分詞的目的是為了提取文件特征，文件特征即網(wǎng)頁(yè)內(nèi)容的結(jié)構(gòu)化表現(xiàn)形式。分詞方法基于字符串匹配的分詞方法基于理解的分詞方法基于統(tǒng)計(jì)的分詞方法基于字符串匹配的分詞方法也叫做基于字典的分詞方法，它是以字典為依據(jù)的。按照一定的策略將待分析的漢字串與一個(gè)“充分大的”機(jī)器詞典中的

2、詞條進(jìn)行匹配。若在詞典中找到某個(gè)字符串，則匹配成功，即識(shí)別出一個(gè)詞。又分為三種：正向最大匹配法（由左到右的方向）；逆向最大匹配法（由右到左的方向）；最少切分法（使每一句中切出的詞數(shù)最小）。基于理解的分詞方法該方法又稱基于人工智能的分詞方法。它是利用漢語(yǔ)的語(yǔ)法知識(shí)和語(yǔ)義知識(shí)以及心理學(xué)知識(shí)進(jìn)行分詞，需要建立分詞數(shù)據(jù)庫(kù)、知識(shí)庫(kù)和推理機(jī)。這種分詞方法需要使用大量的語(yǔ)言知識(shí)和信息。目前還處在試驗(yàn)階段?；诮y(tǒng)計(jì)的分詞方法又稱為無(wú)字典分詞，它的主要思想是：詞是穩(wěn)定的組合，因此在上下文中，相鄰的字同時(shí)出現(xiàn)的次數(shù)越多，就越有可能構(gòu)成一個(gè)詞。因此字與字相鄰出現(xiàn)的概率或頻率能較好地反映成詞的可信度?？梢詫?duì)訓(xùn)練文本中

3、相鄰出現(xiàn)的各個(gè)字的組合的頻度進(jìn)行統(tǒng)計(jì)，計(jì)算它們之間的互現(xiàn)信息。分詞工具IkAnalyzer2012，國(guó)外有名的分析系統(tǒng)，也可以處理中文。使用簡(jiǎn)單。NLPIR2014, NLPIR2015ICTCLAS5.0中科院開(kāi)發(fā)的專門(mén)針對(duì)中文的分詞系統(tǒng)，中文分詞較準(zhǔn)確，稍微麻煩點(diǎn)教育學(xué)院/n_new/3.34/2#學(xué)院/n/2.58/19#教育/vn/1.74/3#信息/n/1.74/3#工程/n/1.34/5#教學(xué)/vn/1.27/3#網(wǎng)頁(yè)特征提取所有分出來(lái)的詞都要保留嗎？我該如何取舍呢？只保留一定數(shù)量的能代表網(wǎng)頁(yè)內(nèi)容特征的關(guān)鍵詞。最簡(jiǎn)單的就是統(tǒng)計(jì)詞頻，將出現(xiàn)頻率最高的n個(gè)詞保留。索引索引是對(duì)數(shù)據(jù)庫(kù)表中

4、一列或多列的值進(jìn)行排序的一種結(jié)構(gòu)。此處指的是將爬取的網(wǎng)頁(yè)進(jìn)行預(yù)處理之后的，將關(guān)于這個(gè)URL的信息存入數(shù)據(jù)庫(kù)，被稱為索引庫(kù)。 索引庫(kù)中關(guān)于URL的信息不僅是組成頁(yè)面內(nèi)容的關(guān)鍵詞及其特征(位置、格式等)，還有鏈接、更新情況等信息。建立倒排索引的基本過(guò)程（1）頁(yè)面分析將原始頁(yè)面的不同部分進(jìn)行識(shí)別并標(biāo)記，例如：title、keywords、content、link、anchor、評(píng)論、其他非重要區(qū)域等等；（2）對(duì)網(wǎng)頁(yè)內(nèi)容分詞。分詞的過(guò)程實(shí)際上包括了切詞分詞同義詞轉(zhuǎn)換同義詞替換等等。以對(duì)某頁(yè)面title分詞為例，得到的將是這樣的數(shù)據(jù)：term文本、termid、詞類(lèi)、詞性等等；（3）之前的準(zhǔn)備工作完成后

5、，接下來(lái)即是建立倒排索引，形成termdoc，倒排索引(Inverted Index)可以根據(jù)單詞快速獲取包含這個(gè)單詞的文檔列表。是實(shí)現(xiàn)“單詞單詞-文檔矩陣文檔矩陣”的一種具體存儲(chǔ)形式存儲(chǔ)形式。倒排索引的建立實(shí)際上在建立倒排索引的最后還需要有一個(gè)入庫(kù)寫(xiě)庫(kù)的過(guò)程，而為了提高效率這個(gè)過(guò)程還需要將全部term保存在文件頭部，并且對(duì)數(shù)據(jù)進(jìn)行壓縮，這些涉及到的技術(shù)自行學(xué)習(xí)。建立索引建立索引兩遍文檔遍歷法（兩遍文檔遍歷法（2-Pass In-Memory Inversion）在第一遍掃描文檔集合時(shí)，該方法并沒(méi)有立即開(kāi)始建立索引，而是收集一些全局的統(tǒng)計(jì)信息。比如文檔集合包含的文檔個(gè)數(shù)N，文檔集合內(nèi)所包含的不

6、同單詞個(gè)數(shù)M，每個(gè)單詞在多少個(gè)文檔中出現(xiàn)過(guò)的信息DF。每一項(xiàng)記載某個(gè)文檔的文檔ID和單詞在該文檔對(duì)應(yīng)的出現(xiàn)次數(shù)TF。第一遍掃描的主要目的是獲得一些統(tǒng)計(jì)信息，并根據(jù)統(tǒng)計(jì)信息分配內(nèi)存等資源，同時(shí)建立好了單詞相對(duì)應(yīng)倒排列表在內(nèi)存中的位置信息，即主要做些資源準(zhǔn)備工作。在第二遍掃描的時(shí)候，開(kāi)始真正建立每個(gè)單詞的倒排列表信息，即對(duì)于某個(gè)單詞來(lái)說(shuō)，獲得包含這個(gè)單詞的每個(gè)文檔的文檔ID，以及這個(gè)單詞在文檔中的出現(xiàn)次數(shù)TF，這樣就可以不斷填充第一遍掃描所分配的內(nèi)存空間。排序法（排序法（Sort-basedInversion）在建立索引的過(guò)程中，始終在內(nèi)存中分配固定大小的內(nèi)存，用來(lái)存放詞典信息和索引的中間結(jié)果，當(dāng)

7、分配的內(nèi)存被消耗光的時(shí)候，把中間結(jié)果寫(xiě)入磁盤(pán)，清空內(nèi)存里中間結(jié)果所占內(nèi)存，以用作下一輪存放索引中間結(jié)果的存儲(chǔ)區(qū)。 中間結(jié)果如何存儲(chǔ)，中間結(jié)果如何排序自行學(xué)習(xí)。歸并法（歸并法（Merge-basedInversion）?！皻w并法”對(duì)此做出了改進(jìn)，即每次將內(nèi)存中數(shù)據(jù)寫(xiě)入磁盤(pán)時(shí)，包括詞典在內(nèi)的所有中間結(jié)果信息都被寫(xiě)入磁盤(pán)，這樣內(nèi)存所有內(nèi)容都可以被清空，后續(xù)建立索引可以使用全部的定額內(nèi)存。 圖3-14是“歸并法”的示意圖。其整體流程和排序法大致相同，也是分為兩個(gè)大的階段，首先在內(nèi)存里維護(hù)中間結(jié)果，當(dāng)內(nèi)存占滿后，將內(nèi)存數(shù)據(jù)寫(xiě)入磁盤(pán)臨時(shí)文件，第二階段對(duì)臨時(shí)文件進(jìn)行歸并形成最終索引。正排索引也稱為前向索引。

8、它是創(chuàng)建倒排索引的基礎(chǔ)，具有以下字段。（1）LocalId字段（表中簡(jiǎn)稱Lid）：表示一個(gè)文檔的局部編號(hào)。（2）WordId字段：表示文檔分詞后的編號(hào)，也可稱為索引詞編號(hào)。（3）NHits字段：表示某個(gè)索引詞在文檔中出現(xiàn)的次數(shù)。（4）HitList變長(zhǎng)字段：表示某個(gè)索引詞在文檔中出現(xiàn)的位置，即相對(duì)于正文的偏移量。多字段索引（自學(xué)）針對(duì)每個(gè)不同的字段，分別建立一個(gè)索引，當(dāng)用戶指定某個(gè)字段作為搜索范圍時(shí)，可以從相應(yīng)的索引里提取結(jié)果。倒排列表方式擴(kuò)展列表方式索引更新索引更新完全重建策略（完全重建策略（CompleteRe-Build）當(dāng)新增文檔達(dá)到一定數(shù)量，將新增文檔和原先的老文檔進(jìn)行合并，然后利用

9、前述章節(jié)提到的建立索引的方式，對(duì)所有文檔重新建立索引。新索引建立完成后，老的索引被遺棄釋放，之后對(duì)用戶查詢的響應(yīng)完全由新的索引負(fù)責(zé)。 再合并策略（再合并策略（Re-Merge）有新增文檔進(jìn)入搜索系統(tǒng)時(shí)，搜索系統(tǒng)在內(nèi)存維護(hù)臨時(shí)倒排索引來(lái)記錄其信息，當(dāng)新增文檔達(dá)到一定數(shù)量，或者指定大小的內(nèi)存被消耗完，則把臨時(shí)索引和老文檔的倒排索引進(jìn)行合并，以生成新的索引。原地更新策略（原地更新策略（In-Place） 原地更新策略試圖改進(jìn)“再合并策略”的缺點(diǎn)。就是說(shuō)，在索引更新過(guò)程中，如果老索引的倒排列表沒(méi)有變化，可以不需要讀取這些信息，而只對(duì)那些倒排列表變化的單詞進(jìn)行處理。即使老索引的倒排列表發(fā)生變化，只在其末尾進(jìn)行追加操作，而不需要讀取原先的倒排列表并重寫(xiě)到磁盤(pán)另外一個(gè)位置? 在索引合并時(shí)，不生成新的索引文件，而是直接在原先老的索引文件里進(jìn)行追加操作，將增量索引里單詞的倒排列表項(xiàng)追加到老索引相應(yīng)位置的末尾混合策略（混合策略（Hybrid）將單詞根據(jù)其不同性質(zhì)進(jìn)行分類(lèi)，