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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

存儲(chǔ)原始的權(quán)重因子，是為了在查找的時(shí)候更方便的計(jì)算詞項(xiàng)權(quán)重?？梢园?df、tf、最大頻度、總文檔數(shù)等等。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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