[科普中國]-通用信息索引

信息索引技術

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

（1）需要有足夠的內存來存儲倒排表，對’J幾搜索引擎來說，都是G級別數(shù)據(jù)，特別是當規(guī)模不斷擴大時，難以提供這么多的內存。

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

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

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

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

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

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

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