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

????計算機中的不同對象如果要存儲下來不丟失任何信息，所需要的最少存儲空間，就等于它們的信息熵，但如果只是區(qū)分，則遠不需要這么長的編碼，一種簡單實用的做法就是用一種隨機算法（通常是哈希算法），來將任何一段二進制信息映射成一個隨機數(shù)，作為區(qū)別它和其他信息的指紋（fingerprint），當然這種偽隨機數(shù)產(chǎn)生算法可能會產(chǎn)生概率很小的沖突或碰撞：

????考察當選取數(shù)字的總數(shù)量不斷增加到很大時，不同信息產(chǎn)生相同信息指紋的概率不可忽視，此時信心指紋算法就不再適用了。采用逆向思維，考慮在什情況下不會出現(xiàn)重復的信息指紋。假定要隨機挑選k個數(shù)，讓它們不重復：第一個信息指紋可以有N中選法（N=2^128）；第二個N-1種，...，第k個指紋有N-k種，于是k個指紋不重復的概率：

????由于Pk隨k單調(diào)遞減，來看一下Pk<=0.5時會發(fā)生什么，根據(jù)斯特林公式，當N非常大時：

????也就是說，對一個很大的N，k是一個很大的數(shù)，如果用MD5指紋驗證，它有128位二進制數(shù)，算出來 k > 2^64?≈ 1.8x10^19。即每1800億億次才能重復一次。

????信息指紋的【用途】有：

????1）網(wǎng)絡爬蟲需要知道每個網(wǎng)頁是否已下載，記錄URL要很多字節(jié)，直接存64位的信息指紋即可，大量降低存儲壓力

????2）比較兩個文件是否相同，直接對比其信息指紋，因為隨機性讓不同目標無法映射到同一個數(shù)字上，帶來了安全

????3）系統(tǒng)數(shù)據(jù)庫或管理登陸的服務器中不再存儲密碼明文，而是只存密碼的信息指紋（當然工業(yè)上還額外加鹽（即隨機數(shù)Salt））

10.2 隨機性與量子通信

????這一小節(jié)很有意思，今天所說的量子通信，主要是利用光子的偏振特性傳遞一次性密鑰，用一次性密鑰對信息進行加密（香農(nóng)Claude Shannon證明，只有一次性加密是完全無法破解的加密方式）

????發(fā)送端和接受段約定好兩組信息編碼方式（0，1的偏振光對應），然后在通信接收端放置偏振鏡，就可以用來進行調(diào)制和解調(diào)：

????表10.1中，用+和x代表垂直/水平和45度/135度兩種不同的調(diào)制方式，在調(diào)制時，隨機采用上述兩種方式，接收端由于不知道發(fā)送端是怎么做的，只能隨便猜，假定接收方猜的結(jié)果如表10.2所示：

????在該例子中，6次一致，4次不一致，一致時接收端信息接收無誤，但4次不一致時，接收信息可能有誤，假定接收信息如表10.3所示：

????注意第4，6兩個信息接收錯誤（【】中），第2，8兩個（粗體數(shù)字）信息雖然偏振解調(diào)錯了，但信息蒙對。一般，如果解調(diào)方式和調(diào)制一直，那么解碼后信息誤碼率0%，這種情況占所有發(fā)送信息的50%左右；如果解調(diào)方式與調(diào)制不一致，解調(diào)后得到的信息也會有50%左右蒙對。即不論接收端如何設置偏振鏡解調(diào)方向，最后得到的信息大約有50%x100%+50%x50%=75%和發(fā)送一致，誤碼率為25%。

????如果在傳輸過程中，信息被竊聽截獲，光子再經(jīng)過被錯誤放置的光山時，偏振方向無從得知，得到0還是1完全隨機，如果這時它再將信息轉(zhuǎn)發(fā)給原本的接收端，接收端得到的信息只有75%x75%≈56%和發(fā)送端一致，如果接收端再將自己得到的信息送還給發(fā)送端確認，發(fā)送端就會發(fā)現(xiàn)只有56%的一致性，即可知道傳輸竊聽，可以立即終止通信或采用其他信道。而中間竊聽者運氣好，得到信息和發(fā)送端一致性碰巧超過75%，而接收端得到的信息和它所轉(zhuǎn)發(fā)的一致性也超過75%很多的可能性極小。比如發(fā)送1000比特時，竊聽者經(jīng)過一次轉(zhuǎn)發(fā)仍有75%一致性的概率只有10^-35。

????當確定信道安全后，則需要確認雙方通信密鑰，發(fā)送端用明碼將它所設置對的信息位告訴發(fā)送端即可。比如在例子中，第1、3、5、7、9、10位傻姑娘的信息，如表10.4:

????即便竊聽者知道收發(fā)雙方選用了第1、3、5、7、9、10位信息作為密鑰，也不知道這些信息是什么。該協(xié)議被稱作BB84，由其發(fā)明者Charles Bennett和Gilles Brassard在1984年發(fā)表。

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

????維特比算法（Viterbi Algorithm）的改進：該算法是一種特殊的動態(tài)規(guī)劃算法，廣泛應用于通信的解碼問題，主要解決在圖10.1所示的一種網(wǎng)格圖中尋找最短路徑：

????????維特比算法針對這樣一張圖，從左到右一列列計算截止每一個時間點的最短路徑，算法時間復雜度位O(K^2 * L)，如果想進一步改進維特比算法，需做近似，即需要剪枝：

? ? 1）在計算完從七點到每一個時間點t的所有K條最短路徑后，對它們做一次排序，放到優(yōu)先隊列Q中，從小到大排

????2）進行剪枝，假定隊列Q中第一個路徑長度為x，可以確定一個大雨1的常數(shù)c，把所有長度大于cx的路徑都砍掉。當t大于某個閾值T之后，可以設定只保留m條路徑（m << K），將計算復雜度降低到O(mKL)

????該算法也被稱作聚光搜索（Beam Search）。其搜索工作原理示意如圖10.2：

????由于一開始獲得的前后相關信息較少，不確定性大，因此保留路徑較多，但隨著時間點的增加，即在網(wǎng)格圖中走過的列的數(shù)量增加，獲得了足夠多的前后相關信息，可以開始大膽剪枝。此時短的那條路徑和排在后面的路徑之間的距離只差會不斷增加，即如果一條候選路徑?jīng)]有排在前面，它以后拍到前面的可能性也不大，剪掉它們不影響最后結(jié)果。

????在聚光搜索中，最終的最短路徑落在這m條候選路徑中的概率和光束的寬度n有關，增加n可以提高該概率。通常在一個深度為幾萬的網(wǎng)格圖中，把光束的寬度n限制在幾十的范圍內(nèi)，已經(jīng)能過保證99.9%甚至更高的置信度了。

總結(jié)：

????偶然性、隨機性與確定性一樣，也是這個世界的固有屬性，有時候也要用偶然性來確定一個目標，判斷真?zhèn)?。當使用計算機解決問題時，通常會有一個理論上的最有算法，無法改進。但在實際應用中，我們依然有可能對某些特殊情況進行進一步優(yōu)化，特別是在資源有限時，犧牲一些精確性，在一定的置信度下，獲得對大部分情況下的有效處理。