很早之前看了幾篇博文赎线，只留下模糊印象 。這次是在學(xué)習(xí)人工智能的基礎(chǔ)知識(shí)后再看钥弯，其中研究自然語(yǔ)言的方法從基于規(guī)則轉(zhuǎn)變?yōu)榛诮y(tǒng)計(jì)径荔，對(duì)我啟發(fā)很大。 在面對(duì)一個(gè)復(fù)雜的問題時(shí)脆霎，一定要去想著把它轉(zhuǎn)化成數(shù)學(xué)問題总处，而不是按照慣性思維去分析，只有轉(zhuǎn)化成簡(jiǎn)單優(yōu)雅的數(shù)學(xué)模型睛蛛，才證明你的研究方向?qū)α损新怼ｋ娔X并不神秘，它其實(shí)只是傻瓜
全書內(nèi)容多，本文只介紹三條主線：自然語(yǔ)言的統(tǒng)計(jì)模型、拼音輸入法印蔗、搜索引擎。PS：簡(jiǎn)書不支持latex公式旭从，讓這篇文章寫的很麻煩。
目錄
1.文字和語(yǔ)言 vs 數(shù)字和信息
2.自然語(yǔ)言處理 - 從規(guī)則到統(tǒng)計(jì)
3.統(tǒng)計(jì)語(yǔ)言模型
4.中文分詞
5.隱含馬爾可夫模型
6.信息熵
7.牛人介紹: 賈里尼克（Jelinek，現(xiàn)代自然語(yǔ)言處理奠基者遇绞，將語(yǔ)音識(shí)別看作通信問題）
8.布爾代數(shù)键袱，搜索引擎的索引
9.圖論、網(wǎng)絡(luò)爬蟲
10.Page Rank摹闽，網(wǎng)頁(yè)排名技術(shù)
11.TF-IDF蹄咖，網(wǎng)頁(yè)與查詢相關(guān)性
12.有限狀態(tài)機(jī)和動(dòng)態(tài)規(guī)劃-地圖和本地搜索
13.牛人介紹：阿米特·辛格，
14.余弦定理和新聞分類
15.矩陣計(jì)算付鹿、文本處理中兩個(gè)分類問題
16.信息指紋：哈希
17.密碼學(xué)中的數(shù)學(xué)澜汤、信息論
18.搜索引擎反作弊
19.數(shù)學(xué)模型重要性
20.最大熵模型
21.拼音輸入法的數(shù)學(xué)原理
22.牛人介紹：馬庫(kù)斯（Marcus），建立語(yǔ)料庫(kù)舵匾。
23.布隆過濾器
24.貝葉斯網(wǎng)絡(luò)
25.條件隨機(jī)場(chǎng)和句法分析
26.牛人介紹：維特比俊抵，高通創(chuàng)辦者，制定CDMA協(xié)議坐梯。
27.期望最大化算法
28.邏輯回歸和搜索廣告
29.Map Reduce
1. 自然語(yǔ)言處理徽诲，語(yǔ)音識(shí)別，機(jī)器翻譯
1.1 基于規(guī)則的語(yǔ)言處理
早期學(xué)術(shù)界認(rèn)為吵血，要讓機(jī)器完成翻譯和語(yǔ)音識(shí)別這種人類才能做的事情谎替，就必須先讓計(jì)算機(jī)理解自然語(yǔ)言，而做到這點(diǎn)就要讓機(jī)器有類似人類的智能蹋辅。這個(gè)方法論被稱為“鳥飛派”（通過觀察鳥的飛行方式钱贯，采用仿生的思路造出飛機(jī)）。
那么怎么讓機(jī)器理解自然語(yǔ)言呢侦另？受傳統(tǒng)語(yǔ)言學(xué)的影響秩命，他們覺得要讓機(jī)器做好兩件事：分析句子語(yǔ)法和獲取語(yǔ)義。分析句子語(yǔ)法就是按照語(yǔ)法把句子拆分褒傅，分清它的主語(yǔ)弃锐、謂語(yǔ)、賓語(yǔ)是什么殿托，每個(gè)部分的詞性是什么拿愧，用什么標(biāo)點(diǎn)符號(hào)。而語(yǔ)義分析碌尔，就是弄清句子要表達(dá)的具體意思。語(yǔ)法規(guī)則很容易用計(jì)算機(jī)算法描述券敌，這讓人們覺得基于規(guī)則的方法是對(duì)的唾戚。但是這種方法很快就陷入困境，因?yàn)榛谡Z(yǔ)法的分析器處理不了復(fù)雜句子待诅，同時(shí)叹坦，詞的多義性無(wú)法用規(guī)則表述，例如下面的例子：
The pen is in the box. 和 The box is in the pen.
第二句話讓非英語(yǔ)母語(yǔ)的人很難理解绪囱，盒子怎么在鋼筆里呢齿椅？其實(shí)在這里遣蚀，pen是圍欄的意思粥帚。這里pen是鋼筆還是圍欄，通過上下文已經(jīng)不能解決，而需要常識(shí)匀油，即鋼筆可以放在盒子里蒲每，但是盒子比鋼筆大刁品，所以不能放在盒子里，于是pen在這里是圍欄的意思魁淳，盒子可以放在圍欄里少欺。
1.2 基于統(tǒng)計(jì)的語(yǔ)言處理
賈里尼克（Jelinek）把語(yǔ)音識(shí)別問題當(dāng)作通信問題扰付，并用兩個(gè)隱含馬爾可夫模型（聲學(xué)和語(yǔ)言模型）概括了語(yǔ)音識(shí)別荒给，推動(dòng)了基于統(tǒng)計(jì)的語(yǔ)言處理方法鱼蝉。
在語(yǔ)音識(shí)別中洁奈，計(jì)算機(jī)需要知道一個(gè)文字序列是否能構(gòu)成一個(gè)大家理解而且有意義的句子。早期的做法是判斷給出的句子是否合乎語(yǔ)法婉弹，由前文可知這條路走不通睬魂。賈里尼克從另外角度看這個(gè)問題：通過計(jì)算一個(gè)句子出現(xiàn)的概率大小來(lái)判斷它的合理性，于是語(yǔ)音識(shí)別問題轉(zhuǎn)換成計(jì)算概率問題镀赌，根據(jù)這個(gè)思路氯哮，賈里尼克建立了統(tǒng)計(jì)語(yǔ)言模型。
假定S表示某一個(gè)有意義的句子商佛，由一連串特定順序排列的詞w1,w2,w3...組成喉钢。我們想知道S在文本中出現(xiàn)的可能性，計(jì)算S的概率P(S)良姆，根據(jù)條件概率公式：
其中P(w1)為w1出現(xiàn)的概率肠虽，P(w2|w1)為已知第一個(gè)詞出現(xiàn)的條件下，第二個(gè)詞出現(xiàn)的概率玛追，以此類推税课。前面幾個(gè)概率容易計(jì)算闲延，但是后面的概率隨著變量增多，變得不可計(jì)算韩玩。在這里需要應(yīng)用馬爾可夫假設(shè)來(lái)簡(jiǎn)化計(jì)算垒玲。馬爾可夫假設(shè)假定當(dāng)前狀態(tài)只與前一個(gè)狀態(tài)有關(guān)，即Wi出現(xiàn)的概率只同它前面的詞有關(guān)Wi-1找颓，于是上面的公式可以簡(jiǎn)化為：
接下來(lái)的問題是估算條件概率P(Wi|Wi-1)合愈，由條件概率公式得：
而估計(jì)聯(lián)合概率P(Wi-1, Wi)和P(Wi-1)可以統(tǒng)計(jì)語(yǔ)料庫(kù)得到，通過計(jì)算(Wi-1, Wi)這對(duì)詞在語(yǔ)料庫(kù)中前后相鄰出現(xiàn)的次數(shù)C击狮，以及Wi-1單獨(dú)出現(xiàn)的次數(shù)佛析，就可得到這些詞或者二元組的相對(duì)頻度。根據(jù)大數(shù)定理彪蓬，只要統(tǒng)計(jì)量足夠寸莫，相對(duì)頻度就等于概率，于是
于是復(fù)雜的語(yǔ)序合理性問題寞焙，變成了簡(jiǎn)單的次數(shù)統(tǒng)計(jì)問題储狭。
上式對(duì)應(yīng)的統(tǒng)計(jì)語(yǔ)言模型是二元模型，實(shí)際應(yīng)用中捣郊，google翻譯用到四元模型辽狈。
1.3 中文分詞
對(duì)于西方拼音語(yǔ)言來(lái)說，詞之間有明確的分界符（空格）呛牲，但是中刮萌、日、韓娘扩、泰等語(yǔ)言沒有着茸。因此，首先要對(duì)句子進(jìn)行分詞琐旁，才能做進(jìn)一步自然語(yǔ)言處理涮阔。對(duì)一個(gè)句子正確的分詞結(jié)果如下：
分詞前：中國(guó)航天官員應(yīng)邀到美國(guó)與太空總署官員開會(huì)。
分詞后：中國(guó)/航天/官員/應(yīng)邀/到/美國(guó)/與/太空/總署/官員/開會(huì)/灰殴。
最容易想到的分詞方法是“查字典”敬特，即把一個(gè)句子從左到右掃描一遍，遇到字典里有的詞就標(biāo)出來(lái)牺陶，遇到復(fù)合詞就找最長(zhǎng)匹配伟阔，遇到不認(rèn)識(shí)的字串就分割成單字。這個(gè)方法能解決七八成的問題掰伸，但是遇到有二義性的分割就無(wú)能為力了皱炉，例如“發(fā)展中國(guó)家”，正確的分割是“發(fā)展-中-國(guó)家”狮鸭，但是按照查字典法就會(huì)分成“發(fā)展-中國(guó)-家”合搅。另外多搀，并不是最長(zhǎng)匹配都一定正確，例如“上海大學(xué)城書店”历筝，正確的分割是“上海-大學(xué)城-書店”酗昼，而不是“上海大學(xué)-城-書店”。
按照前文的成功思路梳猪，依靠語(yǔ)法規(guī)則無(wú)法解決分詞的二義性問題，還是得靠統(tǒng)計(jì)語(yǔ)言模型蒸痹。
假設(shè)一個(gè)句子S有n種分詞方法春弥，利用前文的統(tǒng)計(jì)語(yǔ)言模型，分別計(jì)算出每種分詞方法的概率叠荠，概率最大的即為最好的分詞方法匿沛。因?yàn)楦F舉所有的分詞方法計(jì)算量太大，所以可以把它看成是一個(gè)動(dòng)態(tài)規(guī)劃問題榛鼎，并利用維特比算法快速找到最佳分詞逃呼。具體應(yīng)用時(shí)還要考慮分詞的顆粒度。
2. 拼音輸入法
2.1 拼音輸入法中的數(shù)學(xué)
中文輸入法經(jīng)歷了以自然音節(jié)編碼輸入者娱，到偏旁筆畫拆字輸入抡笼，再回歸自然音節(jié)輸入的過程。輸入法輸入漢字的快慢取決于對(duì)漢字編碼的平均長(zhǎng)度黄鳍，也就是擊鍵次數(shù)乘以尋找這個(gè)鍵需要的時(shí)間推姻。單純地減少編碼長(zhǎng)度未必能提高輸入速度，因?yàn)閷ふ乙粋€(gè)鍵的時(shí)間會(huì)增長(zhǎng)框沟。
將漢字輸入到計(jì)算機(jī)中藏古，是將人能看懂的信息編碼變成計(jì)算機(jī)約定的編碼（Unicode或UTF-8）的過程。對(duì)漢字的編碼分為兩部分：對(duì)拼音的編碼和消除（一音多字）歧義忍燥。鍵盤上可使用的是26個(gè)字母和10個(gè)數(shù)字鍵拧晕，最直接的方式是讓26個(gè)字母對(duì)應(yīng)拼音，用10個(gè)數(shù)字消除歧義性梅垄。只有當(dāng)兩個(gè)編碼都縮短時(shí)厂捞，漢字的輸入才能夠變快。早期的輸入法常常只注重第一部分而忽略第二部分哎甲，例如雙拼輸入法和五筆輸入法蔫敲。
每一個(gè)拼音對(duì)應(yīng)多個(gè)漢字，把一個(gè)拼音串對(duì)應(yīng)的漢字由左向右連起來(lái)炭玫，就是一張有向圖奈嘿，如下圖所示，y1,y2,y3...是輸入的拼音串吞加，W11,W12,W13是第一個(gè)音的候選漢字（后面的文字描述用W1代替）裙犹，以此類推尽狠。從第一個(gè)字到最后一個(gè)字可以組成很多句子，每個(gè)句子對(duì)應(yīng)圖中的一條路徑叶圃。
拼音輸入法就是要根據(jù)上下文在給定的拼音條件下找到最優(yōu)的句子袄膏，即求
（Arg是argument的縮寫，Arg Max為獲得最大值的信息串）
化簡(jiǎn)這個(gè)概率需要用到隱含馬爾可夫模型（見2.2介紹）掺冠，我們把拼音串看成能觀察到的“顯狀態(tài)”沉馆，候選漢字看成“隱狀態(tài)”，然后求在這個(gè)“顯狀態(tài)”下的“隱狀態(tài)”概率德崭。帶入下文中的隱含馬爾可夫模型公式（2.3）斥黑，式（2.1）化簡(jiǎn)為：
化簡(jiǎn)連乘， 需要將等式兩邊取對(duì)數(shù)得
乘法變成了加法眉厨。我們定義兩個(gè)詞之間的距離
這樣锌奴，尋找最大概率問題變成了尋找最短路徑問題。
2.2 隱含馬爾可夫模型
上文介紹過馬爾可夫假設(shè)（研究隨機(jī)過程中的一個(gè)假設(shè)）憾股，即在隨機(jī)狀態(tài)序列中鹿蜀，假設(shè)其中的一個(gè)狀態(tài)只于前一個(gè)狀態(tài)有關(guān)。如天氣預(yù)報(bào)服球，假設(shè)今天的天氣只與昨天有關(guān)茴恰，這樣就能得到近似解：
符合這個(gè)假設(shè)的隨機(jī)過程稱為馬爾可夫過程，也叫馬爾可夫鏈有咨。隱含馬爾可夫模型是馬爾可夫鏈的一個(gè)擴(kuò)展：任意時(shí)刻t的狀態(tài)St是不可見的琐簇，但在每個(gè)時(shí)刻會(huì)輸出Ot， Ot僅和St相關(guān)座享，這叫獨(dú)立輸出假設(shè)婉商，數(shù)學(xué)公式如下：
P(Ot|St)我們可以通過觀察得到。
解決問題通常是通過已知求未知渣叛，我們要通過觀察到$o_t$求出$s_t$的概率丈秩，即求
由條件概率公式可得：
因?yàn)橛^察到的狀態(tài)O一旦產(chǎn)生就不會(huì)變了，所以它是一個(gè)可忽略的常數(shù)淳衙，上式可以化簡(jiǎn)為
因?yàn)?/p>
式(2.2)可以化簡(jiǎn)為
3.信息論：信息的度量和作用
3.1 信息熵
香農(nóng)在他的論文“通信的數(shù)學(xué)原理”[想到牛頓的“自然哲學(xué)與數(shù)學(xué)原理”]蘑秽，提出了信息熵（shang），把信息和數(shù)字聯(lián)系起來(lái)箫攀，解決了信息的度量肠牲，并量化出信息的作用。
一條信息的信息量和它的不確定性正相關(guān)靴跛，信息熵約等于不確定性的多少缀雳。香農(nóng)給出的信息熵公式為
P(x)為x的概率分布。
信息熵的公式為什么取負(fù)數(shù)梢睛？因?yàn)楦怕市∮?肥印，小數(shù)求得的對(duì)數(shù)是負(fù)數(shù)识椰，給整個(gè)公式加上負(fù)號(hào)，最終的結(jié)果為正深碱。
下面舉例說明信息熵公式為什么會(huì)用到log和概率腹鹉。
猜中世界杯冠軍需要多少次？
足球世界杯共32個(gè)球隊(duì)敷硅，給他們編號(hào)1-32號(hào)功咒，第一次猜冠軍是否在1-16號(hào)之中，如果對(duì)了就會(huì)接著猜是否在1-8號(hào)绞蹦，如果錯(cuò)了就知道冠軍在9-16號(hào)航瞭，第三次猜是否在9-12號(hào)，這樣只需要5次就能猜中坦辟，log32 = 5。這里采用的是折半查找章办，所以取對(duì)數(shù)锉走。
但實(shí)際情況不需要猜5次，因?yàn)榍蜿?duì)有強(qiáng)弱藕届，可以先把奪冠熱門分一組挪蹭，剩下的分一組，問冠軍是否在熱門組中休偶，再繼續(xù)這個(gè)過程梁厉，按照奪冠概率對(duì)剩下的球隊(duì)分組。引入概率就會(huì)讓查找數(shù)更少踏兜，也就是不確定性更小词顾，信息熵更小〖钭保可以計(jì)算肉盹，當(dāng)每支球隊(duì)奪冠概率相等時(shí)（1/32），信息熵的結(jié)果為5疹尾。
3.2 條件墑：
假定X和Y是兩個(gè)隨機(jī)變量上忍，X是我們要了解的，已知X的隨機(jī)分布P(X)纳本，于是X的熵為：
假定我們還知道Y的一些情況窍蓝，包括它和X一起出現(xiàn)的概率，即聯(lián)合概率分布繁成，以及在Y取不同值前提下X的概率分布吓笙，即條件概率分布，于是在Y條件下X的條件熵為：
可證明H(X|Y) <H(X), 即引入相關(guān)信息后朴艰，不確定性下降了观蓄。
3.3 互信息
信息之間的相關(guān)性如果度量呢混移？ 香農(nóng)提出了用互信息度量?jī)蓚€(gè)隨機(jī)事件的相關(guān)性。例如侮穿，“好悶熱”和“要下雨了”的互信息很高歌径。
X與Y的互信息公式如下：
經(jīng)過演算，可得到
只要有足夠的語(yǔ)料庫(kù)亲茅，P(x,y), P(x) 和P(y)是很容易計(jì)算的回铛。
機(jī)器翻譯中最難的兩個(gè)問題之一是二義性，如Bush 既可以是總統(tǒng)布什克锣，也可以是灌木叢茵肃，Kerry既可以是國(guó)務(wù)卿克里，也可以是小母牛袭祟。如何正確的翻譯验残？一種思路是通過語(yǔ)法辨別，但效果不好巾乳； 另一種思路是用互信息您没，從大量文本中找出和總統(tǒng)布什一起出現(xiàn)的詞語(yǔ)，如總統(tǒng)胆绊、美國(guó)氨鹏、國(guó)會(huì)等，再用同樣的方法找出和灌木叢一起出現(xiàn)的詞压状，如土壤仆抵、植物等，有了這兩組詞种冬，在翻譯Bush時(shí)镣丑，看看上下文中哪類詞更多就可以了。
3.4 相對(duì)熵/交叉熵
相對(duì)熵（KL Divergence）碌廓，衡量?jī)蓚€(gè)取值為正的函數(shù)的相似性:
結(jié)論：
- 兩個(gè)完全相等的函數(shù)传轰，相對(duì)熵為零；
- 相對(duì)熵越大谷婆，兩個(gè)函數(shù)差異越大慨蛙。
- 對(duì)于概率分布函數(shù)，或者概率密度函數(shù)纪挎，相對(duì)熵可以度量?jī)蓚€(gè)隨機(jī)分布的差異性期贫。
在自然語(yǔ)言處理中，常用相對(duì)熵計(jì)算兩個(gè)常用詞在不同文本中的概率分布异袄，看他們是否同義通砍；或者根據(jù)兩篇文章中不同詞的分布，衡量它們的內(nèi)容是否相等。利用相對(duì)熵封孙，可以得到信息檢索中最重要的概念：詞頻率-逆向文檔頻率（TF-IDF）迹冤，在后面的搜索章節(jié)會(huì)對(duì)它詳細(xì)介紹。
4. 搜索
4.1 獲取網(wǎng)頁(yè)：網(wǎng)絡(luò)爬蟲
把整個(gè)互聯(lián)網(wǎng)看作一張大圖虎忌，每個(gè)網(wǎng)頁(yè)就是圖中的一個(gè)節(jié)點(diǎn)泡徙，超鏈接是連接節(jié)點(diǎn)的弧。通過網(wǎng)絡(luò)爬蟲膜蠢，用圖的遍歷算法堪藐，就能自動(dòng)地訪問到每個(gè)網(wǎng)頁(yè)并把它們存起來(lái)。
網(wǎng)絡(luò)爬蟲是這樣工作：假定從一家門戶網(wǎng)站的首頁(yè)出發(fā)挑围，先下載這個(gè)網(wǎng)頁(yè)礁竞，再通過這個(gè)網(wǎng)頁(yè)分析出里面包含的所有超鏈接，接下來(lái)訪問并下載這些超鏈接指向的網(wǎng)頁(yè)杉辙。讓計(jì)算機(jī)不同地做下去模捂，就能下載整個(gè)互聯(lián)網(wǎng)。 還需要用一個(gè)記事本（哈希表）記錄下載了哪些網(wǎng)頁(yè)避免重復(fù)下載蜘矢。
工程實(shí)現(xiàn)問題：
- 遍歷算法采用廣度優(yōu)先還是深度優(yōu)先枫绅？
搜索引擎要做到在有限的時(shí)間內(nèi)，最多地爬下最重要的網(wǎng)頁(yè)硼端。顯然各個(gè)網(wǎng)站最重要的是它的首頁(yè)，那么就應(yīng)該先下載所有網(wǎng)站的首頁(yè)寓搬。如果把爬蟲再擴(kuò)大一點(diǎn)珍昨，就要繼續(xù)下載首頁(yè)直接鏈接的網(wǎng)頁(yè)，因?yàn)檫@些網(wǎng)頁(yè)是網(wǎng)站設(shè)計(jì)者自己認(rèn)為相當(dāng)重要的網(wǎng)頁(yè)句喷。在這個(gè)前提下镣典，似乎應(yīng)該采用廣度優(yōu)先。
但是還要考慮網(wǎng)絡(luò)通信的“握手”問題唾琼。網(wǎng)絡(luò)爬蟲每次訪問網(wǎng)站服務(wù)器時(shí)兄春，都要通過“握手”建立連接（TCP協(xié)議），如果采用廣度優(yōu)先锡溯，每個(gè)網(wǎng)站先輪流下載所有首頁(yè)赶舆，再回過頭來(lái)下載第二級(jí)網(wǎng)頁(yè)，這樣就要頻繁的訪問網(wǎng)站祭饭，增加“握手”耗時(shí)芜茵。
實(shí)際的網(wǎng)絡(luò)爬蟲是由成百上千臺(tái)服務(wù)器組成的分布式系統(tǒng)，由調(diào)度系統(tǒng)決定網(wǎng)頁(yè)下載的順序倡蝙，對(duì)于某個(gè)網(wǎng)站九串，一般是由特定的一臺(tái)或幾臺(tái)服務(wù)器專門下載，這些服務(wù)器先下載完一個(gè)網(wǎng)站再進(jìn)入下一個(gè)網(wǎng)站，這樣可以減少握手次數(shù)（深度優(yōu)先）猪钮。具體到每個(gè)網(wǎng)站品山，采用廣度優(yōu)先，先下載首頁(yè)烤低，再下載首頁(yè)直接鏈接的網(wǎng)頁(yè)肘交。
頁(yè)面分析和超鏈接（URL）提取
早期的網(wǎng)頁(yè)都是直接用HTML書寫，URL以文本的形式放在網(wǎng)頁(yè)中拂玻，前后有明顯標(biāo)識(shí)酸些，很容易提取出來(lái)。但現(xiàn)在很多網(wǎng)頁(yè)都是用腳本語(yǔ)言（如JavaScript）生成檐蚜，URL不是直接可見的文本魄懂，所以網(wǎng)絡(luò)爬蟲要模擬瀏覽器運(yùn)行網(wǎng)頁(yè)后才能得到隱含的URL，但很多網(wǎng)頁(yè)的腳本寫的不規(guī)范闯第，很難解析市栗，這就導(dǎo)致這樣的網(wǎng)頁(yè)無(wú)法被搜索引擎收錄。維護(hù)超鏈接哈希表
在一臺(tái)服務(wù)器上建立和維護(hù)一張哈希表并不是難事咳短，但如果同時(shí)有成千上萬(wàn)臺(tái)服務(wù)器一起下載網(wǎng)頁(yè)填帽，維護(hù)一張統(tǒng)一的哈希表就會(huì)遇到很多問題：
首先，這張哈希表會(huì)大到存不下來(lái)咙好；其次篡腌，每臺(tái)服務(wù)器下載前和下載后都要訪問哈希表，于是哈希表服務(wù)器的通信就成了整個(gè)爬蟲系統(tǒng)的瓶頸勾效。解決辦法是：明確分工嘹悼，將某個(gè)區(qū)間的URL分給特定的幾臺(tái)服務(wù)器，避免所有服務(wù)器對(duì)同一個(gè)URL做判斷层宫；批量詢問哈希表杨伙，減少通信次數(shù)，每次更新一大批哈希表的內(nèi)容萌腿。
4.2 網(wǎng)頁(yè)檢索：布爾代數(shù)
最簡(jiǎn)單的索引結(jié)構(gòu)是用一個(gè)很長(zhǎng)的二進(jìn)制數(shù)表示一個(gè)關(guān)鍵字是否在每個(gè)網(wǎng)頁(yè)中限匣，有多少個(gè)網(wǎng)頁(yè)就有多少位數(shù)，每一位對(duì)應(yīng)一個(gè)網(wǎng)頁(yè)毁菱，1代表相應(yīng)的網(wǎng)頁(yè)有這個(gè)關(guān)鍵字米死，0代表沒有。比如關(guān)鍵字“原子能”對(duì)應(yīng)的二進(jìn)制數(shù)是0100 1000 1100 0001...表示（從左到右）第二贮庞、第五哲身、第九、第十贸伐、第十六個(gè)網(wǎng)頁(yè)包含這個(gè)關(guān)鍵字勘天。假定關(guān)鍵字“應(yīng)用”對(duì)應(yīng)的二進(jìn)制數(shù)是0010 1001 1000 0001...，那么要找到同時(shí)包含“原子能”和“應(yīng)用”的網(wǎng)頁(yè)時(shí)，只需要將這兩個(gè)二進(jìn)制數(shù)進(jìn)行布爾AND運(yùn)算脯丝，結(jié)果是0000 1000 0000 0001...表示第五和第十六個(gè)網(wǎng)頁(yè)滿足要求商膊。 這個(gè)二進(jìn)制數(shù)非常長(zhǎng)，但是計(jì)算機(jī)做布爾運(yùn)算非吵杞快晕拆，現(xiàn)在最便宜的微機(jī)，在一個(gè)指令周期進(jìn)行32位布爾運(yùn)算材蹬，一秒鐘十億次以上实幕。
為了保證對(duì)任何搜索都能提供相關(guān)網(wǎng)頁(yè)，主要的搜索引擎都是對(duì)所有詞進(jìn)行索引堤器，假如互聯(lián)網(wǎng)上有100億個(gè)有意義的網(wǎng)頁(yè)昆庇，詞匯表大小是30萬(wàn)，那么這個(gè)索引至少是100億x30萬(wàn)=3000萬(wàn)億闸溃≌海考慮到大多數(shù)的詞只出現(xiàn)在一部分文本中，壓縮比是100：1辉川，也是30萬(wàn)億的量級(jí)表蝙。為了網(wǎng)頁(yè)排名方便，索引中還要存其他附加信息乓旗，如每個(gè)詞出現(xiàn)的位置府蛇，次數(shù)等等。因此整個(gè)索引就變得非常大屿愚，需要通過分布式存儲(chǔ)到不同服務(wù)器上（根據(jù)網(wǎng)頁(yè)編號(hào)劃分為很多小塊欲诺，根據(jù)網(wǎng)頁(yè)重要性建立重要索引和非重要索引）。
4.3 度量網(wǎng)頁(yè)和查詢的相關(guān)性：TF-IDF
我們以查找包含“原子能的應(yīng)用”網(wǎng)頁(yè)舉例渺鹦，“原子能的應(yīng)用”可以分成三個(gè)關(guān)鍵詞：原子能、的蛹含、應(yīng)用毅厚。憑直覺，我們認(rèn)為包含這三個(gè)關(guān)鍵詞較多的網(wǎng)頁(yè)浦箱，比包含它們較少的網(wǎng)頁(yè)相關(guān)吸耿。但這并不可取，因?yàn)檫@樣的話酷窥，內(nèi)容長(zhǎng)的網(wǎng)頁(yè)比內(nèi)容短的網(wǎng)頁(yè)占便宜咽安，所以要根據(jù)網(wǎng)頁(yè)長(zhǎng)度對(duì)關(guān)鍵詞的次數(shù)進(jìn)行歸一化，用關(guān)鍵詞的次數(shù)蓬推，除以網(wǎng)頁(yè)的總字?jǐn)?shù)妆棒，這個(gè)商叫做“關(guān)鍵詞的頻率”或“單文本頻率”（TF：Term Frequency）。比如，某個(gè)網(wǎng)頁(yè)上有1000詞糕珊，其中“原子能”“的”“應(yīng)用”分別出現(xiàn)了2次动分、35次、5次红选，那么它們的詞頻就是0.002澜公、0.035、0.005喇肋，將這三個(gè)數(shù)相加就是相應(yīng)網(wǎng)頁(yè)和查詢“原子能的應(yīng)用”的單文本頻率坟乾。所以，度量網(wǎng)頁(yè)和查詢的相關(guān)性蝶防，一個(gè)簡(jiǎn)單的方法就是直接使用各個(gè)關(guān)鍵詞在網(wǎng)頁(yè)中出現(xiàn)的總頻率甚侣。
但是這也有不準(zhǔn)確的地方，例如上面的例子中慧脱，“的”占了總詞頻的80%以上渺绒，但是它對(duì)確定網(wǎng)頁(yè)的主題幾乎沒什么用，我們叫這樣的詞為停止詞（stop word）菱鸥，類似的還有“是”“和”等宗兼。 另外“應(yīng)用”是很普通的詞，而“原子能”是專業(yè)詞氮采，后者在相關(guān)性排名中比前者重要殷绍。因此需要給每個(gè)詞給一個(gè)權(quán)重，權(quán)重的設(shè)定滿足兩個(gè)條件：
- 一個(gè)詞預(yù)測(cè)主題的能力越強(qiáng)鹊漠，權(quán)重就越大主到；
- 停止詞權(quán)重為零。
在信息檢索中躯概，使用最多的是“逆文本頻率指數(shù)”（IDF：Inverse Document Frequency）登钥，公式為
（D是全部網(wǎng)頁(yè)數(shù)，Dw為關(guān)鍵詞w出現(xiàn)的網(wǎng)頁(yè)個(gè)數(shù)）娶靡。最終確定查詢相關(guān)性牧牢，是利用TF和IDF的加權(quán)求和。 （IDF其實(shí)是在特定條件下關(guān)鍵詞概率分布的交叉熵）
4.4 搜索結(jié)果頁(yè)排序：Page Rank算法
這是拉里·佩奇和謝爾蓋·布林發(fā)明的計(jì)算網(wǎng)頁(yè)自身質(zhì)量的數(shù)學(xué)模型姿锭，google憑借該算法塔鳍，使搜索的相關(guān)性有了質(zhì)的飛躍，圓滿解決了以往搜索頁(yè)中排序不好的問題呻此。該算法的核心思想為：如果一個(gè)網(wǎng)頁(yè)被很多其他網(wǎng)頁(yè)所鏈接轮纫，說明它收到普遍的承認(rèn)和信賴，那么它的排名就高焚鲜。當(dāng)然掌唾，在具體應(yīng)用中還要加上權(quán)重放前，給排名高的網(wǎng)頁(yè)鏈接更高的權(quán)重。這里有一個(gè)怪圈郑兴，計(jì)算搜索結(jié)果網(wǎng)頁(yè)排名過程中需要用到網(wǎng)頁(yè)本身的排名犀斋，這不是“先有雞還是先有蛋的問題”嗎？ 謝爾蓋·布林解決了這個(gè)問題情连，他把這個(gè)問題變成了一個(gè)二維矩陣問題叽粹，先假定所有網(wǎng)頁(yè)排名相同（1/N），在根據(jù)這個(gè)初始值不斷迭代排名却舀，最后能收斂到真實(shí)排名虫几。
4.5 新聞分類：余弦定理
google有新聞?lì)l道，里面的內(nèi)容是由計(jì)算機(jī)聚合挽拔、整理并分類各網(wǎng)站內(nèi)容辆脸。以前門戶網(wǎng)站的內(nèi)容是由編輯在讀懂之后，再根據(jù)主題分類螃诅。但是計(jì)算機(jī)根本讀不懂新聞啡氢，它只會(huì)計(jì)算，所以要讓計(jì)算機(jī)分類新聞术裸，首先就要把文字變成可計(jì)算的數(shù)字倘是，再設(shè)計(jì)一個(gè)算法來(lái)計(jì)算任意兩篇新聞的相似性。
計(jì)算一篇新聞中所有實(shí)詞的TF-IDF值袭艺，再把這些值按照對(duì)應(yīng)的實(shí)詞在詞匯表的位置依次排列搀崭，就得到一個(gè)向量。例如詞匯表中有64000個(gè)詞猾编，其編號(hào)和詞如左下表所示瘤睹，在某一篇新聞中，這64000個(gè)詞的TF-IDF值如右下表所示答倡，這64000個(gè)數(shù)就組成了一個(gè)64000維的向量轰传，我們就用這個(gè)向量代表這篇新聞，成為這篇新聞的特征向量瘪撇。每篇新聞都有一個(gè)特征向量获茬，向量中的每個(gè)數(shù)代表對(duì)應(yīng)的詞對(duì)這篇新聞主題的貢獻(xiàn)。
同一類的新聞设江，一定某些主題詞用的較多，兩篇相似的新聞攘轩，它們的特征向量一定在某幾個(gè)緯度的值比較大叉存。如果兩個(gè)向量的方向一致，就說明新聞的用詞比例基本一致度帮，我們采用余弦定理計(jì)算兩個(gè)向量間的夾角：
新聞分類算法分為有目標(biāo)和無(wú)目標(biāo)：第一種是已知一些新聞?lì)悇e的特征向量歼捏，拿它分別和所有待分類的新聞?dòng)?jì)算余弦相似性稿存，并分到對(duì)應(yīng)的類別中，這些已知的新聞?lì)悇e特征向量既可以手工建立瞳秽，也可以自動(dòng)建立瓣履； 第二種是沒有分好類的特征向量做參考，它采用自底向上的聚類方法练俐，計(jì)算所有新聞兩兩之間的余弦相似性袖迎，把相似性大于一個(gè)閾值的新聞分作一個(gè)小類，再比較各小類之間的余弦相似性腺晾，就這樣不斷待在聚合燕锥，一直到某一類因?yàn)樘蠖鴮?dǎo)致里面的新聞相似性很小時(shí)停止。
