高效的'滾動/移動散列'計算（如移動平均）

我想優化一個程序，需要計算一個數據流中的每個位置（字節）的恆定大小的窗口散列。需要在磁盤文件中查找比可用RAM大得多的重複數據。目前，我爲每個窗口計算單獨的md5散列，但花費很多時間（窗口大小爲幾千字節，因此每個數據字節處理幾千次）。我想知道是否存在一種方法來計算常量（窗口大小無關）時間內的每個後續散列（例如移動平均中1個元素的加減）？散列函數可以是任何東西，只要它不會產生很長的哈希（50-100位是確定的）並且其計算速度相當快。它也必須在多達數以萬億計的非隨機窗口（數據TB）上進行實驗 - 每次碰撞都意味着我的磁盤訪問（crc32非常弱，md5在這方面沒問題）。高效的'滾動/移動散列'計算（如移動平均）

如果您指出我現有的Linux上可用的庫函數（如果有的話），我將非常感激。

這是我的第一個問題，所以如果我做錯了，請耐心等待。

問候，的Bartosz

來源

2013-01-11 bzaborow

良好散列函數的特性之一（導致統計適量的衝突）是它們的最終值取決於混合/輸入數據的所有位，即在每個處理步驟的計算中下一塊數據的結果取決於迄今爲止已處理的所有位。如果現在你想「只」省略前N位，這意味着所有後續計算步驟所依賴的數據是不同的，所以所有的步驟都必須重做。所以你必須至少放棄今天好的散列函數的這種強度。 – PlasmaHH

你描述的，是非常接近的重複數據刪除存儲使用的基本方法。

重複數據刪除系統中，我們通常使用Rabin's fingerprinting方法作爲快速滾動哈希函數。然而，雖然拉賓指紋是良好的和很好理解的碰撞特性，但它不是密碼安全的，即有將是是碰撞。檢查例如如何Bentley et al. used such a method in their compression method。問題是如果和多少碰撞你可以容忍。如果你能忍受偶爾的碰撞，一個好的拉賓指紋實現可能是一個好主意。好的實現可以爲每個內核每秒處理超過200 MB的內存。

我不知道有任何方法幾乎沒有碰撞（又名密碼保護）和滾動在同一時間。作爲PlasmaHH，我非常懷疑這實際上是可能的。

想想如果你能放鬆你的限制。也許你可以允許錯過一些重複。在這些情況下，更快的方式是可能的。

來源

2013-01-11 15:33:12 dmeister

謝謝。我會嘗試拉賓指紋方法，希望它會足夠好。我真的不想錯過比我更多的重複項目（因爲大塊大小）。但是，碰撞時磁盤訪問的成本可能會低於哈希性能增益。 – bzaborow

Rabin-Karp方法確實執行得很好，並且在64位算法中實現時，對於此任務而言具有足夠罕見的衝突。萬分感謝！ – bzaborow

上rolling hashes維基百科文章具有ngramhashing鏈接它實現在C++中的幾個不同的技術，包括：

隨機卡普-拉賓（有時稱爲拉賓-卡普）
通過循環多項式哈希（也稱爲Buzhash）
通過不可約多項式哈希

（也可在GitHub）

來源

2013-01-11 15:06:41 Joni

有用的鏈接，至少我可以嘗試現有的實現。謝謝！ – bzaborow

高效的'滾動/移動散列'計算（如移動平均）

回答

相關問題