[科普中國(guó)]-通用信息索引

信息索引技術(shù)

經(jīng)過(guò)網(wǎng)頁(yè)預(yù)處理后，可以建立索引數(shù)據(jù)庫(kù)。對(duì)于數(shù)目龐大的文檔數(shù)據(jù)庫(kù)使用簡(jiǎn)單匹配方法是不可行的，需要對(duì)文檔的表示建立索引。為了提高檢索效率，應(yīng)該按照一定的規(guī)則建立索引。索引文件一般是按照倒排文件的格式存放的，通用的信息索引的建立包括：

(1) 分析：處理文件中可能的錯(cuò)誤；

(2) 索引：完成分析的文件被編碼存入索引數(shù)據(jù)庫(kù)；

(3) 排序：將索引數(shù)據(jù)庫(kù)按照一定的規(guī)則排序，產(chǎn)生全文索引。1

順排索引技術(shù)順排索引的主要思想是將文檔中的每一條記錄依次去匹配用戶的檢索提問(wèn)集合，文檔處理完畢后，將各提問(wèn)的命中結(jié)果歸并分發(fā)給有關(guān)用戶。順排索引是用文檔中記錄一條一條去匹配提問(wèn)的，是順序?qū)ξ臋n記錄檢索的方法，所以也稱為順排文檔檢索。常用的順排索引方法主要有：表展開法、邏輯樹法等。

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

正排表是以文檔的ID為關(guān)鍵字，表中記錄文檔中每個(gè)字的位置信息，查找時(shí)掃描表中每個(gè)文檔中字的信息直到找出所有包含查詢關(guān)鍵字的文檔。正排表結(jié)構(gòu)如圖1所示，這種組織方法在建立索引的時(shí)候結(jié)構(gòu)比較簡(jiǎn)單，建立比較方便且易于維護(hù)；因?yàn)樗饕腔谖臋n建立的，若是有新的文檔加入，直接為該文檔建立一個(gè)新的索引塊，掛接在原來(lái)索引文件的后面。若是有文檔刪除，則直接找到該文檔號(hào)文檔對(duì)應(yīng)的索引信息，將其直接刪除。但是在查詢的時(shí)候需對(duì)所有的文檔進(jìn)行掃描以確保沒有遺漏，這樣就使得檢索時(shí)間大大延長(zhǎng)，檢索效率低下。

倒排索引技術(shù)倒排文檔是一種而向單詞的索引機(jī)制，相對(duì)順排文檔而言，是將順排文檔中可檢索字段的作者名、關(guān)健詞、分類號(hào)等取出，按一定規(guī)則排序，歸并相同詞匯，并把在順排文檔中相關(guān)記錄的記錄號(hào)集合賦予其后，以保證通過(guò)某一特征詞能夠快速、方便地獲取相關(guān)記錄。圖2是倒排索引的結(jié)構(gòu)圖。

倒排表以字或詞為關(guān)鍵字進(jìn)行索引，表中關(guān)鍵字所對(duì)應(yīng)的記錄表項(xiàng)記錄了出現(xiàn)這個(gè)字或詞的所有文檔，一個(gè)表項(xiàng)就是一個(gè)字表段，它記錄該文檔的ID和字符在該文檔中出現(xiàn)的位置情況。

由于每個(gè)字或詞對(duì)應(yīng)的文檔數(shù)量在動(dòng)態(tài)變化，所以倒排表的建立和維護(hù)都較為復(fù)雜，但是在查詢的時(shí)候由于可以一次得到查詢關(guān)鍵字所對(duì)應(yīng)的所有文檔，所以效率高于正排表。在全文檢索中，檢索的快速響應(yīng)是一個(gè)最為關(guān)鍵的性能，而索引建立由于在后臺(tái)進(jìn)行，盡管效率相對(duì)低一些，但不會(huì)影響整個(gè)搜索引擎的效率。倒排表的結(jié)構(gòu)圖如圖3所示。

倒排文檔倒排文檔的組成倒排文檔的組成元素主要包括：關(guān)鍵字(作者、主題詞、分類號(hào)等)、目長(zhǎng)(含有該關(guān)鍵字記錄的條數(shù))、記錄號(hào)集合(所有與該關(guān)鍵字有關(guān)的記錄號(hào))。

倒排文檔的建立倒排文檔的建立是建筑在順排文檔(主文檔)的基礎(chǔ)之上，它是從主文檔中提取可檢索字段內(nèi)容，也有采取自動(dòng)從標(biāo)題、文摘或全文中提取關(guān)鍵詞，利用所得到的這些屬性詞來(lái)建立倒排文檔。

由順排文檔構(gòu)造倒排文檔需要經(jīng)過(guò)抽詞、排序、歸并和組織等過(guò)程，具體實(shí)現(xiàn)步驟如下：

（1）選擇需要做索引的字段屬性(如作者、關(guān)鍵詞等)，抽出其中的內(nèi)容，并在其后附上其記錄號(hào)；

（2）對(duì)抽出的內(nèi)容進(jìn)行排序，使之便于歸并相同內(nèi)容；

（3）對(duì)相同內(nèi)容進(jìn)行歸并，把合并后的內(nèi)容放入倒排文檔的主鍵字段(如標(biāo)引詞、作者等)，統(tǒng)計(jì)每一數(shù)據(jù)的頻次作為目長(zhǎng)，把每一內(nèi)容后的記錄號(hào)順序放在記錄號(hào)集合字段。

通用信息索引的建立通用信息索引的構(gòu)建相當(dāng)于從正排表到倒排表的建立過(guò)程。主要的構(gòu)建方法有簡(jiǎn)單法和合并法。

簡(jiǎn)單法當(dāng)分析完網(wǎng)頁(yè)時(shí)，得到的是以網(wǎng)頁(yè)為主碼的索引表。當(dāng)索引建立完成后，應(yīng)得到倒排表，流程描述如下：

（1）將文檔分析稱單詞term標(biāo)記；

（2）使用hash去重單詞term；

（3）對(duì)單詞生成倒排列表。

倒排列表就是文檔編號(hào)DocID，沒有包含其他的信息(如詞頻，單詞位置等)，這就是簡(jiǎn)單的索引。

簡(jiǎn)單索引功能可以用于小數(shù)據(jù)，例如索引幾千個(gè)文檔。然而它有兩點(diǎn)限制：

（1）需要有足夠的內(nèi)存來(lái)存儲(chǔ)倒排表，對(duì)’J幾搜索引擎來(lái)說(shuō)，都是G級(jí)別數(shù)據(jù)，特別是當(dāng)規(guī)模不斷擴(kuò)大時(shí)，難以提供這么多的內(nèi)存。

（2）算法是順序執(zhí)行，不便于并行處理。

合并法（1）頁(yè)面分析，生成臨時(shí)倒排數(shù)據(jù)索引A、B，當(dāng)臨時(shí)倒排數(shù)據(jù)索引A,、B占滿內(nèi)存后，將內(nèi)存索引A、 B寫入臨時(shí)文件生成臨時(shí)倒排文件；

（2）對(duì)生成的多個(gè)臨時(shí)倒排文件，執(zhí)行多路歸并，輸出得到最終的倒排文件。

通用信息索引更新策略完全重建策略當(dāng)新增文檔到達(dá)一定數(shù)量，將新增文檔和原先的老文檔整合，然后利用靜態(tài)索引創(chuàng)建方法對(duì)所有文檔重建索引，新索引建立完成后老索引會(huì)被遺棄。此法代價(jià)高，但是主流商業(yè)搜索引擎一股是采用此方式來(lái)維護(hù)索引的更新。

再合并策略當(dāng)新增文檔進(jìn)入系統(tǒng)，解析文檔，之后更新內(nèi)存中維護(hù)的臨時(shí)索引，文檔中出現(xiàn)的每個(gè)單詞，在其倒排表列表末尾追加倒排表列表項(xiàng);一旦臨時(shí)索引將指定內(nèi)存消耗光，即進(jìn)行一次索引合并，這里需要倒排文件里的倒排列表存放順序已經(jīng)按照索引單詞字典順序由低到高排序，這樣直接順序掃描合井即可。其缺點(diǎn)是：因?yàn)橐尚碌牡古潘饕募?，所以?duì)老索引中的很多單詞，盡管其在倒排列表并未發(fā)生任何變化，也需要將其從老索引中取出來(lái)并寫入新索引中，這樣對(duì)磁盤消耗是沒必要的。

原地更新策略試圖改進(jìn)再合并策略，在原地合并倒排表，這需要提前分配一定的空間給未來(lái)插入，如果提前分配的空間l不夠了需要遷移。

混合策略能夠結(jié)合不同索引更新策略的長(zhǎng)處，將不同索引更新策略混合，以形成更高效的方法。1