在PHP中快速實現滾動散列

我已經在PHP中實現了Adler32滾動散列，但由於ord非常慢（我的開發計算機上每秒大約1MB）以獲取字符串中的chanters整數值，因此此解決方案對於100MB +文件無法使用。在PHP中快速實現滾動散列

PHP的mhash函數可以非常快速地計算adler32（在我的開發機器上每秒120MB）。然而，mhash似乎不支持adler32的滾動特性，所以當滾動窗口移動時，必須計算一個全新的adler32，而不是僅僅重新計算實際更改的兩個字節的哈希。

我沒有綁定到adler32算法，我只需要一個非常快速的PHP滾動哈希。

來源

2015-06-14 Dom

呼叫低兩個字節阿德勒-32 甲和高兩個字節乙，其中即序列{X1，X2，...，XN}阿德勒-32。

爲了得到阿德勒-32的{X2，...，XN}，減去X1從甲，模65521，並減去N * X1 + 1從乙，再次模65521.

需要注意的是，如果你的窗口大小ň恰好是65521多，那麼你可以只減一乙（模65521）。如果可以的話，這可能是一個很好的窗口大小。還要注意的是，如果n大於65521，則可以將x1乘以（n模65521）。如果n是一個常量，那麼可以提前做模運算。

（注意用C是%運營商和PHP是不模操作，而其餘的操作。所以，你需要照顧負數。）

來源

2015-06-15 03:14:30

馬克您好，感謝這麼多的寫作回答。然而，我的問題並不在於你的（？）算法的實現（我已經這樣做了），而是在PHP中快速實現它。從PHP字符串獲取字節以進行操作似乎是一個緩慢的過程，大約每秒1MB。 adler32的內部mhash實現清楚地從字符串中讀取約三個數量級或更快的字節，但它沒有提供任何方法來使用algorythm的滾動特性。 – Dom

加一個關於模的非常有用的提示。 – Dom

我的答案解決了你所說的問題：「所以當滾動窗口移動時，你必須計算一個全新的adler32，而不是僅僅重新計算實際改變的兩個字節的散列值。」你不必爲整個窗口計算一個新的Adler-32，而只需要將它更新爲從一開始就丟棄的字節並添加到結尾。我無法對PHP的內部實現做任何事情。 –

在PHP中快速實現滾動散列

回答

相關問題