第三章

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

本章內(nèi)容順序文檔索引基于內(nèi)存單次掃描的索引構(gòu)建技術(shù)基于塊的排序索引技術(shù)本章小結(jié)倒排文檔索引概要概要

基于文本的檢索技術(shù)信息檢索技術(shù)基于內(nèi)容的檢索技術(shù)概要概要

順排文檔把記錄按照一定順序完整地組織起來如：物品數(shù)據(jù)庫依據(jù)物品記錄號順序進(jìn)行建立。順排文檔（SequentialFile）把順排文檔中具有檢索屬性的項(xiàng)目信息抽取出來，重新排列組織成新的數(shù)據(jù)文檔如：將物品數(shù)據(jù)庫中的價(jià)格數(shù)據(jù)項(xiàng)抽取出來，依據(jù)物品價(jià)格有高到低重新建立新的索引文檔。倒排文檔（InvertedFile）

3.1基于塊的排序索引技術(shù)3.1.1索引文檔建立必須考慮的硬件性能

3.1基于塊的排序索引技術(shù)

利用緩沖區(qū)壓縮數(shù)據(jù)硬件性能連續(xù)存放數(shù)據(jù)塊內(nèi)存調(diào)用利用磁盤

3.1基于塊的排序索引技術(shù)內(nèi)存調(diào)用：訪問內(nèi)存數(shù)據(jù)比訪問磁盤數(shù)據(jù)快得多（5×10?9sVS2×10?8s），盡可能地把數(shù)據(jù)放在內(nèi)存中。

連續(xù)存放數(shù)據(jù)塊：磁盤的尋道時(shí)間平均為4ms-5ms，連續(xù)讀取的數(shù)據(jù)塊也應(yīng)該在磁盤上連續(xù)存放。

3.1基于塊的排序索引技術(shù)利用緩沖區(qū)：操作系統(tǒng)往往以數(shù)據(jù)塊為單位進(jìn)行讀寫。數(shù)據(jù)塊的大小通常為8KB、16KB、32KB或64KB。

壓縮數(shù)據(jù)：數(shù)據(jù)從磁盤傳輸?shù)絻?nèi)存是由系統(tǒng)總線而不是處理器來實(shí)現(xiàn)的，這意味著在磁盤I/0時(shí)處理器仍然可以處理數(shù)據(jù)。

3.1基于塊的排序索引技術(shù)

利用磁盤：系統(tǒng)的服務(wù)器往往有數(shù)GB甚至數(shù)十GB的內(nèi)存，可以利用服務(wù)器磁盤空間大小一般比內(nèi)存大小要高幾個(gè)數(shù)量級：TB-PB。

3.1基于塊的排序索引技術(shù)

3.1.2基于塊的排序索引方法

首先掃描一篇文檔集合得到所有具有檢索意義的詞語的“此項(xiàng)-文檔ID”數(shù)據(jù)集；然后依據(jù)此項(xiàng)的索引文檔及的主鍵和文檔ID為次鍵進(jìn)行排序；最后將每個(gè)此項(xiàng)的文檔ID組織成為倒排記錄表，并計(jì)算此項(xiàng)頻率或文檔頻率的統(tǒng)計(jì)量。思想

圖3-1桂林電子科技大學(xué)-新聞模塊目錄實(shí)例3.1基于塊的排序索引技術(shù)

3.1基于塊的排序索引技術(shù)

圖3-2桂林電子科技大學(xué)-新聞內(nèi)容文檔實(shí)例

3.1基于塊的排序索引技術(shù)

符號含義統(tǒng)計(jì)值N文檔總量900000L每篇文檔的平均詞項(xiàng)數(shù)量160M詞項(xiàng)目總數(shù)190000每個(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ù)40000000

表3-1桂林電子科技大學(xué)-新聞文檔集統(tǒng)計(jì)數(shù)據(jù)表

3.1基于塊的排序索引技術(shù)基于磁盤的外部排序算法ESA（ExternalSortingAlgorithm）核心在索引排序時(shí)，盡量減少磁盤尋道次數(shù)基礎(chǔ)BSBI算法（BlockedSort-basedIndexingAlgorithm,基于塊的排序算法）

3.1基于塊的排序索引技術(shù)

BSBI算法步驟：1將文檔集分割成多個(gè)大小相等的部分4將所有的中間文件合并成最終的索引2將每個(gè)部分的詞項(xiàng)ID—文檔ID對排序3將中間產(chǎn)生的臨時(shí)排序結(jié)果存放到磁盤中

3.1基于塊的排序索引技術(shù)

選擇合適的塊算法，下圖的算法將每個(gè)塊的倒排索引存入文件中f1…fn，最后合并為fmerged。

圖3-3基于塊的排序索引算法

3.1基于塊的排序索引技術(shù)

依據(jù)圖3-3的算法將待合并的倒排記錄表（兩個(gè)數(shù)據(jù)塊）從磁盤讀入內(nèi)存，然后在內(nèi)存中合并后寫入磁盤（見圖3-4）。

圖3-4基于塊的排序方法合并示意圖

3.2基于內(nèi)存單次掃描的排序構(gòu)建技術(shù)

基于內(nèi)存單次掃描的索引算法SPIMI(single-passin-memoryindexing)：每塊采用不同的詞典，將每個(gè)塊的詞典寫入磁盤，對于下一個(gè)塊則重新采用新的詞典。只要硬盤空間足夠大，SPIMI就能夠索引任何大小的文檔集。原因基于塊的排序索引算法具有很好的可擴(kuò)展性，但是需要一種將所有詞項(xiàng)放到內(nèi)存。對于大規(guī)模的文檔集來說，該數(shù)據(jù)結(jié)構(gòu)會(huì)很大以致在內(nèi)存中難以存放。

3.2基于內(nèi)存單次掃描的排序構(gòu)建技術(shù)

SPIMI算法的步驟：ClicktoaddTitleClicktoaddTitleClicktoaddTitle2將所有的中間文件合并成最終的索引1處理文檔，直到內(nèi)存不足，寫入磁盤

3.2基于內(nèi)存單次掃描的排序構(gòu)建技術(shù)

圖3-5SPIMI算法的塊倒排索引生成算法

3.2基于內(nèi)存單次掃描的排序構(gòu)建技術(shù)

SPIMI算法與BSBI的區(qū)別：通過判定循環(huán)動(dòng)態(tài)增加排序記錄表的，倒排記錄表的SPIMI算法直接在倒排記錄表中增加定位符項(xiàng)，且開始就需要處理形成所有項(xiàng)的“詞項(xiàng)－文檔ＩＤ”并進(jìn)行排序BSBI算法

3.3順排文檔索引

將文檔中的每一條記錄依次去匹配用戶的檢索提問集合，文檔處理完畢后，將各提問的命中結(jié)果歸并分發(fā)給有關(guān)用戶。思想

用文檔中記錄一條一條去匹配提問的，是順序?qū)ξ臋n記錄檢索的方法定義

采用列表處理方法將提問邏輯式（檢索式）變換成等價(jià)的提問展開式，按提問展開表的內(nèi)容對順排文檔的每篇文獻(xiàn)進(jìn)行檢索關(guān)鍵技術(shù)表展開法、邏輯樹法等常見方法

3.3順排文檔索引

3.3.1表展開法索引

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

3.3順排文檔索引

1、展開表的含義

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

2、展開表生成過程

檢索詞檢索運(yùn)算符改變運(yùn)算次序的括號供檢索匹配的表格前處理

3.3順排文檔索引

前處理判斷提問式中的字符，從上而下填寫表格。對不同類型對象的處理方式如下：表3-3對不同類型對象的處理表類型符號處理方式檢索詞將其存入展開表內(nèi)的檢索詞欄，并記下在表中的地址運(yùn)算符+前一詞滿足，指向“*”；不滿足，指向后一詞*前一詞滿足，指向后一詞括號（在其后的檢索詞所在行的“級位”欄值加1）在其后的檢索詞所在行的“級位”欄值減1括號結(jié)束最后一個(gè)檢索詞所在行的“條件滿足指向”欄放入“命中”，“條件不滿足”放入“落選”

3.3順排文檔索引

后處理后處理的主要任務(wù)就是填滿整個(gè)表的空白單元，填表的依據(jù)是表中“級位”欄的前后級位值，填表的順序是從下向上，直至表的頂部，從而得到一個(gè)完整的提問展開表。

3.3順排文檔索引

3、表展開法的檢索應(yīng)用描述

每讀取一條記錄，就生成一個(gè)檢索標(biāo)識表（可檢索項(xiàng)），然后將該表中的檢索項(xiàng)去查展開表，并對命中的做上標(biāo)記。查匹配

根據(jù)展開表查詢情況，分析提問是否命中。命中者，就在相應(yīng)的提問號下記下記錄號及相關(guān)信息，取下條記錄進(jìn)行對比。檢索項(xiàng)查完

得到本次檢索的最終結(jié)果通過提問號調(diào)出檢索結(jié)果中各自命中結(jié)果的記錄給用戶。全部匹配完3.3順排文檔索引

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

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)地址以及檢索處理登記欄。運(yùn)算類型子項(xiàng)類型父項(xiàng)地址處理標(biāo)志檢索處理表3-4主邏輯樹表結(jié)構(gòu)

3.3順排文檔索引

（2）檢索詞地址表

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

3.3順排文檔索引

（3）檢索詞位置表

檢索詞位置表是在邏輯提問式轉(zhuǎn)換成邏輯樹表的過程中，臨時(shí)生成的一個(gè)中間處理過程表，該表還將作為從邏輯提問式到詞邏輯樹子表的橋梁，一旦子表生成完畢，該表將被清除。表3-6檢索詞位置表結(jié)構(gòu)檢索詞種類起始位置終止位置

3.3順排文檔索引

（4）中間工作表

由于在進(jìn)行邏輯提問式到邏輯樹表的轉(zhuǎn)換過程中，涉及一些中間數(shù)據(jù)，這些數(shù)據(jù)在生成邏輯樹時(shí)需多次使用，因此需要建立一個(gè)中間過程工作區(qū)（中間工作表）來記錄這些數(shù)據(jù)，一旦主邏輯樹生成完畢，該表即可以清除。

表3-7中間工作表結(jié)構(gòu)起始位置終止位置父項(xiàng)地址輔助信息

3.3順排文檔索引

（5）主邏輯樹表的生成

主邏輯樹表的生成算法思想為：采用多次掃描的分層分解構(gòu)造法。首先分解出邏輯式中最外層“＋”號下的子項(xiàng)，括號內(nèi)的項(xiàng)暫時(shí)不分解；其次掃描已分解出的子項(xiàng)（在最外層沒有“＋”項(xiàng)的情況下對整個(gè)邏輯式進(jìn)行）中的“*”號的運(yùn)算子項(xiàng)，若該子項(xiàng)為括號括起項(xiàng)，則仍分解“＋”號子項(xiàng)；最后分解“-”號子項(xiàng)。

3.3順排文檔索引2、邏輯樹法檢索應(yīng)用

邏輯提問式最終轉(zhuǎn)換為邏輯樹的三個(gè)表：主邏輯樹表、檢索詞地址表、檢索詞字符樹表。這三個(gè)表構(gòu)成了用戶檢索提問文檔，整個(gè)檢索主要依賴這三個(gè)表。實(shí)際檢索過程為：從文檔中讀取一條記錄，將記錄中的標(biāo)引項(xiàng)（主題詞、責(zé)任者、分類號等可供檢索的著錄項(xiàng)）去匹配相關(guān)的檢索詞邏輯樹，匹配成功者，根據(jù)檢索詞地址指針去判斷檢索詞地址表對應(yīng)的檢索登錄區(qū)，若為“1”，表明該吃已命中過，不需要在處理；若為“0”，則將該項(xiàng)置為“1”，同時(shí)根據(jù)本行的“主表位置”字段去修改主邏輯樹表。

3.3順排文檔索引

對主邏輯樹表的檢索處理如下：在主邏輯樹表中該詞的“處理標(biāo)志”欄中填上“1”，然后根據(jù)父項(xiàng)地址的指針找到父項(xiàng)行，對“檢索處理”欄作加“1”運(yùn)算，再查看“處理標(biāo)識”欄，若為“1”，表示該子項(xiàng)已做過向上遍歷處理，可返回進(jìn)行下一詞的處理；若為“0”，則根據(jù)“運(yùn)算種類”做相應(yīng)的處理。隨著父項(xiàng)指針移動(dòng)到頂行時(shí)，若該行的處理標(biāo)志為“1”，則已命中，把提問號和記錄號寫入命中文檔。種類動(dòng)作+在完成標(biāo)識欄置“1”，再向父項(xiàng)移動(dòng)*N檢索處理=N子項(xiàng)相等，標(biāo)識欄置“1”，再向父項(xiàng)移動(dòng)不相等，就返回進(jìn)行下一詞的處理-順著父項(xiàng)進(jìn)行注銷處理

常見方法為逆波蘭展開法。3.4倒排文檔索引

是一種面向單詞的索引機(jī)制，相對順排文檔而言，是將順排文檔中可檢索字段的作者名、關(guān)鍵詞、分類號等取出，按一定規(guī)則排序，歸并相同詞匯，并把在順排文檔中相關(guān)記錄的記錄號集合賦予其后，以保證通過某一特征詞能夠快速、方便地獲取相關(guān)記錄。思想

3.4倒排文檔索引

3.4.1倒排文檔索引的建立

倒排文檔的組成元素如下：關(guān)鍵字目長記錄號集合作者主題詞分類號含有該關(guān)鍵字記錄的條數(shù)所有與該關(guān)鍵字有關(guān)的記錄號

3.4倒排文檔索引

1、倒排文檔的結(jié)構(gòu)

倒排文檔可視為主文檔的輔助索引，它從不同的角度提供了對主文檔的快速查詢，不同屬性的數(shù)據(jù)結(jié)構(gòu)構(gòu)成不同的倒排索引文檔。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)容后的記錄號順序放在記錄號集合字段歸并

3.4倒排文檔索引

記錄號篇名作者標(biāo)引詞1知識管理與企業(yè)管理信息系統(tǒng)建設(shè)A知識管理，管理信息系統(tǒng)，企業(yè)信息化2論知識鏈與知識管理B知識管理，知識鏈，學(xué)習(xí)型組織，知識創(chuàng)新3芻議知識故那里及其體系框架C知識管理，知識創(chuàng)新，知識共享4知識管理的知識基礎(chǔ)A知識管理，學(xué)習(xí)型組織5論技術(shù)創(chuàng)新的知識空間C技術(shù)創(chuàng)新，知識空間，知識創(chuàng)新6建立企業(yè)競爭性的信息結(jié)構(gòu)A企業(yè)信息化，信息結(jié)構(gòu)，競爭情報(bào)7知識管理在企業(yè)競爭情報(bào)研究中的應(yīng)用B知識管理，競爭情報(bào)，知識創(chuàng)新8管理信息系統(tǒng)中文化行為研究B管理信息系統(tǒng)，企業(yè)文化9企業(yè)競爭情報(bào)管理系統(tǒng)的構(gòu)建研究C管理信息系統(tǒng)，競爭情報(bào)10企業(yè)知識管理主體研究C知識管理，企業(yè)文化，管理創(chuàng)新表3-8文獻(xiàn)及部分屬性舉例

3.4倒排文檔索引

標(biāo)引詞目長記錄號集合管理創(chuàng)新110管理信息系統(tǒng)31；8；9技術(shù)創(chuàng)新15競爭情報(bào)36；7；9企業(yè)文化28；10企業(yè)信息化21；6信息結(jié)構(gòu)16學(xué)習(xí)型組織22；4；知識創(chuàng)新42；3；5；7；知識共享13知識管理61；2；3；4；7；10知識空間15知識鏈12表3-9關(guān)鍵詞索引

3.4倒排文檔索引

作者目長記錄號集合A31；4；6B32；7；8C43；5；9;10表3-10作者索引建立倒排文檔的過程中需要注意：第一，倒排文檔的建立應(yīng)具有即時(shí)更新的功能。第二，需要建立一處文檔來解決不等長問題。

3.4倒排文檔索引

3.4.2邏輯提問式的轉(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)換。

3.4倒排文檔索引

運(yùn)算符優(yōu)先處理的級別（）1+2*3-4表3-11運(yùn)算符的優(yōu)先級為轉(zhuǎn)換處理開辟三個(gè)存儲區(qū)：檢索詞表存儲區(qū)逆波蘭輸出區(qū)123算子棧存放轉(zhuǎn)換過程中的運(yùn)算存放檢索詞存放邏輯提問式的逆波蘭表達(dá)式3.4倒排文檔索引

從左向右逐個(gè)掃描提問邏輯是的字符，遇到不同的對象做相應(yīng)處理：對象類型處理動(dòng)作運(yùn)算符P當(dāng)前>P前一為真，將該算符送算子棧內(nèi)為假，將頂部算符取出送逆波蘭輸出區(qū)，，當(dāng)前算符再與棧內(nèi)頂部算符比較，當(dāng)前算符的優(yōu)先級低就取出送逆波蘭輸出區(qū)，否則就將該算符送算子棧內(nèi)左括號將左括號無條件置入算子棧內(nèi)右括號棧內(nèi)括號間的所有算符無條件出棧，并送逆波蘭輸出去，同時(shí)放棄這對括號運(yùn)算項(xiàng)將運(yùn)算檢索項(xiàng)存入檢索詞表，并將其在檢索詞表的位置送逆波蘭輸出區(qū)結(jié)束號算子棧內(nèi)的算子依次出棧并送入逆波蘭輸出區(qū)*其中，P當(dāng)前>P前一：當(dāng)前算符的優(yōu)先級高于前一算符；為假時(shí)，包括相等。3.4倒排文檔索引

注意兩點(diǎn)：1、棧的規(guī)則是元素“先進(jìn)后出”，轉(zhuǎn)換結(jié)束其棧為空2、逆波蘭輸出去的算子特征為1，檢索詞特征為03.4倒排文檔索引

地址檢索詞01A02B03C04EF……特征內(nèi)容0010021+0030041+1*0*逆波蘭法處理示意圖（+…檢索詞表（A+B）*（C+EF）詞表地址算子區(qū)分運(yùn)算項(xiàng)

還是運(yùn)算符逆波蘭輸出區(qū)邏輯提問式算子棧圖3-6逆波蘭轉(zhuǎn)換處理示意圖3.4倒排文檔索引3.4.3檢索指令表的生成

逐行掃描逆波蘭輸出表，實(shí)現(xiàn)從逆波蘭表轉(zhuǎn)換為檢索指令表。操作指令表由四列元素組成：第一列為操作碼，指定本行操作類型；以后三列為操作