Wu-Manber算法采用跳躍不可能比對字元和hash散列的方法，加速比對的進行。該方法需要對所有模式進行預處理，建構SHIFT，HASH和PREFIX這3個表。SHIFT表同Boyer-Moore算法裡的轉移表，用來存儲字元集中所有塊字元在文本中出現時的轉移距離；HASH表用來存儲比對視窗内尾塊字元散列值相同的模式串；PREFIX表用來存儲比對視窗内首塊字元散列值相同的模式串。在對模式串進行比對的時候就是利用這三個表完成文本的掃描和尋找比對的過程。
首先介紹預處理過程：
1、計算模式集合P中最短的模式長度m。後續讨論僅考慮每個模式串的前m個字元（那剩餘的怎麼辦呢？o還沒想明白），設這些長度為m的模式串組成新集合P’。
2、對P’中每個模式串進行分塊，以B個字元為塊長度，每次比較長度為B的塊。推薦取B=log|Σ|(2*m*k)，其中k是模式串的個數，|Σ|是the size of alphabet。
3、建構一個SHIFT表，該表用于在掃描文本串時，根據讀入的塊決定移動的距離。對于|Σ|大小的字元集，長度為B的塊的組合方式有|Σ|^B種可能，是以表的大小為|Σ|^B。
4、将每個長度為B的塊用哈希函數計算出一個整數值h，将h為SHIFT表的索引值。
5、窮舉P’中所有長度為B的塊，對于每個塊Bl，計算其相應的SHIFT表值。計算規則如下：找出Bl在P’的每個模式串中出現的最右位置，設這些位置中的最大值為j（以末尾位置為準），則SHIFT[h]=m-j。[注1]
6、其餘所有不在P’中的塊，SHIFT表值為m-B+1。[注2] [注3]
7、建構HASH表：設HASH[h]=p，p指向兩個單獨的表：PAT_POINT和PREFIX[注4]。有一個排序過的（根據模式串末B位的哈希值排序）指針連結清單PAT_POINT，存儲着指向所有模式串的指針。p指向PAT_POINT中末B位哈希值為h的第一個節點。
8、建構PREFIX表：将每個模式串前B’位（B’的推薦值為2）的哈希值存入PREFIX表[注5]，用于檢查字首是否比對，可以進一步減少需要樸素比對的模式串個數。
[注1] 等同于BM算法的“壞字元規則”
[注2] SHIFT表值為m-B+1的原因：這B個字元不出現在P’中，說明最多可能有(B-1)個字元出現在P’中，是以SHIFT表值為m-(B-1)=m-B+1。
[注3] 預處理的5、6步與原文表述的順序不同，但效果是一樣的。原文的做法是先将SHIFT表所有位置初始化為m-B+1，再根據本文的第5步更新SHIFT表值。參見原文第4頁第1自然段。
[注4] 此處的表述是按照自己的了解總結得出的，可能不正确。原文第4~5頁表述如下：“Let h be the hash value of the current suffix in the text and assume that SHIFT[h] = 0. The value of HASH[h] is a pointer p that points into two separate tables at the same time: We keep a list of pointers to the patterns, PAT_POINT, sorted by the hash values of the last B characters of each pattern. The pointer p points to the beginning of the list of patterns whose hash value is h. To find the end of this list, we keep incrementing this pointer until it is equal to the value in HASH[h+1] (because the whole list is sorted according to the hash values). So, for example, if SHIFT [h] 0, then HASH [h] = HASH [h+1] (because no pattern has a suffix that hash to h). In addition,
we keep a table called PREFIX, which will be described shortly.”
[注5] 預處理過程SHIFT、HASH和PREFIX表的記憶體位置關系圖（根據個人對原文的了解畫出，可能不正确）：
SHIFT表的構造 不用等到實際考查text時再計算SHIFT，我們預處理各pat就可以把SHIFT表填上。對于每個pat，計算其每個長度為B的subpat(aj-B+1…aj)的值，SHIFT[hashFun(subpat)]=min{m-B+1,m-j}。
HASH表的構造 記現正掃描的text的末B位的哈希值為h。那麼HASH[h]的值是p（p指向PAT_POINT中哈希值為h的第一個結點處）。
HASH[]表大小同SHIFT，但相對就稀疏多了，人那兒存着所有可能的組合的SHIFT值。哎，犧牲空間換時間，時空一向兩難全。
PREFIX表的構造 對每一個pat，要記錄其首B’位字元的哈希值（PREFIX）。
複雜度O（BN/M），B、M含義同前，N是text字元數。Patterns很短或很少的時候，Wu-Manber不是很牛叉。而成千上萬的patterns一起比對過去，Wu-Manber牛氣沖天了。
轉載于:https://www.cnblogs.com/StevenL/p/6818450.html