字串匹配-Multiple pattern search
Rabin-Karp 演算法
如果今天您要實作一個聊天室的訊息過濾器,您會如何實作?
共 N 個敏感詞彙,每個敏感詞彙的平均長度為 M,每個句子包含 K 個字元。
Q1. 使用何種資料結構? 所需空間複雜度為何?
Q2. 使用何種方式過濾? 所需時間複雜度為何?
Q3. 使用何種方式進行測試?
Q4. 在運作期間要更新詞彙列表的話要如何處理?
Q1. 使用何種資料結構? 所需空間複雜度為何?
如果要求一定要正確抓出敏感詞彙,有就有,沒有就沒有,資料結構使用hash table。
空間複雜度:O(N)不是敏感詞彙,卻顯示是敏感詞彙,心態是寧可錯殺不可放過,如果允許這樣的誤報,
那麼資料結構使用Bloom Filter的變體,也就是Cuckoo Filter。
空間複雜度:O(1)
Q2. 使用何種方式過濾? 所需時間複雜度為何?
首先對所有的敏感詞彙做前置處理,將敏感詞彙輸入到hash函數,所得到的hash值儲存到 hash table 或 Cuckoo Filter。
其中hash函數的設計與字串長度有關,時間複雜度為O(M),而現在有N個敏感詞彙,故前置處理階段的時間複雜度為O(NM)。
匹配運算中, 第14行計算子字串的hash值,hash函數與字串長度有關,其時間複雜度為O(M),為了減少這部分的時間複雜度,利用rolling hash
的技巧,由於每個子字串與下一個子字串有高度的重複性,利用這樣的特性,目前子字串的hash值=前一個子字串的hash值-前一個字元的hash值+新出現字元的hash值
,藉由這樣的方式就不需要每次迴圈都計算子字串中的M個字元,只需要考慮頭尾字元所造成的影響,第14行的時間複雜度變為O(1)。
第12行,查詢子字串的hash值是否存在於敏感詞彙hash值的集合hsSet,由於hsSet 是以hash table的方式儲存,第12行的時間複雜度為O(1),但即使hash值相等還是要考慮到碰撞的情況產生,因此需要依序對比字串,時間複雜度為O(1*M)。
若是在很倒楣的情況,比如說不斷出現重複的字元,那麼每次都會發生hash碰撞,匹配運算的最糟時間複雜度為O((K-M)M),但正常情況hash碰撞的情況很少發生, 其時間複雜度為O((K-M) + cM) = O(K+M)。
Q3. 使用何種方式進行測試?
1.以array儲存預設要輸入的訊息,依序輸入,判斷輸出是否符合預期
2.建構隨機字串,依序輸入,判斷輸出是否符合預期
Q4. 在運作期間要更新詞彙列表的話要如何處理?
更新詞彙列表對運作中的訊息過濾器不會有影響,理由有兩個:
- 函數是用by value傳遞敏感詞彙,因此外部更新詞彙列表也不會有影響
- 在前置處理階段已經確定了敏感詞彙的hash值,匹配過程中,即使更新詞彙列表,也不會影響已經計算過了敏感詞彙的hash值
假設更新詞彙列表只增加不會減少,畢竟不是戒嚴時期,敏感詞彙應該不會減少只會增加,那麼就將更新前過濾的文章,輸入新的敏感詞彙,再次做一次過濾動作,不需要對舊的敏感詞彙做過濾
結語:
Rabin–Karp在 single pattern的情況下並不是好的選擇,但是在Multiple pattern有不錯的效果。