MIT 6.006 Introduction to Algorithms 9.2

9. Table Doubling, Karp-Rabin

前提

前面提到在 Hashing 的幫忙下，可以達到

Insert / Delete / Search Time Cost = O ( 1 )

Hashing 的好處不只有這些！

還有更多的應用領域，比如這次會介紹 Text Search Engine ，也是利用到 Hashing 的幫忙。

結論

這次介紹如何利用 Rolling Hashing 的優點，把複雜的比對變得簡單：

• Text Matching
• File Matching
• …

Hashing 好棒棒

字串比對問題

給予兩個 String s & t，請問 s 字串是否出現在 t 字串裡面：

s = "algorithm"
t = "/(wholeInboxText)"  

t 是一個超乎想像的大型的字串，可能是你所有的email，也可能是全世界的website…

我們先從簡單的 algorithm 開始…

Simple Algorithm For Matching

for i in range( length(t) - length(s) ) {
    if ( s == t[i -> i + length(s)] ){
        return true
    }
}
return false

Matching Algorithm

對 String t 跑一個 for loop，並且每次 i 都檢查 t 區間的每個字母是否等於 String s。這樣子的 algorithm 實在非常慢：

Time Cost = O( |s| * ( |t| - |s| ) ) = O( |s| * |t| )

尤其當你的 t 字串很大時。 s 很大時，你每次一個字一個字比對的成本也很高…

該如何解決？…Hashing！

將每次比對的大字串 hash 成容易比較的數字，讓每次比較的成本降低！

在這裡，我們需要的是一種特別的 Hashing：

Rolling Hash ADT

• r = hash value of String x
• r.append( c ) = hash( x + new char c )
• r.skip() = hash( x remove first char )

Rolling Hash 有一個特性，你可以隨意地對 Hash 後的結果變動，變動後一樣保持 Hash 的結果：

//對字串 x 做 rolling hash
String x = "abc"
rollHash(x) = "123"
//對 x 增加字母 "d"
String x' = "abcd"
//重新hash的結果與執行append的結果一樣
rollHash(x') = "1234"
rollHash(x).append(d) = "1234"
//對 x 刪去第一個字母 "a"
String x'' = "bcd"
//重新hash的結果與執行skip的結果一樣 
rollHash(x'') = "234"
rollHash(x').skip() = "234"

我們可以利用 Rolling Hash Method 的特色，重新設計剛剛的matching algorithm：

Karp — Rabin Algorithm

var rs = rollingHash(s)
var rt = rollingHash(t[0 -> length(s)])
for i in range( length(t) - length(s) ) {
    rt.skip()
    rt.append(t[i])
    if ( rs == rt ){
        //進一步檢查hash前的值是否相同
        if (s == t[i -> i + length(s)]) {
            return true
        }
    }
}
return false

對 String t 跑一個 for loop，並且每次 i 都檢查 Hash 後的結果，如果結果match，才真的一個字一個字的去比對：

Time Cost = O( |s| + |t| + #number of hash match * |s|)

這比原先的 algorithm 快得多了！

Rolling Hash

其實上週介紹的 Division Hash Method 就擁有 Rolling Hash 的特性，影片有去證明 Division Hash 擁有這樣的特性。

Division Method

hash(k) = k mod m

直接將 k 這個巨大的數字，模除 m （Number of Keys In Dictionary）後，作為新的 key

如果忘記了可以點下面連結：

MIT 6.006 Introduction to Algorithms 8

下一堂課，我們會介紹另一種解決 collision 的辦法...

MIT 6.006 Introduction to Algorithms 10