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 中国語 Web サイトの他の関連記事を参照してください。