Programme PHP pour la recherche de modèles utilisant l'algorithme de Rabin-Karp

Qu'est-ce que l'algorithme de Rabin-Karp ?

L'algorithme Rabin-Karp est un algorithme de correspondance de modèles de chaînes qui recherche efficacement les occurrences de modèles dans des textes plus volumineux. Il a été développé en 1987 par Michael O. Rabin et Richard M. Karp.

Cet algorithme utilise des techniques de hachage pour comparer les valeurs de hachage des modèles et des sous-chaînes de texte. Voici comment cela fonctionne :

• Calculez la valeur de hachage de la première fenêtre de motif et de texte.

• Faites glisser le motif sur le texte, une position à la fois et comparez les hachages.

• Si les hachages correspondent, comparez les caractères du motif et la fenêtre de texte actuelle pour confirmer la correspondance.

• S'il y a une correspondance, enregistrez la position/l'index correspondant.

• Calculez le hachage de la prochaine fenêtre de texte à l'aide d'une fonction de hachage roulant.

• Répétez les étapes 3 à 5 jusqu'à ce que toutes les positions du texte aient été vérifiées.

La fonction de hachage roulant met à jour efficacement la valeur de hachage pour chaque nouvelle fenêtre en soustrayant la contribution du premier caractère de la fenêtre précédente et en ajoutant la contribution du caractère suivant dans la nouvelle fenêtre. Cela permet d'éviter de recalculer les hachages à partir de zéro pour chaque fenêtre, ce qui rend l'algorithme plus efficace.

Programme PHP pour l'algorithme Rabin-Karp pour la recherche de modèles

<?php

function rabinKarp($pattern, $text)
{
   $d = 256; // Number of characters in the input alphabet
   $q = 101; // A prime number

   $M = strlen($pattern);
   $N = strlen($text);
   $p = 0; // Hash value for pattern
   $t = 0; // Hash value for text
   $h = 1;

   // Calculate the hash value of pattern and first window of text
   for ($i = 0; $i < $M - 1; $i++)
      $h = ($h * $d) % $q;

   for ($i = 0; $i < $M; $i++) {
      $p = ($d * $p + ord($pattern[$i])) % $q;
      $t = ($d * $t + ord($text[$i])) % $q;
   }

   // Slide the pattern over text one by one
   for ($i = 0; $i <= $N - $M; $i++) {

      // Check the hash values of current window of text and pattern
      // If the hash values match, then only check for characters one by one
      if ($p == $t) {
         $match = true;

         // Check for characters one by one
         for ($j = 0; $j < $M; $j++) {
            if ($text[$i + $j] != $pattern[$j]) {
               $match = false;
               break;
            }
         }

         // Pattern found
         if ($match)
            echo "Pattern found at index " . $i . "</p><p>";
      }

      // Calculate the hash value for the next window of text
      if ($i < $N - $M) {
         $t = ($d * ($t - ord($text[$i]) * $h) + ord($text[$i + $M])) % $q;

         // If the calculated hash value is negative, make it positive
         if ($t < 0)
            $t = $t + $q;
      }
   }
}

// Example usage
$text = "ABCABCABCABCABC";
$pattern = "BC";
rabinKarp($pattern, $text);
?>

Sortie

Pattern found at index 1 
Pattern found at index 4
Pattern found at index 7
Pattern found at index 10
Pattern found at index 13

Description du code

Le code PHP implémente l'algorithme Rabin-Karp pour la recherche de modèles. Il prend un modèle et du texte en entrée et recherche dans le texte les occurrences du modèle. Cet algorithme calcule la valeur de hachage de la première fenêtre de motif et de texte. Il fait ensuite glisser le motif sur le texte, en comparant le hachage de la fenêtre actuelle et le motif. Si les hachages correspondent, les caractères sont ensuite vérifiés un par un. Si une correspondance est trouvée, il imprime l'index auquel le modèle a été trouvé. L'algorithme utilise une fonction de hachage glissant pour mettre à jour efficacement la valeur de hachage pour chaque fenêtre. Ce code démontre l'utilisation de l'algorithme en recherchant le modèle « BC » dans le texte « ABCABCABCABCABC ».

Conclusion

En résumé, le programme PHP implémente efficacement l'algorithme Rabin-Karp pour la recherche de modèles. En utilisant une fonction de hachage roulant et en comparant les valeurs de hachage, l'algorithme peut rechercher efficacement des occurrences de modèles dans des textes plus volumineux. Le programme identifie correctement l'index du modèle trouvé dans le texte et affiche le résultat. Avec une structure claire et des calculs de hachage appropriés, ce programme démontre la puissance et l'utilité de l'algorithme Rabin-Karp pour la recherche de modèles en PHP.

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!