基于文本的索引構(gòu)建技術(shù)

1、第三章 基于文本的索引構(gòu)建技術(shù) 2/20本章內(nèi)容本章內(nèi)容順序文檔索引基于內(nèi)存單次掃描的索引構(gòu)建技術(shù)基于塊的排序索引技術(shù)本章小結(jié)倒排文檔索引3/20概要概要概要基于文本的檢索技術(shù)信息檢索技術(shù)基于內(nèi)容的檢索技術(shù)4/20概要概要概要 順排文檔把記錄按照一定順序完整地組織起來 如：物品數(shù)據(jù)庫依據(jù)物品記錄號順序進(jìn)行建立。順排文檔（Sequential File） 把順排文檔中具有檢索屬性的項(xiàng)目信息抽取出來，重新排列組織成新的數(shù)據(jù)文檔 如：將物品數(shù)據(jù)庫中的價(jià)格數(shù)據(jù)項(xiàng)抽取出來，依據(jù)物品價(jià)格有高到低重新建立新的索引文檔。倒排文檔（Inverted File）5/20 3.1基于塊的排序索引技術(shù)基于塊的排序索引

2、技術(shù)3.1.1索引文檔建立必須考慮的硬件性能6/203.1基于塊的排序索引技術(shù)基于塊的排序索引技術(shù) 7/20 3.1基于塊的排序索引技術(shù)基于塊的排序索引技術(shù)v內(nèi)存調(diào)用內(nèi)存調(diào)用：訪問內(nèi)存數(shù)據(jù)比訪問磁訪問內(nèi)存數(shù)據(jù)比訪問磁盤數(shù)據(jù)盤數(shù)據(jù)快得多（快得多（ 5 5 10 10 9 9s VS 2 s VS 2 10 10 8 8s s），盡可能地把數(shù)據(jù)放在內(nèi)存中盡可能地把數(shù)據(jù)放在內(nèi)存中。 v連續(xù)存放數(shù)據(jù)塊：磁盤的尋道時(shí)間平均為連續(xù)存放數(shù)據(jù)塊：磁盤的尋道時(shí)間平均為4ms-5ms4ms-5ms，連續(xù)讀取的數(shù)據(jù)塊也應(yīng)該在磁盤連續(xù)讀取的數(shù)據(jù)塊也應(yīng)該在磁盤上連續(xù)存放。上連續(xù)存放。 8/20 3.1基于塊的排序索引技

3、術(shù)基于塊的排序索引技術(shù)v利用緩沖區(qū)：利用緩沖區(qū)：操作系統(tǒng)往往以數(shù)據(jù)塊為單操作系統(tǒng)往往以數(shù)據(jù)塊為單位進(jìn)行讀寫。數(shù)據(jù)塊的大小通常為位進(jìn)行讀寫。數(shù)據(jù)塊的大小通常為 8 KB 8 KB、16 KB16 KB、32 KB 32 KB 或或 64 KB 64 KB。 v壓縮數(shù)據(jù)：壓縮數(shù)據(jù)：數(shù)據(jù)從磁盤傳輸?shù)絻?nèi)存是由系統(tǒng)數(shù)據(jù)從磁盤傳輸?shù)絻?nèi)存是由系統(tǒng)總線而不是處理器來實(shí)現(xiàn)的，這意味著在磁總線而不是處理器來實(shí)現(xiàn)的，這意味著在磁盤盤 I/0 I/0 時(shí)處理器仍然可以處理數(shù)據(jù)。時(shí)處理器仍然可以處理數(shù)據(jù)。9/20 3.1基于塊的排序索引技術(shù)基于塊的排序索引技術(shù) v利用磁盤：利用磁盤：系統(tǒng)的服務(wù)器往往有數(shù)系統(tǒng)的服務(wù)器往往

4、有數(shù) GB GB 甚甚至數(shù)十至數(shù)十 GB GB 的內(nèi)存的內(nèi)存，可以利用，可以利用服務(wù)器磁盤服務(wù)器磁盤空間大小一般比內(nèi)存大小要高幾個(gè)數(shù)量級：空間大小一般比內(nèi)存大小要高幾個(gè)數(shù)量級：TB-PBTB-PB。10/20 3.1基于塊的排序索引技術(shù)基于塊的排序索引技術(shù) 3.1.2 3.1.2 基于塊的排序索引方法基于塊的排序索引方法 首先掃描一篇文檔集合得到所有具有檢索意義的詞語的“此項(xiàng)-文檔ID”數(shù)據(jù)集；然后依據(jù)此項(xiàng)的索引文檔及的主鍵和文檔ID為次鍵進(jìn)行排序；最后將每個(gè)此項(xiàng)的文檔ID組織成為倒排記錄表，并計(jì)算此項(xiàng)頻率或文檔頻率的統(tǒng)計(jì)量。思想11/20 圖3-1 桂林電子科技大學(xué)-新聞模塊目錄實(shí)例3.1基

5、于塊的排序索引技術(shù)基于塊的排序索引技術(shù) 12/20 3.1基于塊的排序索引技術(shù)基于塊的排序索引技術(shù) 圖3-2 桂林電子科技大學(xué)-新聞內(nèi)容文檔實(shí)例13/20 3.1基于塊的排序索引技術(shù)基于塊的排序索引技術(shù) 表3-1 桂林電子科技大學(xué)-新聞文檔集統(tǒng)計(jì)數(shù)據(jù)表14/20 3.1基于塊的排序索引技術(shù)基于塊的排序索引技術(shù)基于磁盤的外部排序算法ESA（External Sorting Algorithm）核心在索引排序時(shí)，盡量減少磁盤尋道次數(shù)基礎(chǔ)BSBI算法（Blocked Sort-based Indexing Algorithm,基于塊的排序算法）15/20 3.1基于塊的排序索引技術(shù)基于塊的排序索引技

6、術(shù) BSBI算法步驟：1將文檔集分割成多個(gè)大小相等的部分4將所有的中間文件合并成最終的索引2將每個(gè)部分的詞項(xiàng) ID文檔 ID 對排序3將中間產(chǎn)生的臨時(shí)排序結(jié)果存放到磁盤中16/20 3.1基于塊的排序索引技術(shù)基于塊的排序索引技術(shù) 選擇合適的塊算法，下圖的算法將每個(gè)塊的倒排索引存選擇合適的塊算法，下圖的算法將每個(gè)塊的倒排索引存入文件中入文件中f f1 1f fn n，最后合并為，最后合并為f fmergedmerged。 圖圖3-3 3-3 基于塊的排序索引算法基于塊的排序索引算法17/20 3.1基于塊的排序索引技術(shù)基于塊的排序索引技術(shù) 依據(jù)圖依據(jù)圖3-33-3的算法將待合并的倒排記錄表（兩個(gè)

7、數(shù)據(jù)塊）的算法將待合并的倒排記錄表（兩個(gè)數(shù)據(jù)塊）從磁盤讀入內(nèi)存，然后在內(nèi)存中合并后寫入磁盤（見圖從磁盤讀入內(nèi)存，然后在內(nèi)存中合并后寫入磁盤（見圖3-43-4）。）。 圖圖3-4 3-4 基于塊的排序方法合并示意圖基于塊的排序方法合并示意圖18/20 3.2基于內(nèi)存單次掃描的排序構(gòu)建技術(shù)基于內(nèi)存單次掃描的排序構(gòu)建技術(shù) 基于內(nèi)存單次掃描的索引算法基于內(nèi)存單次掃描的索引算法SPIMI (single-pass SPIMI (single-pass in-memory indexing)in-memory indexing)：n每塊采用不同的詞典，將每個(gè)塊的詞典寫入磁盤，每塊采用不同的詞典，將每個(gè)塊的

8、詞典寫入磁盤，對于下一個(gè)塊則重新采用新的詞典。對于下一個(gè)塊則重新采用新的詞典。n只要硬盤空間足夠大，只要硬盤空間足夠大，SPIMI SPIMI 就能夠索引任何大小就能夠索引任何大小的文檔集。的文檔集。原因基于塊的排序索引算法具有很好的可擴(kuò)展性，但是需要一種將所有詞項(xiàng)放到內(nèi)存。對于大規(guī)模的文檔集來說，該數(shù)據(jù)結(jié)構(gòu)會很大以致在內(nèi)存中難以存放。19/20 3.2基于內(nèi)存單次掃描的排序構(gòu)建技術(shù)基于內(nèi)存單次掃描的排序構(gòu)建技術(shù) SPIMISPIMI算法的步驟：算法的步驟：Click to add TitleClick to add TitleClick to add Title2將所有的中間文件合并成最終的

9、索引1處理文檔，直到內(nèi)存不足，寫入磁盤20/20 3.2基于內(nèi)存單次掃描的排序構(gòu)建技術(shù)基于內(nèi)存單次掃描的排序構(gòu)建技術(shù) 圖圖3-5 SPIMI3-5 SPIMI算法的塊倒排索引生成算法算法的塊倒排索引生成算法21/20 3.2基于內(nèi)存單次掃描的排序構(gòu)建技術(shù)基于內(nèi)存單次掃描的排序構(gòu)建技術(shù) SPIMISPIMI算法與算法與BSBIBSBI的區(qū)別：的區(qū)別：通過判定循環(huán)動態(tài)增加排序記錄表的，倒排記錄表的SPIMISPIMI算法算法直接在倒排記錄表中增加定位符項(xiàng)，且開始就需要處理形成所有項(xiàng)的“詞項(xiàng)文檔”并進(jìn)行排序BSBIBSBI算法算法22/20 3.3順排文檔索引順排文檔索引 將文檔中的每一條記錄依次去

10、匹配用戶的將文檔中的每一條記錄依次去匹配用戶的檢索提問集合，文檔處理完畢后，將各提問的檢索提問集合，文檔處理完畢后，將各提問的命中結(jié)果歸并分發(fā)給有關(guān)用戶。命中結(jié)果歸并分發(fā)給有關(guān)用戶。思想 用文檔中記錄一條一條去匹配提問的，是順用文檔中記錄一條一條去匹配提問的，是順序?qū)ξ臋n記錄檢索的方法序?qū)ξ臋n記錄檢索的方法定義 采用列表處理方法將提問邏輯式（檢索式）變采用列表處理方法將提問邏輯式（檢索式）變換成等價(jià)的提問展開式，按提問展開表的內(nèi)容換成等價(jià)的提問展開式，按提問展開表的內(nèi)容對順排文檔的每篇文獻(xiàn)進(jìn)行檢索對順排文檔的每篇文獻(xiàn)進(jìn)行檢索關(guān)鍵技術(shù)表展開法、邏輯樹法等表展開法、邏輯樹法等常見方法23/20 3

11、.3順排文檔索引順排文檔索引 3.3.1 3.3.1 表展開法索引表展開法索引 1968 1968年，日本學(xué)者菊池敏典提出，又稱年，日本學(xué)者菊池敏典提出，又稱“菊池菊池敏典算法敏典算法”。目前主要用于面向定向服務(wù)的檢索系。目前主要用于面向定向服務(wù)的檢索系統(tǒng)，旨在將代表用戶的邏輯提問式轉(zhuǎn)換成檢索表的統(tǒng)，旨在將代表用戶的邏輯提問式轉(zhuǎn)換成檢索表的形式，該檢索表規(guī)定了表內(nèi)容走向和檢索命中與否形式，該檢索表規(guī)定了表內(nèi)容走向和檢索命中與否的判斷，檢索時(shí)根據(jù)表內(nèi)容走向及其他相關(guān)信息來的判斷，檢索時(shí)根據(jù)表內(nèi)容走向及其他相關(guān)信息來判斷每條記錄是否檢索命中。判斷每條記錄是否檢索命中。24/20 3.3順順排排文檔

12、索引文檔索引 1 1、展開表的含義、展開表的含義 將經(jīng)典布爾邏輯檢索的邏輯提問表達(dá)式轉(zhuǎn)換為邏輯將經(jīng)典布爾邏輯檢索的邏輯提問表達(dá)式轉(zhuǎn)換為邏輯檢索表，每個(gè)檢索詞的檢索組配關(guān)系要求能夠用表進(jìn)行檢索表，每個(gè)檢索詞的檢索組配關(guān)系要求能夠用表進(jìn)行精確映射，檢索的記錄是夠最終命中檢索需求要能準(zhǔn)確精確映射，檢索的記錄是夠最終命中檢索需求要能準(zhǔn)確反映出來。反映出來。(A+B)(A+B)* *(C+D)(C+D)的展開表如的展開表如3-23-2所示所示表表3-2 3-2 （A+BA+B）* *（C+DC+D）的展開檢索基礎(chǔ)表）的展開檢索基礎(chǔ)表l表中，“命中”表示被查比的文獻(xiàn)滿足查詢要求的出口，“落選”表示反之25

13、/203.3順順排排文檔索引文檔索引 2 2、展開表生成、展開表生成v過程過程v檢索檢索詞詞v檢索運(yùn)算符檢索運(yùn)算符v改變運(yùn)算次序的括號改變運(yùn)算次序的括號供檢索匹配的表格前處理26/20 3.3順順排排文檔索引文檔索引 v前處理前處理n判斷提問式中的字符，從上而下填寫表格判斷提問式中的字符，從上而下填寫表格。對不同類型對不同類型對象的處理方式如下：對象的處理方式如下：表表3-3 3-3 對不同類型對象的處理表對不同類型對象的處理表27/20 3.3順順排排文檔索引文檔索引 v后處理后處理n后處理的主要任務(wù)就是填滿整個(gè)表的空白單元，后處理的主要任務(wù)就是填滿整個(gè)表的空白單元，填表的依據(jù)是表中填表的依

14、據(jù)是表中“級位級位”欄的前后級位值，填欄的前后級位值，填表的順序是從下向上，直至表的頂部，從而得到表的順序是從下向上，直至表的頂部，從而得到一個(gè)完整的提問展開表。一個(gè)完整的提問展開表。28/20 3.3順順排排文檔索引文檔索引 3 3、表展開法的檢索應(yīng)用描述、表展開法的檢索應(yīng)用描述 每讀取一條記錄，就生成一個(gè)檢索標(biāo)每讀取一條記錄，就生成一個(gè)檢索標(biāo)識表識表（可檢索項(xiàng)可檢索項(xiàng)），然后將，然后將該該表中的檢索表中的檢索項(xiàng)去查展開表，并對命中的做上標(biāo)記項(xiàng)去查展開表，并對命中的做上標(biāo)記。查查匹配匹配 根據(jù)展開表查詢情況，分析提問是否命根據(jù)展開表查詢情況，分析提問是否命中中。命中者，就在相應(yīng)的提問號下記下

15、記命中者，就在相應(yīng)的提問號下記下記錄號及相關(guān)信息，取下條記錄進(jìn)行對錄號及相關(guān)信息，取下條記錄進(jìn)行對比。比。檢索項(xiàng)查檢索項(xiàng)查完完 得到本次檢索的最終結(jié)果得到本次檢索的最終結(jié)果通過提問號通過提問號調(diào)出檢索結(jié)果中各自命中結(jié)果的記錄給用調(diào)出檢索結(jié)果中各自命中結(jié)果的記錄給用戶。戶。全部全部匹配匹配完完29/203.3順順排排文檔索引文檔索引 3.3.2 3.3.2 邏輯樹索引邏輯樹索引v邏輯樹展開法是將邏輯提問式展開成樹型結(jié)構(gòu)（下稱主邏輯樹），運(yùn)算符構(gòu)成樹的結(jié)點(diǎn)，檢索詞被視為樹葉，所有檢索詞也按照有限自動機(jī)原理構(gòu)造成字符樹（即子樹），主樹與子樹間的相關(guān)元素用指針鏈接。v檢索采取遍歷樹原則，先用文檔中的索

16、引詞逐字符的遍歷子樹，當(dāng)遍歷到樹的一個(gè)端點(diǎn)（樹葉），然后依照指針登記主樹，并根據(jù)遍歷樹方式分析提問是否命中。v邏輯樹展開法包括三個(gè)部分：邏輯提問式的分解、字符樹的生成、檢索實(shí)現(xiàn)。30/203.3順順排排文檔索引文檔索引 1 1、邏輯提問式分解、邏輯提問式分解 邏輯提問式分解的分解目標(biāo)為：提供可直接用于檢索實(shí)現(xiàn)的主邏輯樹表、檢索詞地址表以及檢索詞在檢索式中的位置表。這些表在檢索實(shí)踐中分別發(fā)揮著應(yīng)有的作用。（1）主邏輯樹表 主邏輯樹表是邏輯提問式的一種樹形表達(dá)形式，它用層次型的樹形結(jié)構(gòu)把運(yùn)算符、運(yùn)算項(xiàng)關(guān)聯(lián)起來，其主要內(nèi)容包括；運(yùn)算種類、子項(xiàng)個(gè)數(shù)、父項(xiàng)地址以及檢索處理登記欄。表表3-4 3-4 主邏

17、輯樹表結(jié)構(gòu)主邏輯樹表結(jié)構(gòu)31/20 3.3順順排排文檔索引文檔索引 （2）檢索詞地址表）檢索詞地址表 檢索詞地址表是主邏輯樹表與檢索詞地址表是主邏輯樹表與子子表的聯(lián)系紐帶，在表的聯(lián)系紐帶，在檢索中，當(dāng)一個(gè)檢索詞命中以后，通過檢索中，當(dāng)一個(gè)檢索詞命中以后，通過子子表找到其在檢表找到其在檢索詞地址表的位置，再根據(jù)該表中記錄的主表位置進(jìn)行索詞地址表的位置，再根據(jù)該表中記錄的主表位置進(jìn)行檢索處理（在檢索處理欄加檢索處理（在檢索處理欄加1等操作）。該表由兩個(gè)字段等操作）。該表由兩個(gè)字段組成：檢索狀況登錄區(qū)、檢索詞在主表中位置組成：檢索狀況登錄區(qū)、檢索詞在主表中位置 。表表3-5 3-5 檢索詞地址表結(jié)構(gòu)

18、檢索詞地址表結(jié)構(gòu)32/20 3.3順順排排文檔索引文檔索引 （3）檢索詞位置表）檢索詞位置表 檢索詞位置表是在邏輯提問式轉(zhuǎn)換成邏輯樹表的過檢索詞位置表是在邏輯提問式轉(zhuǎn)換成邏輯樹表的過程中，臨時(shí)生成的一個(gè)中間處理過程表，該表還將作為程中，臨時(shí)生成的一個(gè)中間處理過程表，該表還將作為從邏輯提問式到詞邏輯樹從邏輯提問式到詞邏輯樹子子表的橋梁，一旦表的橋梁，一旦子子表生成完表生成完畢，該表將被清除。畢，該表將被清除。表表3-6 3-6 檢索詞位置表結(jié)構(gòu)檢索詞位置表結(jié)構(gòu)33/20 3.3順順排排文檔索引文檔索引 （4）中間工作表）中間工作表 由于在進(jìn)行邏輯提問式到邏輯樹表的轉(zhuǎn)換過程中，由于在進(jìn)行邏輯提問式

19、到邏輯樹表的轉(zhuǎn)換過程中，涉及一些中間數(shù)據(jù)，這些數(shù)據(jù)在生成邏輯樹時(shí)需多次使涉及一些中間數(shù)據(jù)，這些數(shù)據(jù)在生成邏輯樹時(shí)需多次使用，因此需要建立一個(gè)中間過程工作區(qū)（中間工作表）用，因此需要建立一個(gè)中間過程工作區(qū)（中間工作表）來記錄這些數(shù)據(jù)，一旦主邏輯樹生成完畢，該表即可以來記錄這些數(shù)據(jù)，一旦主邏輯樹生成完畢，該表即可以清除。清除。 表表3-7 3-7 中間工作表結(jié)構(gòu)中間工作表結(jié)構(gòu)34/20 3.3順順排排文檔索引文檔索引 （5）主邏輯樹表的生成）主邏輯樹表的生成 主邏輯樹表的生成算法思想為：采用多次掃描的分主邏輯樹表的生成算法思想為：采用多次掃描的分層分解構(gòu)造法。首先分解出邏輯式中最外層層分解構(gòu)造法。

20、首先分解出邏輯式中最外層“”號下的號下的子項(xiàng)，括號內(nèi)的項(xiàng)暫時(shí)不分解；其次掃描已分解出的子子項(xiàng)，括號內(nèi)的項(xiàng)暫時(shí)不分解；其次掃描已分解出的子項(xiàng)（在最外層沒有項(xiàng)（在最外層沒有“”項(xiàng)的情況下對整個(gè)邏輯式進(jìn)行）項(xiàng)的情況下對整個(gè)邏輯式進(jìn)行）中的中的“*”號的運(yùn)算子項(xiàng)，若該子項(xiàng)為括號括起項(xiàng)，則仍分號的運(yùn)算子項(xiàng)，若該子項(xiàng)為括號括起項(xiàng)，則仍分解解“”號子項(xiàng)；最后分解號子項(xiàng)；最后分解“-”號子項(xiàng)。號子項(xiàng)。35/20 3.3順順排排文檔索引文檔索引2、邏輯樹法檢索應(yīng)用 邏輯提問式最終轉(zhuǎn)換為邏輯樹的三個(gè)表：主邏輯樹表、檢索詞地址表、檢索詞字符樹表。這三個(gè)表構(gòu)成了用戶檢索提問文檔，整個(gè)檢索主要依賴這三個(gè)表。 實(shí)際檢索過

21、程為：從文檔中讀取一條記錄，將記錄中的標(biāo)引項(xiàng)（主題詞、責(zé)任者、分類號等可供檢索的著錄項(xiàng)）去匹配相關(guān)的檢索詞邏輯樹，匹配成功者，根據(jù)檢索詞地址指針去判斷檢索詞地址表對應(yīng)的檢索登錄區(qū)，若為“1”，表明該吃已命中過，不需要在處理；若為“0”，則將該項(xiàng)置為“1”，同時(shí)根據(jù)本行的“主表位置”字段去修改主邏輯樹表。36/20 3.3順順排排文檔索引文檔索引 對主邏輯樹表的檢索處理如下：對主邏輯樹表的檢索處理如下：v在主邏輯樹表中該詞的在主邏輯樹表中該詞的“處理標(biāo)志處理標(biāo)志”欄中填上欄中填上“1”，然后根據(jù)父項(xiàng)地址的指針找到父項(xiàng)行，對然后根據(jù)父項(xiàng)地址的指針找到父項(xiàng)行，對“檢索處理檢索處理”欄作加欄作加“1”

22、運(yùn)算，再查看運(yùn)算，再查看“處理標(biāo)識處理標(biāo)識”欄，若為欄，若為“1”，表示該子項(xiàng)已做過向上遍歷處理，可返回進(jìn)行，表示該子項(xiàng)已做過向上遍歷處理，可返回進(jìn)行下一詞的處理；若為下一詞的處理；若為“0”，則根據(jù)，則根據(jù)“運(yùn)算種類運(yùn)算種類”做相做相應(yīng)的處理。應(yīng)的處理。v隨著父項(xiàng)指針移動到頂行時(shí)，若該行的處理標(biāo)志為隨著父項(xiàng)指針移動到頂行時(shí)，若該行的處理標(biāo)志為“1”，則已命中，把提問號和記錄號寫入命中文檔。，則已命中，把提問號和記錄號寫入命中文檔。37/20 常見方法為逆波蘭展開法。3.4倒排文檔索引倒排文檔索引 是一種面向單詞的索引機(jī)制，相對順排文檔而言，是將順排文檔中可檢索字段的作者名、關(guān)鍵詞、分類號等取

23、出，按一定規(guī)則排序，歸并相同詞匯，并把在順排文檔中相關(guān)記錄的記錄號集合賦予其后，以保證通過某一特征詞能夠快速、方便地獲取相關(guān)記錄。思想38/20 3.4倒排文檔索引倒排文檔索引 3.4.1 3.4.1 倒排文檔索引的建立倒排文檔索引的建立 倒排文檔的組成元素如下：如下： 關(guān)鍵字目長記錄號集合作者主題詞分類號含有該關(guān)鍵字記錄的條數(shù)所有與該關(guān)鍵字有關(guān)的記錄號39/20 3.4倒排文檔索引倒排文檔索引 1 1、倒排文檔的結(jié)構(gòu)、倒排文檔的結(jié)構(gòu) 倒排文檔可視為主文檔的輔助索引，它從不同的角度倒排文檔可視為主文檔的輔助索引，它從不同的角度提供了對主文檔的快速查詢，不同屬性的數(shù)據(jù)結(jié)構(gòu)構(gòu)成不提供了對主文檔的快

24、速查詢，不同屬性的數(shù)據(jù)結(jié)構(gòu)構(gòu)成不同的倒排索引文檔。同的倒排索引文檔。2 2、倒排文檔的建立、倒排文檔的建立 選擇需要做索引的字段屬性(如作者、關(guān)鍵詞等)，抽出其中的內(nèi)容，并在其后附上記錄號抽詞抽詞 對抽出的內(nèi)容進(jìn)行排序，使之便于歸并相同內(nèi)容排序排序 對相同內(nèi)容進(jìn)行歸并，把合并后的內(nèi)容放入倒排文檔的主鍵字段(如標(biāo)引詞、作者等)，統(tǒng)計(jì)每一數(shù)據(jù)的頻次為目長，把每一內(nèi)容后的記錄號順序放在記錄號集合字段歸并歸并40/20 3.4倒排文檔索引倒排文檔索引 表表3-8 3-8 文獻(xiàn)及部分屬性舉例文獻(xiàn)及部分屬性舉例41/20 3.4倒排文檔索引倒排文檔索引 表表3-9 3-9 關(guān)鍵詞索引關(guān)鍵詞索引42/20

25、3.4倒排文檔索引倒排文檔索引 表表3-10 3-10 作者索引作者索引建立倒排文檔的過程中需要注意：第一，倒排文檔的建立應(yīng)具有即時(shí)更新的功能。第二，需要建立一處文檔來解決不等長問題。43/20 3.4倒排文檔索引倒排文檔索引 3.4.2 3.4.2 邏輯提問式的轉(zhuǎn)換邏輯提問式的轉(zhuǎn)換 1929年波蘭的邏輯學(xué)家盧卡西維茲提出將運(yùn)算符放在運(yùn)算項(xiàng)后面的邏輯表達(dá)式，又稱“逆波蘭表達(dá)式”日本的福島首先將逆波蘭表達(dá)式應(yīng)用于情報(bào)檢索，故又稱“福島方法”。例如：邏輯提問式 A*(B+C)+D逆波蘭表達(dá)式 ABC+*D+ 思想福島算法首先要進(jìn)行提問式的轉(zhuǎn)換。思想福島算法首先要進(jìn)行提問式的轉(zhuǎn)換。 44/20 3.

26、4倒排文檔索引倒排文檔索引 表表3-11 3-11 運(yùn)算符的優(yōu)先級運(yùn)算符的優(yōu)先級v為轉(zhuǎn)換處理開辟三個(gè)存儲區(qū)：為轉(zhuǎn)換處理開辟三個(gè)存儲區(qū)：檢索詞表存儲區(qū)逆波蘭輸出區(qū)123算子棧存放轉(zhuǎn)換過程中的運(yùn)算存放檢索詞存放邏輯提問式的逆波蘭表達(dá)式45/203.4倒排文檔索引倒排文檔索引 從左向右逐個(gè)掃描提問邏輯是的字符，遇到不同的從左向右逐個(gè)掃描提問邏輯是的字符，遇到不同的對象做相應(yīng)處理：對象做相應(yīng)處理：*其中，P當(dāng)前P前一：當(dāng)前算符的優(yōu)先級高于前一算符；為假時(shí)，包括相等。46/203.4倒排文檔索引倒排文檔索引 注意兩點(diǎn)：注意兩點(diǎn)：1、棧的規(guī)則是、棧的規(guī)則是元素元素“先進(jìn)后先進(jìn)后出出”，轉(zhuǎn)換結(jié)，轉(zhuǎn)換結(jié)束其棧為空束其棧為空2、逆波蘭輸出、逆波蘭輸出去的算子特去的算子特征為征為1，檢索，檢索詞特征為詞特征為047/203.4倒排文檔索引倒排文檔索引 v逆波蘭法處理示意圖逆波蘭法處理示意圖檢索詞表（A+B）*（C+EF）詞表地址算子區(qū)分運(yùn)算項(xiàng)還是運(yùn)算符逆波蘭輸出區(qū)邏輯提問式算子棧圖3-6 逆波蘭轉(zhuǎn)換處理示意圖48/203.4倒排文檔索引倒排文檔索引3.4.3