《第三章 文本處理與信息檢索》由會員分享，可在線閱讀，更多相關《第三章 文本處理與信息檢索（102頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、單擊此處編輯母版標題樣式,,單擊此處編輯母版文本樣式,,第二級,,第三級,,第四級,,第五級,,*,,*,單擊此處編輯母版標題樣式,,單擊此處編輯母版文本樣式,,第二級,,第三級,,第四級,,第五級,,第三章 文本處理與信息檢索,,主講老師,:,胡純?nèi)?知識要點,信息檢索模型,[,難點,],,文本處理,[,難點,],,文本索引,[,難點,],3.1,引言,信息檢索,定義：,,通常指文本信息檢索，包括信息的存儲、組織、表現(xiàn)、查詢、存取等各個方面，其核心為文本信息的,索引和檢索,。,,背景：,,半結構文本和自由文本是其中的一類重要資源；,,文本可以對其他媒體（如圖像、音頻、視頻等）進行標注，然后
2、使用成熟的信息檢索技術進行多媒體信息檢索。,信息檢索、搜索引擎,區(qū)別：,,數(shù)據(jù)量,,內(nèi)容相關性,,搜索引擎發(fā)展的是網(wǎng)頁鏈接分析技術；,,信息檢索要求基于內(nèi)容的相關性排序，和檢索要求最相關的信息排在檢索結果的前面。,,實時性,,搜索引擎的索引生成,周期性更新,,,大的搜索引擎的更新周期需要以周乃至月度量；,,信息檢索需要,實時,反映內(nèi)外信息變化。,,安全性,,互聯(lián)網(wǎng)搜索引擎基于,文件系統(tǒng),；,,企業(yè)應用中的信息檢索一般,存放在數(shù)據(jù)庫,中；,,個性化和智能化,,相對而言信息檢索走得更遠。,,3.2,信息檢索模型,,3.2.1,信息檢索模型分類,分類,,布爾模型：集合,,向量空間模型：代數(shù),,概率模
3、型：概率,3.2.2,經(jīng)典檢索模型,一、任何,檢索策略,都包含,3,個部分：,,文檔表示,,查詢表示,,匹配函數(shù),,,（,1,）,文檔表示,:,反映文檔在系統(tǒng)中的存儲形式，可用一組索引項表示；,,（,2,）,查詢表示,:,反映對用戶信息需求的描述；,,（,3,）,匹配函數(shù),:,將經(jīng)過處理的文檔表示和查詢表示進行匹配，以過濾輸出結果。,,,二、研究信息檢索方法：,,1,、構成檢索系統(tǒng)的兩個要素,:,文檔和檢索式；,,2,、定義和計算文檔和檢索式之間的關系。,,,三、檢索模型的作用：,,1,、更精確地描述出文檔與文檔、文檔與查詢間的相關關系，并能計算和比較；,,2,、安排更合理、更便于檢索的文檔存
4、儲形式；,,3,、此外設計出合理的檢索方式。,,,四、信息檢索模型：,,1,）,集合理論模型：,文檔和查詢用索引項集合表示；,,2,）,代數(shù)模型：,文檔和查詢用,t,維空間的向量來表示；,,3,）,概率模型：,文檔和查詢的機制都是基于概率論的框；架之上的；,,比較重要的還有：結構化模型；,,,五、信息檢索模型可描述如下,:,,,信息檢索模型是個四元組,/,D,，,Q,，,F,，,R,(,q,i,,,d,j,)/,,（,1,）,D,：,文檔的表示；,,（,2,）,Q,：,查詢表示；,,（,3,）,F,：,構建文檔表示、查詢及它們之間關系的模型；,,（,4,）,R,(,q,i,,,d,j,),：排
5、序函數(shù)，該函數(shù)輸出一個與查詢,q,i,∈,Q,和文檔表示,d,j,∈,D,有關的實數(shù)，這樣就在文檔之間根據(jù)查詢,q,i,定義了一個順序。,,,索引項,(index term),,：對于一篇文檔，任何一個在其中出現(xiàn)過的詞語。,,,權值,(weight):,表示該索引項對該篇文檔的重要程度。,,,信息檢索的經(jīng)典模型認為,:,,（,1,）文檔表示：,每篇文檔可以用索引項集合來描述；,,（,2,）明確索引項與文檔內(nèi)容的密切程度。,,經(jīng)典模型的思想,用,k,i,表示索引項，,,d,j,表示文檔，,,w,i,j,≥ 0,為二元組,(,k,i,,,d,j,),的權值,(weight)，,,用,t,表示系統(tǒng)中
6、索引項的數(shù)目，,,K,={,k,1,,,k,2,, ... ,,k,t,},是所有索引項的集合，,w,i,j,＞,0,是文檔,d,j,中的索引項,k,i,的權值，對于沒有出現(xiàn)在文檔文本中的索引項，其權值,w,i,j,=0,。,,文檔,d,j,可以用索引項向量,d,j,來表示：,d,j,= (,w,1,j,,,w,2,j,, …,,w,t,j,),。,,此外，函數(shù),g,i,用以返回任何,t,維向量中索引項,k,i,的權值，即,g,i,(,d,j,) =,w,i,j,。其中，索引項的權重通常被認為是互相獨立的。,,（1）布爾模型,1,）定義：,,基于集合理論和布爾代數(shù)的一種簡單的檢索模型。,,2,
7、）算法：,,假定索引項在文檔中要么出現(xiàn)，要么不出現(xiàn)。因此，索引項的權值全部被設為二值數(shù)據(jù)，,w,i,j,∈{0, 1},；,,查詢,q,：,由連接謂詞,not,、,and,、,or,連接起來的多個索引項所組成，,,如：“奧運會”、“奧運會”,and“,中國”、“奧運會”,and,（“中國”,or,（,not“,體操”））等，通過對索引項與用戶給出的檢索式進行邏輯比較來檢索文本。,,,,如果,sim,(,d,j,,,q,)=1,，則布爾模型表示文檔與查詢相關（,,也可能不相關），否則文檔,d,j,與查詢,q,不相關。,,定義,對于布爾模型而言，索引項權值變量都是二值的，即,w,i,j,∈{0,
8、1},，查詢,q,是一個常規(guī)的布爾表達式。用,q,dnf,表示查詢,q,的析取范式，,q,cc,表示,q,dnf,的任意合取分量。文檔,d,j,和查詢,q,的相似度可以定義為：,預備知識（離散數(shù)學、線性代數(shù)）,一、離散數(shù)學：,,簡單析取式,：僅由有限個命題變項或其否定構成的析取式；,,簡單合取式,：僅由有限個命題變項或其否定構成的合取式；,,析取范式,：僅由有限個簡單合取式構成的析取式；,,合取范式,：僅由有限個簡單析取式構成的合取式；,,,二、線性代數(shù)：,,線性相關：給定向量組,A:,t,1,,,t,2,, ?,,t,m,,，存在一組,k,1,, k,2,, ?, k,m,,不全為零，使,k
9、,1,t,1,+ k,2,,t,2,+ ?+k,m,t,m,=0,,那么線性相關。,,實例,:,若查詢?yōu)?q=k,a,∧(k,b,∨┐k,c,),,找出哪些合取向量與,q,完全相關。,布爾模型的優(yōu)缺點,優(yōu)點：清晰、簡潔,,缺點：,,過于精確的匹配檢索結果過多或過少；,,檢索策略是基于二值決策原則，限制了其檢索性能，更像一個數(shù)據(jù)檢索模型；,,布爾表達式具有準確的語義，但將一個檢索請求轉化成為對應的布爾表達式并不太容易。,,（,2,）向量模型,定義,3.3,,,在向量模型中,,,索引詞、文檔對 的權重 是正數(shù)且非僅二值，查詢,q,的索引項也是有權重的。假設 是
10、,,的權重， 。那么，檢索向量,q,被定義為一個索引項空間下的向量,,,這里,t,是系統(tǒng)中所有索引項的數(shù)目，文檔可表示為：,,,,通過相似度計算公式計算出每個文檔向量與查詢向量的相似度，即,:,Sim,(,d,j,,,q,) =,或,Sim,(,d,j,, q) =,cosθ,=,排序這個,結果后與設立的閾值,進行,比較,：,,如果大于閾值則頁面與查詢相關，保留該頁面查詢結果；,,如果小于則不相關，過濾此頁。,,這樣就,可以控制查詢結果的數(shù)量，,,加快查詢速度。,向量,模型,---,特征項權值計算方法,從向量空間模型的特點可以看出：在特征項確定的情況下，特征項的,權值計算,是文檔
11、分類的,關鍵。,,,特征項權值計算,常用的方法：,TFIDF,函數(shù)應用最為廣泛,，主要思想是：詞語加權技術（與聚類技術的基本原理密切相關）。,,其中，,TF：,表示索引項頻率，用于衡量一個索引項對于文檔內(nèi)容的,描述能力,；,,IDF：,表示逆文檔頻率，其作用是降低一些很多文檔中都出現(xiàn)的索引項在判斷是否相關時的,區(qū)分能力,。,,,TF,因子,定義,3.4,,,假設 是系統(tǒng)中所有文檔的數(shù)目， 是索引項 出現(xiàn)的文檔數(shù)目， 是索引項 在文檔 中的基礎頻率（比如是 在 的文本內(nèi)容中出現(xiàn)的次數(shù)），那么索引項 在文檔 中的 表示如下：
12、,,,,,其中：最大值 是所有索引項在文檔 的最大值。,,,IDF,因子定義,定義索引項 的逆文檔頻率 的值如下：,,,,,那么,最常用的索引項賦值,表示如下：,,,,,向量模型的優(yōu)勢,索引項賦值的方法提高了檢索性能；,,部分匹配的策略支持檢索一些與查詢請求近似的文檔；,,余弦排序的模式根據(jù)文檔和查詢的相似度對檢索的文檔進行排序。,,,缺點：假設各個索引項在文檔中是互相獨立的。,(3),概率模型,基本思想,:,,根據(jù)用戶的檢索,q,，可以將文檔集,D,中的所有文檔分為兩類：一類與檢索需求,q,相關（集合,R,），另一類與檢索需求不相關,( ),。,,假
13、設,3.1,概率原理,,,給出一個用戶查詢,q,和文檔集中的文檔,d,j,,,概率模型試圖給出文檔,d,j,在用戶預期的結果文檔集中的概率是多少。該模型假設相關的概率僅與查詢和文檔的表示形式有關。,預備知識,劃分,的定義：,,設,S,為試驗,E,的樣本空間， 為,E,的一組事件，若,,（,1,）,,（,2,）,,則稱 為樣本空間,S,的一個劃分。,,若 是樣本空間的一個劃分，那么對每次試驗，事件,,中必有一個且僅有一個發(fā)生。,,定理,,設試驗,E,的樣本空間為,S,，,A,為,E,的事件，,,為,S,的一
14、個劃分，且 ，則,,,,稱為,全概率公式,。,,定理,,設試驗,E,的樣本空間為,S,，,A,為,E,的事件，,,為,S,的一個劃分，且 ， 則,,,,,,稱為,貝葉斯（,Bayes,）公式,.,,,乘法定理,,由條件概率的定義，設,P(A)>0,，則有,,P,（,AB,）,=P,（,B|A,）,P,（,A,）,,,區(qū)分,互斥,、,互不相容,、,相互獨立,投擲一個骰子：,,(1),事件,A,：出現(xiàn)點數(shù)為,1,,事件,B,：出現(xiàn)點數(shù)為,2,,事件,A,和,B,為,互不相容,事
15、件，因為出現(xiàn),A,肯定不能出現(xiàn),B,，出現(xiàn),B,肯定不能出現(xiàn),A,。但是他們不是互斥事件，因為即使不出現(xiàn),A,，也不能保證一定出現(xiàn),B,。,,(2),事件,C,：出現(xiàn)點數(shù)為,1,,事件,D,：出現(xiàn)點數(shù)為,2,，或,3,，或,4,，或,5,，或,6,,則事件,C,和,D,為,互斥,，因為如果不出現(xiàn),C,肯定出現(xiàn),D,，不出現(xiàn),D,肯定出現(xiàn),C,。顯然，,C,和,D,也是,互不相容,的。,,(3),設,A,，,B,是試驗,E,的兩事件，若 可以定義,,如果,A,的發(fā)生對,B,發(fā)生的概率沒有影響時，則稱,A,，,B,為相互獨立事件。,概率模型的相關性算法,,給出一個查詢,q,,概率模
16、型給每篇文檔 一個值,,,這個值表示了該文檔和查詢之間的相似性。計算 和,q,相關的概率與 與,q,不相關的概率之比,.,,,此算法可以減少相關排序時產(chǎn)生的判斷錯誤,.,,定義,3.5,,,在概率模型中,,,索引項權值是二值的,, .,查詢,q,是索引項的子集,.,假設,R,是已知的,(,或最初假設的,),相關文檔的集合,,,是,R,的補集,.,用 來表示文檔 與查詢,q,的相關概率,,,用 來表示文檔 與查詢,q,不相關的概率,.,文檔,,,與查詢,q,的相似性 的計
17、算定義如下,:,,,,使用貝葉斯法則有,,,,,,,,,,,,,由于,P(R),和,P(,,),對于所有文檔都是相同的，因此,,,,根據(jù)索引項的獨立性假設有,,,,,,其中,:,,(1),表示索引項,,存在于從,R,中隨機選取的文檔,,中的概率,;,,(2),索引項 不存在于從,R,中隨機選取的文檔中,,的概率,.,,,,,,考慮到,,,相似度可以這樣計算,:,,,,計算 和 的方法：,在開始檢索前，一般作如下簡單初始假定，以啟動檢索進程：,,對于所有索引詞 的值都是常數(shù)，并且通常情況下規(guī)定為：,,,索引
18、詞在非相關文檔集合中的概率分布近似于索引詞在全體文檔集合中的概率分布，即：,,,,,,分別表示含索引詞的文檔數(shù)和系統(tǒng)擁有的全體文檔數(shù)。,,據(jù)上述初始假定，針對用戶提問的檢索操作就可以獲得一批相關文檔，,,用,V,來表示這批排序輸出文檔最靠前的,r,個文檔（,r,是一個預先指定的閥值）,,用,Vi,表示集合,V,中含有索引詞而形成的文檔集合，,Vi,中的文檔數(shù)量為,ri,個。,,基于相關反饋原理，常用的改進方案主要有：,,概率模型,優(yōu)勢,:,在理論上可以按照它們可能是相關的概率來排序,.,,劣勢,:,,需要對文檔最初是相關還是不相關作一個假設,;,,沒有考慮到文檔中出現(xiàn)的索引項的頻率,(,即索引
19、項權重是二值,);,,采用索引項獨立假設,,,這種假設沒有被驗證,;,,經(jīng)典模型之間的簡單比較,.,3.3,文本處理,,背景,實施文本處理的原因,:,,通常來講,,,名詞最能代表一篇文檔的內(nèi)容,;,,使用文檔集中出現(xiàn)的所有詞語作為索引項將產(chǎn)生很大的,”,噪聲,”;,,,一種減少,”,噪聲,”,的辦法就是減少索引項的大小,;,,問題,：哪些詞語可用來作索引項？,3.3.1,文本預處理,文本預處理主要的操作,:,,文本詞匯分析,(lexical analysis);,,去除停用詞,;,,詞根還原,(stemming);,,索引項選擇,;,,創(chuàng)建索引項分類結構,(,比如辭典,thesauri),,文
20、本預處理的邏輯圖,非結構化文檔,結構化,,文 檔,名 詞,,詞 組,自動手動建索引,,,,分詞技術,去停用詞：,,除去各種非實義詞（冠詞、介詞連詞等）,,,,去詞根詞綴：,,如,beat,beating,beated.,,索引項,(1),文本詞匯分析,定義,:,,一個將字符流轉換成詞語,(,候選索引項,),流的過程,,,即分詞過程,.,,數(shù)字,:,,數(shù)字通常不作為索引項,,,因為數(shù)字離開上下文通常都沒有意義,;,,數(shù)字和字母混在一起時,,,數(shù)字是一個非常重要的索引項,,,但是這種情況的規(guī)則很難被總結出來,;,有的數(shù)字也很重要,,,比如身份證號碼,,,可以作為一個索引項,;,,,一種最簡單的處理
21、就是將文本中出現(xiàn)的所有數(shù)字全部去除,,,除非是一些特殊指定的（比如通過正則表達式表示的規(guī)則中的數(shù)字）。,,,連字符,:,,有些連接詞語分開仍然有用,;,,有些連字符連接的是數(shù)字,;,,總結出一個通用規(guī)則并將特殊情況一一指定出來,.,,標點符號,:,,,通常在語義分析的時候,,,標點符號,全部除去,,,對于一些特殊情況應該單獨考慮，若一段程序代碼作為文本的一部分（如,x.id,xid,）。,,字母的大小寫,:,,通過將所有的文本當做一種字體,;,,一些特殊情況需要單獨處理,,,如,Bank,、,bank。,,(2),去除停用詞,停用詞,:,,攜帶信息很少、沒有區(qū)分力度的詞。,,停用詞由于出現(xiàn)太多
22、次，因此其攜帶的語義信息性少，需要從索引項中除去。,,冠詞、前置詞和連詞一般都是停用詞的候選詞語,,清除停用詞可以縮減索引結構的大??；,,因此可以擴大停用詞包含的范圍，從冠詞、前置詞、連詞擴大到一些動詞、副詞和形容詞。,,弊端,:,可能會降低召回率。,(3),詞根還原,這個專指英文文本,.,,定義：就是一個單詞去除詞組后剩下的部分。,,優(yōu)點：有助于縮小索引結構，提高檢索性能。,,流行算法：,Porter,算法。,（,4,）索引項選擇,自然語言組成的文本：,,,由名詞、代詞、冠詞、動詞、形容詞、副詞和連詞等構成。,,語義信息都由名詞攜帶。,（,5,）辭典,定義,：包括一個預先編譯的各學科中的重要
23、詞語表以及表中每個詞語的一些相關詞語的一些相關詞語。,,目的,：,,提供索引的搜索的標準詞典；,,幫助用戶更好地進行查詢變換；,,提供分類層次從而可以根據(jù)用戶的要求擴展或縮小當前的查詢請求。,（,6,）中文分詞,英文是以,“,詞,”,為單位的，以空格隔開；,,中文是以,“,字,”,為單位的，句子中所有的字連起來才能描述一個意思。,,現(xiàn)有的分詞算法：,,基于字符串匹配的分詞方法,,基于理解的分詞方法,,基于統(tǒng)計的分詞方法,3.3.2,文本特性,熵：,,定義：表示信息含量。如果字母表中有,σ,個符號，在一個文本中每一個符號出現(xiàn)的概率為,P,i,，,那么這個文本的熵的定義為：,,,文本：由字母表中一
24、個有限的符號集合中的元素構成的。,,,可把這些符號分成兩個子集：,,一類是區(qū)分詞語的符號；,,另一類是構成詞語的符號。,,中文通常所采用方法：漢語自動標引方法，如,,詞典標引法,,切分標記法,,語法分析標引法,,漢語自動標引專家系統(tǒng),,單漢字標引法,,,西文所采用的方法：,,有限狀態(tài)機模型,,語法模型,,五個待處理問題：,,為自然語言選擇一個合適的語法模型是一個尚未解決的問題；,,不同的詞語在每篇文檔中具體是怎么分布的。,,文檔集中出現(xiàn)的詞語的分布情況；,,一篇文檔中到底有多少個不同的詞語；,,單詞的平均長度。,3.3.3,文本聚類,聚類的基本想法：,,將相似的文檔聚合在一起形成一個類別，該想
25、法基于聚類假設：緊密關聯(lián)的文檔往往與相同的查詢要求有關。,,適應范圍：文檔、索引項,,作用：,,對文檔而言：加速搜索過程；,,對索引項而言：自動構造詞典、降維。,,過程：生成聚類、聚類搜索,,聚類方法：,,基于文檔間相似矩陣穩(wěn)定性方法；,,更有效的直接來自文檔向量的選代方法,,但這兩種方法不可以同時滿足穩(wěn)定性準則和高效性準則。,,,聚類檢索：,,經(jīng)典的方法：夾角余弦函數(shù)。,3.4,文本索引,,,outline,經(jīng)典文本檢索方法,,菊池敏典算法（順排文檔）,,福島算法（倒排文檔）,,加權檢索,,文本預處理,------,分詞、詞干,,索引和排序,,幾個概念：,索引：,,在文本之上建立一個數(shù)據(jù)結構
26、，稱為此數(shù)據(jù)結構的索引。,,作用：,,加速文檔搜索，當文檔集很大而且基本保持不變的時候，構建和維護一個文檔集的索引是非常必要的。,,三種主要的索引技術：,,倒排表,,后綴序列,,簽名文件,,,字符樹,:,,又稱數(shù)字搜索樹,,,是一棵多叉樹,,,可以存儲字符串集合并且可以在與其長度相同的線性時間內(nèi)檢索到所有的字符串,.,,每個字符串的最后都要加上一個,特殊的字符,以確保這個字符串,不是其他字符串的前綴,.,樹中的每一條邊都有一個標簽,.,,建立,詞表字符樹,示例,(,見,P71,),3.4.1,：菊池敏典算法,---,信息檢索系統(tǒng)的構成,信息采集子系統(tǒng),,廣泛地、定期地采集各種信息源；,,標引子
27、系統(tǒng),,人工或者自動標引；,,建庫子系統(tǒng),,數(shù)據(jù)錄入、錯誤檢查與處理、數(shù)據(jù)格式轉換、生成各種文檔。僅提供,定題服務,，則建立能支持順序檢索的,順排文檔,。若需支持,回溯檢索,，則建立各種,倒排文檔,。,,詞表管理子系統(tǒng),,管理維護系統(tǒng)中已有的詞表，使它與標引、建庫等子系統(tǒng)相連接，支持用戶查詢操作。,,,用戶接口子系統(tǒng),,由用戶模型、信息顯示、命令語言和反饋機制,,提問處理子系統(tǒng),,（,1,）接收提問,,（,2,）提問校驗,,（,3,）提問加工，指對原提問式進行解釋性或編譯性的加工，生成便于機器處理的目標提問式。加工方式常有順序檢索中的表展開法、倒排檢索分別以菊池敏典法和福島法,,（,4,）檢索
28、,展開表概念,1968,年，日本科技情報中心的菊池敏典研究出脫機批處理檢索處理檢索信息的表展開法（菊池敏典算法）。,,屬于傳統(tǒng)的,布爾邏輯檢索模型,，基于文本信息檢索，主要適用于二次文獻信息的檢索。,,主要思想：將代表用戶的,邏輯提問式,轉換成表的形式。該表規(guī)定了表的內(nèi)容走向和是否命中的判斷，檢索時根據(jù)表的走向及其相關信息來判斷每條記錄是否命中。,表展開法的概念,用表來表示邏輯提問式，要求：,,能夠充分體現(xiàn)提問式中復雜的邏輯運算關系,,能夠準確反映每個檢索詞的檢索匹配要求,,能夠準確給出記錄最終的命中與否,（,1,）,展開表的結構,,表展開法是將每個邏輯提問式轉換成一個展開表，,,如果有,N,
29、個提問式就可做,N,個展開表。展開表由地址、檢索詞、檢索詞號、,AFD,、,NFD,、層級值等欄構成，其一般格式如下：,地址,AFD,NFD,級位,檢索詞,字段號,截斷說明,比較條件,權值,有效位,檢索詞標識,,,,,,,,,,,,1),地址：表示檢索詞地址；,2)AFD,：匹配成功時轉向地址；,3)NFD,：匹配不成功時轉向地址；,4),級位：據(jù)檢索詞的運算符等給出處理的優(yōu)先級；,5),字段號：表示檢索詞屬于哪個字段；,650,表示關鍵詞字段；,260,表示出版年 代字段；,6）,截斷說明：表示檢索詞截斷的類型，通常“１、２、３、４”＝｛不截斷、后截斷、前后截斷、前截斷｝；,7）,比較條件：
30、,{,１，２，３，４｝＝｛等于，不等于，大于，小于｝；,8）,權值：在進行加權檢索時，指定的檢索詞的權值；,9),有效位：檢索詞字符數(shù)。,,,1.,若是,檢索詞,，則將對應的檢索詞有關內(nèi)容存入展開表內(nèi),,,并記下該詞在表中的地址。,6.,若是,“,·”,為結束標志，則將最后一檢索詞的,AFD,欄放入“命中”，,NFD,欄放入“不命中”,2.,若是,“,+”,，則將其前一檢索詞的,NFD,欄放入后一詞的地址,3.,若是,“,﹡”,，則將其左邊檢索詞的,AFD,欄放入后一詞的地址,4.,若是,“（”,，則將其后的檢索詞所在行的級位欄值加,1,；若有多個“（”則級位值連續(xù)加,1,，級位初值為,0,5
31、.,若是,“）”,，則將其緊前一個檢索詞所在行的級位欄值減,1,；若有多個“）”則級位值連續(xù)減,1,,,,,,,前處理算法,（2,）,展開表的生成,分為兩個過程：前處理算法和后處理算法,后處理算法：,主要任務：,,填滿整個表的空白單元，填表的依據(jù)是,比較,表中,“,級位,”,欄的前、后級位值，填表的順序是從下向上，直至表的頂部，從而得到一個完整的提問展開表。,展開表的生成,,后處理,,算法,A,、大于,,,,,右括號,B,、等于,C,、小于,,,,,左括號,,1,）若,NFD,空,,,,*,運算,,,應把上一行,NFD,,內(nèi)容復制到當前行,NFD,；,2,）若,AFD,空,,,,+,運算,,,
32、應把上一行,AFD,,內(nèi)容復制到當前行,AFD,；,,1,）若,NFD,空,,,則與,A-1,）處理相同。,2,）若,AFD,空,,,,+,運算,,,惟有遇到閉括號或,,結束時，把當前行檢索詞后的第一個右括,,號或結束號前的檢索詞所在行的,AFD,欄內(nèi),,容復制到當前行的,AFD,欄；,,1,）若,NFD,空,,,則把前面處理過的第一個與當,,前行級位值相等或小那一行的,NFD,復制到當,,前行的,NFD,欄,；,2,）若,AFD,空,,,則需要把當前行緊后一個復合,,檢索項中最后一個檢索詞所在行的,AFD,內(nèi)容,,復制到當前行的,AFD,欄；,例,1,：,展開表的生成：邏輯提問式,(A+B)
33、﹡(C+D)﹡E,的展開表形式,級位,條件滿足指向,檢索詞,,代號,地址,條件不滿足指向,字段號,比較條件,檢索詞,ABCDE,12345,3355,10100,命中,不命中,不命中,不命中,2,4,(,略,),若干邏輯提問式轉換為展開表后，將這些展開表匯集到一起，,構造用戶提問檔集合,，可更方便地進行順排文檔的檢索。,例,2,：,表展開法的應用,,,((A+B+C)﹡D+E) ﹡F,下表為邏輯提問式的展開表生成過程。,,,級位,條件滿足指向,檢索詞代號,地址,條件不滿足指向,字段號,比較條件,檢索詞,A,,B,,C,,D,,E,,F,1,,2,,3,,4,,5,,6,4,,4,,4,,6,,
34、6,2,,2,,1,,1,,0,,0,命中,不命中,不命中,2,,3,,5,,5,(,略,),按算法填寫的順序應如中,）,序號填,箭頭指向,為后處理算法推導過程,2,）,1,）,4,）,3,）,6,）,5,）,7,）,10,）,9,）,8,）,12,）,11,）,遇右括號，級位減,1,前有兩個左括號,,,,,,例,3:,表展開法的應用,,下表為邏輯提問式,A﹡(B+C)+(D﹡(E+F+G)),的展開表生成過程。,,,級位,條件滿足指向,檢索詞代號,地址,條件不滿足指向,字段號,比較條件,檢索詞,A,,B,,C,,D,,E,,F,,G,1,,2,,3,,4,,5,,6,,7,2,,命中,,命中
35、,,5,,命中,,7,,命中,0,,1,,0,,1,,2,,2,,0,4,,3,,4,,不命中,,6,,不命中,,不命中,(,略,),1,）,2,）,3,）,4,）,5,）,6,）,7,）,8,）,9,）,10,）,11,）,12,）,13,）,14,）,,,,,,展開表法的檢索,生成的展開表為若干邏輯提問式的集合，形成展開表提問文檔；,,檢索時，提問展開表調(diào)入內(nèi)存,,查比時，每從數(shù)據(jù)庫中讀取一條記錄，生成一個由可檢索項組成的檢索標識表，每一檢索項查對展開表，并對命中的檢索詞做上標記,,所有檢索項查詢完畢，分析提問是否命中，命中者在相應的提問號下記下記錄號,,再取下一記錄比對,菊池敏典算法,-
36、--,優(yōu)點,以提問中的提問條件項為檢索查比的主動項,,由于每個獨立的提問所涉及的提問條件項的屬性范圍都不太多，因此，檢索時，在文獻中查找的范圍只需局限于單個提問所涉及的那一小部分（如關鍵詞、標題等等，具體的提問條件項只在其本身屬性范圍內(nèi)查找）。,,菊池敏典算法用便于查找的提問展開表代替了原來的提問邏輯式,,電腦可以順著提問的思路查閱有關文獻。一旦提問要求得到判定性的答案后，則可立即停止關于其他提問項的查比，而不一定要求將提問中所有提問條件項都一一查比。,,菊池敏典算法的實質(zhì),：,,1,）凡是可不查閱的文獻屬性一定不查；,,2）,凡是可不再查比的提問條件項一定不再查；,,3）,節(jié)約了機器的查比時
37、間，使菊池敏典算法在早期開發(fā)情報檢索自動化系統(tǒng)得到相當?shù)闹匾暭皬V泛的應用。,,3.4.2,：福島算法,---,倒排文檔的建立,倒排文檔相對順排文檔而言，是將順排文檔中的可檢索字段取出，按照一定的規(guī)則排序，歸并相同詞匯，并把在順排文檔中的記錄號集合賦予其后形成的文檔，可看成為輔助文檔。,,倒排文檔將兩個檢索詞的邏輯運算轉換成了兩個檢索詞之間的記錄號集合的運算。目前最常見的倒排文檔檢索為逆波蘭展開法。,,倒排文檔的組成元素主要包括：,,關鍵字：作者，主題詞，分類號,,目長：含有該關鍵字記錄的條數(shù),,記錄號集合：所有與該關鍵字有關的記錄號,1、,倒排文檔的結構,倒排文檔可視為主文檔的輔助索引，它從不
38、同的角度提供了對主文檔的快速查詢，一般來說，不同屬性的數(shù)據(jù)構成不同的倒排索引文檔，如下給出了,10,篇文獻（表,1,）的作者倒排文檔（表,2,）和標引詞倒排文檔（表,3,）,表,1：,文獻及其部分屬性舉例,記錄號,篇名,作者,標引詞,1,知識管理與企業(yè)管理信息系統(tǒng)建設,A,知識管理、管理信息系統(tǒng)、企業(yè)信息化,2,論知識鏈與知識管理,B,知識管理、知識鏈、學習型組織、知識創(chuàng)新,3,芻議知識管理及其體系框架,C,知識管理、知識創(chuàng)新、知識共享,4,知識管理的組織基礎,A,知識管理、學習型組織,5,論技術創(chuàng)新的知識空間,C,技術創(chuàng)新、知識空間、知識創(chuàng)新,6,建立企業(yè)競爭性的信息結構,A,企業(yè)信息化、信
39、息結構、競爭情報,7,知識管理在企業(yè)競爭情報研究中的應用,B,知識管理、競爭情報、知識創(chuàng)新,8,管理信息系統(tǒng)中的文化行為研究,B,管理信息系統(tǒng)、企業(yè)文化,9,企業(yè)競爭情報管理系統(tǒng)的構建研究,C,管理信息系統(tǒng)、競爭情報,10,企業(yè)知識管理主體研究,C,知識管理、企業(yè)文化、管理創(chuàng)新,表,2：,作者索引,作者,目長,記錄號集合,A,3,1；4；6,B,3,2；7；8,C,4,3；5；9；10,表,3：,關鍵詞索引,標引詞,目長,記錄號集合,管理創(chuàng)新,1,10,管理信息系統(tǒng),3,1；8；9,技術創(chuàng)新,1,5,競爭情報,3,6；7；9,企業(yè)文化,2,8；9,企業(yè)信息化,2,1；6,信息結構,1,6,學習
40、型組織,2,2；4,知識創(chuàng)新,4,2；3；5；7,知識共享,1,3,知識管理,6,1；2；3；4；7；10,知識空間,1,5,知識鏈,1,2,,由表,1、,表,2、,表,3,可以看出，倒排文檔主要三個字段的作用：,,作者或標引詞字段,：主要為快速檢索提供索引；,,記錄號集合,：主要作用是為了在檢索中進行集合運算和對命中結果的直接調(diào)用；,,目長,：在檢索中起輔助作用。,2、,倒排文檔的建立,由順排文檔構造倒排文檔需要經(jīng)過抽詞、排序、歸并和組織等過程，具體實現(xiàn)步驟如下：,,選擇需要做索引的字段屬性（如作者、關鍵詞等），抽出其中的內(nèi)容，并在其后附上其記錄號；,,對抽出的內(nèi)容進行排序，使之便于歸并相同
41、內(nèi)容；,,對相同內(nèi)容進行歸并，把合并后的內(nèi)容放入倒排文檔的主鍵字段（如標引詞、作者等），統(tǒng)計每一數(shù)據(jù)的頻次作為目長，把每一內(nèi)容后的記錄號順序放在記錄號集合字段。,,在建立倒排文檔的過程中還有,兩個問題,需要注意：,,上述的過程是批處理的過程，在實際的數(shù)據(jù)庫建設中是不斷追加數(shù)據(jù)的過程。因此，倒排文檔的建立應具有及時更新的功能，所以對批處理創(chuàng)建倒排文檔的過程需要更改：,,從增加的記錄中取出倒排索引的字段內(nèi)容；,,查詢倒排索引，若命中，則將該記錄的目長加,1，,并將增加記錄的記錄號追加進倒排文檔的記錄號集合字段；若沒命中，則將該字段內(nèi)容以及記錄號增加到倒排文檔之中，并將目長置,1。,,由于每一個關鍵
42、字所對應的記錄數(shù)相差很大，因此對于只能處理定長字段的數(shù)據(jù)庫或文件系統(tǒng)，需建立溢出文檔來解決不定長問題,2.1:,邏輯提問式的轉換,1929,年波蘭的邏輯學家盧卡西維茲提出將運算符放在運算項后面的邏輯表達式，又稱,“,逆波蘭表達式,”。,,日本的福島首先將逆波蘭表達式應用于情報檢索，故又稱,“,福島方法,”。,,例如，將邏輯提問式,“A*（B+C）+D”,轉換為逆波蘭式,,ABC+*D+,,邏輯提問式中運算符優(yōu)先次序：,(),-,*,+,,逆波蘭表達式中的次序,: (),+,*,-,,中綴法,前綴法,后綴法,A+b,+ab,Ab+,A+b*c,+a*bc,Abc*+,(a+b)*c,*+abc
43、,Ab+c*,A
44、到高于棧頂運算符,(a),遇檢索詞,,,將其置入檢索詞表中,,,詞表地址送入逆波蘭輸出區(qū),(d),遇”,)”,,則將棧內(nèi)與其對應的左括號之間的運算符盤出,,,送入逆波蘭輸出區(qū),.,清除這對括號,(e),遇”,·,”,,棧內(nèi)算子依次出棧送入逆波蘭輸出區(qū),,轉換規(guī)則注意事項：,在轉換過程中應注意兩點：,,算子棧的元素后進先出，轉換結束其算子棧為空；,,逆波蘭輸出區(qū)的算子特征為,1，,檢索詞特征為,0。,(A+B) * (C+D)+E,．的逆波蘭變換處理示例：,(A+B)*(C+D)+E,．,地址 檢索詞,＋,＋,（,*,＋,0,（,特征 內(nèi)容,0,,0,,1,,0,,0,,1,,1,,0,
45、,1,,0,或,1,01,,02,,+,,03,,04,,+,,*,,05,,+,,·,01,,02,,03,,04,,05,,…,A,,B,,C,,D,,E,,…,檢索詞表,詞表地址,算子,逆波蘭輸出區(qū),算子棧,區(qū)分運算項還是運算符,課堂小練習：,給出邏輯提問式（,A+B,）,*（C+EF）,逆波蘭轉換示意圖。,（二）檢索指令表的生成,,邏輯提問式的逆波蘭表達式,并不能,直接用于檢索，需要將其轉換成一組檢索指令才能進行檢索操作。操作指令表由四列元素組成：第一列為操作碼，指定,本行操作類型,，如,輸入、運算、轉儲操作,等；以后三列為操作數(shù)屬性，根據(jù)操作碼來決定三個操作數(shù)之間的關系。,檢索指令操
46、作碼（,ON,）,第一操作數(shù),,（,AD1,）,第二操作數(shù),,（,AD2,）,第三操作數(shù),,（,AD3,）,１,０３,,２,表,4:,檢索詞操作指令表,語義：檢索詞表的０３號關鍵詞的記錄號集合,存放,在第２工作區(qū),檢索指令操作碼（,ON,）,第一操作數(shù),,（,AD1,）,第二操作數(shù),,（,AD2,）,第三操作數(shù),,（,AD3,）,４,３,４,１,表,5.,２ 運算操作指令表,語義,：第３、４工作區(qū)的記錄號集合進行,“,與,”,運算，其結果存放在第１,,工作區(qū)。若為運算符，操作碼為,“,３／＋,”,、,“,４／＊,”,、,“,５／－,”,。,檢索指令操作碼（,ON,）,第一操作數(shù),,（,AD1,
47、）,第二操作數(shù),,（,AD2,）,第三操作數(shù),,（,AD3,）,２,４,,７,表,6.,３ 轉儲操作指令表,語義,：結束行的操作碼置２，表示轉儲操作，第一操作數(shù)放檢索結果占,,用的工作區(qū)，表示把檢索的最終結果轉移到第７工作區(qū)。,檢索指令操作碼（,ON,）,第一操作數(shù),,（,AD1,）,第二操作數(shù),,（,AD2,）,第三操作數(shù),,（,AD3,）,０,,,,表,7.,４ 轉儲操作指令表,語義,：轉儲操作結束，將最后一行的操作碼置為０，表示終,,止操作，其他操作數(shù)為空。,,福島方法設定工作區(qū)為,7,個，工作區(qū)的使用從前向后遇空閑即分配，從而保證了,7,個工作區(qū)能夠滿足檢索過程的需要。,,在工作區(qū)狀態(tài)
48、表中的兩列表示：,,第一列：,該工作區(qū)是否被占用,。,,第二列：,該工作區(qū)的運算次序,。,,生成檢索指令表，要從逆波蘭輸出區(qū)的第一行開始逐行掃描而生成檢索指令表，中間有工作區(qū)狀態(tài)表作為輔助表。,,,檢索指令表生成過程示例,檢索指令表生成過程示例,,,檢索指令表生成過程示例,,（四）檢索實施,檢索指令表生成結束才真正進入實際檢索處理，整個檢索過程主要依賴檢索詞表和檢索操作指令表，執(zhí)行步驟按照檢索指令表的順序進行，具體操作如下：,,若操作碼為,“1”，,應進行查找和輸入操作。將該行第一操作數(shù)中數(shù)據(jù)取出，根據(jù)其在檢索詞表中獲得檢索詞，以該檢索詞去查倒排索引文檔，得到的記錄號集合存儲到第三操作數(shù)指定的
49、工作區(qū)中。,,若操作碼為,“2”，,說明應進行轉儲操作。需將第一操作數(shù)指定的工作區(qū)中的記錄號集合存儲到第三操作數(shù)指定的工作區(qū)中；,,若操作碼大于,“2”，,表示需進行邏輯運算操作，應將第一、二操作數(shù)指定的工作區(qū)中的記錄號集合，按操作碼代號進行響應的邏輯運算，運算結果存放到第三操作數(shù)指定的工作中。,,若操作碼為,“0”，,則表示該邏輯提問式檢索結束，需根據(jù)第,7,工作區(qū)的內(nèi)容（命中結果）到主文檔中調(diào)出命中記錄，顯示或打印給用戶。,3.5,相關反饋和查詢擴展,,由于缺少對整個文檔集的了解，很多用戶提交的查詢不能完全表達他們的檢索目的，就得不到理想的檢索答案，解決辦法：,,初次查詢的結果并不作為檢索
50、的答案，而是一個中間結果：,,根據(jù)這個結果得到用戶的相關反饋來進行查詢重寫；,,根據(jù)這個結果進行查詢擴展,1、,相關反饋,,3.6,檢索評測,,,系統(tǒng)性能評測,評測標準,：時間和空間，響應時間越短，所需空間越小，就認為這個系統(tǒng)的性能越好。,,最常用的,檢索評測方法,：召回率和查準率,,,召回率,=|R,a,|/R,,,查準率,=|R,a,|/R,,小結,:,三種經(jīng)典的,信息檢索,模型,:,布爾模型、向量模型和概率模型，其中最為實用有效的是向量模型,,文本預處理，并介紹了文本的特性、文本聚類的方法及信息檢索中的應用。,,三種索引方法的構造和對應的查詢,,評測方法,課后習題,P91:,,3、4,、,5、9、14、15,,
第三章 文本處理與信息檢索
