改變世界的九大演算法 Nine Algorithms That Changed the Future
改變世界的九大演算法
讓今日電腦無所不能的最強概念
Nine Algorithms That Changed the Future
The Ingenious Ideas That Drive Today’s Computers
John MacCormick——著
陳正芬——譯
經濟新潮——出版
via amazon
本書介紹讓電腦網路世界得以運作，並塑造今日人類生活的九大演算法。
電腦科學的偉大概念通常是在描述如何解決某個東西。電腦程式需要以非常精準的指令來編寫，若想要電腦解決某個問題，就需要為那個問題開發「演算法」（algorithm）。
- 你是否曾經在數十億份資料中搜尋，然後挑出兩三份最合乎你需求的資料？
- 你是否儲存或傳輸了數百萬筆資訊，沒有一次發生錯誤，即使所有的電子器材都遭到電磁干擾？
- 你是否成功地完成一筆線上交易，即使還有數千個人也同時把資料敲進同一台伺服器？
- 你是否在電纜線上安全地傳輸機密資訊（如信用卡卡號），哪怕有幾十台電腦可能透過纜線窺伺你的一舉一動？
- 你是否運用神奇的壓縮技術，把一張數MB大的照片壓縮成方便電郵傳送的大小？
- 最後，你是否利用手持裝置那小小鍵盤上，針對你輸入的字詞進行自動偵錯的人工智慧而不自知？
- 每天會被一般電腦使用者用到的演算法，因此諸如「編譯器」（compiler）和「程式認證」（program verification）等主要被IT專業人士使用的演算法，不在此列。
- 必須能解決現實世界的具體問題，例如壓縮檔案，或是透過繁忙的網路連線精準無誤地傳輸檔案。這項標準把大學的電腦科學課程中最重要的一些演算法排除在外，包括快速排序法（quicksort）等排序演算法、Dijkstra的最短路徑演算哪等圖形演算法，以及雜湊法（hash table）等資料結構，這些無疑都是了不起的演算法且符合第一項標準，但這些演算法是可被應用到各種問題上的通用演算法，本書將聚焦在某些特定問題的演算法上，因為這些演算法要解決的問題，對一般電腦使用者來說較為明確。
- 主要是與電腦科學理論有關的演算法，因此凡以CPU、螢幕和網路等硬體為主的演算法就不在挑選內。這項標準也不強調網際網路之類基礎設施的設計。作者聚焦在電腦科學理論，是由於作者撰寫本書的部分動機在於一般人對電腦科學的認知失衡，人們普遍認為電腦科學是跟寫程式（軟體）和機器設計（硬體）有關，事實上，電腦科學中的一些最美的概念是抽象的、理論性的概念。
- 美、簡潔、優雅。本書中所提的演算法，其精隨都是利用一些聰明的「技法」（trick）來解決問題。英國數學家G. H. Hardy在其著作《A Mathematician's Apology》中，如此解釋數學家的所作所為：「第一個考驗的是美。這世界沒有醜陋數學的永久容身之處。」電腦科學也同樣要接受這項考驗。
- 搜尋引擎的索引（search engine indexing）
- 搜尋引擎的無遠弗屆的影響力，證明了演算法技術可以影響所有電腦使用者，因此我納入一些與網路搜尋相關的核心演算法。第二章敘述搜尋引擎如何利用標註索引的方式找到符合查詢條件的文件。
- 網頁排序（page rank）
- 第三章解釋何謂網頁排序，這是谷歌為了確保最相關的文件被列在搜尋結果的最頂端，所使用演算法的原始版本。
- 公鑰加密（public-key cryptography）
- 有些偉大的演算法卻往往在電腦使用者渾然不覺之際被啟動，如第四章的公鑰加密。每當你進入一個安全的網站（網址是以https開頭，並非http），就是在使用所謂密碼交換（key exchange）的公鑰加密來保護傳輸的資料，第四章將解釋這種密碼交換的機制。
- 錯誤更正碼（error-correcting codes）
- 第五章的錯誤更正碼，也是我們一直在使用卻沒有察覺的演算法，事實上錯誤更正碼可說是至今人們最頻繁使用的偉大概念，電腦無須借助備份或重新傳輸，就能查知並更正被儲存或傳輸資料的錯誤。錯誤更正碼無所不在，包括所有硬碟機、許多網路傳輸、CD和DVD，甚至在某些電腦的記憶體裏──只是錯誤更正碼運作得太完美，以至於我們根本沒有意識到它的存在。
- 模式辨識（pattern recognition，如手寫辨識、聲音辨識、人臉辨識等等）
- 第六章探討模式辨識的演算法，可說是被我夾帶進入電腦科學的偉大概念清單，因為它並非電腦使用大眾每天使用，因此不符第一項標準。電腦透過此種技術來辨識手寫、口說和人臉等具高度變異性的資訊。事實上，在21世紀的第一個10年間，日常電算功能大多沒有使用這項技術，但在我撰寫本書的2011年，模式辨識的重要性驟增，行動裝置螢幕上的小型鍵盤需要自動更正、平板裝置必須辨識手寫輸入，且愈來愈多這類裝置（特別是智慧型手機）採用聲控，有些網站甚至用模式辨識來判斷該把什麼類型的廣告呈現給使用者。我個人偏愛模式辨識，因為那是我的專業研究領域，因此第六章將說明最近鄰居分類法（nearest-neighbor classifier）、決策樹（decision tree）和神經網路（neural networks）等三種最有趣且最成功的模式辨識技術。
- 資料壓縮（data compression）
- 第七章的壓縮演算法來自另一組偉大的發想，讓電腦變得更聰明有用。電腦使用者有時為了節省硬碟空間或縮小照片所佔的記憶容量以便透過電郵傳送而直接應用壓縮，其實壓縮功能在私底下更常被使用，我們沒有注意到上傳和下載的資料可能經過壓縮以節省頻寬，資料中心往往壓縮顧客資料以節省成本，至於電郵提供者容許你使用的5GB空間，實際占用的儲存空間說不定遠小於5GB！
- 資料庫（databases）
- 第八章是資料庫的一些基本演算法，主要是探討如何達到一致性──資料庫中資料之間的關係絕不會彼此矛盾。少了這些精妙的技術，你我的網路生活（包括網路購物、在臉書之類社交網站上的互動）將毀在電腦層出不窮的錯誤中。這一章將解釋「一致性」的問題，電腦科學家如何解決它，而不犧牲網路系統帶來的無比效率。
- 數位簽章（digital signature）
- 第九章來到電腦科學理論公認的閃亮巨星──數位簽章。乍看之下，用數位方式在電子文件上「簽章」似乎不可能，你當然會想，所有這類的簽章一定包含了數位資訊，因此凡是想偽造簽章的人都可以輕易拷貝。解決這種兩難局面正是電腦科學最了不起的成就之一。
- 一種如果存在的話將會很了不起的偉大演算法，並探討電腦能力的極限。
- 電腦科學家把許多重要概念描述成一個個「演算法」。概念和演算法之間有什麼不同？簡單來說，演算法好比一個「精確的食譜」，把解決問題的確切步驟解釋得一清二楚。演算法的各步驟具有機械式的特質，每個步驟必須絕對精確，不需要靠人類的直覺或猜測，這也是演算法的關鍵特點，如此一來每個純機械式的步驟就可以被編寫成程式之後輸入電腦。另一個重要特點，就是無論輸入什麼都能給出正確答案。那究竟這個精確的機械式食譜要多精確？哪些基礎運算是被允許的？就以相加的演算法為例，可不可以光是說「把兩個數加起來」，還是必須明確列出一整組單一數字相加的表格？像這類細節或許有點做作，但這些問題其實正是電腦科學的核心問題，而且與哲學、物理學、神經科學和基因遺傳學相關。演算法究竟是什麼，這個深奧的問題終歸所謂「丘池─圖靈論點」（Church-Turing thesis），這個議題也會在書中的第十章談到。
- 這章將不介紹已經存在的偉大演算法，而是看看如果存在的話會很了不起的演算法。我們將會發現，這麼了不起的演算法竟然不可能存在，這也證實電腦解決問題的能力受到某些絕對的限制，我們也將簡短探討這在哲學和生物學上的含義。
每一種演算法，都是一個解決問題的創意與線索，也讓我們得以一窺近代數學家、資訊科學家的努力探索成果。
最後在結論中，將從各個偉大的演算法歸納出共同理路，並推測：未來還會有更多偉大的演算法被發明出來嗎？
Search Engine Indexing
“Now, Huck, where we're a-standing you could touch that hole I got out of with a fishing-pole. See if you can find it.”本章及下一章探討網路搜尋必定會用到的核心演算法，如何進行「配對」（matching）和「排序」（ranking）。基於效率的考量，搜尋引擎把配對和排序合併成一個程序，但這兩個階段在概念上是分開的，因此我們將假設配對完成後才開始排序。
——Mark Twain《The Adventures of Tom Sawyer》
配對 排序
查詢時刻表 → 符合條件的網頁 → 排序後的網頁
好的搜尋引擎會挑出最佳的結果，最適合的網頁會列在首位，並以最相關、最方便使用的順序呈現。目前佔高市佔率的搜尋龍頭Google，一般都認為是因為它強大的排序演算法，排序系統的品質決定了搜尋引擎的生死，。
1994年的Infoseek和Lycos可說是最早的商用網頁搜尋工具。AltaVista則是在1995年推出的搜尋引擎，它也在90年代中期佔據搜尋引擎的寶座，AltaVista是最先將每個網頁的內文完整「標註索引」（indexing）的搜尋引擎。
「索引」是每個搜尋引擎背後最基礎的概念，標住索引堪稱電腦科學中最古老且有用的概念。搜尋引擎的索引和書籍索引的原理相同，書籍的「第幾頁」變成網頁，搜尋引擎賦予每個網頁一個頁碼。「片語搜尋」是搜尋某個特定片語，而不只是某一頁上某處出現的幾個字，然而，古早的陽春式索引將在搜尋片語時極無效率。
因此，索引不該只儲存每個字在哪一頁，也要儲存每個網頁中的位置資訊，也就是每個字在網頁中的位置，這種建構式索引稱為「文字－位置技法」（word-location trick）。
對於排序的概念，真正的問題並非「這個網頁根所要查詢的東西符不符合？」而是「這個網頁跟所要查詢的東西相關嗎？」電腦科學家用「相關」來說明某特定網頁對特定查詢的適合度或有用度。
「元詞技法」（metaword trick）讓搜尋引擎以極有效率的方式回答文件架構的查詢，此技術可以讓你搜尋網頁標題、超連結內的字、圖像說明等各種網頁有用的部分。
元詞技法讓AltaVista成功地在網路中有效率地找到配對，在1999年美國專利的存檔中，有篇文章＜Constrained Searching of an Index＞就提到元詞技法，不過AltaVista精心設計的配對演算法不足以讓它安然度過早期搜尋產業的動盪，除了有效率的配對法，對符合條件的網頁進行排序才是重頭戲，一種新型態的排序演算法將讓AltaVista黯然失色，並將Google推上搜尋引擎的寶座。
網頁排序
Page Rank
Google成立於1998年9月，在加州Menlo Park的某個車庫裡營運。事實上，當時Google經營網路搜尋已有一年多，兩位創辦人利用史丹佛大學的伺服器經營，但其服務變得越來越熱門，導致所需的平寬令大學不堪負荷，於是才將業務移轉到公園車庫。在正式成立後的三個月，Google就入選《PC Magazine》1998年百大網站之一，它以其「搜尋結果具高度相關性的超強能力」獲此殊榮。這其中最重要的因素，就是Google替搜尋結果排序的創新演算法，也就是「網頁排序」（PageRank）。
PageRank是個雙關語，它既是一種排序演算法，也是主要發明人Larry Page的演算法。1998年Larry Page和Sergey Brin在一個學術會議上發表〈The Anatomy of a Large-Scale Hypertextual Web Search Engine〉這篇論文，將此演算法公諸於世。這篇論文如其標題所示，不光說明了網頁排序，而是完整敘述了1998年時的Google系統。然而藏在大量技術細節當中的，是21世紀時將成為演算法之王的網頁排序演算法。
via cdn.theatlantic.com
超連結（hyperlink）是網頁上的「片語」，只要用滑鼠點它就會帶你到另一個網頁。大部分的網頁瀏覽器會用藍色底線標示來凸顯。1945年，大約電子計算機剛被開發時，工程師Vannevar Bush發表一篇＜As We May Thing＞的文章，他在文章中談到許多有潛力的科技，包括一台他稱為memex的機器，這台機器會儲存文件然後自動標註索引，不只如此，它還能做「聯想式索引……人們可以隨意讓任何一個項目立即且自動去挑選另一個項目」，換言之就是早期的超連結。從那之後，超連結不斷地發展，如今已是搜尋引擎排序的最重要工具，Google的排序技術也以它為基礎。
要了解網頁排序，第一步就是了解「超連結技法」這個概念。
電腦無法輕易了解某個網頁真正的意思，因此搜尋引擎無法檢視這些搜尋到的網頁，並評估每個連結網頁的狀況。但電腦很會計數，所以一個簡單的方法是去計算每個網頁分別有幾個外來的連結，然後根據這個數量來排序。結果發現，在沒有其他資訊的情況下，一個網頁所擁有的外來連結數，可能足以成為該網頁實用性與權威性的指標，於是搜尋引擎在呈現結果時，會將連結數較多的網頁排在前面。
當然，有時不好的網頁翻而得到較多連結數，但好在實務上，超連結的褒多於貶，因此這種技法還是有用的。
「權威性技法」（authority trick），指的就是來自高權威性網頁的連結，應該比低權威性網頁的連結獲得較高的排序。
這個原則看來合情合理，但以目前這種形式對搜尋引擎並沒有用處，電腦要如何自動判斷哪個網頁更具權威性？將超連結技法結合權威性技法或許有幫助。所有網頁一開始的權威分數都是1分，但如果某個網頁有幾個外來連結，它的權威性就等於這些外來連結的權威分數加總，換言之，如果X和Y網頁連結到Z，則Z的權威分數就等於X和Y的權威分數的和。
看來這個策略能讓電腦自動計算權威分數又無需真正了解網頁內容，但不幸的是，這個方法可能有個大問題。超連結很可能形成電腦科學家所謂的「兜圈子」（cycle），如果你藉由點擊一連串超連結能夠回到原點，這時的你就是在兜圈子。
「隨機漫遊技法」（random surfer trick）可以解決這個問題。
隨機漫遊技法一開始的描述與超連結與權威性技法並無相似之處，等探討過隨機漫遊技法的基本機制後，會分析它不可思議的特質，看它如何結合超連結與權威性技法的優點，即使在兜圈子的情況下依舊能發揮應有的功能。隨機漫遊模擬計算出的百分比，正好是我們在衡量網頁的權威性所需的。我們把某個網頁的漫遊者權威分數（surfer authority score），定義為隨機漫遊者花在造往該網頁上的時間百分比。漫遊者的權威分數會同時納入先前兩種替網頁排序的技法。首先是超連結技法，當一個網頁有很多外來連結時就應排在前面，這點也適用漫遊者模型。其次是權威性技法，來自高權威網頁的連結所獲得的排名，將優於來自權威性較低網頁的連結，隨機漫遊者模型也將此納入考量，因為熱門網頁的連結比非熱門網頁的連結更有可能被追蹤。隨機漫遊者模型涵蓋這兩種技法，一併考慮每個網頁外來連結的質與量。
首先，想像有人正隨機地在網路上漫遊，這位漫遊者從全球資訊網上隨機挑選一個網頁開始，接著檢視這個網頁上所有的超連結，隨機挑選其中一個按下滑鼠。接著，他檢視這個新網頁並隨機選擇一個超連結按下滑鼠……這個過程繼續下去，每個新網頁都是在前一個網頁隨機點選一個超連結而產生的。
整個過程有一個特點，也就是當漫遊者來到一個網頁時，他不點選其中一個超連結而選擇重新開始的機率是固定的（假設是15%），這時他會從網路隨機挑選另一個網頁，重新開始整個過程。可以這麼想像：網路漫遊者有15%的機率會對任何一個網頁感到無趣，因此重新開始，走另一趟新的連結。（本章所有隨機漫遊的例子是用15%的重新開始機率。而谷歌創辦人佩吉和布林在最初的論文中，就是用15%的重新開始機率來說明他們的搜尋引擎原型。）(p.64, 65)
但現代搜尋引擎真正採用的技術，在某方面已經不同於此處的隨機漫遊技法。人們可能會濫用超連結技法而刻意拉抬自己的網頁排名。搜尋引擎稱這種濫用的結果稱網路垃圾（web spam，這詞來自e-mail spam，一堆塞住網路搜尋結果的垃圾網頁，就好比塞滿你收件夾的垃圾郵件）。偵測並消除各種型態的網路垃圾，對搜尋引擎來說是重要的長期抗戰。這場軍備競賽，席捲了學術界和產業大量投入研究，改善「網頁排序」，因此孕育出一些利用網路超連結架構來替網頁排序的演算法，這類演算法通常被稱為連結基礎的排序演算法（link-based ranking algorithms）。
另一個使情況更為複雜的因素，則是和「網頁排序」的計算效率有關，漫遊者的權威分數是執行隨機模擬去計算的，但這樣的模擬太耗時，因此搜尋引擎不是藉由網路執行模擬來計算值，而是用數學方法去得出和隨機漫遊者模擬相同的答案。漫遊者模擬技術具有很直覺的優點，也描述了搜尋引擎計算什麼，而非如何計算。
公鑰加密
Public-key Cryptography
“Who knows those most secret things of me that are hidden from the world.”
——Bob Dylan＜Covenant Woman＞
人喜歡八卦，喜歡祕密。加密的目的是為了傳遞祕密，因此每個人都是天生的加密高手──人能夠比電腦更輕易地祕密溝通，如果你想告訴朋友一個祕密，只要在對方的耳朵旁講悄悄話就行了，電腦可就沒那麼容易辦到，電腦沒辦法把信用卡卡號「輕聲」說給另一台電腦聽，如果電腦和網際網路連線，就更加無從控制信用卡卡號會被傳到哪裏、被哪幾台電腦窺知。本章將探索電腦如何利用公鑰加密（public key cryptography）來克服這個問題，而這也是電腦科學至今最聰明且最具影響力的概念。(p.75)
我們把公鑰加密比喻成用明信片溝通，現實生活中，如果你想寄機密文件給某人，你當然會把文件妥善密封在信封裏寄出，雖無法保證天衣無縫，但畢竟不失為穩妥的做法。把機密訊息寫在明信片上寄出顯然無法保密，因為凡是接觸得到明信片的人（例如郵務員）都會看到明信片上的訊息。回到明信片的比喻，這狀況聽起來有點矛盾，收件者看到的資訊與郵務員看到的資訊一模一樣，但收件者能夠將訊息解密，郵務員卻不能。公鑰加密會為這個矛盾提供解答。
以上正是電腦在網際網路上進行祕密溝通時遇到的問題。由於網路上的任何訊息通常都會經過許多「路由器」（routers），凡是能進入路由器的人（包括惡意竊聽者）都能一窺訊息內容，因此從你的電腦出去的每一筆資料進入網路後，就如同寫在明信片上一樣！
或許你已經替明信片問題想到快速的解決之道。何不用密碼在訊息上加密後，再寫在明信片上？如果你認識收件人，這麼做是可行的，因為你們過去可能已經針對密碼達成共識，但真正的問題在於你寄明信片給不認識的人時，如果你在這張明信片上使用密碼，那麼郵務員將無從知道你的訊息，但收件人也看不懂！公鑰加密真正厲害的地方是，你使用只有收件人能破解的密碼，儘管你們根本沒機會針對使用的密碼暗中達成共識。
電腦在面對不認識的收件人時也面臨同樣的溝通問題。例如你第一次用信用卡在亞馬遜網站買東西，於是電腦必須將你的信用卡卡號傳給亞馬遜的伺服器，但是你的電腦從沒和亞馬遜的伺服器傳輸過訊息，因此這兩台電腦過去沒有機會針對密碼達成共識，而它們試圖達成的任何共識，都可以被網路上它們之間所有的路由器觀察到。(p.75, 76, 77)
錯誤更正碼
Error-correcting Codes
“It is one thing to show a man that he is in error, and another to put him in possession of the truth.”1940年，貝爾電話公司的Richard Hamming在週末要用電腦讀取資料時，電腦卻一再當機。他在不久後就創造出有史以來的第一個錯誤更正碼，它能偵測並且改正電腦資料的錯誤，少了這些碼，今日的電腦和通訊系統無論在速度、運算能力和可靠度都將遜色許多。
——John Locke《An Essay Concerning Human Understanding》
電腦有三種基本功能，最重要的是計算，電腦在資料輸入後，必須以某種方式轉換資料來產生答案，但是如果少了儲存資料和轉換資料這兩種功能，電腦基本是無用的。電腦大多將資料儲存在記憶體和硬碟，而且通常透過網際網路來傳輸資料。想像一台電腦不能儲存也無法傳輸資訊，那幾乎是台廢物。
但資料的傳輸和儲存面對一個巨大挑戰：資料必須是完全正確的，因為在許多情況下即使是一個微小的錯誤，都可能使資料變成垃圾。我們經常需要正確無誤地傳輸和儲存資訊，有時資料錯誤比資料無用更嚴重，例如儲存電腦程式的檔案若有錯，可能導致程式當掉或無法執行該做的事情。在一些財務檔案中的錯誤，甚至造成金錢損失。
對人們來說，需要留存的無誤資訊在數量上並不督，而且只要仔細檢查就能避免例如銀行帳好、密碼、電子信箱等重要資訊出錯；但是，電腦需要正確無誤地儲存和傳輸的資訊量非常龐大，假設你某種電算裝置擁有100G的容量，這100G就相當於一千五百萬頁的文字，即使這台電腦的儲存系統在每一百萬頁中只犯一個錯，在容量滿載的情況下仍平均會有15個錯誤。資料傳輸也是如此，當你下載20MB的軟體，你的電腦在接收每一百萬個字元中只出現一個讀取錯誤，你下載的軟體還是會超過20個錯誤，而每個錯誤都可能在你意想不到的時候，造成嚴重當機。
本章將揭開電腦零失誤背後的觀念，還有其技法，就連極不可靠的溝通管道都可傳輸資料，且失誤率幾乎為零。
- 重複技法
- 冗餘技法
- 校驗技法
- 定點目標技法
模式辨識
Pattern Recognition
“The Analytical Engine has no pretensions whatever to originate anything. It can do whatever we know how to order it to perform.”
——Ada Lovelace, Notes upon L. F. Menabrea’s
“Sketch of The Analytical Engine Invented by Charles Babbage”, 1842
這是Ada Lovelace於1843年對於一台被稱為「分析引擎」（Analytical Engine）的機械式電算機的射機，所做的評論。她強調電腦缺乏原創性，也就是說，電腦必須像奴隸一樣遵循程式設計師的指令。
本章所要提的模式辨識屬於人工智慧（artificial intelligence）的一部分，包含人臉辨識、目標辨識、語音辨識及手寫辨識等。模式辨識的一般定義是，要求電腦根據含有許多變異性的輸入資料，採取「有智能」（intelligent）的行動。
在討論這種技術之前，我們要先把各式各樣的任務整理一下，接著為我們想解決的單一問題給出一個定義，這裡的標準做法是，將模式辨識視為一種分類的問題。
電腦會使用兩種不同的壓縮型態，一種是無損失壓縮（lossless compression），另外一種則是損失壓縮（lossy compression）。無損失壓縮的演算法將資料壓縮成原始大小的幾分之一，之後經過壓縮會回復到跟原始檔案一模一樣。好的壓縮演算法可以針對特定幾種常見的檔案格式，帶來顯著的空間節省。資料壓縮的基本概念是找到彼此相同的資料，利用某種技法以更有效率的方式描述這些部分。
當資料具有重複性，上述做法就很容易做到。舉例來說，你大概知道如何壓縮下列資料：
不過，此編碼只在壓縮非常特定的資料型態時才有用，實務上多半只是和其他壓縮演算法合併使用，例如傳真機就是將資料長度編碼與Huffman coding並用。資料長度編碼的主要問題在於資料的重複性彼此靠近，不能有其他資料夾在重複的部分之間。使用此編碼來壓縮ABABAB是容易的，但不能壓縮ABXABYAB。
傳真機在定義上是黑白文件，這些文件被轉成大量的點，每個點非黑即白。當你依序（從左到右，從上到下）閱讀這些點，會遇到大串白點（背景）和小串的黑點（文字或手寫文字），因此可以很有效率地使用資料長度編碼。但正如上述所提，只有特定的某些資料型態具備這種特性。
於是電腦科學家發明更高明的方法，基本概念都是尋找重複的部分然後有效率地描述它們，但即使重複的部分不彼此靠近也能發揮作用。
資料庫牽涉到交易處理的兩大議題：效率和可靠性。資料庫透過演算法提供效率，讓幾千個顧客同時進行交易而不會導致衝突或不一致；此外資料庫透過演算法提供可靠性，讓資料在經歷電腦組件的故障時依然完好無缺，例如硬碟之類的故障通常會造成嚴重的資料毀損。線上金融則需要卓越的效率與百分之百的可靠性。
資料庫背後有三個基本且美麗的概念：
資料庫最重要的特質是，資料庫中的資訊具備是先定義好的架構，而這也是資料庫不同於其他儲存資訊方式之處。
先來了解「架構」的意義，所謂無架構的資訊如下：
本章所要提的模式辨識屬於人工智慧（artificial intelligence）的一部分，包含人臉辨識、目標辨識、語音辨識及手寫辨識等。模式辨識的一般定義是，要求電腦根據含有許多變異性的輸入資料，採取「有智能」（intelligent）的行動。
如今，科學家們對於電腦在原則上能否展現智能可說是意見分歧，而一旦神經科學家、哲學家和神學家也進來攪和，辯論就變得更加複雜。
為符合本書主旨，最好用「有用」來取代「智能」，因此模式辨識的基本任務，就是運用某些極具變異性的資料來做一些有用的事情。在討論這種技術之前，我們要先把各式各樣的任務整理一下，接著為我們想解決的單一問題給出一個定義，這裡的標準做法是，將模式辨識視為一種分類的問題。
- 最近鄰居分類法（nearest neighbor classifier）
- 決策樹（decision tree）
- 「二十個問題」（twenty question）的遊戲，在電腦科學家心目中有特別的魅力。在這場遊戲中，一位參加者心理暗想一個東西，其他人只能問他最多二十個是非題，要能猜出這東西是什麼。
- 關於好問題和爛問題的直覺判斷是資訊理論的核心，也就是決策樹這個簡單但威力強大的模式辨識技術的精隨。
- 人工神經網路（artificial neural networks，又稱類神經網路）
- 英國科學家Alan Turing在1950年發表＜Computing Machinery and Intelligence＞中，針對電腦是否能偽裝成人類，進行哲學性的探討。這篇論文中介紹了可用於評估電腦和人類相似性的科學方法，也就是圖靈測試（Turing test）。但圖靈在這篇論文較不為人知的段落中，直接分析了使用電腦建構人腦模型的可能性，他估計只要幾GB的記憶體應該就夠了。
- 六十年後，人們大多認為圖靈低估了模擬人腦所需花費的心力，但電腦科學家卻已許多不同的面相不斷追求這目標，其中一個結果就是人工神經網路，簡稱神經網路。
資料壓縮
Data Compression
電腦會使用兩種不同的壓縮型態，一種是無損失壓縮（lossless compression），另外一種則是損失壓縮（lossy compression）。無損失壓縮的演算法將資料壓縮成原始大小的幾分之一，之後經過壓縮會回復到跟原始檔案一模一樣。好的壓縮演算法可以針對特定幾種常見的檔案格式，帶來顯著的空間節省。資料壓縮的基本概念是找到彼此相同的資料，利用某種技法以更有效率的方式描述這些部分。
當資料具有重複性，上述做法就很容易做到。舉例來說，你大概知道如何壓縮下列資料：
AAAAAAAAAAAAAAAAAAAAABCBCBCBCBCBCBCBCBCBCAAAAAADEFDEFDEF如果你要將以上資料說給別人聽，你當然不會一個個照實唸出，而是類似「21個A，然後10個BC，再6個A，然後3個DEF」，或在紙上記下這筆資料，可能是「21A，10BC，6A，3DEF」，這時你已經將原始的56個字母壓縮到16個字母。這種技法被稱為「資料長度編碼」（run-length encoding），因為它用當次資料的長度對重複的資料編碼。
不過，此編碼只在壓縮非常特定的資料型態時才有用，實務上多半只是和其他壓縮演算法合併使用，例如傳真機就是將資料長度編碼與Huffman coding並用。資料長度編碼的主要問題在於資料的重複性彼此靠近，不能有其他資料夾在重複的部分之間。使用此編碼來壓縮ABABAB是容易的，但不能壓縮ABXABYAB。
傳真機在定義上是黑白文件，這些文件被轉成大量的點，每個點非黑即白。當你依序（從左到右，從上到下）閱讀這些點，會遇到大串白點（背景）和小串的黑點（文字或手寫文字），因此可以很有效率地使用資料長度編碼。但正如上述所提，只有特定的某些資料型態具備這種特性。
於是電腦科學家發明更高明的方法，基本概念都是尋找重複的部分然後有效率地描述它們，但即使重複的部分不彼此靠近也能發揮作用。
- 「同前技法」（same-as-earlier trick）
- 「較短符號技法」（shorter-symbol trick）
資料庫
Databases
via web.zizinya.com
“Data! Data! Data!” he cried impatiently. “I can’t make bricks without clay.”二十一世紀後，線上帳單支付和線上金融系統開始出現，網際網路的普及促成了這些轉變，除了第四章的公鑰加密外，資料庫也是線上交易不可或缺的技術。電腦使用者通常不會意識到這點，但幾乎所有的線上交易都是使用1970年代以來電腦科學家所開發完備的資料庫技術來處理。
——Conan Doyle《The Adventure of the Copper Beeches》
資料庫牽涉到交易處理的兩大議題：效率和可靠性。資料庫透過演算法提供效率，讓幾千個顧客同時進行交易而不會導致衝突或不一致；此外資料庫透過演算法提供可靠性，讓資料在經歷電腦組件的故障時依然完好無缺，例如硬碟之類的故障通常會造成嚴重的資料毀損。線上金融則需要卓越的效率與百分之百的可靠性。
資料庫背後有三個基本且美麗的概念：
- 預寫日誌（write-ahead logging）
- 兩階段承諾（two-phase commit）
- 關聯式資料庫（relational database）
資料庫最重要的特質是，資料庫中的資訊具備是先定義好的架構，而這也是資料庫不同於其他儲存資訊方式之處。
先來了解「架構」的意義，所謂無架構的資訊如下：
羅西娜三十五歲，她是麥特的朋友，麥特二十六歲。靜宜三十七歲，桑迪普三十一歲，麥特、靜宜和桑迪普彼此是朋友。這類資訊再遵循「表格」（table）這種架構轉為：
姓名 年齡 朋友
羅西娜 35 麥特
靜宜 37 麥特、桑迪普
麥特 26 羅西娜、靜宜、桑迪普
桑迪普 31 靜宜、麥特
表格上每一行是一件事的資訊（此處為人），每一攔是特定型態的資訊（如人的年齡或名字），資料庫通常由許多表格組成。
資料庫的操作人員相當執著於一致性（consistency），它代表資料庫中的資訊不會自相矛盾，而矛盾或不一致正是資料庫管理員的噩夢。
事實上，這種不一致在新資料加入資料庫時很容易避免，電腦擅長於守規定，要讓資料庫遵守「如果A和B結婚，B就一定是和A結婚」的規則並不困難，如果某人想輸入的資料違反此規則，就會收到錯誤訊息而無法輸入，因此這類案例只要制定簡單的規則來確保一致性，不需要多高明的方法。
資料庫戰勝了不可靠的元件——也就是電腦科學家口中的「容錯」（fault-tolerance）——是許多研究人員花了數十年所得到的結果，其中最重要的人物Jim Gray，他於1992年出版了一本談交易處理的著作《Transaction Processing: Concepts and Techniques》。
應該有不少人覺得，資料庫是個無趣的主題，畢竟要對資料的儲存感到興奮是很困難的，但在無趣的外表下，資料庫背後的概念卻很精彩。
資料庫不受硬體故障的限制，賦予線上金融等活動效率和堅若磐石的可靠度，代辦事項清單的技法給予我們如原子般的微小交易，使我們在許多顧客同時與資料庫互動下仍保有一致性。這個高度併行性加上透過虛擬表格技法達到的快速查詢回應，讓大型資料庫也很有效率。待辦事項技法在面對故障時確保一致，加上準備然後承諾技法的複製資料庫，史資料兼具緊密的一致性和持久性。
「數位」照字面解釋是「由一串數字所構成的」，因此凡是數位的東西都可被拷貝，只要一一將這些數字拷貝即可。但是，「簽章」的基本概念是可被讀取但是除了簽章的人以外其他人都無法拷貝。
數位簽章不是在交給別人的文件上使用，通常是別人在傳送文件給你之前使用。
事實上，電腦接收並認證數位簽章的頻率高得嚇人，因為一些經常被使用的網路協定就是利用數位簽章來確認與你互動的電腦的身分。例如網址以https開頭的安全伺服器通常會先傳給你的電腦一個數位簽章的憑證後，才建立安全連線。數位簽章也被用來驗證許多軟體元件的真實性，如瀏覽器插件（browser plugin），你在網路瀏覽時大概都看過類似的警告訊息。軟體簽章也是你最常看見的數位簽章之一。
本章說明如何創造一個無法被偽造的數位簽章。
數位簽章的第一步是完全捨棄書面簽章，改由上鎖、鑰匙和鎖箱來證明文件的真偽。在這套方法下，每位參與者都有大量的鎖，同一個人的鎖必定是一模一樣。此外，每位參與者的鎖必須互斥，沒有人能製造或取得與別人相同的鎖。最後，這些鎖都附有生物測定感應器（biometric sensor）以確保只能被擁有者上鎖。上述就是所謂的「實體鎖技法」（physical padlock trick）。
數位簽章依賴一個只有簽章者知道的秘密以及被簽章的訊息，這個簽章者是用同一個秘密來簽章他的每個訊息，但是不同的訊息會有不同的簽章。因此，雖然任何人都可拷貝簽章，但卻無關緊要，因為簽章不能被移轉到另一個訊息上，因此光是拷貝並無法完成偽造。
少了數位簽章，網際網路將不存在，資料雖還可透過加密來安全傳送，但要驗證收到資料的來源將會難上加難。
到底有什麼事是電腦辦不到的？
是，確實有些問題電腦永遠無法解決，永遠都會有些問題是「不可計算」（uncomputable）。
1930年代，美國科學家Alonzo Church，在計算理論方面的大突破，至今依舊是電腦科學的基礎；英國科學家Alan Turing，則被公認為奠定電腦科學的最重要人物，圖靈的研究成果涵蓋整個電算概念的光譜，從複雜的數學理論、深奧的哲學乃至大膽實用的工程學。
進入21世紀，自動檢查工具的大幅進步，減少了許多電腦軟體當機的頻率。但是，自動的軟體檢查工具並不能偵測出電腦程式中所有的潛在問題、當機狀況。
在電腦科學中，當我們說「X經證明不可能」，我們不光是指X顯然是困難的或實務上不可能達到，而是百分之百肯定X永遠達不道，因為已經有人用一連串演繹的數學推論證明了這點。
但電腦科學的預測，很有可能在有生之年就被證明是錯的。
牛津歷史學家A. J. P. Taylor曾在他的系列演講結尾中，直接提及會不會發生第三次世界大戰，答案是「會」他說，因為人類「一再重蹈覆轍」，這系列演講內容也以《How Wars Begin》於1997年出版成書。
順著歷史的洪流，這些演算法的技術勢必會持續加速成長，但這本身並不足以保證會出現偉大的演算法。未來演算法的創新將放慢步調，因為電腦科學相較於數學、物理學和化學等領域是相當年輕的，要發現偉大的演算法相對容易。這也表示，未來要找到聰明且具廣大應用的演算法會越來越困難。新技術提供的新利基偶爾會為新的演算法提供大展身手的舞台，然而領域的漸趨成熟卻使得到機會愈來愈窄。
然而，仍有些極具潛力的利基和技術，人工智慧（尤其是模式辨識）愈來愈長在日常生活中使用，因此在這個領域很可能會有新穎的精采演算法出現。
另一個領域，是被稱為零知識協定（Zero-knowledge protocol）的演算法。這些協定使用特殊的加密方式，能做到比數位簽章更令人驚豔的事，它能讓兩個以上的個體將資訊加以組合而不透露任何一方的任何資訊。其中一個潛在的應用是網路拍賣，投標者使用零知識協定就能將自己投下的標單加密，雖然拍賣的最後結果仍會公布，但任何人都不會知道其他標單的任何資訊。
另一個則是學術界大量研究但實用性有限的概念，分散式雜湊表（distributed hash table），這種表是在同儕系統（peer to peer system，沒有中央伺服器導引資訊流通的系統）中儲存資訊的巧妙方式。
拜占庭容錯（Byzantine fault tolerance）技術也是令人驚艷，但因為乏人採用還無法被歸為偉大。拜占庭容錯讓某些電腦系統可容忍任何型態的錯誤（只要沒有太多同時發生的錯誤）。與此對比則是一般的容錯概念，也就是禁得起比較良性的錯誤，如硬碟機的永久故障或是作業系統的當機。
本書所提到的偉大演算法之間是否存在共同的主題？
所有偉大的觀念不需要會寫程式等等電腦科學的知識就能夠解釋。
作者在撰寫本書時，認為偉大演算法不出兩類，其中是核心具備簡單巧妙的技法，而這些技法無須任何技術知識就能夠理解，第二類演算法高度依賴先進的電腦科學概念，不具備這個領域的知識就無法理解。
另一個共同主題，就是電腦科學的領域不僅僅是寫程式。電腦程式語言和電腦科學的主要概念之間，為了建置演算法並對演算法進行實驗，電腦科學的研究人員需要將演算法轉換成電腦程式，每個程式用一種程式語言來寫，如C++、Java或Python。因此，電腦科學家必須了解程式語言，但這只是先決條件，發明、改寫以及了解演算法才是重頭戲。
資料庫的操作人員相當執著於一致性（consistency），它代表資料庫中的資訊不會自相矛盾，而矛盾或不一致正是資料庫管理員的噩夢。
姓名 年齡 朋友如上表，靜宜是羅西娜的朋友，但第二行卻顯示羅西娜並非靜宜的朋友，這違反了友誼的基本概念。
羅西娜 35 麥特、靜宜
靜宜 37 麥特、桑迪普
事實上，這種不一致在新資料加入資料庫時很容易避免，電腦擅長於守規定，要讓資料庫遵守「如果A和B結婚，B就一定是和A結婚」的規則並不困難，如果某人想輸入的資料違反此規則，就會收到錯誤訊息而無法輸入，因此這類案例只要制定簡單的規則來確保一致性，不需要多高明的方法。
資料庫戰勝了不可靠的元件——也就是電腦科學家口中的「容錯」（fault-tolerance）——是許多研究人員花了數十年所得到的結果，其中最重要的人物Jim Gray，他於1992年出版了一本談交易處理的著作《Transaction Processing: Concepts and Techniques》。
應該有不少人覺得，資料庫是個無趣的主題，畢竟要對資料的儲存感到興奮是很困難的，但在無趣的外表下，資料庫背後的概念卻很精彩。
資料庫不受硬體故障的限制，賦予線上金融等活動效率和堅若磐石的可靠度，代辦事項清單的技法給予我們如原子般的微小交易，使我們在許多顧客同時與資料庫互動下仍保有一致性。這個高度併行性加上透過虛擬表格技法達到的快速查詢回應，讓大型資料庫也很有效率。待辦事項技法在面對故障時確保一致，加上準備然後承諾技法的複製資料庫，史資料兼具緊密的一致性和持久性。
數位簽章
Digital Signature
「數位」照字面解釋是「由一串數字所構成的」，因此凡是數位的東西都可被拷貝，只要一一將這些數字拷貝即可。但是，「簽章」的基本概念是可被讀取但是除了簽章的人以外其他人都無法拷貝。
數位簽章不是在交給別人的文件上使用，通常是別人在傳送文件給你之前使用。
事實上，電腦接收並認證數位簽章的頻率高得嚇人，因為一些經常被使用的網路協定就是利用數位簽章來確認與你互動的電腦的身分。例如網址以https開頭的安全伺服器通常會先傳給你的電腦一個數位簽章的憑證後，才建立安全連線。數位簽章也被用來驗證許多軟體元件的真實性，如瀏覽器插件（browser plugin），你在網路瀏覽時大概都看過類似的警告訊息。軟體簽章也是你最常看見的數位簽章之一。
本章說明如何創造一個無法被偽造的數位簽章。
數位簽章的第一步是完全捨棄書面簽章，改由上鎖、鑰匙和鎖箱來證明文件的真偽。在這套方法下，每位參與者都有大量的鎖，同一個人的鎖必定是一模一樣。此外，每位參與者的鎖必須互斥，沒有人能製造或取得與別人相同的鎖。最後，這些鎖都附有生物測定感應器（biometric sensor）以確保只能被擁有者上鎖。上述就是所謂的「實體鎖技法」（physical padlock trick）。
數位簽章依賴一個只有簽章者知道的秘密以及被簽章的訊息，這個簽章者是用同一個秘密來簽章他的每個訊息，但是不同的訊息會有不同的簽章。因此，雖然任何人都可拷貝簽章，但卻無關緊要，因為簽章不能被移轉到另一個訊息上，因此光是拷貝並無法完成偽造。
少了數位簽章，網際網路將不存在，資料雖還可透過加密來安全傳送，但要驗證收到資料的來源將會難上加難。
什麼是可計算的？
未來會如何呢？
到底有什麼事是電腦辦不到的？
是，確實有些問題電腦永遠無法解決，永遠都會有些問題是「不可計算」（uncomputable）。
1930年代，美國科學家Alonzo Church，在計算理論方面的大突破，至今依舊是電腦科學的基礎；英國科學家Alan Turing，則被公認為奠定電腦科學的最重要人物，圖靈的研究成果涵蓋整個電算概念的光譜，從複雜的數學理論、深奧的哲學乃至大膽實用的工程學。
進入21世紀，自動檢查工具的大幅進步，減少了許多電腦軟體當機的頻率。但是，自動的軟體檢查工具並不能偵測出電腦程式中所有的潛在問題、當機狀況。
在電腦科學中，當我們說「X經證明不可能」，我們不光是指X顯然是困難的或實務上不可能達到，而是百分之百肯定X永遠達不道，因為已經有人用一連串演繹的數學推論證明了這點。
via youtube
“We can only see a short distance ahead, but we can see plenty there that needs to be done.”1991年劍橋大學的達爾文講座，Stephen Hawking在一場名為「宇宙的未來」（The Future of the Universe）演講中，預測宇宙在至少未來的一百億年將繼續擴張，他說：「我不期待到時我還在這裡，被人們證明我是錯的。」
——Alan Turing《Computing Machinery and Intelligence》
但電腦科學的預測，很有可能在有生之年就被證明是錯的。
牛津歷史學家A. J. P. Taylor曾在他的系列演講結尾中，直接提及會不會發生第三次世界大戰，答案是「會」他說，因為人類「一再重蹈覆轍」，這系列演講內容也以《How Wars Begin》於1997年出版成書。
順著歷史的洪流，這些演算法的技術勢必會持續加速成長，但這本身並不足以保證會出現偉大的演算法。未來演算法的創新將放慢步調，因為電腦科學相較於數學、物理學和化學等領域是相當年輕的，要發現偉大的演算法相對容易。這也表示，未來要找到聰明且具廣大應用的演算法會越來越困難。新技術提供的新利基偶爾會為新的演算法提供大展身手的舞台，然而領域的漸趨成熟卻使得到機會愈來愈窄。
然而，仍有些極具潛力的利基和技術，人工智慧（尤其是模式辨識）愈來愈長在日常生活中使用，因此在這個領域很可能會有新穎的精采演算法出現。
另一個領域，是被稱為零知識協定（Zero-knowledge protocol）的演算法。這些協定使用特殊的加密方式，能做到比數位簽章更令人驚豔的事，它能讓兩個以上的個體將資訊加以組合而不透露任何一方的任何資訊。其中一個潛在的應用是網路拍賣，投標者使用零知識協定就能將自己投下的標單加密，雖然拍賣的最後結果仍會公布，但任何人都不會知道其他標單的任何資訊。
另一個則是學術界大量研究但實用性有限的概念，分散式雜湊表（distributed hash table），這種表是在同儕系統（peer to peer system，沒有中央伺服器導引資訊流通的系統）中儲存資訊的巧妙方式。
拜占庭容錯（Byzantine fault tolerance）技術也是令人驚艷，但因為乏人採用還無法被歸為偉大。拜占庭容錯讓某些電腦系統可容忍任何型態的錯誤（只要沒有太多同時發生的錯誤）。與此對比則是一般的容錯概念，也就是禁得起比較良性的錯誤，如硬碟機的永久故障或是作業系統的當機。
本書所提到的偉大演算法之間是否存在共同的主題？
所有偉大的觀念不需要會寫程式等等電腦科學的知識就能夠解釋。
作者在撰寫本書時，認為偉大演算法不出兩類，其中是核心具備簡單巧妙的技法，而這些技法無須任何技術知識就能夠理解，第二類演算法高度依賴先進的電腦科學概念，不具備這個領域的知識就無法理解。
另一個共同主題，就是電腦科學的領域不僅僅是寫程式。電腦程式語言和電腦科學的主要概念之間，為了建置演算法並對演算法進行實驗，電腦科學的研究人員需要將演算法轉換成電腦程式，每個程式用一種程式語言來寫，如C++、Java或Python。因此，電腦科學家必須了解程式語言，但這只是先決條件，發明、改寫以及了解演算法才是重頭戲。