搜索引擎的故事
哈克，在咱倆站著的地方的下面，你拿一根釣魚竿就可以觸到我鑽出來的那個洞。看看你能不能找到。
——馬克·吐溫，《湯姆·索亞歷險記》
有一些特別重要的演算法。
首先，是大家用得最多的搜索引擎索引。在浩瀚的網路中尋找某些信息，無異於在世界上最大的草垛中尋針。
搜索引擎對我們的生活產生了深遠影響。
絕大多數人每天都進行多次搜索查詢，但我們極少會停下來思考這個令人驚嘆的工具是如何奏效的。
搜索引擎提供的海量信息以及搜索結果的速度與質量變得如此平常，如果我們搜索的問題沒有在幾秒內得到回答，我們就會困惑。
我們傾向於忘記，每一個成功的搜索引擎都是從世界上最大的草垛——萬維網——尋針。
事實上，搜索引擎提供的超級服務，不僅僅是針對搜索拋出一大堆花哨技術的結果，每個大型搜索引擎公司都運營著一個由無數數據中心組成的國際網路，其中包括數以千計的伺服器計算機和先進的網路設備。
但沒有聰明的演算法來組織和檢索我們請求的信息，所有這些硬體都會變得毫無用處。
搜索引擎的兩大主要任務就是匹配（matching）和排名（ranking）。
當你發起一次網路搜索查詢時會發生什麼？搜索有兩個主要階段：匹配和排名。
一個好的搜索引擎不僅僅會挑出最好的幾個命中，而且會以最有用的順序顯示它們——最匹配的頁面排在第一，然後是匹配度排名第二的頁面，依此類推。
在實際中，搜索引擎將匹配和排名組合成一個流程以實現一致性。
現實搜索引擎中的許多查詢都有數百、數千乃至數百萬個「命中」，而搜索引擎用戶通常只喜歡查看幾個結果，最多5個或10個。
因此，搜索引擎必須從大量命中里挑出最好的幾個，以正確順序挑選出最好的幾個命中被稱為「排名」。
在搜索行業的殘酷世界中，搜索引擎的生死由其排名系統的質量決定。
第一個互聯網級別的匹配演算法叫作AltaVista，1995年推出，20世紀90年代中期的幾年中，AltaVista是搜索引擎的王者。
索引的概念是所有搜索引擎背後最基礎的思想。
但索引並非由搜索引擎發明：事實上，索引的思想幾乎和書寫本身一樣古老。
比如，人類學家發現了一座具有五千年歷史的巴比倫神廟圖書館，裡面按學科對楔形文字泥版進行了分類。
因此，索引可以稱得上是計算機科學中最古老的有用思想。
如今，「索引」這個詞通常指參考書最後的一個板塊。你可能想要查看的所有概念都以固定順序（通常是按字母排序）列出，每一個概念下都列出了這個概念出現的位置（通常是頁碼）。
互聯網搜索引擎的索引和一本書的索引有著相同的工作原理。書「頁」現在成了萬維網上的網頁，而搜索引擎則給互聯網上的每個網頁分配了一個不同的頁碼。
想像萬維網只由上面顯示的3個短網頁組成，它們分別分配到了頁碼1、2和3。通過這種簡單方法，搜索引擎就已經能回答許多簡單的查詢，不過，不幸的是，這種簡單方法完全不能滿足現代搜索引擎的需要。
此時出現了另一個重要演算法，就是PageRank，這是一項讓谷歌騰飛的技術。
在當年《個人計算機雜誌》的評論中，谷歌的精英管理層因為谷歌「以超乎尋常的技巧返回相關度極高的結果」而獲獎，正是得益於谷歌用來對其搜索結果進行排名的創新演算法，PageRank，使其在搜索質量上超越當時已經很受歡迎的Lycos和AltaVista。
你肯定已經知道了超鏈接是什麼：超鏈接是網頁上的一個短語，當你點擊它時，你將被帶到另一個網頁。
絕大多數網路瀏覽器用藍色底線顯示超鏈接，以便能輕易識別。
其實，超鏈接也是老想法，來源於1945年美國工程師範內瓦·布希發表的一篇極具前瞻性的論文《誠若所思》。
在這篇涉獵廣泛的論文中，布希描述了大量可能的新技術，包括一台被稱作麥麥克斯的機器。
谷歌的兩位聯合創始人於1998年在他們著名的會議論文《解析大規模超文本網路搜索引擎》中描述了隨機訪問者把戲。
通過和其他許多技術結合，這一把戲的變體仍被主流搜索引擎所使用。
不過，由於眾多複雜因素，應用在現代搜索引擎中的實際技術和本章描述的隨機訪問者把戲略有不同。
其中一個複雜因素直擊PageRank的核心：有時候，假設超鏈接傳輸的合法權威性有爭議。
儘管超鏈接能代表批評而非推薦，但這在現實中並不是個很大的問題。另一個更加嚴重的問題是，人們可以濫用超鏈接把戲，人為地提高自己網頁的排名。
第三個重要的演算法，叫作公鑰加密。
人們喜歡傳謠，也喜歡了解秘密。而由於加密的目的就是傳輸秘密，所以我們都是天生的密碼員。
但人類進行秘密溝通要比計算機容易。
如果你想向朋友透露一個秘密，你只需在朋友耳邊低聲說就行，計算機要做到這一點就不那麼容易了。
一台計算機沒有辦法「低聲」向另一台計算機透露一張信用卡的卡號。如果計算機由互聯網相連，它們控制不了信用卡卡號的流向，也無法控制會有哪些計算機知道卡號。
在現實生活中，如果你想要發送一份機密文件給某人，你自然會在發送前將文件封存在一個安全的密封的信封內。這並不能保證機密性，但卻是正確方向上的一個合理步驟。
這也正是計算機在互聯網上嘗試相互進行機密通信時面臨的問題。
因為互聯網上的所有消息都會通過無數被稱為路由器的計算機，消息的內容可以為任何訪問路由器的人所見，而這也包括潛在的惡意竊聽者。
因此，每一塊離開你計算機並進入互聯網的數據，就好像寫在明信片上！
公鑰加密演算法是公開建立一個共享密鑰。大家都知道，互聯網上絕大多數加密技術的運作原理是：將消息分成塊，使用加法把戲變體加密每個塊，但這是加密簡單的地方。
難點在於一開始要建立一個共享密鑰，計算機科學家們用了一個精巧的解決方案解決這個問題，被稱為為迪菲—赫爾曼密鑰交換。
第四個重要的演算法，叫作糾錯碼。
計算機有三項基本工作。最重要的工作是執行計算，即給予計算機一些輸入數據，計算機必須用某種方法轉化數據，並得出一個有用的答案。
但如果沒有計算機執行的另外兩項非常重要的工作：存儲數據和傳輸數據，計算答案的能力基本上也沒用。
對於計算機而言，精確度達到99.9999%也還是不夠好。計算機必須能在存儲和傳輸數十億塊信息的情況下，不犯任何一個錯誤。
要通過一個不可靠的頻道進行可靠的通信，其中最根本的把戲是我們都熟悉的：要確保一些信息正確地傳輸，你只需重複幾次該信息。這是重複把戲。
假設銀行的一台計算機試圖通過互聯網把你的賬戶餘額傳給你。你的賬戶餘額是5213.75美元，但不幸的是，網路不穩定，每一個數字都有20%的概率變成其他東西。你不能只發送原始消息：你要發送一些多餘的東西以增加可靠性。這是冗餘把戲。
公鑰加密，是最精巧、最具有影響力的計算機科學思想之一，最流行的分塊密碼是高級加密標準AES，AES能配合多種不同配置使用，但標準配置是使用16個字母的塊，配備128位密鑰，進行10輪混合操作。
第五個重要的演算法，叫作圖形識別。
圖形識別是人工智慧的一部分，包括面部識別、物體識別、語音識別和筆跡識別等任務。
更具體的例子，如判定一張照片是不是你姊妹的照片，或判定手寫信封上的城市及地名。
因此，圖形識別可以更通俗地定義為，讓計算機基於輸入數據「聰明地」行動的任務，這些數據包含大量的變數。
因此，圖形識別的基本任務就是處理一些變數極多的數據——如不同光照環境下的各種人臉照片，或不同人書寫許多不同字的筆跡樣本——並做一些有用的事。
從一開始看，圖形識別的任務種類多得似乎超乎尋常。計算機能使用一個單獨的圖形識別技術工具包來識別筆跡、面部、語音及更多東西嗎？
這一問題的可能答案之一是：盯著我們的臉看，人腦在處理多種多樣的識別任務上速度超快、精確度超高。我們能編寫一個計算機程序來做到相同的事嗎？
在討論那樣一個程序可能用到的技術之前，我們需要統一令人眼花繚亂的多種任務，定義一個單一問題讓我們來嘗試解決。
要實現這一點，標準做法是將圖形識別看作分類問題。我們假設要處理的數據被分解成合理大小的塊，這些塊被稱為「樣本」，每一個樣本都屬於可能「類」（class）的固定集之一。
比如，在一個人臉識別問題中，每一個樣本都是一張人臉圖片，而類則是系統能識別出的這些人的身份。
有三種相關的演算法：最近鄰分類器（nearest-neighbor classifier）、決策樹（decision tree）以及人工神經網路（artificial neural network）。
分析引擎沒有原創任何東西的權利，它只能按照我們的指令執行任何事情。
——艾達·勒芙蕾絲
心歸航，再啟航
願每日微小知識激發你的深刻思考
TAG:DeepSci |