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

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

2、硬件性能6/203.1基于塊的排序索引技術(shù) 7/20 3.1基于塊的排序索引技術(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基于塊的排序索引技術(shù)v利用緩沖區(qū)：利用緩沖區(qū)：操作系統(tǒng)往往以數(shù)據(jù)塊為單操作系統(tǒng)往往以數(shù)據(jù)塊為單

3、位進(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ù) v利用磁盤：利用磁盤：系統(tǒng)的服務(wù)器往往有數(shù)系統(tǒng)的服務(wù)器往往有數(shù) GB GB 甚甚至數(shù)十至數(shù)十 GB GB 的內(nèi)存的內(nèi)存，可以利用，可以利用服務(wù)器磁盤服務(wù)器磁盤空間大小一般比內(nèi)

4、存大小要高幾個(gè)數(shù)量級(jí)：空間大小一般比內(nèi)存大小要高幾個(gè)數(shù)量級(jí)：TB-PBTB-PB。10/20 3.1基于塊的排序索引技術(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基于塊的排序索引技術(shù) 12/20 3.1基于塊的排序索引技術(shù) 圖3-2 桂林電子科技大學(xué)-新聞內(nèi)容文檔實(shí)例13/20 3.1基于塊的排序索

5、引技術(shù) 符號(hào)符號(hào)含義含義統(tǒng)計(jì)值統(tǒng)計(jì)值N文檔總量900 000L每篇文檔的平均詞項(xiàng)數(shù)量160M詞項(xiàng)目總數(shù)190 000每個(gè)詞項(xiàng)的平均字節(jié)數(shù)（包含空格與標(biāo)點(diǎn)）4.1B每個(gè)詞項(xiàng)的平均字節(jié)數(shù)（不包含空格與標(biāo)點(diǎn)）3.7B每個(gè)詞項(xiàng)的平均字節(jié)數(shù)4.6BT倒排記錄總數(shù)40 000 000 表3-1 桂林電子科技大學(xué)-新聞文檔集統(tǒng)計(jì)數(shù)據(jù)表14/20 3.1基于塊的排序索引技術(shù)基于磁盤的外部排序算法ESA（External Sorting Algorithm）核心在索引排序時(shí)，盡量減少磁盤尋道次數(shù)基礎(chǔ)BSBI算法（Blocked Sort-based Indexing Algorithm,基于塊的排序算法）15/

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

7、算法將待合并的倒排記錄表（兩個(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)存單次掃描的索引算法基于內(nèi)存單次掃描的索引算法SPIMI (single-pass SPIMI (single-pass in-memory indexing)in-memory indexing)：n每塊采用不同的詞典，將每個(gè)塊的詞典寫入磁盤，每塊采用不同的詞典，將每個(gè)塊的詞典寫入磁盤，對(duì)于下一個(gè)塊則重新采用新的

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

9、描的排序構(gòu)建技術(shù) 圖圖3-5 SPIMI3-5 SPIMI算法的塊倒排索引生成算法算法的塊倒排索引生成算法21/20 3.2基于內(nèi)存單次掃描的排序構(gòu)建技術(shù) SPIMISPIMI算法與算法與BSBIBSBI的區(qū)別：的區(qū)別：通過判定循環(huán)動(dòng)態(tài)增加排序記錄表的，倒排記錄表的SPIMISPIMI算法算法直接在倒排記錄表中增加定位符項(xiàng)，且開始就需要處理形成所有項(xiàng)的“詞項(xiàng)文檔”并進(jìn)行排序BSBIBSBI算法算法22/20 3.3順排文檔索引 將文檔中的每一條記錄依次去匹配用戶的將文檔中的每一條記錄依次去匹配用戶的檢索提問集合，文檔處理完畢后，將各提問的檢索提問集合，文檔處理完畢后，將各提問的命中結(jié)果歸并分發(fā)

10、給有關(guān)用戶。命中結(jié)果歸并分發(fā)給有關(guān)用戶。思想 用文檔中記錄一條一條去匹配提問的，是順用文檔中記錄一條一條去匹配提問的，是順序?qū)ξ臋n記錄檢索的方法序?qū)ξ臋n記錄檢索的方法定義 采用列表處理方法將提問邏輯式（檢索式）采用列表處理方法將提問邏輯式（檢索式）變換成等價(jià)的提問展開式，按提問展開表的內(nèi)變換成等價(jià)的提問展開式，按提問展開表的內(nèi)容對(duì)順排文檔的每篇文獻(xiàn)進(jìn)行檢索容對(duì)順排文檔的每篇文獻(xiàn)進(jìn)行檢索關(guān)鍵技術(shù)表展開法、邏輯樹法等表展開法、邏輯樹法等常見方法23/20 3.3順排文檔索引 3.3.1 3.3.1 表展開法索引表展開法索引 1968 1968年，日本學(xué)者菊池敏典提出，又稱年，日本學(xué)者菊池敏典提出，

11、又稱“菊池菊池敏典算法敏典算法”。目前主要用于面向定向服務(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順排文檔索引 1 1、展開表的含義、展開表的含義 將經(jīng)典布爾邏輯檢索的邏輯提問表達(dá)式轉(zhuǎn)換為邏輯將經(jīng)典布爾邏輯檢索的邏輯提問表達(dá)式轉(zhuǎn)換為邏輯檢索表，每個(gè)檢索詞的檢索組配

12、關(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ǔ)表地址地址檢索詞檢索詞條件滿足指向條件滿足指向條件非滿足指向條件非滿足指向1A322B3落選3C命中44D命中落選l表中，“命中”表示被查比的文獻(xiàn)滿足查詢要求的出口，“落選”表示反之25/203.3順排文檔索引 2 2、展開表生成、展開表生

13、成v過程過程v檢索檢索詞詞v檢索運(yùn)算符檢索運(yùn)算符v改變運(yùn)算次序的括號(hào)改變運(yùn)算次序的括號(hào)供檢索匹配的表格前處理26/20 3.3順排文檔索引 v前處理前處理n判斷提問式中的字符，從上而下填寫表格判斷提問式中的字符，從上而下填寫表格。對(duì)不同類型對(duì)不同類型對(duì)象的處理方式如下：對(duì)象的處理方式如下：表表3-3 3-3 對(duì)不同類型對(duì)象的處理表對(duì)不同類型對(duì)象的處理表類型類型符號(hào)符號(hào)處理方式處理方式檢索詞將其存入展開表內(nèi)的檢索詞欄，并記下在表中的地址運(yùn)算符+前一詞滿足，指向“*”；不滿足，指向后一詞*前一詞滿足，指向后一詞括號(hào)（在其后的檢索詞所在行的“級(jí)位”欄值加1）在其后的檢索詞所在行的“級(jí)位”欄值減1括號(hào)

14、結(jié)束最后一個(gè)檢索詞所在行的“條件滿足指向”欄放入“命中”，“條件不滿足”放入“落選”27/20 3.3順排文檔索引 v后處理后處理n后處理的主要任務(wù)就是填滿整個(gè)表的空白單元，后處理的主要任務(wù)就是填滿整個(gè)表的空白單元，填表的依據(jù)是表中填表的依據(jù)是表中“級(jí)位級(jí)位”欄的前后級(jí)位值，填欄的前后級(jí)位值，填表的順序是從下向上，直至表的頂部，從而得到表的順序是從下向上，直至表的頂部，從而得到一個(gè)完整的提問展開表。一個(gè)完整的提問展開表。28/20 3.3順排文檔索引 3 3、表展開法的檢索應(yīng)用描述、表展開法的檢索應(yīng)用描述 每讀取一條記錄，就生成一個(gè)檢索標(biāo)每讀取一條記錄，就生成一個(gè)檢索標(biāo)識(shí)表（可檢索項(xiàng)），然后將

15、該表中的檢索識(shí)表（可檢索項(xiàng)），然后將該表中的檢索項(xiàng)去查展開表，并對(duì)命中的做上標(biāo)記。項(xiàng)去查展開表，并對(duì)命中的做上標(biāo)記。查匹配查匹配 根據(jù)展開表查詢情況，分析提問是否命根據(jù)展開表查詢情況，分析提問是否命中。命中者，就在相應(yīng)的提問號(hào)下記下記中。命中者，就在相應(yīng)的提問號(hào)下記下記錄號(hào)及相關(guān)信息，取下條記錄進(jìn)行對(duì)比。錄號(hào)及相關(guān)信息，取下條記錄進(jìn)行對(duì)比。檢索項(xiàng)查完檢索項(xiàng)查完 得到本次檢索的最終結(jié)果通過提問號(hào)得到本次檢索的最終結(jié)果通過提問號(hào)調(diào)出檢索結(jié)果中各自命中結(jié)果的記錄給用調(diào)出檢索結(jié)果中各自命中結(jié)果的記錄給用戶。戶。全部匹配完全部匹配完29/203.3順排文檔索引 3.3.2 3.3.2 邏輯樹索引邏輯樹索

16、引v邏輯樹展開法是將邏輯提問式展開成樹型結(jié)構(gòu)（下稱主邏輯樹），運(yùn)算符構(gòu)成樹的結(jié)點(diǎn)，檢索詞被視為樹葉，所有檢索詞也按照有限自動(dòng)機(jī)原理構(gòu)造成字符樹（即子樹），主樹與子樹間的相關(guān)元素用指針鏈接。v檢索采取遍歷樹原則，先用文檔中的索引詞逐字符的遍歷子樹，當(dāng)遍歷到樹的一個(gè)端點(diǎn)（樹葉），然后依照指針登記主樹，并根據(jù)遍歷樹方式分析提問是否命中。v邏輯樹展開法包括三個(gè)部分：邏輯提問式的分解、字符樹的生成、檢索實(shí)現(xiàn)。30/203.3順排文檔索引 1 1、邏輯提問式分解、邏輯提問式分解 邏輯提問式分解的分解目標(biāo)為：提供可直接用于檢索實(shí)現(xiàn)的主邏輯樹表、檢索詞地址表以及檢索詞在檢索式中的位置表。這些表在檢索實(shí)踐中分別

17、發(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)地址以及檢索處理登記欄。運(yùn)算類型運(yùn)算類型子項(xiàng)類型子項(xiàng)類型父項(xiàng)地址父項(xiàng)地址處理標(biāo)志處理標(biāo)志檢索處理檢索處理表表3-4 3-4 主邏輯樹表結(jié)構(gòu)主邏輯樹表結(jié)構(gòu)31/20 3.3順排文檔索引 （2）檢索詞地址表）檢索詞地址表 檢索詞地址表是主邏輯樹表與檢索詞地址表是主邏輯樹表與子子表的聯(lián)系紐帶，在表的聯(lián)系紐帶，在檢索中，當(dāng)一個(gè)檢索詞命中以后，通過檢索中，當(dāng)一個(gè)檢索詞命中以后，通過子子表找到其在檢表找到其在檢索詞地址表的位置，再根據(jù)該表中記錄

18、的主表位置進(jìn)行索詞地址表的位置，再根據(jù)該表中記錄的主表位置進(jìn)行檢索處理（在檢索處理欄加檢索處理（在檢索處理欄加1等操作）。該表由兩個(gè)字段等操作）。該表由兩個(gè)字段組成：檢索狀況登錄區(qū)、檢索詞在主表中位置組成：檢索狀況登錄區(qū)、檢索詞在主表中位置 。檢索登錄檢索登錄主標(biāo)位置主標(biāo)位置表表3-5 3-5 檢索詞地址表結(jié)構(gòu)檢索詞地址表結(jié)構(gòu)32/20 3.3順排文檔索引 （3）檢索詞位置表）檢索詞位置表 檢索詞位置表是在邏輯提問式轉(zhuǎn)換成邏輯樹表的過檢索詞位置表是在邏輯提問式轉(zhuǎn)換成邏輯樹表的過程中，臨時(shí)生成的一個(gè)中間處理過程表，該表還將作為程中，臨時(shí)生成的一個(gè)中間處理過程表，該表還將作為從邏輯提問式到詞邏輯樹

19、從邏輯提問式到詞邏輯樹子子表的橋梁，一旦表的橋梁，一旦子子表生成完表生成完畢，該表將被清除。畢，該表將被清除。表表3-6 3-6 檢索詞位置表結(jié)構(gòu)檢索詞位置表結(jié)構(gòu)檢索詞種類檢索詞種類起始位置起始位置終止位置終止位置33/20 3.3順排文檔索引 （4）中間工作表）中間工作表 由于在進(jìn)行邏輯提問式到邏輯樹表的轉(zhuǎn)換過程中，由于在進(jìn)行邏輯提問式到邏輯樹表的轉(zhuǎn)換過程中，涉及一些中間數(shù)據(jù)，這些數(shù)據(jù)在生成邏輯樹時(shí)需多次使涉及一些中間數(shù)據(jù)，這些數(shù)據(jù)在生成邏輯樹時(shí)需多次使用，因此需要建立一個(gè)中間過程工作區(qū)（中間工作表）用，因此需要建立一個(gè)中間過程工作區(qū)（中間工作表）來記錄這些數(shù)據(jù)，一旦主邏輯樹生成完畢，該表即

20、可以來記錄這些數(shù)據(jù)，一旦主邏輯樹生成完畢，該表即可以清除。清除。 表表3-7 3-7 中間工作表結(jié)構(gòu)中間工作表結(jié)構(gòu)起始位置起始位置終止位置終止位置父項(xiàng)地址父項(xiàng)地址輔助信息輔助信息34/20 3.3順排文檔索引 （5）主邏輯樹表的生成）主邏輯樹表的生成 主邏輯樹表的生成算法思想為：采用多次掃描的分主邏輯樹表的生成算法思想為：采用多次掃描的分層分解構(gòu)造法。首先分解出邏輯式中最外層層分解構(gòu)造法。首先分解出邏輯式中最外層“”號(hào)下號(hào)下的子項(xiàng)，括號(hào)內(nèi)的項(xiàng)暫時(shí)不分解；其次掃描已分解出的的子項(xiàng)，括號(hào)內(nèi)的項(xiàng)暫時(shí)不分解；其次掃描已分解出的子項(xiàng)（在最外層沒有子項(xiàng)（在最外層沒有“”項(xiàng)的情況下對(duì)整個(gè)邏輯式進(jìn)項(xiàng)的情況下對(duì)

21、整個(gè)邏輯式進(jìn)行）中的行）中的“*”號(hào)的運(yùn)算子項(xiàng)，若該子項(xiàng)為括號(hào)括起項(xiàng)，號(hào)的運(yùn)算子項(xiàng)，若該子項(xiàng)為括號(hào)括起項(xiàng)，則仍分解則仍分解“”號(hào)子項(xiàng)；最后分解號(hào)子項(xiàng)；最后分解“-”號(hào)子項(xiàng)。號(hào)子項(xiàng)。35/20 3.3順排文檔索引2、邏輯樹法檢索應(yīng)用 邏輯提問式最終轉(zhuǎn)換為邏輯樹的三個(gè)表：主邏輯樹表、檢索詞地址表、檢索詞字符樹表。這三個(gè)表構(gòu)成了用戶檢索提問文檔，整個(gè)檢索主要依賴這三個(gè)表。 實(shí)際檢索過程為：從文檔中讀取一條記錄，將記錄中的標(biāo)引項(xiàng)（主題詞、責(zé)任者、分類號(hào)等可供檢索的著錄項(xiàng)）去匹配相關(guān)的檢索詞邏輯樹，匹配成功者，根據(jù)檢索詞地址指針去判斷檢索詞地址表對(duì)應(yīng)的檢索登錄區(qū)，若為“1”，表明該吃已命中過，不需要在處

22、理；若為“0”，則將該項(xiàng)置為“1”，同時(shí)根據(jù)本行的“主表位置”字段去修改主邏輯樹表。36/20 3.3順排文檔索引 對(duì)主邏輯樹表的檢索處理如下：對(duì)主邏輯樹表的檢索處理如下：v在主邏輯樹表中該詞的在主邏輯樹表中該詞的“處理標(biāo)志處理標(biāo)志”欄中填上欄中填上“1”，然后根據(jù)父項(xiàng)地址的指針找到父項(xiàng)行，對(duì)然后根據(jù)父項(xiàng)地址的指針找到父項(xiàng)行，對(duì)“檢索處理檢索處理”欄作加欄作加“1”運(yùn)算，再查看運(yùn)算，再查看“處理標(biāo)識(shí)處理標(biāo)識(shí)”欄，若為欄，若為“1”，表示該子項(xiàng)已做過向上遍歷處理，可返回進(jìn)行，表示該子項(xiàng)已做過向上遍歷處理，可返回進(jìn)行下一詞的處理；若為下一詞的處理；若為“0”，則根據(jù)，則根據(jù)“運(yùn)算種類運(yùn)算種類”做相

23、做相應(yīng)的處理。應(yīng)的處理。v隨著父項(xiàng)指針移動(dòng)到頂行時(shí)，若該行的處理標(biāo)志為隨著父項(xiàng)指針移動(dòng)到頂行時(shí)，若該行的處理標(biāo)志為“1”，則已命中，把提問號(hào)和記錄號(hào)寫入命中文檔。，則已命中，把提問號(hào)和記錄號(hào)寫入命中文檔。種類種類動(dòng)作動(dòng)作+在完成標(biāo)識(shí)欄置在完成標(biāo)識(shí)欄置“1”，再向父項(xiàng)移動(dòng)，再向父項(xiàng)移動(dòng)*N檢索處理檢索處理=N子項(xiàng)子項(xiàng)相等，標(biāo)識(shí)欄置相等，標(biāo)識(shí)欄置“1”，再向父項(xiàng)移，再向父項(xiàng)移動(dòng)動(dòng)不相等，就返回進(jìn)行下一詞的處理不相等，就返回進(jìn)行下一詞的處理-順著父項(xiàng)進(jìn)行注銷處理順著父項(xiàng)進(jìn)行注銷處理37/20 常見方法為逆波蘭展開法。3.4倒排文檔索引 是一種面向單詞的索引機(jī)制，相對(duì)順排文檔而言，是將順排文檔中可檢索

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

25、文檔的快速查詢，不同屬性的數(shù)據(jù)結(jié)構(gòu)構(gòu)成不同的倒排索引文檔。同的倒排索引文檔。2 2、倒排文檔的建立、倒排文檔的建立 選擇需要做索引的字段屬性(如作者、關(guān)鍵詞等)，抽出其中的內(nèi)容，并在其后附上記錄號(hào)抽詞抽詞 對(duì)抽出的內(nèi)容進(jìn)行排序，使之便于歸并相同內(nèi)容排序排序 對(duì)相同內(nèi)容進(jìn)行歸并，把合并后的內(nèi)容放入倒排文檔的主鍵字段(如標(biāo)引詞、作者等)，統(tǒng)計(jì)每一數(shù)據(jù)的頻次為目長(zhǎng)，把每一內(nèi)容后的記錄號(hào)順序放在記錄號(hào)集合字段歸并歸并40/20 3.4倒排文檔索引 記錄號(hào)篇名作者標(biāo)引詞1知識(shí)管理與企業(yè)管理信息系統(tǒng)建設(shè)A知識(shí)管理，管理信息系統(tǒng)，企業(yè)信息化2論知識(shí)鏈與知識(shí)管理B知識(shí)管理，知識(shí)鏈，學(xué)習(xí)型組織，知識(shí)創(chuàng)新3芻議知

26、識(shí)故那里及其體系框架C知識(shí)管理，知識(shí)創(chuàng)新，知識(shí)共享4知識(shí)管理的知識(shí)基礎(chǔ)A知識(shí)管理，學(xué)習(xí)型組織5論技術(shù)創(chuàng)新的知識(shí)空間C技術(shù)創(chuàng)新，知識(shí)空間，知識(shí)創(chuàng)新6建立企業(yè)競(jìng)爭(zhēng)性的信息結(jié)構(gòu)A企業(yè)信息化，信息結(jié)構(gòu)，競(jìng)爭(zhēng)情報(bào)7知識(shí)管理在企業(yè)競(jìng)爭(zhēng)情報(bào)研究中的應(yīng)用B知識(shí)管理，競(jìng)爭(zhēng)情報(bào)，知識(shí)創(chuàng)新8管理信息系統(tǒng)中文化行為研究B管理信息系統(tǒng)，企業(yè)文化9企業(yè)競(jìng)爭(zhēng)情報(bào)管理系統(tǒng)的構(gòu)建研究C管理信息系統(tǒng)，競(jìng)爭(zhēng)情報(bào)10企業(yè)知識(shí)管理主體研究C知識(shí)管理，企業(yè)文化，管理創(chuàng)新表表3-8 3-8 文獻(xiàn)及部分屬性舉例文獻(xiàn)及部分屬性舉例41/20 3.4倒排文檔索引 標(biāo)引詞目長(zhǎng)記錄號(hào)集合管理創(chuàng)新110管理信息系統(tǒng)31；8；9技術(shù)創(chuàng)新15競(jìng)爭(zhēng)情報(bào)36

27、；7；9企業(yè)文化28；10企業(yè)信息化21；6信息結(jié)構(gòu)16學(xué)習(xí)型組織22；4；知識(shí)創(chuàng)新42；3；5；7；知識(shí)共享13知識(shí)管理61；2；3；4；7；10知識(shí)空間15知識(shí)鏈12表表3-9 3-9 關(guān)鍵詞索引關(guān)鍵詞索引42/20 3.4倒排文檔索引 作者目長(zhǎng)記錄號(hào)集合A31；4；6B32；7；8C43；5；9;10表表3-10 3-10 作者索引作者索引建立倒排文檔的過程中需要注意：第一，倒排文檔的建立應(yīng)具有即時(shí)更新的功能。第二，需要建立一處文檔來解決不等長(zhǎng)問題。43/20 3.4倒排文檔索引 3.4.2 3.4.2 邏輯提問式的轉(zhuǎn)換邏輯提問式的轉(zhuǎn)換 1929年波蘭的邏輯學(xué)家盧卡西維茲提出將運(yùn)算符放在

28、運(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.4倒排文檔索引 運(yùn)算符運(yùn)算符優(yōu)先處理的級(jí)別優(yōu)先處理的級(jí)別（ ）1+2*3-4表表3-11 3-11 運(yùn)算符的優(yōu)先級(jí)運(yùn)算符的優(yōu)先級(jí)v為轉(zhuǎn)換處理開辟三個(gè)存儲(chǔ)區(qū)：為轉(zhuǎn)換處理開辟三個(gè)存儲(chǔ)區(qū)：檢索詞表存儲(chǔ)區(qū)逆波蘭輸出區(qū)123算子棧存放轉(zhuǎn)換過程中的運(yùn)算存放檢索詞存放邏輯提問式的逆波蘭表達(dá)式45/203.4倒排文檔索引 從左向右逐個(gè)掃描提問邏輯是的

29、字符，遇到不同的從左向右逐個(gè)掃描提問邏輯是的字符，遇到不同的對(duì)象做相應(yīng)處理：對(duì)象做相應(yīng)處理：對(duì)象類型對(duì)象類型處理動(dòng)作處理動(dòng)作運(yùn)算符運(yùn)算符P當(dāng)前當(dāng)前P前一前一為真，將該算符送算子棧內(nèi)為真，將該算符送算子棧內(nèi)為假，將頂部算符取出送逆波蘭輸出區(qū)，當(dāng)前算符再與棧內(nèi)為假，將頂部算符取出送逆波蘭輸出區(qū)，當(dāng)前算符再與棧內(nèi)頂部算符比較，當(dāng)前算符的優(yōu)先級(jí)低就取出送逆波蘭輸出區(qū)，頂部算符比較，當(dāng)前算符的優(yōu)先級(jí)低就取出送逆波蘭輸出區(qū)，否則就將該算符送算子棧內(nèi)否則就將該算符送算子棧內(nèi)左括號(hào)左括號(hào)將左括號(hào)無條件置入算子棧內(nèi)將左括號(hào)無條件置入算子棧內(nèi)右括號(hào)右括號(hào)棧內(nèi)括號(hào)間的所有算符無條件出棧，并送逆波蘭輸出去，同時(shí)放棄這

30、對(duì)括號(hào)棧內(nèi)括號(hào)間的所有算符無條件出棧，并送逆波蘭輸出去，同時(shí)放棄這對(duì)括號(hào)運(yùn)算項(xiàng)運(yùn)算項(xiàng)將運(yùn)算檢索項(xiàng)存入檢索詞表，并將其在檢索詞表的位置送逆波蘭輸出區(qū)將運(yùn)算檢索項(xiàng)存入檢索詞表，并將其在檢索詞表的位置送逆波蘭輸出區(qū)結(jié)束號(hào)結(jié)束號(hào)算子棧內(nèi)的算子依次出棧并送入逆波蘭輸出區(qū)算子棧內(nèi)的算子依次出棧并送入逆波蘭輸出區(qū)*其中，P當(dāng)前P前一：當(dāng)前算符的優(yōu)先級(jí)高于前一算符；為假時(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倒排文檔索引 地址地址檢索詞檢索詞0101A A0202B B0303C C0404EFEF特征特征內(nèi)容內(nèi)容0 001010 002021 1+ +0 003030 004041 1+ +1 1* *0 0* *v逆波蘭法處理示意圖逆波蘭法處理示意圖（+ +檢索詞表（A+B）*（C