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

1、搜索引擎基本原理及實現(xiàn)技術索引技術網(wǎng)絡爬蟲辛辛苦苦的把網(wǎng)頁爬回來之后預處理系統(tǒng)主要工作信息抽取分詞分類等處理工作生成正排發(fā)送 到索引系統(tǒng)生成倒排索引。信息抽取去標簽和去噪去標簽構造 DOM 樹。tinyHTML，htmlParser，Jsoup；去噪去掉與正文不相關的廣告或者其他信息。如廣告，評論，導航條，版權信息，友情鏈接等等。分詞分詞的目的是為了提取文件特征，文件特征即網(wǎng)頁內(nèi)容的結構化表現(xiàn)形式。分詞方法基于字符串匹配的分詞方法基于理解的分詞方法基于統(tǒng)計的分詞方法分詞思想設計的原則1、顆粒度越大越好顆粒度越大越好：用于進行語義分析的文本分詞，要求分詞結果的顆粒度越大，即單詞的字數(shù)越多，所能表

2、示的含義越確切，如： “公安局長”可以分為“公安 局長”、“公安局 長”、“公安局長”都算對，但是要用于語義分析，則“公安局長”的分詞結果最好（當然前提是所使用的詞典中有這個詞）2、切分結果中非詞典詞越少越好，單字字典詞數(shù)越少越好切分結果中非詞典詞越少越好，單字字典詞數(shù)越少越好，這里的“非詞典詞”就是不包含在詞典中的單字，而“單字字典詞”指的是可以獨立運用的單字，如“的”、“了”、“和”、“你”、“我”、“他”。例如：“技術和服務”，可以分為“技術 和服 務”以及“技術 和 服務”，但“務”字無法獨立成詞（即詞典中沒有），但“和”字可以單獨成詞（詞典中要包含），因此“技術 和服 務”有1個非詞

3、典詞，而“技術 和 服務”有0個非詞典詞，因此選用后者。3、總體詞數(shù)越少越好總體詞數(shù)越少越好，在相同字數(shù)的情況下，總詞數(shù)越少，說明語義單元越少，那么相對的單個語義單元的權重會越大，因此準確性會越高?；谧址ヅ涞姆衷~方法也叫做基于字典的分詞方法，它是以字典為依據(jù)的。按照一定的策略將待分析的漢字串與一個“充分大的”機器詞典中的詞條進行匹配。若在詞典中找到某個字符串，則匹配成功，即識別出一個詞。又分為三種：正向最大匹配法（由左到右的方向）；逆向最大匹配法（由右到左的方向）；雙向最大匹配法。最大匹配法 最大匹配是指以詞典為依據(jù)，取詞典中最長單詞為第一個次取字數(shù)量的掃描串，在詞典中進行掃描。例如：詞

4、典中最長詞為“中華人民共和國”共7個漢字，則最大匹配起始字數(shù)為7個漢字。然后逐字遞減，在對應的詞典中進行查找。下面以“我們在野生動物園玩我們在野生動物園玩”詳細說明一下這幾種匹配方法：正向最大匹配法1、正向最大匹配法：正向即從前往后取詞，從7-1，每次減一個字，直到詞典命中或剩下1個單字。第1次：“我們在野生動物”，掃描7字詞典，無無第2次：“我們在野生動”，掃描6字詞典，無無。第6次：“我們”，掃描2字詞典，有有掃描中止，輸出第1個詞為“我們”，去除第1個詞后開始第2輪掃描，即：第2輪掃描：第1次：“在野生動物園玩”，掃描7字詞典，無無第2次：“在野生動物園”，掃描6字詞典，無無。第6次：“

5、在野”，掃描2字詞典，有有掃描中止，輸出第2個詞為“在野”，去除第2個詞后開始第3輪掃描，即：第3輪掃描：第1次：“生動物園玩”，掃描5字詞典，無無第2次：“生動物園”，掃描4字詞典，無無第3次：“生動物”，掃描3字詞典，無無第4次：“生動”，掃描2字詞典，有有掃描中止，輸出第3個詞為“生動”，第4輪掃描，即：第4輪掃描：第1次：“物園玩”，掃描3字詞典，無無第2次：“物園”，掃描2字詞典，無無第3次：“物”，掃描1字詞典，無無掃描中止，輸出第4個詞為“物”，非字典詞數(shù)加1，開始第5輪掃描，即：第5輪掃描：第1次：“園玩”，掃描2字詞典，無無第2次：“園”，掃描1字詞典，有有掃描中止，輸出第5

6、個詞為“園”，單字字典詞數(shù)加1，開始第6輪掃描，即：第6輪掃描：第1次：“玩”，掃描1字字典詞，有有掃描中止，輸出第6個詞為“玩”，單字字典詞數(shù)加1，整體掃描結束。正向最大匹配法，最終切分結果為：“我們我們/在野在野/生動生動/物物/園園/玩玩”，其中其中單字字典詞為單字字典詞為2，非詞典詞為，非詞典詞為1。逆向最大匹配法：逆向最大匹配法：逆向即從后往前取詞，其他邏輯和正向相同。即：第1輪掃描：“在野生動物園玩”第1次：“在野生動物園玩”，掃描7字詞典，無無第2次：“野生動物園玩”，掃描6字詞典，無無。第7次：“玩”，掃描1字詞典，有有掃描中止，輸出“玩”，單字字典詞加1，開始第2輪掃描第2輪

7、掃描：“們在野生動物園”第1次：“們在野生動物園”，掃描7字詞典，無無第2次：“在野生動物園”，掃描6字詞典，無無第3次：“野生動物園”，掃描5字詞典，有有掃描中止，輸出“野生動物園”，開始第3輪掃描第3輪掃描：“我們在”第1次：“我們在”，掃描3字詞典，無無第2次：“們在”，掃描2字詞典，無無第3次：“在”，掃描1字詞典，有有掃描中止，輸出“在”，單字字典詞加1，開始第4輪掃描第4輪掃描：“我們”第1次：“我們”，掃描2字詞典，有有掃描中止，輸出“我們”，整體掃描結束。逆向最大匹配法，最終切分結果為：“我們我們/在在/野生動物園野生動物園/玩玩”，其中，單字字典詞為，其中，單字字典詞為2，非

8、詞典詞為，非詞典詞為0。雙向最大匹配法雙向最大匹配法正向最大匹配法和逆向最大匹配法，都有局限性。因此有人又提出了雙向最大匹配法，雙向最大匹配法。即，兩種算法都切一遍，然后根據(jù)大顆粒度詞越多越好，非詞典詞和單字詞越少越好的原則，選取其中一種分詞結果輸出。正向最大匹配法，最終切分結果為：“我們我們/在野在野/生動生動/物物/園園/玩玩”，其中，兩字詞兩字詞3個，單字字典詞為個，單字字典詞為2，非詞典詞為，非詞典詞為1。逆向最大匹配法，最終切分結果為：“我們我們/在在/野生動物園野生動物園/玩玩”，其中，五字詞五字詞1個，兩字詞個，兩字詞1個，單字字典詞為個，單字字典詞為2，非詞典詞為，非詞典詞為0

9、。非字典詞：非字典詞：正向(1)逆向(0)（越少越好）單字字典詞：單字字典詞：正向(2)=逆向(2)（越少越好）總詞數(shù)：總詞數(shù)：正向(6)逆向(4)（越少越好）因此最終輸出為逆向結果。最終輸出為逆向結果?；诶斫獾姆衷~方法該方法又稱基于人工智能的分詞方法。它是利用漢語的語法知識和語義知識以及心理學知識進行分詞，需要建立分詞數(shù)據(jù)庫、知識庫和推理機。這種分詞方法需要使用大量的語言知識和信息。目前還處在試驗階段?；诮y(tǒng)計的分詞方法又稱為無字典分詞，它的主要思想是：詞是穩(wěn)定的組合，因此在上下文中，相鄰的字同時出現(xiàn)的次數(shù)越多，就越有可能構成一個詞。因此字與字相鄰出現(xiàn)的概率或頻率能較好地反映成詞的可信度。

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

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

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

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

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

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

16、行合并，然后利用前述章節(jié)提到的建立索引的方式，對所有文檔重新建立索引。新索引建立完成后，老的索引被遺棄釋放，之后對用戶查詢的響應完全由新的索引負責。 再合并策略（再合并策略（Re-Merge）有新增文檔進入搜索系統(tǒng)時，搜索系統(tǒng)在內(nèi)存維護臨時倒排索引來記錄其信息，當新增文檔達到一定數(shù)量，或者指定大小的內(nèi)存被消耗完，則把臨時索引和老文檔的倒排索引進行合并，以生成新的索引。原地更新策略（原地更新策略（In-Place） 原地更新策略試圖改進“再合并策略”的缺點。就是說，在索引更新過程中，如果老索引的倒排列表沒有變化，可以不需要讀取這些信息，而只對那些倒排列表變化的單詞進行處理。即使老索引的倒排列表發(fā)

17、生變化，只在其末尾進行追加操作，而不需要讀取原先的倒排列表并重寫到磁盤另外一個位置? 在索引合并時，不生成新的索引文件，而是直接在原先老的索引文件里進行追加操作，將增量索引里單詞的倒排列表項追加到老索引相應位置的末尾混合策略（混合策略（Hybrid）將單詞根據(jù)其不同性質(zhì)進行分類，不同類別的單詞，對其索引采取不同的索引更新策略。根據(jù)單詞的倒排列表長度進行區(qū)分，將單詞劃分為“長倒排列表單詞”-原地更新策略“短倒排列表單詞”- -再合并策略因為“原地更新策略” 策略能夠節(jié)省磁盤讀寫次數(shù)。而 “短倒排列表單詞”讀寫開銷不算太大，所以利用“再合并策略”來處理，充分利用其順序讀寫優(yōu)勢索引建立的過程1 正向索引路徑的輸入 正向索引路徑的建立最好建立在文件中，因為它只是建立索引的中間過程，不需要存入數(shù)據(jù)中路徑的格式：1）相對路徑2）絕對路徑2 建立正向索引1）分詞（lucene分詞工具）2）停用詞的去除 public static String transJe(String testString, String c1, String c2) String result = ; try Analyzer analyzer = new MIK_CAnalyzer(); Reader r = new StringReader(testString); TokenS