Wu-Manber演算法簡介及Python實作說明

Wu-Manber演算法是一種字串匹配演算法，用於高效地搜尋字串。它是一種混合演算法，結合了Boyer-Moore和Knuth-Morris-Pratt演算法的優勢，可提供快速且準確的模式匹配。

Wu-Manber演算法步驟

#1.建立一個雜湊表，將模式的每個可能子字串對應到該子字串出現的模式位置。

2.此雜湊表用於快速識別文字中模式的潛在起始位置。

3.遍歷文字並將每個字元與模式中的對應字元進行比較。

4.如果字元匹配，則可以移動到下一個字元並繼續比較。

5.如果字元不匹配，可以使用雜湊表來確定在模式的下一個潛在起始位置之前可以跳過的最大字元數。

6.這允許演算法快速跳過大部分文本，而不會錯過任何潛在的匹配。

Python實作Wu-Manber演算法

# Define the hash_pattern() function to generate
# a hash for each subpattern


def hashPattern(pattern, i, j):
h = 0
for k in range(i, j):
h = h * 256 + ord(pattern[k])
return h

# Define the Wu Manber algorithm


def wuManber(text, pattern):

# Define the length of the pattern and
# text
m = len(pattern)
n = len(text)

# Define the number of subpatterns to use
s = 2

# Define the length of each subpattern
t = m // s

# Initialize the hash values for each
# subpattern
h = [0] * s
for i in range(s):
h[i] = hashPattern(pattern, i * t, (i + 1) * t)

# Initialize the shift value for each
# subpattern
shift = [0] * s
for i in range(s):
shift[i] = t * (s - i - 1)

# Initialize the match value
match = False

# Iterate through the text
for i in range(n - m + 1):
# Check if the subpatterns match
for j in range(s):
if hashPattern(text, i + j * t, i + (j + 1) * t) != h[j]:
break
else:
# If the subpatterns match, check if
# the full pattern matches
if text[i:i + m] == pattern:
print("Match found at index", i)
match = True

# Shift the pattern by the appropriate
# amount
for j in range(s):
if i + shift[j] < n - m + 1:
break
else:
i += shift[j]

# If no match was found, print a message
if not match:
print("No match found")


# Driver Code
text = "the cat sat on the mat"
pattern = "the"

# Function call
wuManber(text, pattern)

KMP和Wu-Manber演算法之間的差異

#KMP演算法和Wu Manber演算法都是字串比對演算法，也就是說它們都是用來在一個較大的字串中尋找一個子字串。這兩種演算法具有相同的時間複雜度，這意味著它們在演算法運行所需的時間方面具有相同的效能特徵。

但是，它們之間存在一些差異：

#1、KMP演算法使用預處理步驟產生部分匹配表，用於加快字符串匹配過程。這使得當搜尋的模式相對較長時，KMP演算法比Wu Manber演算法更有效。

2、Wu Manber演算法使用不同的方法來進行字串匹配，它將模式劃分為多個子模式，並使用這些子模式在文本中搜尋匹配項。這使得Wu Manber演算法在搜尋的模式相對較短時比KMP演算法更有效。

#

以上是Wu-Manber演算法簡介及Python實作說明的詳細內容。更多資訊請關注PHP中文網其他相關文章！