477
《大數據算法》一2.5 串相等判定算法
本節書摘來異步社區《大數據算法》一書中的第2章 ，第2.5節，王宏誌 編著, 更多章節內容可以訪問雲棲社區“異步社區”公眾號查看。
2.5 串相等判定算法
本節討論一個通信亞線性算法問題，因為在很多情況下，數據傳輸時間和數據量大致成正比，因而將通信亞線性算法歸到本章討論。
在現實中會有這樣的問題，假設A公司總部有一個龐大的數據庫，而在分公司B處保存這個數據庫的副本，為了數據庫的一致性，要定期地比較數據。這就涉及串相等判定問題。
串相等判定問題
輸入：串s1和s2。
輸出：如果s1=s2輸出“是”，如果s1≠s2輸出“否”。
很顯然，任何一致性檢測都要求發送所有n位數據，否則，無法檢測未發送位置的錯誤。但是，對於龐大的數據庫，n可能非常大，傳輸全部n位幾乎不可能。
設將s1中的n位數據表示為（a1,…,an）,s2中的n位數據表示為（b1,…,bn），一個可能的方法是隨機選一些位，然後對隨機選擇的位進行判斷。這樣做的問題在於，如果產生的錯誤在總的串中比例很小(比如僅有一個錯誤)，則這種方法將失效。因而需要具有全局性的方法。
基本想法是為兩個字符串製作指紋來體現字符串的全局特征，即我們將數據看成n位的整數a和b，
，定義指紋函數（p為素數）：Fp(x)=x mod p。
算法是隨機選取素數p，檢測Fp(a)=Fp(b)是否成立。
下麵討論p的選取對算法的影響。
根據這個算法，在計算過程中，需要比較的數字最大不超過p，因而需要傳輸logp位，而不是n位。考慮到傳輸效率的問題，希望選擇一個較小的p。
下麵討論算法的誤判概率，在a和b不等且都與p同餘的情況下會發生假陽性的誤判。
設c =a-b，也就是，當a≠b且c整除p時發生誤判。由於c≤2n，c的素因子至多有n個。給定一個p，通過素數定理，大概有p/ln(p)個小於p的素數，此時出錯的概率是nlnp/p。
根據上述討論，現在我們想選擇一個素數p，這個數字要足夠大以確保有足夠多小於p的素數，同時這個數字又要足夠小以確保高效的通信。
取p=2n2ln(n)(取這個數是為了計算方便，但這樣的p可能不是一個整數，在實際實現中可以取p是一個大於2n2ln(n)但和2n2ln(n)最接近的素數)，代入出錯概率公式，發生錯誤的概率不超過2/n,在這種情況下需要傳輸的位數為O(logn)。
習題
2.1 證明2.1.3節中生成的多邊形PA和PB包含點的個數為O(n)。
2.2 為了保障航運安全，旅客不允許攜帶危險品乘坐飛機，因此在旅客登機前需要由安檢人員檢測旅客是否攜帶危險物品。假設共有n名旅客需要登機，用o(n)時間近似判斷這n名旅客是否有人攜帶危險品。
2.3 在輸入的正文串（長度為n）中查找某一字符是否出現，若出現，輸出1，否則輸出0。設計時間複雜度為o(n)的算法求解這個問題。
2.4 miRNA（微小RNA）在生命活動中具有重要功能，由約21個堿基構成，比如AUGUCCUCCUUAUGCCUAUGC可能就是一條miRNA。如果我們想知道細胞內有沒有感興趣的miRNA，可以通過測序解決。測序結果可能是n個21堿基的序列。設計時間複雜度為o(n)的算法，給定包含n個測序結果的集合S（n條序列）和感興趣的miRNA序列l，判定S是否包含l。
2.5 一幅二值圖（有n個像素）僅由0和1組成，設計時間複雜度為o(n)的算法，判斷該圖的黑色(1)和白色(0)是否各占一半。
2.6 設計亞線性算法檢查兩個字符串是否相同。
2.7 設計時間複雜度為o(n)的算法，判斷一個包含n個數的數組是否有相同的數字。
2.8 設計時間複雜度為o(n)的算法，判定輸入規模為n的0,1數組中，是否正好有k（k≤n）個0。
2.9 設計時間複雜度為o(n)的算法,判定一個長度為n的0，1數組是否為0，1交替的循環數組。
最後更新：2017-06-21 13:31:40