如何檢測大文件（TB）中的少量變化

Question

我剛剛發現一個有趣的博客，談論一些面試問題。其中一個問題是：

給定一個非常大的文件（多TB），檢測連續運行程序之間文件中4MB範圍發生了哪些變化。

我對此沒有任何線索。任何人都可以提出一些想法嗎？

Answer 1

如果您對在創建數據的任何控制，你可以使用Merkle trees

分割數據成小片段（假設10MB各的，但它不是問題），併爲每個片段創建h=hash(fragment)。

現在，所有這些哈希將是樹的葉子。現在，從葉子上創建一個完整的二叉樹：h(father) = hash(father.left XOR father.right)。
現在，你已經有了一棵樹 - 如果你比較兩棵樹，h（root1）= h（root2）當且僅當tree1 = tree2 - 具有高概率（如果使用128位散列，錯誤是1/2^128，這實在可以忽略不計）。

當然，對於任何子樹也是如此，這可以讓你快速找到不同的葉子，這片葉子代表了變化的片段。

這個想法被Amazon's Dynamo用來比較兩個數據庫是否發生了變化，並迅速找到變化。

Answer 2

您可以逐字節比較並找出差異。這將需要很長時間，但值得一試。

我想不到的另一個解決方案是將文件分割爲500 GB並計算md5值並將其與分割的原始md5值進行比較。一個會和原來的不一樣，你可以把它分成250GB，然後再比較原始的md5值。而且你會做得更多，直到你獲得4 MB。

它與有限圈數的稱重機的硬幣問題類似。