通用信息索引

信息索引技術是信息檢索的關鍵技術，它的性能直接影響到搜尋結果的準確性。通用信息索引的建立包括分析、索引和排序三個步驟。典型的信息索引技術有順排索引技術和倒排索引技術，其中，倒排索引技術是信息檢索系統中最普遍使用的索引機制。

基本介紹

• 中文名：通用信息索引
• 外文名：universal information index
• 領域：計算機
• 性質：信息索引是信息檢索的關鍵技術
• 建立步驟：分析、索引和排序
• 建立方法：簡單法、合併法

技術介紹

經過網頁預處理後，可以建立索引資料庫。對於數目龐大的文檔資料庫使用簡單匹配方法是不可行的，需要對文檔的表示建立索引。為了提高檢索效率，應該按照一定的規則建立索引。索引檔案一般是按照倒排檔案的格式存放的，通用的信息索引的建立包括：

(1) 分析：處理檔案中可能的錯誤；

(2) 索引：完成分析的檔案被編碼存入索引資料庫；

(3) 排序：將索引資料庫按照一定的規則排序，產生全文索引。

順排索引

順排索引的主要思想是將文檔中的每一條記錄依次去匹配用戶的檢索提問集合，文檔處理完畢後，將各提問的命中結果歸併分發給有關用戶。順排索引是用文檔中記錄一條一條去匹配提問的，是順序對文檔記錄檢索的方法，所以也稱為順排文檔檢索。常用的順排索引方法主要有：表展開法、邏輯樹法等。

順排索引的關鍵技術是採用列表(正派表)處理方法將提問邏輯式(檢索式)變換成等價的提問展開式，按提問展開表的內容對順排文檔的每篇文獻進行檢索。

正排表是以文檔的ID為關鍵字，表中記錄文檔中每個字的位置信息，查找時掃描表中每個文檔中字的信息直到找出所有包含查詢關鍵字的文檔。正排表結構如圖1所示，這種組織方法在建立索引的時候結構比較簡單，建立比較方便且易於維護；因為索引是基於文檔建立的，若是有新的文檔加入，直接為該文檔建立一個新的索引塊，掛接在原來索引檔案的後面。若是有文檔刪除，則直接找到該文檔號文檔對應的索引信息，將其直接刪除。但是在查詢的時候需對所有的文檔進行掃描以確保沒有遺漏，這樣就使得檢索時間大大延長，檢索效率低下。

圖1 正排表結構圖

倒排索引

倒排文檔是一種而向單詞的索引機制，相對順排文檔而言，是將順排文檔中可檢索欄位的作者名、關健詞、分類號等取出，按一定規則排序，歸併相同辭彙，並把在順排文檔中相關記錄的記錄號集合賦予其後，以保證通過某一特徵詞能夠快速、方便地獲取相關記錄。圖2是倒排索引的結構圖。

圖2 倒排索引結構圖

倒排表以字或詞為關鍵字進行索引，表中關鍵字所對應的記錄表項記錄了出現這個字或詞的所有文檔，一個表項就是一個字表段，它記錄該文檔的ID和字元在該文檔中出現的位置情況。

由於每個字或詞對應的文檔數量在動態變化，所以倒排表的建立和維護都較為複雜，但是在查詢的時候由於可以一次得到查詢關鍵字所對應的所有文檔，所以效率高於正排表。在全文檢索中，檢索的快速回響是一個最為關鍵的性能，而索引建立由於在後台進行，儘管效率相對低一些，但不會影響整個搜尋引擎的效率。倒排表的結構圖如圖3所示。

圖3 倒排表結構圖

倒排文檔

組成

倒排文檔的組成元素主要包括：關鍵字(作者、主題詞、分類號等)、目長(含有該關鍵字記錄的條數)、記錄號集合(所有與該關鍵字有關的記錄號)。

建立

倒排文檔的建立是建築在順排文檔(主文檔)的基礎之上，它是從主文檔中提取可檢索欄位內容，也有採取自動從標題、文摘或全文中提取關鍵字，利用所得到的這些屬性詞來建立倒排文檔。

由順排文檔構造倒排文檔需要經過抽詞、排序、歸併和組織等過程，具體實現步驟如下：

（1）選擇需要做索引的欄位屬性(如作者、關鍵字等)，抽出其中的內容，並在其後附上其記錄號；

（2）對抽出的內容進行排序，使之便於歸併相同內容；

（3）對相同內容進行歸併，把合併後的內容放入倒排文檔的主鍵欄位(如標引詞、作者等)，統計每一數據的頻次作為目長，把每一內容後的記錄號順序放在記錄號集合欄位。

索引的建立

通用信息索引的構建相當於從正排表到倒排表的建立過程。主要的構建方法有簡單法和合併法。

簡單法

當分析完網頁時，得到的是以網頁為主碼的索引表。當索引建立完成後，應得到倒排表，流程描述如下：

（1）將文檔分析稱單詞term標記；

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

（3）對單詞生成倒排列表。

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

簡單索引功能可以用於小數據，例如索引幾千個文檔。然而它有兩點限制：

（1）需要有足夠的記憶體來存儲倒排表，對’J幾搜尋引擎來說，都是G級別數據，特別是當規模不斷擴大時，難以提供這么多的記憶體。

（2）算法是順序執行，不便於並行處理。

合併法

（1）頁面分析，生成臨時倒排數據索引A、B，當臨時倒排數據索引A,、B占滿記憶體後，將記憶體索引A、 B寫入臨時檔案生成臨時倒排檔案；

（2）對生成的多個臨時倒排檔案，執行多路歸併，輸出得到最終的倒排檔案。

更新策略

完全重建

當新增文檔到達一定數量，將新增文檔和原先的老文檔整合，然後利用靜態索引創建方法對所有文檔重建索引，新索引建立完成後老索引會被遺棄。此法代價高，但是主流商業搜尋引擎一股是採用此方式來維護索引的更新。

再合併

當新增文檔進入系統，解析文檔，之後更新記憶體中維護的臨時索引，文檔中出現的每個單詞，在其倒排表列表末尾追加倒排表列表項;一旦臨時索引將指定記憶體消耗光，即進行一次索引合併，這裡需要倒排檔案里的倒排列表存放順序已經按照索引單詞字典順序由低到高排序，這樣直接順序掃描合井即可。其缺點是：因為要生成新的倒排索引檔案，所以對老索引中的很多單詞，儘管其在倒排列表並未發生任何變化，也需要將其從老索引中取出來並寫入新索引中，這樣對磁碟消耗是沒必要的。

原地更新

試圖改進再合併策略，在原地合併倒排表，這需要提前分配一定的空間給未來插入，如果提前分配的空間l不夠了需要遷移。

混合

能夠結合不同索引更新策略的長處，將不同索引更新策略混合，以形成更高效的方法。