文件組織架構(gòu)，也稱 index (索引)，常用于提升一個檢索系統(tǒng)的性能。

回顧向量空間模型，我們知道在查詢時，命中的 doc 應(yīng)該是與 query 最為相近的幾個向量。當查詢時，若只在所有 可能相似的文檔 （至少含有一個 query 中的關(guān)鍵詞）中查找，可以大大減少資源浪費。

那么就需要先得到 query 中各個 term 出現(xiàn)過的文檔，再取 并集 ，最后在并集中進行相似度的計算——「 過濾 」思想。

此時用特殊的索引方式，就可以更快地實現(xiàn)文檔的過濾。有人提出 Hash 的設(shè)想，但是 Hash 的缺點在于不能模糊匹配，當用戶的 Query 和詞典中的 term 略有差距時，可能在 hash table 中會相距十分遙遠。

我們通過一組對比，引入「 倒排 」的概念：

由此我們可以得到倒排文件組織架構(gòu)的 構(gòu)成 ：

有了上述的架構(gòu)，當用戶輸入 query 時，我們可以提取出 term，直接訪問對應(yīng)的 Index file，再根據(jù)鏈接來到 Posting file。對于多個 term，可以先完成交、并等邏輯運算，得到結(jié)果后，再去訪問過濾后的文檔集。

由此，我們可以知道當爬取到新的文檔時，構(gòu)建索引的步驟：

接下來介紹搜索引擎如何解析一個新爬取到的文檔，這個過程往往是離線進行的（在線進行的是用戶查詢過程）。

而由于文檔的多樣性，往往解析過程中會面臨各式各樣的問題：文件格式、各國語言、字符編碼、停用詞等。這些問題往往用 啟發(fā)式 （heuristically）的方法解決。

Token 來自文檔的原始字符串，是根據(jù)空格劃分提取出的原始單詞。在實際中，要考慮：是否保留 's 、是否保留連字符、專有名詞是否拆開、數(shù)字嵌入等子問題。

而針對不同語言，也有更多新的問題：法語中大量的 ' 使用、德語中名詞復(fù)合現(xiàn)象、中文日文不適用空格分詞、日語的平假片假、阿拉伯語的書寫次序等。

在文本中，往往還需要把最頻繁出現(xiàn)的無意義詞停用。在文檔解析中，如何利用停用詞進行壓縮空間？在查詢優(yōu)化中，如何判別停用詞？當停用詞有意義時，如何識別？這些都是需要考慮的問題。

在英語中，通常時以定義「 等價集 」（equivalence classing）來歸并詞項。通常將單詞歸并到其原型，而對于特殊的單詞有特殊的規(guī)則，例如規(guī)定 “U.S.A.” 歸并于 “USA”，規(guī)定 “anti-discriminatory” 歸并于 “antidiscriminatory”。

對于有的單詞，不同形式可能含有不同語義，例如 window/windows/Windows。此時在查詢時可以先做 不對稱展開 （asymmetric expansion），對展開項搜索后取并集。

主要針對 Synonyms (同義詞)、Homonyms (同形同音異義詞)，這種情況下也可以利用等價集和不對稱展開解決。

此外，當用戶查詢中有英文拼寫錯誤時，常用的方法是 Soundex (探測法)，返回同音字串。Soundex 是基于語音啟發(fā)式方法生成的 語音等價集 。這種方法在漢語拼音中同樣有很大應(yīng)用。

將單詞的名詞、動詞、形容詞等形式統(tǒng)一歸并到 詞根 ，將單復(fù)數(shù)、人稱所有格、時態(tài)等統(tǒng)一歸并到 原型 。

解析完文檔后，我們可以將新的文檔直接存入文檔集，也可以利用 摘要生成 技術(shù)生成 Surrogates (文檔替代品)，減少存儲空間。

此外，當我們搜索到頁面文檔時，其文件格式可能各不相同，如 HTML、XML 等，故檢索到網(wǎng)頁后還需要進行 Page Purifing (文檔凈化)，從而獲得便于識別的文本文檔和內(nèi)部鏈接。

之前的文章介紹過，用于連接 term 和 doc 的詞典表往往是個稀疏矩陣。而倒排文件用 鏈表 的形式存儲每一行的內(nèi)容，即包含此 term 的所有 doc 及其基本信息，串接而成。鏈表中的每個元素稱為一個 posting (記錄)。

其中，基本信息可以包含：Document ID (文檔的唯一標識)、Location Pointer (該文檔在 Doc file 中的位置)、原始的權(quán)重因子。

存儲原始的權(quán)重因子，是為了在查找的時候更方便的計算詞項權(quán)重。可以包括 df、tf、最大頻度、總文檔數(shù)等等。

此外，鏈表中的元素以 Doc ID 排序，這樣存儲有利于多頁倒排表的 合并 匹配。

索引文件通常以詞典的形式存儲 term ID、含有該 term 的文檔數(shù)以及該 term 在記錄文件中的位置（指針）。

以下列出幾種常用的索引文件組織形式：

前文提到，在解析一篇文檔獲得索引時，最簡單的方法就是先提取 token，再獲得 term 作為索引。而在真正高效的索引模型（Index Model）中，往往要先對文檔進行 特征選取 ，從而構(gòu)成索引。

而特征選擇問題，可以轉(zhuǎn)化為詞項權(quán)重（term weighting）計算，一篇文檔中權(quán)重較大的 term 往往更能表示這篇文檔。

在前面的文章中有提到，tf 及其衍生的權(quán)重計算方法，是 IR 模型中最常用的權(quán)重計算方法。這里就不再重復(fù)介紹，僅提及一個有趣的定理 Zipf's Law 。

該定理描述了如下現(xiàn)象：在一個大的文檔集中，統(tǒng)計出各個詞項的 tf 排名后，記排名為 r ，頻率為 f ，則有

而在實際中，排名最高的詞項通常都是停用詞，最「 重要 」的詞往往詞頻不是很高，而最罕見的詞往往沒有普遍價值。這也與 tf·idf 的思想契合，下圖說明了這一點。

在倒排文檔中，移除停用詞和罕見詞、保留重要詞，可以節(jié)約大量的記錄空間。

對于一個確定大小的文檔集，需要多少詞項才能很好的索引全部文檔呢？這便是根據(jù)文檔集大小確定詞典大?。↙exicon Size）的問題。 Heap's Law 對此進行了估算：

其中， K 通常取 10 到 100 間的整數(shù)， 通常取 0.4 到 0.6 之間的小數(shù)。繪制出的圖如下：

在一個向量空間中，文檔由 基向量 加權(quán)構(gòu)成的向量表示。

我們可以計算文檔之間的相似度，相似度越高，代表空間越緊湊，反之則越松散。計算文檔集兩兩之間的相似度需要 的復(fù)雜度。

當然，如果先計算出一個「 平均文檔 」，再計算其他文檔與其的相似度，則只需要 的復(fù)雜度。

詞項判別模型則是通過 引入 一個新的 term 作為基向量，觀察相似度的變化分析該 term 的重要性。大致的思想是：