Introduction à l'algorithme Wu-Manber et aux instructions d'implémentation Python

L'algorithme Wu-Manber est un algorithme de correspondance de chaînes utilisé pour rechercher efficacement des chaînes. Il s'agit d'un algorithme hybride qui combine les avantages des algorithmes de Boyer-Moore et de Knuth-Morris-Pratt pour fournir une correspondance de modèles rapide et précise.

Étapes de l'algorithme Wu-Manber

1. Créez une table de hachage qui mappe chaque sous-chaîne possible du motif à la position du motif où cette sous-chaîne apparaît.

2. Cette table de hachage est utilisée pour identifier rapidement les positions de départ potentielles des modèles dans le texte.

3. Parcourez le texte et comparez chaque caractère avec le caractère correspondant dans le motif.

4. Si les caractères correspondent, vous pouvez passer au caractère suivant et continuer à comparer.

5. Si les caractères ne correspondent pas, une table de hachage peut être utilisée pour déterminer le nombre maximum de caractères pouvant être ignorés avant la prochaine position de départ potentielle du motif.

6. Cela permet à l'algorithme de sauter rapidement de grandes portions de texte sans manquer aucune correspondance potentielle.

Python implémente l'algorithme 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)

La différence entre les algorithmes KMP et Wu-Manber

L'algorithme KMP et l'algorithme Wu Manber sont tous deux des algorithmes de correspondance de chaînes, ce qui signifie qu'ils sont tous deux utilisés Trouver une sous-chaîne dans une chaîne plus grande. Les deux algorithmes ont la même complexité temporelle, ce qui signifie qu’ils ont les mêmes caractéristiques de performances en termes de temps d’exécution de l’algorithme.

Cependant, il existe quelques différences entre eux :

1 L'algorithme KMP utilise une étape de prétraitement pour générer une table de correspondance partielle, qui est utilisée pour accélérer le processus de correspondance de chaînes. Cela rend l'algorithme KMP plus efficace que l'algorithme Wu Manber lorsque le modèle recherché est relativement long.

2. L'algorithme Wu Manber utilise une méthode différente pour la correspondance des chaînes. Il divise le modèle en plusieurs sous-modèles et utilise ces sous-modèles pour rechercher des correspondances dans le texte. Cela rend l'algorithme Wu Manber plus efficace que l'algorithme KMP lorsque le modèle recherché est relativement court.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!