Pengenalan kepada algoritma Wu-Manber dan arahan pelaksanaan Python

Algoritma Wu-Manber ialah algoritma pemadanan rentetan yang digunakan untuk mencari rentetan dengan cekap. Ia adalah algoritma hibrid yang menggabungkan kelebihan algoritma Boyer-Moore dan Knuth-Morris-Pratt untuk menyediakan padanan corak yang pantas dan tepat.

Langkah algoritma Wu-Manber

1 Cipta jadual cincang yang memetakan setiap subrentetan corak ke kedudukan corak di mana subrentetan itu berlaku.

2. Jadual cincang ini digunakan untuk mengenal pasti potensi kedudukan permulaan corak dalam teks.

3 Gelung melalui teks dan bandingkan setiap aksara dengan watak yang sepadan dalam corak.

4. Jika watak itu sepadan, anda boleh beralih ke watak seterusnya dan teruskan membandingkan.

5 Jika aksara tidak sepadan, jadual cincang boleh digunakan untuk menentukan bilangan maksimum aksara yang boleh dilangkau sebelum potensi kedudukan permulaan corak seterusnya.

6 Ini membolehkan algoritma melangkau sebahagian besar teks dengan cepat tanpa kehilangan sebarang kemungkinan padanan.

Python melaksanakan algoritma 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)

Perbezaan antara algoritma KMP dan Wu-Manber

Algoritma KMP dan algoritma Wu Manber adalah kedua-dua algoritma pemadanan rentetan, yang bermaksud kedua-duanya berada dalam kedua-dua algoritma pemadanan rentetan. rentetan yang lebih besar. Kedua-dua algoritma mempunyai kerumitan masa yang sama, yang bermaksud ia mempunyai ciri prestasi yang sama dari segi masa yang diperlukan untuk algoritma dijalankan.

Walau bagaimanapun, terdapat beberapa perbezaan antara mereka:

1 Algoritma KMP menggunakan langkah prapemprosesan untuk menghasilkan jadual padanan separa, yang digunakan untuk mempercepatkan proses pemadanan rentetan. Ini menjadikan algoritma KMP lebih cekap daripada algoritma Wu Manber apabila corak yang dicari agak panjang.

2 Algoritma Wu Manber menggunakan kaedah yang berbeza untuk padanan rentetan Ia membahagikan corak kepada berbilang sub-corak dan menggunakan sub-corak ini untuk mencari padanan dalam teks. Ini menjadikan algoritma Wu Manber lebih cekap daripada algoritma KMP apabila corak yang dicari agak pendek.

Atas ialah kandungan terperinci Pengenalan kepada algoritma Wu-Manber dan arahan pelaksanaan Python. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!