KMP 單元利用前綴資訊確定性地匹配模式。另一種方法比較等長字串的短數值摘要。視窗移動時可以有效更新這些指紋,但指紋相等只能提供可能相等的候選。
字串的多項式
令 為質數,把有限字母表的每個符號單射編碼為 的元素。選擇隨機種子之前,先固定長度 的模式 及長度 的文字 。獨立於這些字串,從整個域均勻選擇 。
定義 6.3.1
(多項式指紋)
對已編碼的長度 字串 及底數 ,指紋定義為
常數次方 ,包括 的情況。
相同字串必有相同雜湊值。對不同字串 ,單射編碼保證差多項式非零,且次數至多 。
定理 6.3.2
(兩個字串的碰撞界)
設 是固定的已編碼長度 字串, 在 上均勻。則
證明
(碰撞就是非零多項式的根)
令 。由於編碼是單射且 ,某個係數 非零,所以 非零且次數至多 。碰撞恰好意味著 。
域上非零 次多項式至多有 個不同根:每個根提供一個線性因子,而所有不同根因子的乘積整除該多項式。因此在 個機會均等的 值中,至多 個會造成碰撞,這就是所述的界。當 ,非零差多項式是常數,碰撞概率為零。若次數上界至少為 ,此概率界可能沒有資訊;證明仍然有效。
證明透視
根的數目給出碰撞界
核心想法是把概率陳述轉化為根的計數。先固定 ,再抽取 ,這使 成為固定的多項式,而碰撞只是 在 個機會均等的值中的一個根。
每個假設都恰好用一次。編碼是單射,使 非零,因此只有有限多個根。域的性質給出根的上界:在環 上,二次多項式 有四個根 ,所以沒有域時這個計數不成立。 均勻且與字串獨立,使根的計數成為概率。若編碼不是單射,不同符號也可能使 為零,那麼每個 都會碰撞。
下一個陳述同時涵蓋文字中的所有視窗。
定理 6.3.3
(全部視窗的碰撞界)
對 的固定 個視窗,任何不等於 的視窗與 指紋相同的概率至多為 。
證明
(共用種子下的聯集界)
由上一個定理,每個不等於 的視窗與 碰撞的概率至多為 。至多 個事件中至少有一個發生的概率,不超過各事件概率之和,這就是所述的界。所有視窗共用同一種子,碰撞事件可能相依;聯集界不要求獨立。
若在看到 後才選擇字串,那是不同的對手模型,不受此固定輸入保證涵蓋。
移動視窗
令當前視窗從位置 開始,並以 表示文字位置 的編碼符號。使用從零開始的索引及 ,令 。
定理 6.3.4
(滾動更新)
以 如上,
此恆等式不需要模除法,對每個 (包括 )及 都成立。
證明
(去掉最高次項、移位、再附加)
依定義,。減去 即去掉 一項,餘下 。乘以 並代入 ,得 。 缺少的那一項,即 ,是 ,這一項被加上。當 時求和為空,公式成為 。
例題 6.3.5
(小域中的一次滾動更新)
取 ,,,,,即 。第一個雜湊值為 。此時 ,
直接計算得 ,所以更新與定義相符。
例題 6.3.6
(邊界情形:底數為零)
當 且 ,除最後一項外各項都消失,所以 就是最後一個符號。對 ,兩個視窗的雜湊值分別為 和 。滾動公式仍然有效:,。這樣的底數使任何最後一個符號相同的兩個視窗碰撞,是一次壞的抽取。它出現的概率為 ,與碰撞界一致。
小域中的一次碰撞
例題 6.3.7
(兩個不同視窗有相同雜湊值)
取 ,把 編碼為 ,令模式 、文字 。視窗為 和 。對底數 ,
兩者恰在 ,即 時碰撞。此時雜湊值均為 ,但 ;第二個視窗則真的匹配。若 在 均勻,這對不同字串的碰撞概率是 ,與一次多項式的界吻合。
反例模式
雜湊匹配不能證明字串匹配
在 時,若返回所有雜湊匹配的視窗,便會錯把 bac 的第一個視窗報成 ac 的出現位置。逐符號直接核對每個候選可移除假陽性。在所述精確域算術下,這使輸出精確;單靠雜湊則有單側錯誤:真正匹配的視窗絕不會有不同雜湊值。
工作量與保證
計算模式、第一個視窗的雜湊值及 需 次域運算;其後每個視窗只需額外 次。若能以常數時間取得移出及移入的編碼符號,掃描需 次域運算。串流實作可用環形緩衝區保留最近 個符號。域運算的位元成本取決於 及算術實作。
不核對時,應把雜湊匹配報作候選,並使用上述固定輸入概率界。若逐符號核對每次雜湊匹配,正確性是確定性的,但至多 次核對各可耗 ,包括真正匹配;最壞工作量變為 。這不能取代 KMP 的確定性線性時間保證。精確的隨機域抽樣與算術是假設,並非對特定機器實作的聲稱。
常見錯誤
常見錯誤
(用錯誤的次方移除移出的符號)
移出的符號帶有 ,而不是 ,因為視窗有 個符號,其第一個符號的指數是 。在 、、、 的例子中,若用 ,得 ,而 的正確指紋是 。
常見錯誤
(預先固定底數)
界 是對獨立於字串而抽取的隨機 而言的。若底數是公開的常數,便可以構造出與模式碰撞的文字。取 及固定底數 ,如前所算,模式 與視窗 必定碰撞,不論文字多長。要在輸入選定之後才抽取底數,保證才得以恢復。
習題
快速檢查
(例子中取 ,求 與 模 的雜湊值。)
利用 和 。
解答 · 答案
,。兩個雜湊值不同,所以在 時這一對不碰撞。
快速檢查
(單射編碼下,兩個不同單符號字串的碰撞概率是多少?)
當 時,指紋是甚麼?
解答 · 答案
零。當 ,指紋就是符號本身,,單射使不同符號無論 為何都不相同。這與界 一致。
快速檢查
(若 且 ,哪個符號決定雜湊值?)
當 時,哪個次方不為零?
解答 · 答案
最後一個符號,因為只有 保留下來,所以 。滾動公式仍適用,如底數為零的例子所示。
快速檢查
(所有視窗共用種子,為何仍可用聯集界?)
聯集界對這些事件假設了甚麼?
解答 · 答案
聯集界對任意事件都成立,不要求事件之間獨立。共用種子使碰撞事件相依,但至少有一個發生的概率仍不超過各事件概率之和。