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

1、搜索引擎基本原理及實(shí)現(xiàn)(shxin)技術(shù)索引(suyn)技術(shù)共三十九頁(yè)網(wǎng)絡(luò)爬蟲辛辛苦苦(xn xn k k)的把網(wǎng)頁(yè)爬回來(lái)之后共三十九頁(yè)預(yù)處理系統(tǒng)(xtng)主要工作信息抽取(chu q)分詞分類等處理工作生成正排發(fā)送 到索引系統(tǒng)生成倒排索引。共三十九頁(yè)信息(xnx)抽取去標(biāo)簽和去噪去標(biāo)簽構(gòu)造 DOM 樹(shù)。tinyHTML，htmlParser，Jsoup；去噪去掉與正文不相關(guān)(xinggun)的廣告或者其他信息。如廣告，評(píng)論，導(dǎo)航條，版權(quán)信息，友情鏈接等等。共三十九頁(yè)分詞(fn c)分詞的目的(md)是為了提取文件特征，文件特征即網(wǎng)頁(yè)內(nèi)容的結(jié)構(gòu)化表現(xiàn)形式。分詞方法基于字符串匹配的分詞方法基于

2、理解的分詞方法基于統(tǒng)計(jì)的分詞方法共三十九頁(yè)分詞(fn c)思想設(shè)計(jì)的原則1、顆粒度越大越好：用于進(jìn)行語(yǔ)義分析的文本分詞，要求分詞結(jié)果的顆粒度越大，即單詞的字?jǐn)?shù)越多，所能表示的含義越確切，如： “公安局長(zhǎng)”可以(ky)分為“公安 局長(zhǎng)”、“公安局 長(zhǎng)”、“公安局長(zhǎng)”都算對(duì)，但是要用于語(yǔ)義分析，則“公安局長(zhǎng)”的分詞結(jié)果最好（當(dāng)然前提是所使用的詞典中有這個(gè)詞）2、切分結(jié)果中非詞典詞越少越好，單字字典詞數(shù)越少越好，這里的“非詞典詞”就是不包含在詞典中的單字，而“單字字典詞”指的是可以獨(dú)立運(yùn)用的單字，如“的”、“了”、“和”、“你”、“我”、“他”。例如：“技術(shù)和服務(wù)”，可以分為“技術(shù) 和服 務(wù)”以及“

3、技術(shù) 和 服務(wù)”，但“務(wù)”字無(wú)法獨(dú)立成詞（即詞典中沒(méi)有），但“和”字可以單獨(dú)成詞（詞典中要包含），因此“技術(shù) 和服 務(wù)”有1個(gè)非詞典詞，而“技術(shù) 和 服務(wù)”有0個(gè)非詞典詞，因此選用后者。共三十九頁(yè)3、總體詞數(shù)越少越好，在相同(xin tn)字?jǐn)?shù)的情況下，總詞數(shù)越少，說(shuō)明語(yǔ)義單元越少，那么相對(duì)的單個(gè)語(yǔ)義單元的權(quán)重會(huì)越大，因此準(zhǔn)確性會(huì)越高。共三十九頁(yè)基于(jy)字符串匹配的分詞方法也叫做基于字典(zdin)的分詞方法，它是以字典為依據(jù)的。按照一定的策略將待分析的漢字串與一個(gè)“充分大的”機(jī)器詞典中的詞條進(jìn)行匹配。若在詞典中找到某個(gè)字符串，則匹配成功，即識(shí)別出一個(gè)詞。又分為三種：正向最大匹配法（由左到

4、右的方向）；逆向最大匹配法（由右到左的方向）；雙向最大匹配法。共三十九頁(yè)最大匹配(ppi)法 最大匹配是指以詞典為依據(jù)，取詞典中最長(zhǎng)單詞為第一個(gè)次取字?jǐn)?shù)量的掃描串，在詞典中進(jìn)行掃描。例如：詞典中最長(zhǎng)詞為“中華人民共和國(guó)”共7個(gè)漢字(Hnz)，則最大匹配起始字?jǐn)?shù)為7個(gè)漢字。然后逐字遞減，在對(duì)應(yīng)的詞典中進(jìn)行查找。下面以“我們?cè)谝吧鷦?dòng)物園玩”詳細(xì)說(shuō)明一下這幾種匹配方法：共三十九頁(yè)正向(zhn xin)最大匹配法1、正向最大匹配法：正向即從前往后取詞，從7-1，每次減一個(gè)字，直到詞典命中或剩下1個(gè)單字。第1次：“我們?cè)谝吧鷦?dòng)物”，掃描7字詞典，無(wú)第2次：“我們?cè)谝吧?yshng)動(dòng)”，掃描6字詞典，無(wú)

5、。第6次：“我們”，掃描2字詞典，有掃描中止，輸出第1個(gè)詞為“我們”，去除第1個(gè)詞后開(kāi)始第2輪掃描，即：第2輪掃描：第1次：“在野生動(dòng)物園玩”，掃描7字詞典，無(wú)第2次：“在野生動(dòng)物園”，掃描6字詞典，無(wú)。第6次：“在野”，掃描2字詞典，有掃描中止，輸出第2個(gè)詞為“在野”，去除第2個(gè)詞后開(kāi)始第3輪掃描，即：第3輪掃描：第1次：“生動(dòng)物園玩”，掃描5字詞典，無(wú)第2次：“生動(dòng)物園”，掃描4字詞典，無(wú)共三十九頁(yè)第3次：“生動(dòng)物”，掃描3字詞典，無(wú)第4次：“生動(dòng)”，掃描2字詞典，有掃描中止，輸出第3個(gè)詞為“生動(dòng)”，第4輪掃描，即：第4輪掃描：第1次：“物園玩”，掃描3字詞典，無(wú)第2次：“物園”，掃描2字

6、詞典，無(wú)第3次：“物”，掃描1字詞典，無(wú)掃描中止，輸出第4個(gè)詞為“物”，非字典詞數(shù)加1，開(kāi)始第5輪掃描，即：第5輪掃描：第1次：“園玩”，掃描2字詞典，無(wú)第2次：“園”，掃描1字詞典，有掃描中止，輸出第5個(gè)詞為“園”，單字字典詞數(shù)加1，開(kāi)始第6輪掃描，即：第6輪掃描：第1次：“玩”，掃描1字字典詞，有掃描中止，輸出第6個(gè)詞為“玩”，單字字典詞數(shù)加1，整體(zhngt)掃描結(jié)束。正向最大匹配法，最終切分結(jié)果為：“我們/在野/生動(dòng)/物/園/玩”，其中單字字典詞為2，非詞典詞為1。共三十九頁(yè)逆向最大匹配法：逆向即從后往前取詞，其他邏輯和正向相同。即：第1輪掃描：“在野生動(dòng)物園玩”第1次：“在野生動(dòng)物

7、園玩”，掃描7字詞典，無(wú)第2次：“野生動(dòng)物園玩”，掃描6字詞典，無(wú)。第7次：“玩”，掃描1字詞典，有掃描中止(zhngzh)，輸出“玩”，單字字典詞加1，開(kāi)始第2輪掃描第2輪掃描：“們?cè)谝吧鷦?dòng)物園”第1次：“們?cè)谝吧鷦?dòng)物園”，掃描7字詞典，無(wú)第2次：“在野生動(dòng)物園”，掃描6字詞典，無(wú)第3次：“野生動(dòng)物園”，掃描5字詞典，有掃描中止，輸出“野生動(dòng)物園”，開(kāi)始第3輪掃描第3輪掃描：“我們?cè)凇钡?次：“我們?cè)凇?，掃?字詞典，無(wú)第2次：“們?cè)凇?，掃?字詞典，無(wú)共三十九頁(yè)第3次：“在”，掃描1字詞典，有掃描中止，輸出“在”，單字字典詞加1，開(kāi)始第4輪掃描第4輪掃描：“我們”第1次：“我們”，掃描2字

8、詞典，有掃描中止，輸出“我們”，整體掃描結(jié)束。逆向(n xin)最大匹配法，最終切分結(jié)果為：“我們/在/野生動(dòng)物園/玩”，其中，單字字典詞為2，非詞典詞為0。共三十九頁(yè)雙向最大匹配(ppi)法正向最大匹配法和逆向最大匹配法，都有局限性。因此有人又提出了雙向最大匹配法，雙向最大匹配法。即，兩種算法都切一遍，然后根據(jù)大顆粒度詞越多越好，非詞典詞和單字詞越少越好的原則，選取其中(qzhng)一種分詞結(jié)果輸出。正向最大匹配法，最終切分結(jié)果為：“我們/在野/生動(dòng)/物/園/玩”，其中，兩字詞3個(gè)，單字字典詞為2，非詞典詞為1。逆向最大匹配法，最終切分結(jié)果為：“我們/在/野生動(dòng)物園/玩”，其中，五字詞1個(gè)，

9、兩字詞1個(gè)，單字字典詞為2，非詞典詞為0。非字典詞：正向(1)逆向(0)（越少越好）單字字典詞：正向(2)=逆向(2)（越少越好）總詞數(shù)：正向(6)逆向(4)（越少越好）因此最終輸出為逆向結(jié)果。共三十九頁(yè)基于(jy)理解的分詞方法該方法又稱基于人工智能的分詞方法。它是利用(lyng)漢語(yǔ)的語(yǔ)法知識(shí)和語(yǔ)義知識(shí)以及心理學(xué)知識(shí)進(jìn)行分詞，需要建立分詞數(shù)據(jù)庫(kù)、知識(shí)庫(kù)和推理機(jī)。這種分詞方法需要使用大量的語(yǔ)言知識(shí)和信息。目前還處在試驗(yàn)階段。共三十九頁(yè)基于統(tǒng)計(jì)(tngj)的分詞方法又稱為無(wú)字典分詞，它的主要思想(sxing)是：詞是穩(wěn)定的組合，因此在上下文中，相鄰的字同時(shí)出現(xiàn)的次數(shù)越多，就越有可能構(gòu)成一個(gè)詞。

10、因此字與字相鄰出現(xiàn)的概率或頻率能較好地反映成詞的可信度?？梢詫?duì)訓(xùn)練文本中相鄰出現(xiàn)的各個(gè)字的組合的頻度進(jìn)行統(tǒng)計(jì)，計(jì)算它們之間的互現(xiàn)信息。共三十九頁(yè)分詞(fn c)工具IkAnalyzer2012，國(guó)外有名的分析系統(tǒng)，也可以處理中文(zhngwn)。使用簡(jiǎn)單。NLPIR2014, NLPIR2015ICTCLAS5.0中科院開(kāi)發(fā)的專門針對(duì)中文的分詞系統(tǒng)，中文分詞較準(zhǔn)確，稍微麻煩點(diǎn)共三十九頁(yè)教育學(xué)院(xuyun)/n_new/3.34/2#學(xué)院(xuyun)/n/2.58/19#教育/vn/1.74/3#信息/n/1.74/3#工程/n/1.34/5#教學(xué)/vn/1.27/3#共三十九頁(yè)網(wǎng)頁(yè)(wn

11、y)特征提取所有分出來(lái)的詞都要保留嗎？我該如何取舍(qsh)呢？只保留一定數(shù)量的能代表網(wǎng)頁(yè)內(nèi)容特征的關(guān)鍵詞。最簡(jiǎn)單的就是統(tǒng)計(jì)詞頻，將出現(xiàn)頻率最高的n個(gè)詞保留。共三十九頁(yè)索引(suyn)索引是對(duì)數(shù)據(jù)庫(kù)表中一列或多列的值進(jìn)行排序(pi x)的一種結(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)鍵詞及其特征(位置、格式等)，還有鏈接、更新情況等信息。共三十九頁(yè)建立倒排索引的基本(jbn)過(guò)程（1）頁(yè)面分析將原始(yunsh)頁(yè)面的不同部分進(jìn)行識(shí)別并標(biāo)記，例如：title、keywords、content、l

12、ink、anchor、評(píng)論、其他非重要區(qū)域等等；（2）對(duì)網(wǎng)頁(yè)內(nèi)容分詞。分詞的過(guò)程實(shí)際上包括了切詞分詞同義詞轉(zhuǎn)換同義詞替換等等。以對(duì)某頁(yè)面title分詞為例，得到的將是這樣的數(shù)據(jù)：term文本、termid、詞類、詞性等等；（3）之前的準(zhǔn)備工作完成后，接下來(lái)即是建立倒排索引，形成termdoc，共三十九頁(yè)倒排索引(suyn)(Inverted Index)可以根據(jù)單詞快速獲取包含這個(gè)(zh ge)單詞的文檔列表。是實(shí)現(xiàn)“單詞-文檔矩陣”的一種具體存儲(chǔ)形式。共三十九頁(yè)倒排索引(suyn)的建立共三十九頁(yè)實(shí)際上在建立倒排索引的最后還需要有一個(gè)入庫(kù)寫庫(kù)的過(guò)程，而為了提高效率這個(gè)(zh ge)過(guò)程還需要

13、將全部term保存在文件頭部，并且對(duì)數(shù)據(jù)進(jìn)行壓縮，這些涉及到的技術(shù)自行學(xué)習(xí)。共三十九頁(yè)建立(jinl)索引兩遍文檔遍歷法（2-Pass In-Memory Inversion）在第一遍掃描文檔集合時(shí)，該方法并沒(méi)有立即開(kāi)始建立索引，而是收集一些全局的統(tǒng)計(jì)信息。比如文檔集合包含的文檔個(gè)數(shù)N，文檔集合內(nèi)所包含的不同單詞個(gè)數(shù)M，每個(gè)單詞在多少個(gè)文檔中出現(xiàn)過(guò)的信息DF。每一項(xiàng)記載某個(gè)文檔的文檔ID和單詞在該文檔對(duì)應(yīng)的出現(xiàn)次數(shù)TF。第一遍掃描的主要目的是獲得一些統(tǒng)計(jì)信息，并根據(jù)(gnj)統(tǒng)計(jì)信息分配內(nèi)存等資源，同時(shí)建立好了單詞相對(duì)應(yīng)倒排列表在內(nèi)存中的位置信息，即主要做些資源準(zhǔn)備工作。在第二遍掃描的時(shí)候，開(kāi)

14、始真正建立每個(gè)單詞的倒排列表信息，即對(duì)于某個(gè)單詞來(lái)說(shuō)，獲得包含這個(gè)單詞的每個(gè)文檔的文檔ID，以及這個(gè)單詞在文檔中的出現(xiàn)次數(shù)TF，這樣就可以不斷填充第一遍掃描所分配的內(nèi)存空間。共三十九頁(yè)排序(pi x)法（Sort-basedInversion）在建立索引的過(guò)程中，始終在內(nèi)存中分配(fnpi)固定大小的內(nèi)存，用來(lái)存放詞典信息和索引的中間結(jié)果，當(dāng)分配(fnpi)的內(nèi)存被消耗光的時(shí)候，把中間結(jié)果寫入磁盤，清空內(nèi)存里中間結(jié)果所占內(nèi)存，以用作下一輪存放索引中間結(jié)果的存儲(chǔ)區(qū)。中間結(jié)果如何存儲(chǔ)，中間結(jié)果如何排序自行學(xué)習(xí)。共三十九頁(yè)歸并(gubng)法（Merge-basedInversion）?！皻w并(gu

15、bng)法”對(duì)此做出了改進(jìn)，即每次將內(nèi)存中數(shù)據(jù)寫入磁盤時(shí)，包括詞典在內(nèi)的所有中間結(jié)果信息都被寫入磁盤，這樣內(nèi)存所有內(nèi)容都可以被清空，后續(xù)建立索引可以使用全部的定額內(nèi)存。 圖3-14是“歸并法”的示意圖。其整體流程和排序法大致相同，也是分為兩個(gè)大的階段，首先在內(nèi)存里維護(hù)中間結(jié)果，當(dāng)內(nèi)存占滿后，將內(nèi)存數(shù)據(jù)寫入磁盤臨時(shí)文件，第二階段對(duì)臨時(shí)文件進(jìn)行歸并形成最終索引。共三十九頁(yè)正排索引(suyn)也稱為前向索引。它是創(chuàng)建倒排索引的基礎(chǔ)，具有以下字段。（1）LocalId字段（表中簡(jiǎn)稱Lid）：表示一個(gè)文檔的局部編號(hào)。（2）WordId字段：表示文檔分詞(fn c)后的編號(hào)，也可稱為索引詞編號(hào)。（3）NH

16、its字段：表示某個(gè)索引詞在文檔中出現(xiàn)的次數(shù)。（4）HitList變長(zhǎng)字段：表示某個(gè)索引詞在文檔中出現(xiàn)的位置，即相對(duì)于正文的偏移量。共三十九頁(yè)多字段索引(suyn)（自學(xué)）針對(duì)每個(gè)不同的字段，分別建立一個(gè)索引，當(dāng)用戶指定某個(gè)字段作為搜索范圍時(shí)，可以從相應(yīng)(xingyng)的索引里提取結(jié)果。倒排列表方式擴(kuò)展列表方式共三十九頁(yè)索引(suyn)更新完全重建策略（CompleteRe-Build）當(dāng)新增文檔達(dá)到一定數(shù)量，將新增文檔和原先(yunxin)的老文檔進(jìn)行合并，然后利用前述章節(jié)提到的建立索引的方式，對(duì)所有文檔重新建立索引。新索引建立完成后，老的索引被遺棄釋放，之后對(duì)用戶查詢的響應(yīng)完全由新的索引

17、負(fù)責(zé)。共三十九頁(yè)再合并策略（Re-Merge）有新增文檔進(jìn)入搜索系統(tǒng)時(shí)，搜索系統(tǒng)在內(nèi)存維護(hù)臨時(shí)倒排索引來(lái)記錄(jl)其信息，當(dāng)新增文檔達(dá)到一定數(shù)量，或者指定大小的內(nèi)存被消耗完，則把臨時(shí)索引和老文檔的倒排索引進(jìn)行合并，以生成新的索引。共三十九頁(yè)原地更新策略（In-Place）原地更新策略試圖改進(jìn)“再合并策略”的缺點(diǎn)。就是說(shuō)，在索引更新過(guò)程中，如果老索引的倒排列表沒(méi)有變化，可以不需要讀取這些信息，而只對(duì)那些倒排列表變化的單詞進(jìn)行處理。即使老索引的倒排列表發(fā)生變化，只在其末尾進(jìn)行追加操作，而不需要讀取原先的倒排列表并重寫到磁盤另外一個(gè)位置(wi zhi)? 在索引合并時(shí)，不生成新的索引文件，而是直接

18、在原先老的索引文件里進(jìn)行追加操作，將增量索引里單詞的倒排列表項(xiàng)追加到老索引相應(yīng)位置的末尾共三十九頁(yè)混合策略（Hybrid）將單詞根據(jù)其不同性質(zhì)進(jìn)行分類，不同類別的單詞，對(duì)其索引采取不同的索引更新策略。根據(jù)單詞的倒排列表長(zhǎng)度進(jìn)行區(qū)分，將單詞劃分(hu fn)為“長(zhǎng)倒排列表單詞”-原地更新策略“短倒排列表單詞”- -再合并策略因?yàn)椤霸馗虏呗浴?策略能夠節(jié)省磁盤讀寫次數(shù)。而 “短倒排列表單詞”讀寫開(kāi)銷不算太大，所以利用“再合并策略”來(lái)處理，充分利用其順序讀寫優(yōu)勢(shì)共三十九頁(yè)共三十九頁(yè)索引(suyn)建立的過(guò)程1 正向索引路徑的輸入 正向索引路徑的建立最好建立在文件中，因?yàn)樗皇墙⑺饕闹虚g(zhngjin)過(guò)程，不需要存入數(shù)據(jù)中路徑的格式：1）相對(duì)路徑2）絕對(duì)路徑2 建立正向索引1）分詞（lucene分詞工具）共三十九頁(yè)2）停用詞(yn c)的去除 public static String transJe(String testString, String c1, String c2) String result = ; try Analyzer analyzer =