Structures de données et algorithmes en JavaScript (5) : compétences classiques KMP algorithm

Algorithme KMP et algorithme BM

KMP est un algorithme classique pour la correspondance de préfixes et la correspondance de suffixes BM. On peut voir que la différence entre la correspondance de préfixes et la correspondance de suffixes n'est que dans l'ordre de comparaison

La correspondance de préfixe signifie : la comparaison de la chaîne de modèle et de la chaîne parent se fait de gauche à droite, et le mouvement de la chaîne de modèle se fait également de gauche à droite

La correspondance de suffixe signifie : la comparaison de la chaîne de modèle et de la chaîne parent se fait de droite à gauche, et le mouvement de la chaîne de modèle se fait de gauche à droite.

À travers le chapitre précédent il est évident que l'algorithme BF est aussi un algorithme de préfixe, mais l'efficacité de la correspondance un par un est très arrogante. Naturellement, il n'est pas nécessaire de mentionner O(. mn). KMP, ce qui est ennuyeux en ligne, explique beaucoup de choses. Ils empruntent essentiellement la voie du haut niveau et vous pourriez être confus. J'ai essayé d'utiliser ma propre compréhension pour le décrire de la manière la plus terre-à-terre

KMP

KMP est également une version optimisée de l'algorithme de préfixe. La raison pour laquelle il s'appelle KMP est l'abréviation des trois noms de Knuth, Morris et Pratt. Par rapport à BF, le point d'optimisation de l'algorithme KMP est "le". distance de chaque mouvement vers l'arrière" Il ajustera dynamiquement la distance de déplacement de chaque chaîne de motif. BF est 1 à chaque fois,

Pas forcément pour KMP

Comme le montre la figure, la différence entre les pré-algorithmes BF et KMP est comparée

J'ai comparé les photos et j'ai découvert :

Recherchez la chaîne de motif P dans la chaîne de texte T. Lorsqu'elle correspond naturellement à la sixième lettre c, on constate que le deuxième niveau est incohérent. Ensuite, la méthode BF consiste à déplacer toute la chaîne de motif P d'une place, et KMP doit le déplacer de deux places.

Nous connaissons la méthode de correspondance de BF, mais pourquoi KMP déplace-t-il deux chiffres au lieu d'un ou trois ou quatre chiffres ?

Expliquons l'image précédente. La chaîne de motif P est correcte lorsqu'elle correspond à ababa, et elle est fausse lorsqu'elle correspond à c. Alors l'idée de l'algorithme KMP est : ababa correspond correctement à l'information, peut. nous utilisons ces informations pour ne pas ramener la « position de recherche » à la position qui a été comparée, mais continuer à la déplacer vers l'arrière, ce qui améliore l'efficacité.

Alors la question est : comment puis-je savoir combien de postes déplacer ?

Les auteurs de cet algorithme de décalage KMP nous l'ont résumé :

Copier le code Le code est le suivant :

Chiffres changeants = Nombre de caractères correspondants - Valeur de correspondance partielle correspondante

L'algorithme de décalage n'est lié qu'aux sous-chaînes, pas aux chaînes de texte, une attention particulière doit donc être accordée ici
Alors, comment comprendre le nombre de caractères correspondant dans la sous-chaîne et la valeur de correspondance partielle correspondante ?

Caractères correspondants :

Copier le code Le code est le suivant :

T : abababaabab

p : ababacb

La marque rouge en p est le caractère correspondant, facile à comprendre

Valeur de correspondance partielle :

C'est l'algorithme de base, et il est également difficile à comprendre

Si :

Copier le code Le code est le suivant :

T：aaronaabbcc

P：aaronaac

Nous pouvons observer ce texte. Si nous faisons une erreur lors de la correspondance avec c, où sera notre prochain mouvement basé sur la structure précédente ? Où est le mouvement le plus raisonnable ?

Copier le code Le code est le suivant :

Aaronaabcc
Aaronac

C'est-à-dire : dans le texte du modèle, si le début et la fin d'un certain paragraphe de caractères sont les mêmes, alors ce paragraphe de contenu peut être ignoré lors du filtrage naturel. Cette idée est également raisonnable

Connaissant cette règle, l'algorithme de table de correspondance partielle donné est le suivant :

Tout d'abord, vous devez comprendre deux concepts : « préfixe » et « suffixe ». « Préfixe » fait référence à toutes les combinaisons de têtes d'une chaîne à l'exception du dernier caractère ; « suffixe » fait référence à toutes les combinaisons de queue d'une chaîne à l'exception du premier caractère.

"Valeur de correspondance partielle" est la longueur de l'élément commun le plus long entre "préfixe" et "suffixe""

Jetons un coup d'œil à la division Aaronaac s'il s'agit d'un match BF

Déplacement de BF : a,aa,aar,aaro,aaron,aarona,aaronaa,aaronaac

Et alors, qu’en est-il des divisions de KMP ? Ici, nous devons introduire les préfixes et les suffixes

Regardons d'abord les résultats du tableau de correspondance partielle KMP :

Copier le code Le code est le suivant :

a a r o n a a c

[0, 1, 0, 0, 0, 1, 2, 0]

Je suis vraiment confus, alors ne vous inquiétez pas, décomposons-le, préfixes et suffixes

Copier le code Le code est le suivant :

Chaîne de correspondance : "Aaron"

Préfixe : A, Aa, Aar, Aaro

Suffixe : aron,ron,on,n

Position de déplacement : En fait, il s'agit de comparer le préfixe et le suffixe de chaque caractère correspondant pour voir s'ils sont égaux, puis de calculer la longueur totale

Décomposition du tableau de correspondance partielle

L'algorithme de table de correspondance dans KMP, où p représente le préfixe, n représente le suffixe et r représente le résultat

Copier le code Le code est le suivant :

a, p=>0, n=>0 r = 0

aa, p=>[a], n=>[a], r = a.length => 1

aar, p=>[a,aa], n=>[r,ar] ,r = 0

aaro, p=>[a,aa,aar], n=>[o,ra,aro] ,r = 0

aaron p=>[a,aa,aar,aaro], n=>[n,on,ron,aron] ,r = 0

aarona, p=>[a,aa,aar,aaro,aaron], n=>[a,na,ona,rona,arona] ,r = a.longueur = 1

aaronaa, p=>[a,aa,aar,aaro,aaron,aarona], n=>[a,aa,naa,onaa,ronaa,aronaa] , r = Math.max(a.length ,aa.longueur) = 2

aaronaac p=>[a,aa,aar,aaro,aaron,aarona], n=>[c,ac,aac,naac,onaac,ronaac] r = 0

Semblable à l'algorithme BF, décomposez d'abord la position de chaque indice de correspondance possible et mettez-le en cache. Lors de la correspondance, utilisez ce "tableau de correspondance partielle" pour localiser le nombre de chiffres qui doivent être déplacés

Le résultat final du tableau de correspondance d'aaronaac est donc 0,1,0,0,0,1,2,0

La version JS de KMP sera implémentée ci-dessous, il en existe 2 types

Implémentation KMP (1) : table de correspondance de mise en cache KMP

Implémentation KMP (2) : calculer dynamiquement le prochain KMP

Implémentation KMP (1)

Table assortie

La chose la plus importante dans l'algorithme KMP est la table de correspondance. Si la table de correspondance n'est pas requise, alors c'est l'implémentation de BF. L'ajout de la table de correspondance est KMP

Le tableau de correspondance détermine le prochain nombre de déplacements

Sur la base des règles du tableau de correspondance ci-dessus, nous concevons une méthode kmpGetStrPartMatchValue

function kmpGetStrPartMatchValue(str) {
   var prefix = [];
   var suffix = [];
   var partMatch = [];
   for (var i = 0, j = str.length; i < j; i++) {
    var newStr = str.substring(0, i + 1);
    if (newStr.length == 1) {
     partMatch[i] = 0;
    } else {
     for (var k = 0; k < i; k++) {
      //前缀
      prefix[k] = newStr.slice(0, k + 1);
      //后缀
      suffix[k] = newStr.slice(-k - 1);
      //如果相等就计算大小,并放入结果集中
      if (prefix[k] == suffix[k]) {
       partMatch[i] = prefix[k].length;
      }
     }
     if (!partMatch[i]) {
      partMatch[i] = 0;
     }
    }
   }
   return partMatch;
  }

Copier après la connexion

Tout à fait conforme à l'implémentation de l'algorithme de table de correspondance dans KMP, a->aa->aar->aaro->aaron->aarona-> je 1) aaronaa-aaronaac

Calculez ensuite la longueur des éléments communs par préfixe et suffixe dans chaque décomposition

Algorithme de recul

KMP est également un algorithme frontal. Vous pouvez transférer complètement celui de BF. La seule modification est que BF ajoute directement 1 lors du retour en arrière. Lorsque KMP revient en arrière, nous pouvons calculer la valeur suivante via la table de correspondance
.

//子循环
for (var j = 0; j < searchLength; j++) {
  //如果与主串匹配
  if (searchStr.charAt(j) == sourceStr.charAt(i)) {
    //如果是匹配完成
    if (j == searchLength - 1) {
     result = i - j;
     break;
    } else {
     //如果匹配到了，就继续循环，i++是用来增加主串的下标位
     i++;
    }
  } else {
   //在子串的匹配中i是被叠加了
   if (j > 1 && part[j - 1] > 0) {
    i += (i - j - part[j - 1]);
   } else {
    //移动一位
    i = (i - j)
   }
   break;
  }
}

Copier après la connexion

La marque rouge est le point central de KMP La valeur de next = le nombre de caractères correspondants - la valeur de correspondance partielle correspondante

Algorithme KMP complet

<!doctype html><div id="test2"><div><script type="text/javascript">
 

  function kmpGetStrPartMatchValue(str) {
   var prefix = [];
   var suffix = [];
   var partMatch = [];
   for (var i = 0, j = str.length; i < j; i++) {
    var newStr = str.substring(0, i + 1);
    if (newStr.length == 1) {
     partMatch[i] = 0;
    } else {
     for (var k = 0; k < i; k++) {
      //取前缀
      prefix[k] = newStr.slice(0, k + 1);
      suffix[k] = newStr.slice(-k - 1);
      if (prefix[k] == suffix[k]) {
       partMatch[i] = prefix[k].length;
      }
     }
     if (!partMatch[i]) {
      partMatch[i] = 0;
     }
    }
   }
   return partMatch;
  }



function KMP(sourceStr, searchStr) {
  //生成匹配表
  var part     = kmpGetStrPartMatchValue(searchStr);
  var sourceLength = sourceStr.length;
  var searchLength = searchStr.length;
  var result;
  var i = 0;
  var j = 0;

  for (; i < sourceStr.length; i++) { //最外层循环，主串

    //子循环
    for (var j = 0; j < searchLength; j++) {
      //如果与主串匹配
      if (searchStr.charAt(j) == sourceStr.charAt(i)) {
        //如果是匹配完成
        if (j == searchLength - 1) {
         result = i - j;
         break;
        } else {
         //如果匹配到了，就继续循环，i++是用来增加主串的下标位
         i++;
        }
      } else {
       //在子串的匹配中i是被叠加了
       if (j > 1 && part[j - 1] > 0) {
        i += (i - j - part[j - 1]);
       } else {
        //移动一位
        i = (i - j)
       }
       break;
      }
    }

    if (result || result == 0) {
     break;
    }
  }


  if (result || result == 0) {
   return result
  } else {
   return -1;
  }
}

 var s = "BBC ABCDAB ABCDABCDABDE";
 var t = "ABCDABD";


 show('indexOf',function() {
  return s.indexOf(t)
 })

 show('KMP',function() {
  return KMP(s,t)
 })

 function show(bf_name,fn) {
  var myDate = +new Date()
  var r = fn();
  var div = document.createElement('div')
  div.innerHTML = bf_name +'算法,搜索位置:' + r + ",耗时" + (+new Date() - myDate) + "ms";
   document.getElementById("test2").appendChild(div);
 }


</script></div></div>

Copier après la connexion

KMP（二）

第一种kmp的算法很明显，是通过缓存查找匹配表也就是常见的空间换时间了。那么另一种就是时时查找的算法，通过传递一个具体的完成字符串，算出这个匹配值出来，原理都一样

生成缓存表的时候是整体全部算出来的，我们现在等于只要挑其中的一条就可以了，那么只要算法定位到当然的匹配即可

next算法

function next(str) {
  var prefix = [];
  var suffix = [];
  var partMatch;
  var i = str.length
  var newStr = str.substring(0, i + 1);
  for (var k = 0; k < i; k++) {
   //取前缀
   prefix[k] = newStr.slice(0, k + 1);
   suffix[k] = newStr.slice(-k - 1);
   if (prefix[k] == suffix[k]) {
    partMatch = prefix[k].length;
   }
  }
  if (!partMatch) {
   partMatch = 0;
  }
  return partMatch;
}

Copier après la connexion

其实跟匹配表是一样的，去掉了循环直接定位到当前已成功匹配的串了

完整的KMP.next算法

<!doctype html><div id="testnext"><div><script type="text/javascript">
 
  function next(str) {
    var prefix = [];
    var suffix = [];
    var partMatch;
    var i = str.length
    var newStr = str.substring(0, i + 1);
    for (var k = 0; k < i; k++) {
     //取前缀
     prefix[k] = newStr.slice(0, k + 1);
     suffix[k] = newStr.slice(-k - 1);
     if (prefix[k] == suffix[k]) {
      partMatch = prefix[k].length;
     }
    }
    if (!partMatch) {
     partMatch = 0;
    }
    return partMatch;
  }

  function KMP(sourceStr, searchStr) {
    var sourceLength = sourceStr.length;
    var searchLength = searchStr.length;
    var result;
    var i = 0;
    var j = 0;

    for (; i < sourceStr.length; i++) { //最外层循环，主串

      //子循环
      for (var j = 0; j < searchLength; j++) {
        //如果与主串匹配
        if (searchStr.charAt(j) == sourceStr.charAt(i)) {
          //如果是匹配完成
          if (j == searchLength - 1) {
           result = i - j;
           break;
          } else {
           //如果匹配到了，就继续循环，i++是用来增加主串的下标位
           i++;
          }
        } else {
         if (j > 1) {
          i += i - next(searchStr.slice(0,j));
         } else {
          //移动一位
          i = (i - j)
         }
         break;
        }
      }

      if (result || result == 0) {
       break;
      }
    }


    if (result || result == 0) {
     return result
    } else {
     return -1;
    }
  }

 var s = "BBC ABCDAB ABCDABCDABDE";
 var t = "ABCDAB";


  show('indexOf',function() {
   return s.indexOf(t)
  })

  show('KMP.next',function() {
   return KMP(s,t)
  })

  function show(bf_name,fn) {
   var myDate = +new Date()
   var r = fn();
   var div = document.createElement('div')
   div.innerHTML = bf_name +'算法,搜索位置:' + r + ",耗时" + (+new Date() - myDate) + "ms";
    document.getElementById("testnext").appendChild(div);
  }

</script></div></div>

Copier après la connexion

git代码下载: https://github.com/JsAaron/data_structure

Structures de données et algorithmes en JavaScript (5) : compétences classiques KMP algorithm_javascript