本章探討計算機科學中確定性與隨機性的關係。計算機最初是為了解決確定性問題而設計的，但很多確定性的問題需要利用隨機性來解決。理解隨機性，會讓計算機這個工具的能力倍增，特別是在大數據時代。

10.1 信息指紋：寓確定於隨機之中#

信息指紋（fingerprint）是一種將任何信息映射成一段二進制隨機數的技術，可以作為信息世界中任何對象的唯一標識。

基本原理#

  • 計算機中所有對象（文字、語音、視頻、圖片等）均以二進制數據存儲
  • 透過偽隨機數算法將信息映射到一個編號上，保證不同對象的編號不同
  • 任何兩段信息的指紋都很難重複，如同人類的指紋一樣

信息指紋重複問題#

  • 對於 128 位的信息指紋（如 MD5），可以表示約 3.4 x 10^38 個不同的數字
  • 根據斯特林公式和生日問題的原理，當信息指紋數量達到 k >= (1+sqrt(1+8N*ln2))/2 時，重複概率超過 50%
  • 128 位指紋的 k > 2^64，約 1800 億億次才會重複一次

應用場景#

  • 網絡爬蟲：用 64 位信息指紋替代網頁 URL，節省 90% 存儲空間，且加快比較速度
  • 文件比對：各自生成信息指紋進行對比，比直接對比文件內容高效得多
  • 密碼存儲：服務器只保存密碼的信息指紋，而非密碼原文，即使數據庫洩露也不會暴露原始密碼
  • 信息安全：公開密碼加密方式利用隨機性，讓試圖竊取密碼的人無法從密碼中倒推出原始明碼

要想確定兩條信息是否相同，不需要比較完整的信息，只需要比較它們的信息指紋就可以了。要想讓兩條不同信息的指紋不衝突，在產生信息指紋時，要確保其結果是隨機的。

10.2 隨機性和量子通信#

量子通信實際上是利用光的偏振特性傳遞一次性密鑰，再用一次性密鑰對信息進行加密。香農早已證明，只有一次性加密是完全無法破解的加密方式，而保證一次性密鑰安全傳輸的基礎恰恰是隨機性。

BB84 協議#

  • 發送端和接收端約定好兩組信息編碼方式（基），一組用垂直/水平偏振代表 1/0，另一組用 45 度/135 度代表 1/0
  • 發送端隨機選擇編碼方式發送信息，接收端隨機選擇解調方式
  • 解調方式與調制方式相同時，信息 100% 一致；不同時，信息有 50% 正確率
  • 最終約有 75% 的信息正確、25% 的誤碼率

安全性保證#

  • 如果信息被竊聽者截獲，竊聽者轉發的信息與原始信息的一致性會降到約 56%
  • 接收端通過確認一致性比例，可以判斷是否被竊聽
  • 發送端將調制使用的基（即哪些信息位設置對了）告知接收端，雙方選擇設置一致的信息位作為密鑰
  • 即便竊聽者知道收發雙方選用了哪些信息位作為密鑰，也不知道這些信息是什麼

量子密鑰分發的數學基礎是概率分布本身的穩定性，也就是說等概率的兩個隨機事件，在大量試驗後各自的概率大致相等；如果發現概率不等，說明背後一定出現了干擾。

10.3 置信度：成本與效果的平衡#

當一個算法已經是最優的，就不可能針對一般情況再全面優化，但可以考慮針對一些常見的特殊情況繼續優化。這種在特定置信度（Confidence Level）條件下的優化，是實際工程中非常重要的思維方式。

快速排序與「絕大多數情況」假設#

  • 快速排序最壞時間複雜度是 O(N^2)，但「絕大多數」情況下是 O(NlogN)，且常數係數比堆排序更小
  • 很多算法的改進都是基於「絕大多數情況」的假設，對個別極端現象不去考慮

AlphaGo 的兩個改進#

  • 縱向簡化：引入馬爾可夫假設，當前的一步棋只和後面有限步棋有關，而非整盤棋，大幅減少搜索的對弈可能性
  • 橫向簡化：在搜索時進行剪枝，剪掉博弈樹中不太可能的分枝，減小博弈樹的寬度
  • 維特比算法是一種在網格圖中尋找最短路徑的動態規劃算法，複雜度為 O(K^2*L)
  • 透過剪枝算法進一步改進：在每個時間點只保留 m 條候選路徑，複雜度降低到 O(mKL)
  • 隨著信息增加，可以越來越大膽地剪枝，保證 99.9% 甚至更高的置信度

求交集問題（Google 面試題）#

  • 如何找到同時包含兩個不同關鍵詞 X 和 Y 的網頁
  • 基準方法：合併兩個詞的索引，複雜度 O(L(X)+L(Y))
  • 利用隨機性的改進：假設出現某個詞的網頁編號具有分散性（scattering），可以跳躍式地查找同時包含兩個詞的網頁
  • 計算複雜度在 O(L(X^Y)) 和 O(L(Y)) 之間，Google 的搜索實際上就是這麼做的
  • 這種方法會錯失一些符合條件的網頁，但由於跳躍速度越來越快，優質網頁不太會被漏掉

當一個算法已經是最優的了，我們不可能針對一般情況再全面優化這個算法時，可以考慮針對一些常見的特殊情況繼續優化算法。三級以上的工程師常常需要做決策，決定如何平衡成本和效益的關係。

結束語#

  • 在大多數人的印象中，計算機總是和確定性相聯繫，但偶然性和隨機性才是這個世界的固有屬性
  • 在使用計算機解決問題時，通常會有一個理論上的最優算法，但在應用中，我們仍然有可能對某些特殊的情況進行進一步的優化
  • 特別是在資源有限時，從而更有效地處理大部分情況