1、第第 3 章章 文本信息檢索文本信息檢索技術(shù)與方法技術(shù)與方法文本是一種極其重要的信息和知識(shí)交流媒介。從遠(yuǎn)古時(shí)期的象形文字開始，人類社會(huì)已發(fā)展和創(chuàng)造了各種形式的文字和語言系統(tǒng)。自計(jì)算機(jī)誕生以來，各種文本數(shù)據(jù)一直是其處理和加工的主要對(duì)象，信息檢索領(lǐng)域也不例外。3.1 文本信息概述文本信息概述l3.1.1 文本信息的基本知識(shí)l一、文本的概念l文本文本是基于一定的語言符號(hào)系統(tǒng)而形成的一個(gè)有限符號(hào)序列l(wèi)符號(hào)符號(hào)是不能再分割的記號(hào)單位，如數(shù)字符號(hào)、字母符號(hào)、標(biāo)點(diǎn)符號(hào)等3.1 文本信息概述文本信息概述l符號(hào)表符號(hào)表是有限個(gè)任意符號(hào)組成的非空集合，符號(hào)表中的元素即是“符號(hào)”，如由所有漢字組成的集合，由所有英語

2、詞匯組成的集合等l符號(hào)串符號(hào)串是指由符號(hào)表中的符號(hào)組成的長(zhǎng)度有限的序列。例如，如果符號(hào)表是漢語中所有詞匯的集合，那么，任何漢語句子和短語都是該符號(hào)表上的符號(hào)串l這樣我們就可以將文本文本定義為某符號(hào)表上的符號(hào)串的集合二、文本的信息量二、文本的信息量l假設(shè)在某一給定的文本片段中共出現(xiàn)有個(gè)符號(hào)，而在該文本段中每個(gè)符號(hào)的出現(xiàn)概率為pi(i=1,2, ),則該段文本的信息熵定義為： 熵的單位是比特l例：在某一文本片段中，取=16，每個(gè)符號(hào)以等概率方式出現(xiàn)，則該段文本的信息熵為4比特21 logiiiEpp 三、文本文檔的格式與編碼三、文本文檔的格式與編碼l當(dāng)把文本信息輸入、存放在計(jì)算機(jī)存儲(chǔ)器中，通常需要

3、結(jié)合具體應(yīng)用任務(wù)來指定一定的文檔格式。l常用的文檔格式：TXT、RTF、DOC、PDF、MIME、ARJ、ZIP3.1.2、自然語言文本中詞匯的頻率、自然語言文本中詞匯的頻率與數(shù)量分布規(guī)律與數(shù)量分布規(guī)律l在基于某種自然語言系統(tǒng)的文本文檔集合中，詞匯的出現(xiàn)頻率和數(shù)量是有一定規(guī)律的。l一、詞匯的頻率與齊普夫分布模型 詞的出現(xiàn)頻率和按照頻率高低降序排列后產(chǎn)生的詞的序號(hào)是一個(gè)頻率詞典的兩個(gè)最基本的數(shù)量指標(biāo)。齊普夫分布模型齊普夫分布模型l齊普夫定律即在一個(gè)給定的文本文檔集合中，如果將所有單詞按照其出現(xiàn)頻率遞減排列，并用自然數(shù)依次給單詞賦予等級(jí)序號(hào)1、2、3、，那么，單詞頻率與其等級(jí)序號(hào)的乘積為一個(gè)常數(shù)，

4、其數(shù)學(xué)表達(dá)式為 fr = C 或者 f = C / r 上式中f為某個(gè)單詞的出現(xiàn)頻率，r為該單詞的等級(jí)序號(hào)，C為常數(shù)。齊普夫分布模型齊普夫分布模型詞頻的齊普夫分布模型齊普夫分布模型齊普夫分布模型l齊普夫定律的更普遍形式 或者上式中的參數(shù) 因?qū)W科樣本等不同而有所變化，其取值范圍約在1.5-2之間l對(duì)于文本信息檢索來說，齊普夫定律在詞表編制、自動(dòng)標(biāo)引、倒排文檔組織等方面有比較重要的理論指導(dǎo)價(jià)值frC/fC r二、詞匯的數(shù)量與二、詞匯的數(shù)量與Heaps分布模型分布模型l在文本文檔集合中，不僅詞匯的頻率分布具有顯著的規(guī)律性，詞匯的數(shù)量及其增長(zhǎng)變化也表現(xiàn)出一定的規(guī)律性。l為了預(yù)測(cè)自然語言文本中詞匯的增長(zhǎng)

5、變化，研究人員提出了Heaps模型l該模型認(rèn)為，在一個(gè)長(zhǎng)度為n個(gè)詞的文本片段中，它的詞匯量V與n之間具有以下關(guān)系lK通常取10-100， 則是小于1的正實(shí)數(shù)VK n二、詞匯的數(shù)量與二、詞匯的數(shù)量與Heaps分布模型分布模型詞匯量的Heaps分布模型3.2、布爾檢索、布爾檢索l布爾檢索主要以索引文檔為基礎(chǔ)，通過布爾邏輯運(yùn)算符對(duì)檢索詞進(jìn)行組配，形成檢索提問式，進(jìn)而以此提問式為匹配依據(jù)完成對(duì)索引文檔的匹配處理并獲取查詢結(jié)果3.2.1 布爾邏輯運(yùn)算符號(hào)及其使用布爾邏輯運(yùn)算符號(hào)及其使用l一、布爾邏輯運(yùn)算符及其運(yùn)算含義 布爾邏輯運(yùn)算符是構(gòu)造用戶檢索提問式的一組主要連接組配符號(hào)，主要包括：邏輯或（OR）邏輯

6、與（AND）邏輯非（NOT）邏輯或（邏輯或（OROR）l也稱為“析取聯(lián)接詞”，形式上還可以寫作“+”l檢索詞A和檢索詞B若用“OR”組配，則檢索提問式可表示為l A OR B 或者 A + B邏輯或（邏輯或（OROR） 邏輯或（XOR）運(yùn)算的文氏圖表示邏輯或（邏輯或（OROR）l例如，研究網(wǎng)絡(luò)搜索引擎的用戶，對(duì)有關(guān)Google、Excite、百度的文獻(xiàn)信息都比較感興趣，就可以使用“OR”構(gòu)造如下的提問檢索式： Google OR Excite OR 百度邏輯或（邏輯或（OROR）l對(duì)于檢索提問式“A OR B”, 假設(shè)檢索詞A的所有命中文檔有m篇，檢索詞B的所有命中文檔有n篇，“A OR B”

7、的所有命中文檔有s篇，則：當(dāng)A與B不相關(guān)時(shí)，s = m + n；當(dāng)A與B有一定相關(guān)性時(shí)，s m + n；當(dāng)A與B密切相關(guān)時(shí)，s = Max(m,n)；綜合以上三種情況，有 Max(m,n) s m + n邏輯與（邏輯與（ANDAND）l也稱為“合成聯(lián)接詞”，形式上還可以寫作“*”l檢索詞A和檢索詞B若用“AND”組配，則檢索提問式可表示為l A AND B 或者 A * B邏輯與（邏輯與（ANDAND） 邏輯與（AND）運(yùn)算的文氏圖表示邏輯與（邏輯與（ANDAND）l例如，研究網(wǎng)絡(luò)搜索引擎的用戶，對(duì)同時(shí)出現(xiàn)Google、Excite、百度的文獻(xiàn)信息比較感興趣，就可以使用“AND”構(gòu)造如下的提問

8、檢索式： Google AND Excite AND 百度邏輯與（邏輯與（ANDAND）l對(duì)于檢索提問式“A AND B”, 假設(shè)檢索詞A的所有命中文檔有m篇，檢索詞B的所有命中文檔有n篇，“A AND B”的所有命中文檔有s篇，則：當(dāng)A與B完全無關(guān)時(shí)，s = 0；當(dāng)A與B有一定相關(guān)性時(shí)， 0 s m 或者 0 s n ；當(dāng)A與B密切相關(guān)時(shí)，s = Min(m,n)；綜合以上三種情況，有 0 s Min(m,n)邏輯非（邏輯非（NOTNOT）l也稱為“否定聯(lián)接詞”，形式上還可以寫作“-”l檢索詞A和檢索詞B若用“NOT”組配，則檢索提問式可表示為l A NOT B 或者 A - B邏輯非（邏輯

9、非（NOTNOT） 邏輯非（NOT）運(yùn)算的文氏圖表示邏輯非（邏輯非（NOTNOT）l例如，查找云南大學(xué)的相關(guān)信息，但不想了解云大附中的信息，就可以使用“NOT”構(gòu)造如下的提問檢索式： 云南大學(xué) NOT 云大附中邏輯非（邏輯非（NOTNOT）l對(duì)于檢索提問式“A NOT B”, 假設(shè)檢索詞A的所有命中文檔有m篇，檢索詞B的所有命中文檔有n篇，“A NOT B”的所有命中文檔有s篇，則：當(dāng)A與B完全無關(guān)時(shí)，s = m；當(dāng)A與B有一定相關(guān)性時(shí)，s n時(shí)，則 s = m n，當(dāng)m n, 則 s = 0綜合以上三種情況，有 0 s m布爾邏輯運(yùn)算符的使用說明布爾邏輯運(yùn)算符的使用說明l運(yùn)算規(guī)則同級(jí)運(yùn)算自左

10、向右進(jìn)行布爾運(yùn)算AND和NOT先執(zhí)行，OR次之當(dāng)檢索提問式含有截詞符、位置算符、限制符時(shí)，布爾運(yùn)算最后執(zhí)行先括號(hào)內(nèi)，后括號(hào)外，具有多層括號(hào)時(shí)，按層次從內(nèi)到外逐層進(jìn)行3.2.2 3.2.2 布爾邏輯檢索提問式的變布爾邏輯檢索提問式的變換處理換處理l在以布爾模型為概念基礎(chǔ)的信息檢索系統(tǒng)中，檢索軟件需要對(duì)用戶輸入的布爾邏輯提問式進(jìn)行必要的加工和編輯，以滿足后續(xù)的檢索處理要求。l通常，我們?cè)跁鴮懰阈g(shù)（邏輯）表達(dá)式時(shí)，總是把運(yùn)算符放在兩個(gè)運(yùn)算項(xiàng)的中間，如“A加上B求和，再乘以C”可以寫成(A + B) * C3.2.2 3.2.2 布爾邏輯檢索提問式的變布爾邏輯檢索提問式的變換處理換處理表達(dá)式對(duì)應(yīng)的二叉

11、樹結(jié)構(gòu)示意圖3.2.2 3.2.2 布爾邏輯檢索提問式的變布爾邏輯檢索提問式的變換處理換處理l一般（中綴）表示法 中序遍歷二叉樹: (A + B) * Cl正波蘭（前綴）表示法 前序遍歷二叉樹: * + ABCl逆波蘭（后綴）表示法 后序遍歷二叉樹: AB + C *3.2.2 3.2.2 布爾邏輯檢索提問式的變布爾邏輯檢索提問式的變換處理換處理l例：lA + B * (C + D) 正波蘭表示法：+ A * B + CD 逆波蘭表示法：ABCD + * +l(A + B) * (C + D) 正波蘭表示法：* + AB + CD 逆波蘭表示法：AB + CD + * 3.2.2 3.2.2

12、布爾邏輯檢索提問式的變布爾邏輯檢索提問式的變換處理換處理l準(zhǔn)波蘭變換法 檢索提問式的準(zhǔn)波蘭法處理算法：創(chuàng)建檢索提問式的二叉樹表示比較二叉樹中每一層次上的左、右子樹是否對(duì)稱。如不對(duì)稱，把大的一枝保留或調(diào)到左邊，小的一枝保留或調(diào)到右邊，直到全部節(jié)點(diǎn)的左、右子樹都這樣處理完為止后序遍歷該二叉樹，節(jié)點(diǎn)的輸出序列即為檢索提問式的準(zhǔn)波蘭式3.2.2 3.2.2 布爾邏輯檢索提問式的變布爾邏輯檢索提問式的變換處理換處理l例：lA + B * (C + D)逆波蘭表示法：ABCD + * +準(zhǔn)波蘭表示法：CD+B*A+3.3 3.3 截詞檢索截詞檢索l截詞檢索是基于布爾檢索框架的一種常用聯(lián)機(jī)檢索技術(shù)，尤其是西

13、方語言文本檢索中，更是廣泛使用。西方語言的一個(gè)共同特點(diǎn)是：構(gòu)詞靈活，在詞干上加上不同性質(zhì)的前綴（或后綴），就可以派生出很多新的詞匯。3.3 3.3 截詞檢索截詞檢索l截詞截詞，是指檢索者將檢索詞匯在他認(rèn)為合適的地方截?cái)鄉(xiāng)截詞檢索截詞檢索，是指使用被截?cái)嗟脑~匯進(jìn)行檢索匹配，并認(rèn)為凡滿足這個(gè)詞局部中的所有字符（串）要求的記錄，都為命中結(jié)果l按照截?cái)嗟奈恢?，分為：后截?cái)?、前截?cái)?、中截?cái)鄉(xiāng)按照截?cái)嗟淖址麛?shù)量，分為：有限截?cái)?、無限截?cái)嘁?、后截詞檢索一、后截詞檢索l將截詞符號(hào)置放在一個(gè)字符串右方，以表示其右邊的有限或無限個(gè)字符不影響該字符串的檢索匹配。l例：檢索提問式“brows*”是一個(gè)無限后截詞的例子

14、，可能檢索出來的詞匯有 browse browser browsable browsers browsed browsing 一、后截詞檢索一、后截詞檢索l不難看出，后截詞檢索具有隱含的“邏輯或”（OR）運(yùn)算特性，上例中的檢索提問式等價(jià)于下面的檢索提問式：browse OR browser OR browsers OR browsing 一、后截詞檢索一、后截詞檢索l例：檢索提問式“acid?”是一個(gè)有限后截詞的例子，可能檢索出來的詞匯有 acid acidic acids l但不能檢出下列詞匯 acidicity acidify acidity 一、后截詞檢索一、后截詞檢索l后截詞檢索主要應(yīng)

15、用與以下四種情形：詞的單復(fù)數(shù)，如：book?, potato?年代，如：199？， 19？；作者，如 Lancaster *同根詞，如：biolog*, physic*l注意：使用后截詞檢索有可能檢出無關(guān)詞匯，Google就不提供截詞檢索功能二、前截詞檢索二、前截詞檢索l將截詞符號(hào)置放在一個(gè)字符串左方，以表示其左的有限或無限個(gè)字符不影響該字符串的檢索匹配。l例：檢索提問式“*magnetic”是一個(gè)無限前截詞的例子，可能檢索出來的詞匯有 magnetic electromagnetic(電磁的) paramagnetic(順磁的) thermomagnetic（熱磁的） 二、前截詞檢索二、前截

16、詞檢索l前截詞檢索和后截詞檢索一樣，也存在隱含的“邏輯或”（OR）運(yùn)算特性l在有些情況下，前后截詞檢索可以結(jié)合起來使用l由于技術(shù)實(shí)現(xiàn)上比較復(fù)雜，目前檢索系統(tǒng)中前截詞檢索還比較少見三、中截詞檢索三、中截詞檢索l這種截詞方式是把截詞符號(hào)放置在一個(gè)檢索詞的中間，而不是左右兩側(cè)。中截詞檢索一般只允許檢索詞的有限截?cái)鄉(xiāng)中截詞檢索主要應(yīng)用于以下兩種情形：英語單詞的英美拼寫方式不同： defence、defense defen?edefen?e；sulphur、sulfur sul?ursul?ur某些詞在元音位置上出現(xiàn)單復(fù)數(shù)的不同 woman、women wom?nwom?n3.4 3.4 限制檢索限制檢

17、索l在文本檢索系統(tǒng)中，為了提高或保證檢索的準(zhǔn)確率，常常提供一些縮小或約束檢索結(jié)果的檢索技術(shù)，稱之為“限制檢索”。限制檢索一般仍需要建立在布爾檢索的基礎(chǔ)之上，因此可以把它看做是一種受限的布爾檢索3.4 3.4 限制檢索限制檢索l限制檢索的方式很多，其中最主要的限制技術(shù)是通過限制檢索詞在命中結(jié)果記錄中的出現(xiàn)位置（主要指文本數(shù)據(jù)庫(kù)記錄的不同字段位置）來實(shí)現(xiàn)的，這種限制檢索也因此被稱為“字段檢索”l具體指定檢索字段的方式有兩種：菜單選擇方式檢索命令方式3.4 3.4 限制檢索限制檢索l菜單選擇方式3.4 3.4 限制檢索限制檢索l檢索命令方式例: overload wn AB(seatbelt* OR

18、 (seat belt*) wn TI 用法:Term wn code3.4 3.4 限制檢索限制檢索l除字段檢索外，對(duì)文本信息進(jìn)行限制檢索的另一種形式是“二次檢索”，即提供用戶在檢索結(jié)果中進(jìn)行再次檢索，l位置檢索位置檢索是一類針對(duì)自然語言文本中檢索詞與檢索詞之間特定位置關(guān)系而進(jìn)行的檢索匹配技術(shù)。位置檢索允許用戶使用自然語言作為檢索入口，并可深入到原文的章、節(jié)、段、句等文本范圍內(nèi)進(jìn)行信息的查找和匹配l因此這種檢索技術(shù)可以顯著提高文本信息的檢索精度，改善布爾檢索等既有技術(shù)特定信息的篩選能力3.5 位置檢索位置檢索l目前，聯(lián)機(jī)檢索系統(tǒng)中提供的位置檢索方法已經(jīng)非常豐富多樣。總結(jié)起來看，我們可以將這些

19、位置檢索方法劃分為以下不同類型:鄰接檢索同句檢索同字段檢索同記錄檢索一、一、鄰接檢索鄰接檢索l鄰接檢索是一種對(duì)檢索詞之間相互位置關(guān)系要求最為嚴(yán)格的位置檢索方式。一般地，鄰接檢索需要通過專門的位置運(yùn)算符來規(guī)定檢索提問式中的檢索詞在檢索結(jié)果中出現(xiàn)是應(yīng)滿足的相對(duì)位置要求。l在鄰接檢索檢索中，經(jīng)常使用的位置運(yùn)算符有(W)與(nW)(N)與(nN)一、一、鄰接檢索鄰接檢索l(1) (W)與(nW)l(W)算符的運(yùn)算含義是：在檢索提問式中，它所連接的兩個(gè)檢索詞必須在文本中按照前后順序緊挨著出現(xiàn)，兩個(gè)檢索詞之間除可以有一個(gè)空格、一個(gè)標(biāo)點(diǎn)符號(hào)和一個(gè)連字符外，不得夾有其他任何其他單詞、字母或漢字。l(nW)算符

20、是從(W)算符引申出來的，允許在連接的兩個(gè)檢索詞之間最多夾入n個(gè)其他單詞一、一、鄰接檢索鄰接檢索l例1：對(duì)于檢索提問式“digital(W)library”來說，可以查找出在文獻(xiàn)中出現(xiàn)“digital library”的相關(guān)資料l例2：對(duì)于檢索提問式“l(fā)arge(W)scale(W) integrated(W)circuit”來說，則可以檢索出含有“l(fā)arge scale integrated circuit”的資料l例3：對(duì)于檢索提問式“云南(3W)大學(xué)”,則在檢索結(jié)果中，將會(huì)出現(xiàn)包含“云南大學(xué)”、“云南師范大學(xué)”、“位于云南的一些大學(xué)”等內(nèi)容的相關(guān)信息一、一、鄰接檢索鄰接檢索l(2) (N)與(nN)l(N)算符的運(yùn)算含義是：在檢索提問式中，它所連接的兩個(gè)檢索詞必須在文本中緊密相連著出現(xiàn)，兩個(gè)檢索詞之間除可以有一個(gè)空格、一個(gè)標(biāo)點(diǎn)符號(hào)和一個(gè)連字符外，不得夾有其他任何其他單詞、字母或漢字。l它與(W)的區(qū)別是，(N)算符兩側(cè)的檢索詞出現(xiàn)順序可以顛倒l(nN)算符是從(N)算符引申出來的，允許在連接的兩個(gè)檢索詞之間最多夾入n個(gè)其他單詞一、一、鄰接檢索鄰接檢索l例4：對(duì)于檢索提問式“money(N)supply”的檢索結(jié)果中，將會(huì)包括含有“money supply”和“sup