數學之美 系列一 -- 統計語言模型
2006年4月3日 上午 08:15:00
從本周開始，我們將定期刊登 Google 科學家吳軍寫的《數學之美》系列文章，介紹數學在訊息檢索和自然語言處理中的主導作用和奇妙應用。

發表者: 吳軍, Google 研究員

前言

也許大家不相信，數學是解決訊息檢索和自然語言處理的最好工具。它能非常清晰地描述這些領域的實際問題並且給出漂亮的解決辦法。每當人們應用數學工具解決一個語言問題時，總會感嘆數學之美。我們希望利用 Google 中文黑板報這塊園地，介紹一些數學工具，以及我們是如何利用這些工具來開發 Google 產品的。

系列一︰ 統計語言模型 (Statistical Language Models)

Google 的使命是整合全球的訊息，所以我們一直致力於研究如何讓機器對訊息、語言做最好的理解和處理。長期以來，人類一直夢想著能讓機器代替人來翻譯語言、識別語音、認識文字（不論是印刷體或手寫體）和進行海量文獻的自動檢索，這就需要讓機器理解語言。但是人類的語言可以說是訊息裡最複雜最動態的一部分。為了解決這個問題，人們容易想到的辦法就是讓機器類比人類進行學習 - 學習人類的語法、分析語句等等。尤其是在喬姆斯基（Noam Chomsky 有史以來最偉大的語言學家）提出 “形式語言” 以後，人們更堅定了利用語法規則的辦法進行文字處理的信念。遺憾的是，幾十年過去了，在計算機處理語言領域，基於這個語法規則的方法幾乎毫無突破。

其實早在幾十年前，數學家兼資訊論的祖師爺 香農 (Claude Shannon)就提出了用數學的辦法處理自然語言的想法。遺憾的是當時的計算機條件根本無法滿足大量訊息處理的需要，所以他這個想法當時並沒有被人們重視。七十年代初，有了大規模積體電路的快速計算機後，香農的夢想才得以實現。

首先成功利用數學方法解決自然語言處理問題的是語音和語言處理大師賈裡尼克 (Fred Jelinek)。當時賈裡尼克在 IBM 公司做學術休假 (Sabbatical Leave)，領導了一批傑出的科學家利用大型計算機來處理人類語言問題。統計語言模型就是在那個時候提出的。

給大家舉個例子︰在很多涉及到自然語言處理的領域，如機器翻譯、語音識別、印刷體或手寫體識別、拼寫糾錯、漢字輸入和文獻查詢中，我們都需要知道一個文字序列是否能構成一個大家能理解的句子，顯示給使用者。對這個問題，我們可以用一個簡單的統計模型來解決這個問題。

如果 S 表示一連串特定順序排列的詞 w1， w2，…， wn ，換句話說，S 可以表示某一個由一連串特定順序排練的詞而組成的一個有意義的句子。現下，機器對語言的識別從某種角度來說，就是想知道S在文本中出現的可能性，也就是數學上所說的S 的機率用 P(S) 來表示。利用條件機率的公式，S 這個序列出現的機率等於每一個詞出現的機率相乘，於是P(S) 可展開為︰

P(S) = P(w1)P(w2|w1)P(w3| w1 w2)…P(wn|w1 w2…wn-1)

其中 P (w1) 表示第一個詞w1 出現的機率；P (w2|w1) 是在已知第一個詞的前提下，第二個詞出現的機率；以次類推。不難看出，到了詞wn，它的出現機率取決於它前面所有詞。從計算上來看，各種可能性太多，無法實現。因此我們假定任意一個詞wi的出現機率只同它前面的詞 wi-1 有關(即馬爾可夫假設），於是問題就變得很簡單了。現下，S 出現的機率就變為︰

P(S) = P(w1)P(w2|w1)P(w3|w2)…P(wi|wi-1)…
(當然，也可以假設一個詞又前面N-1個詞決定，模型稍微複雜些。）

接下來的問題就是如何估計 P (wi|wi-1)。現下有了大量機讀文本後，這個問題變得很簡單，只要數一數這對詞（wi-1,wi) 在統計的文本中出現了多少次，以及 wi-1 本身在同樣的文本中前後相鄰出現了多少次，然後用兩個數一除就可以了,（P(wi|wi-1) = P (wi)/[P(wi-1,wi)]。

也許很多人不相信用這么簡單的數學模型能解決複雜的語音識別、機器翻譯等問題。其實不光是常人，就連很多語言學家都曾質疑過這種方法的有效性，但事實證明，統計語言模型比任何已知的借助某種規則的解決方法都有效。比如在 Google 的中英文自動翻譯中，用的最重要的就是這個統計語言模型。去年美國標準局(NIST) 對所有的機器翻譯系統進行了評測，Google 的系統是不僅是全世界最好的，而且高出所有基於規則的系統很多。

現下，讀者也許已經能感受到數學的美妙之處了，它把一些複雜的問題變得如此的簡單。當然，真正實現一個好的統計語言模型還有許多細節問題需要解決。賈裡尼克和他的同事的貢獻在於提出了統計語言模型，而且很漂亮地解決了所有的細節問題。十幾年後，李開複用統計語言模型把 997 詞語音識別的問題簡化成了一個 20 詞的識別問題，實現了有史以來第一次大詞彙量非特定人連續語音的識別。

我是一名科學研究人員 ，我在工作中經常驚嘆於數學語言應用於解決實際問題上時的神奇。我也希望把這種神奇講解給大家聽。當然，歸根結底，不管什莫樣的科學方法、無論多莫奇妙的解決手段都是為人服務的。我希望 Google 多努力一分，用戶就多一分搜索的喜悅。

數學之美 系列二 -- 談談中文分詞
2006年4月10日 上午 08:10:00
發表者: 吳軍， Google 研究員

談談中文分詞
----- 統計語言模型在中文處理中的一個應用

上回我們談到利用統計語言模型進行語言處理，由於模型是建立在詞的基礎上的，對於中日韓等語言，首先需要進行分詞。例如把句子 “中國太空飛行官員應邀到美國與太空總署官員開會。”

分成一串詞︰
中國 / 太空飛行 / 官員 / 應邀 / 到 / 美國 / 與 / 太空 / 總署 / 官員 / 開會。

最容易想到的，也是最簡單的分詞辦法就是查字典。這種方法最早是由北京太空飛行航空大學的梁南元教授提出的。

用 “查字典” 法，其實就是我們把一個句子從左向右掃描一遍，遇到字典裡有的詞就標識出來，遇到複合詞（比如 “上海大學”）就找最長的詞匹配，遇到不認識的字串就分割成單字詞，於是簡單的分詞就完成了。這種簡單的分詞方法完全能處理上面例子中的句子。八十年代，哈工大的王曉龍博士把它理論化，發展成最少詞數的分詞理論，即一句話應該分成數量最少的詞串。這種方法一個明顯的不足是當遇到有二義性 （有雙重理解意思）的分割時就無能為力了。比如，對片語 “開發中國家” 正確的分割是“發展-中-國家”，而從左向右查字典的辦法會將它分割成“發展-中國-家”，顯然是錯了。另外，並非所有的最長匹配都一定是正確的。比如“上海大學城書局”的正確分詞應該是 “上海-大學城-書局，” 而不是 “上海大學-城-書局”。

九十年代以前，海內外不少學人試圖用一些文法規則來解決分詞的二義性問題，都不是很成功。90年前後，清華大學的郭進博士用統計語言模型成功解決分詞二義性問題，將漢語分詞的錯誤率降低了一個數量級。

利用統計語言模型分詞的方法，可以用幾個數學公式簡單概括如下︰
我們假定一個句子S可以有幾種分詞方法，為了簡單起見我們假定有以下三種︰
A1, A2, A3, ..., Ak,
B1, B2, B3, ..., Bm
C1, C2, C3, ..., Cn

其中，A1, A2, B1, B2, C1, C2 等等都是漢語的詞。那麼最好的一種分詞方法應該保證分完詞後這個句子出現的機率最大。也就是說如果 A1,A2,..., Ak 是最好的分法，那麼 （P 表示機率）︰
P (A1, A2, A3, ..., Ak） 〉 P (B1, B2, B3, ..., Bm), 並且
P (A1, A2, A3, ..., Ak） 〉 P(C1, C2, C3, ..., Cn)
因此，只要我們利用上回提到的統計語言模型計算出每種分詞後句子出現的機率，並找出其中機率最大的，我們就能夠找到最好的分詞方法。

當然，這裡面有一個實現的技巧。如果我們窮舉所有可能的分詞方法並計算出每種可能性下句子的機率，那麼計算量是相當大的。因此，我們可以把它看成是一個動態規劃（Dynamic Programming) 的問題，並利用 “維特比”（Viterbi） 算法快速地找到最佳分詞。

在清華大學的郭進博士以後，海內外不少學人利用統計的方法，進一步完善中文分詞。其中值得一提的是清華大學孫茂松教授和香港科技大學吳德凱教授的工作。

需要指出的是，語言學家對詞語的定義不完全相同。比如說 “北京大學”，有人認為是一個詞，而有人認為該分成兩個詞。一個折中的解決辦法是在分詞的同時，找到複合詞的巢狀架構。在上面的例子中，如果一句話包含“北京大學”四個字，那麼先把它當成一個四字詞，然後再進一步找出細分詞 “北京” 和 “大學”。這種方法是最早是郭進在 “Computational Linguistics” （《計算機語言學》）雜誌上發表的，以後不少系統採用這種方法。

一般來講，根據不同應用，漢語分詞的顆粒度大小應該不同。比如，在機器翻譯中，顆粒度應該大一些，“北京大學”就不能被分成兩個詞。而在語音識別中，“北京大學”一般是被分成兩個詞。因此，不同的應用，應該有不同的分詞系統。Google 的葛顯平博士和朱安博士，專門為搜索設計和實現了自己的分詞系統。

也許你想不到，中文分詞的方法也被應用到英語處理，主要是手寫體識別中。因為在識別手寫體時，單字之間的空格就不很清楚了。中文分詞方法可以幫助判別英語單字的邊界。其實，語言處理的許多數學方法通用的和具體的語言無關。在 Google 內，我們在設計語言處理的算法時，都會考慮它是否能很容易地適用於各種自然語言。這樣，我們才能有效地支援上百種語言的搜索。

對中文分詞有興趣的讀者，可以閱讀以下文獻︰

1. 梁南元
書面漢語自動分詞系統
http://www.touchwrite.com/demo/LiangNanyuan-JCIP-1987.pdf

2. 郭進
統計語言模型和漢語音字轉換的一些新結果
http://www.touchwrite.com/demo/GuoJin-JCIP-1993.pdf

3. 郭進
Critical Tokenization and its Properties
http://acl.ldc.upenn.edu/J/J97/J97-4004.pdf

4. 孫茂松
Chinese word segmentation without using lexicon and hand-crafted training data
http://portal.acm.org/citation.c ... GUIDE id=980775

數學之美 系列三 -- 隱含馬爾可夫模型在語言處理中的應用
2006年4月17日 上午 08:01:00
發表者︰吳軍，Google 研究員

前言︰隱含馬爾可夫模型是一個數學模型，到目前為之，它一直被認為是實現快速精確的語音識別系統的最成功的方法。複雜的語音識別問題透過隱含馬爾可夫模型能非常簡單地被表述、解決，讓我不由由衷地感嘆數學模型之妙。

自然語言是人類交流訊息的工具。很多自然語言處理問題都可以等同於通信系統中的解碼問題 -- 一個人根據接收到的訊息，去猜測發話人要表達的意思。這其實就象通信中，我們根據接收端收到的信號去分析、理解、還原發送端傳送過來的訊息。以下該圖就表示了一個典型的通信系統︰

其中 s1，s2，s3...表示訊息源發出的信號。o1, o2, o3 ... 是接受器接收到的信號。通信中的解碼就是根據接收到的信號 o1, o2, o3 ...還原出發送的信號 s1，s2，s3...。

其實我們平時在說話時，腦子就是一個訊息源。我們的喉嚨（聲帶），空氣，就是如電線和光纜般的信道。聽眾耳朵的就是接收端，而聽到的聲音就是傳送過來的信號。根據聲學信號來推測說話者的意思，就是語音識別。這樣說來，如果接收端是一台計算機而不是人的話，那麼計算機要做的就是語音的自動識別。同樣，在計算機中，如果我們要根據接收到的英語訊息，推測說話者的漢語意思，就是機器翻譯； 如果我們要根據帶有拼寫錯誤的語句推測說話者想表達的正確意思，那就是自動糾錯。

那麼怎么根據接收到的訊息來推測說話者想表達的意思呢？我們可以利用叫做“隱含馬爾可夫模型”（Hidden Markov Model）來解決這些問題。以語音識別為例，當我們觀測到語音信號 o1,o2,o3 時，我們要根據這組信號推測出發送的句子 s1,s2,s3。顯然，我們應該在所有可能的句子中找最有可能性的一個。用數學語言來描述，就是在已知 o1,o2,o3,...的情況下，求使得條件機率
P (s1,s2,s3,...|o1,o2,o3....) 達到最大值的那個句子 s1,s2,s3,...

當然，上面的機率不容易直接求出，於是我們可以間接地計算它。利用貝葉斯公式並且省掉一個常數項，可以把上述公式等價變換成

P(o1,o2,o3,...|s1,s2,s3....) * P(s1,s2,s3,...)
其中
P(o1,o2,o3,...|s1,s2,s3....) 表示某句話 s1,s2,s3...被讀成 o1,o2,o3,...的可能性, 而
P(s1,s2,s3,...) 表示字串 s1,s2,s3,...本身能夠成為一個合乎情理的句子的可能性，所以這個公式的意義是用發送信號為 s1,s2,s3...這個數列的可能性乘以 s1,s2,s3...本身可以一個句子的可能性，得出機率。

（讀者讀到這裡也許會問，你現下是不是把問題變得更複雜了，因為公式越寫越長了。別著急，我們現下就來簡化這個問題。）我們在這裡做兩個假設︰

第一，s1,s2,s3,... 是一個馬爾可夫鏈，也就是說，si 只由 si-1 決定 (詳見系列一)；
第二， 第 i 時刻的接收信號 oi 只由發送信號 si 決定（又稱為獨立輸出假設, 即 P(o1,o2,o3,...|s1,s2,s3....) = P(o1|s1) * P(o2|s2)*P(o3|s3)...。
那麼我們就可以很容易利用算法 Viterbi 找出上面式子的最大值，進而找出要識別的句子 s1,s2,s3,...。

滿足上述兩個假設的模型就叫隱含馬爾可夫模型。我們之所以用“隱含”這個詞，是因為狀態 s1,s2,s3,...是無法直接觀測到的。

隱含馬爾可夫模型的應用遠不只在語音識別中。在上面的公式中，如果我們把 s1,s2,s3,...當成中文，把 o1,o2,o3,...當成對應的英文，那麼我們就能利用這個模型解決機器翻譯問題； 如果我們把 o1,o2,o3,...當成掃描文字得到的圖像特徵，就能利用這個模型解決印刷體和手寫體的識別。

P (o1,o2,o3,...|s1,s2,s3....) 根據應用的不同而又不同的名稱，在語音識別中它被稱為“聲學模型” (Acoustic Model)， 在機器翻譯中是“翻譯模型” (Translation Model) 而在拼寫校正中是“糾錯模型” (Correction Model)。 而P (s1,s2,s3,...) 就是我們在系列一中提到的語言模型。

在利用隱含馬爾可夫模型解決語言處理問題前，先要進行模型的訓練。 常用的訓練方法由伯姆（Baum）在60年代提出的，並以他的名字命名。隱含馬爾可夫模型在處理語言問題早期的成功應用是語音識別。七十年代，當時 IBM 的 Fred Jelinek (賈裡尼克) 和卡內基•梅隆大學的 Jim and Janet Baker (貝克夫婦，李開複的師兄師姐) 分別獨立地提出用隱含馬爾可夫模型來識別語音，語音識別的錯誤率相比人工智慧和模式匹配等方法降低了三倍 (從 30% 到 10%)。 八十年代李開複博士堅持採用隱含馬爾可夫模型的框架， 成功地開發了世界上第一個大詞彙量連續語音識別系統 Sphinx。

我最早接觸到隱含馬爾可夫模型是幾乎二十年前的事。那時在《隨機過程》（清華“著名”的一門課）裡學到這個模型，但當時實在想不出它有什麼實際用途。幾年後，我在清華跟隨王作英教授學習、研究語音識別時，他給了我幾十篇文獻。 我印象最深的就是賈裡尼克和李開複的文章，它們的核心思想就是隱含馬爾可夫模型。複雜的語音識別問題居然能如此簡單地被表述、解決，我由衷地感嘆數學模型之妙。

數學之美系列 4 -- 怎樣度量訊息?
2006年4月26日 上午 08:11:00
發表者︰吳軍，Google 研究員

前言: Google 一直以 “整合全球訊息，讓人人能獲取，使人人能受益” 為使命。那麼究竟每一條訊息應該怎樣度量呢？

訊息是個很抽象的概念。我們常常說訊息很多，或者訊息較少，但卻很難說清楚訊息到底有多少。比如一本五十萬字的中文書到底有多少訊息量。直到 1948 年，香農提出了“訊息熵”(sh ng) 的概念，才解決了對訊息的量化度量問題。

一條訊息的訊息量大小和它的不確定性有直接的關係。比如說，我們要搞清楚一件非常非常不確定的事，或是我們一無所知的事情，就需要了解大量的訊息。相反，如果我們對某件事已經有了較多的了解，我們不需要太多的訊息就能把它搞清楚。所以，從這個角度，我們可以認為，訊息量的度量就等於不確定性的多少。

那麼我們如何量化的度量訊息量呢？我們來看一個例子，馬上要舉行世界杯賽了。大家都很關心誰會是冠軍。假如我錯過了看世界杯，賽後我問一個知道比賽結果的觀眾“哪支球隊是冠軍”？ 他不願意直接告訴我， 而要讓我猜，並且我每猜一次，他要收一元錢才肯告訴我是否猜對了，那麼我需要付給他多少錢才能知道誰是冠軍呢? 我可以把球隊編上號，從 1 到 32， 然後提問︰ “冠軍的球隊在 1-16 號中嗎?” 假如他告訴我猜對了， 我會接著問︰ “冠軍在 1-8 號中嗎?” 假如他告訴我猜錯了， 我自然知道冠軍隊在 9-16 中。 這樣只需要五次， 我就能知道哪支球隊是冠軍。所以，誰是世界杯冠軍這條消息的訊息量只值五塊錢。

當然，香農不是用錢，而是用 “比特”（bit）這個概念來度量訊息量。 一個比特是一位二進製數，計算機中的一個位元組是八個比特。在上面的例子中，這條消息的訊息量是五比特。（如果有朝一日有六十四個隊進入決賽階段的比賽，那麼“誰世界杯冠軍”的訊息量就是六比特，因為我們要多猜一次。） 讀者可能已經發現, 訊息量的比特數和所有可能情況的對數函數 log 有關。 (log32=5, log64=6。）

有些讀者此時可能會發現我們實際上可能不需要猜五次就能猜出誰是冠軍，因為象巴西、德國、義大利這樣的球隊得冠軍的可能性比日本、美國、韓國等隊大的多。因此，我們第一次猜測時不需要把 32 個球隊等分成兩個組，而可以把少數幾個最可能的球隊分成一組，把其它隊分成另一組。然後我們猜冠軍球隊是否在那幾只熱門隊中。我們重複這樣的過程，根據奪冠機率對剩下的候選球隊分組，直到找到冠軍隊。這樣，我們也許三次或四次就猜出結果。因此，當每個球隊奪冠的可能性（機率）不等時，“誰世界杯冠軍”的訊息量的訊息量比五比特少。香農指出，它的準確訊息量應該是

= -（p1*log p1 + p2 * log p2 + ．．． ＋p32 *log p32)，

其中，p1，p2 ， ．．．，p32 分別是這 32 個球隊奪冠的機率。香農把它稱為“訊息熵” (Entropy)，一般用符號 H 表示，單位是比特。有興趣的讀者可以推算一下當 32 個球隊奪冠機率相同時，對應的訊息熵等於五比特。有數學基礎的讀者還可以證明上面公式的值不可能大於五。對於任意一個隨機變量 X（比如得冠軍的球隊），它的熵定義如下︰

變量的不確定性越大，熵也就越大，把它搞清楚所需要的訊息量也就越大。

有了“熵”這個概念，我們就可以回答本文開始提出的問題，即一本五十萬字的中文書平均有多少訊息量。我們知道常用的漢字（一級二級國標）大約有 7000 字。假如每個字等機率，那麼我們大約需要 13 個比特（即 13 位二進製數）表示一個漢字。但漢字的使用是不平衡的。實際上，前 10% 的漢字占文本的 95% 以上。因此，即使不考慮上下文的相關性，而只考慮每個漢字的獨立的機率，那麼，每個漢字的訊息熵大約也只有 8-9 個比特。如果我們再考慮上下文相關性，每個漢字的訊息熵只有5比特左右。所以，一本五十萬字的中文書，訊息量大約是 250 萬比特。如果用一個好的算法壓縮一下，整本書可以存成一個 320KB 的檔案。如果我們直接用兩位元組的國標編碼存儲這本書，大約需要 1MB 大小，是壓縮檔案的三倍。這兩個數量的差距，在資訊論中稱作“冗餘度”（redundancy)。 需要指出的是我們這裡講的 250 萬比特是個平均數，同樣長度的書，所含的訊息量可以差很多。如果一本書重複的內容很多，它的訊息量就小，冗餘度就大。

不同語言的冗餘度差別很大，而漢語在所有語言中冗餘度是相對小的。這和人們普遍的認識“漢語是最簡潔的語言”是一致的。

在下一集中， 我們將介紹訊息熵在訊息處理中的應用以及兩個相關的概念互訊息和相對熵。

對中文訊息熵有興趣的讀者可以讀我和王作英教授在電子學報上合寫的一篇文章
《語訊息熵和語言模型的複雜度》

數學之美系列六 -- 簡單之美︰布林代數和搜索引擎的索引
2006年5月10日 上午 09:10:00
發表者: 吳軍，Google 研究員

[建立一個搜索引擎大致需要做這樣幾件事︰自動下載儘可能多的網頁；建立快速有效的索引；根據相關性對網頁進行公平準確的排序。我們在介紹 Google Page Rank (網頁排名) 時已經談到了一些排序的問題，這裡我們談談索引問題，以後我們還會談如何度量網頁的相關性，和進行網頁自動下載。〕

世界上不可能有比二進製更簡單的計數方法了，也不可能有比布爾運算更簡單的運算了。儘管今天每個搜索引擎都宣稱自己如何聰明、多么智能化，其實從根本上講都沒有逃出布爾運算的框框。

布爾（George Boole) 是十九世紀英國一位國小數學老師。他生前沒有人認為他是數學家。布爾在工作之余，喜歡閱讀數學論著、思考數學問題。1854 年“思惟規律”（An Investigation of the Laws of Thought, on which are founded the Mathematical Theories of Logic and Probabilities）一書，第一次向人們展示了如何用數學的方法解決邏輯問題。

布林代數簡單得不能再簡單了。運算的元素只有兩個1 （TRUE， 真) 和 0
（FALSE，假)。基本的運算只有“與”（AND)、“或” (OR) 和“非”（NOT) 三種（後來發現，這三種運算都可以轉換成“與”“非” ＡＮＤ－ＮＯＴ一種運算）。全部運算只用下列幾張真值表就能完全地描述清楚。

AND | 1 0
-----------------------
1 | 1 0
0 | 0 0
這張表說明如果 AND 運算的兩個元素有一個是 0，則運算結果總是 0。如果兩個元素都是 1，運算結果是 1。例如，“太陽從西邊升起”這個判斷是假的(0),“水可以流動”這個判斷是真的（1），那麼，“太陽從西邊升起並且水可以流動”就是假的（0）。

OR | 1 0
-----------------------
1 | 1 1
0 | 1 0
這張表說明如果OR運算的兩個元素有一個是 1，則運算結果總是 1。如果兩個元素都是 0，運算結果是 0。比如說，“張三是比賽第一名”這個結論是假的（0），“李四是比賽第一名”是真的（1），那麼“張三或者李四是第一名”就是真的（1）。

NOT |
--------------
1 | 0
0 | 1
這張表說明 NOT 運算把 1 變成 0，把 0 變成 1。比如，如果“象牙是白的”是真的（1），那麼“象牙不是白的”必定是假的（0）。

讀者也許會問這么簡單的理論能解決什麼實際問題。布爾同時代的數學家們也有同樣的問題。事實上在布林代數提出後80 多年裡，它確實沒有什麼像樣的應用，直到 1938 年香農在他的碩士論文中指出用布林代數來實現開關電路，才使得布林代數成為數字電路的基礎。所有的數學和邏輯運算，加、減、乘、除、乘方、開方等等，全部能轉換成二值的布爾運算。

現下我們看看文獻檢索和布爾運算的關係。對於一個用戶輸入的關鍵詞，搜索引擎要判斷每篇文獻是否含有這個關鍵詞，如果一篇文獻含有它，我們相應地給這篇文獻一個邏輯值 -- 真（TRUE,或 1），否則，給一個邏輯值 -- 假（FALSE, 或0）。比如我們要找有關原子能應用的文獻，但並不想知道如何造原子彈。我們可以這樣寫一個查詢語句“原子能 AND 應用 AND (NOT 原子彈)”，表示符合要求的文獻必須同時滿足三個條件︰
- 包含原子能
- 包含應用
- 不包含原子彈
一篇文獻對於上面每一個條件，都有一個 True 或者 False 的答案，根據上述真值表就能算出每篇文獻是否是要找的。

早期的文獻檢索查詢系統大多基於數據庫，嚴格要求查詢語句符合布爾運算。今天的搜索引擎相比之下要聰明的多，它自動把用戶的查詢語句轉換成布爾運算的算式。當然在查詢時，不能將每篇文獻掃描一遍，來看看它是否滿足上面三個條件，因此需要建立一個索引。

最簡單索引的架構是用一個很長的二進製數表示一個關鍵字是否出現下每篇文獻中。有多少篇文獻，就有多少位數，每一位對應一篇文獻，1 代表相應的文獻有這個關鍵字，0 代表沒有。比如關鍵字“原子能”對應的二進製數是0100100001100001...，表示第二、第五、第九、第十、第十六篇文獻包含著個關鍵字。注意，這個二進製數非常之長。同樣，我們假定“應用”對應的二進製數是 0010100110000001...。那麼要找到同時包含“原子能”和“應用”的文獻時，只要將這兩個二進製數進行布爾運算 AND。根據上面的真值表，我們知道運算結果是0000100000000001...。表示第五篇，第十六篇文獻滿足要求。

注意，計算機作布爾運算是非常非常快的。現下最便宜的微機都可以一次進行三十二位布爾運算，一秒鐘進行十億次以上。當然，由於這些二進製數中絕大部分位數都是零，我們只需要記錄那些等於1的位數即可。於是，搜索引擎的索引就變成了一張大表︰表的每一行對應一個關鍵詞，而每一個關鍵詞後面跟著一組數字，是包含該關鍵詞的文獻序號。

對於互聯網的搜索引擎來講，每一個網頁就是一個文獻。互聯網的網頁數量是巨大的，網路中所用的詞也非常非常多。因此這個索引是巨大的，在萬億位元組這個量級。早期的搜索引擎（比如 Alta Vista 以前的所有搜索引擎），由於受計算機速度和容量的限制，只能對重要的關鍵的主題詞建立索引。至今很多學術雜誌還要求作者提供 3-5 個關鍵詞。這樣所有不常見的詞和太常見的虛詞就找不到了。現下，為了保證對任何搜索都能提供相關的網頁，所有的搜索引擎都是對所有的詞進行索引。為了網頁排名方便，索引中還需存有大量附加訊息，諸如每個詞出現的位置、次數等等。因此，整個索引就變得非常之大，以至於不可能用一台計算機存下。大家普遍的做法就是根據網頁的序號將索引分成很多份（Shards)，分別存儲在不同的伺服器中。每當接受一個查詢時，這個查詢就被分送到許許多多伺服器中，這些伺服器同時並行處理用戶請求，並把結果送到主伺服器進行合併處理，最後將結果返回給用戶。

不管索引如何複雜，查找的基本操作仍然是布爾運算。布爾運算把邏輯和數學聯繫起來了。它的最大好處是容易實現，速度快，這對於海量的訊息查找是至關重要的。它的不足是只能給出是與否的判斷，而不能給出量化的度量。因此，所有搜索引擎在內部檢索完畢後，都要對符合要求的網頁根據相關性排序，然後才返回給用戶。