Laissez-vous comprendre facilement l'algorithme KMP

L'algorithme KMP (l'algorithme de Knuth-Morris-Pratt) est utilisé pour la correspondance de chaînes afin de trouver une sous-chaîne donnée à partir d'une chaîne. Mais ce n’est pas très simple à comprendre et à maîtriser. Comprendre la table de correspondance partielle dans son concept est la clé pour comprendre l'algorithme KMP.

La discussion ici évite la logique obscure qui la sous-tend et se concentre sur sa compréhension à partir de son application.

Recherche de chaîne

Par exemple, recherchez la sous-chaîne abcdef de la chaîne abcdg.

Une solution simple, nous pouvons faire ceci,

• supprimer respectivement le premier chiffre pour la correspondance, et s'ils sont identiques, retirer le deuxième chiffre.
• S'ils sont différents, reculez l'index d'un bit, en commençant par le deuxième chiffre de la chaîne totale, et répétez la première étape.

L'inconvénient de cette solution simple est qu'à chaque fois que la correspondance échoue, l'index ne recule que d'une position, ce qui comporte de nombreuses opérations redondantes et n'est pas efficace.

Au premier tour de correspondance, c'est-à-dire lorsque l'indice est 0, nous pouvons constater que les quatre premiers caractères abcd sont égaux, mais plus tard nous constatons que le g souhaité ne correspond pas au réel e. Cela indique que la correspondance échoue lorsque l'index est 0, et nous commençons à regarder l'index 1. Cependant, comme nous connaissons déjà l'apparence des quatre premiers caractères de la chaîne totale lors du premier tour de correspondance, nous devons encore les faire correspondre un par un à plusieurs reprises.

Table de correspondance partielle/Table de correspondance partielle

En prenant une chaîne de longueur 8 abababca comme exemple, la table de correspondance partielle est :

<span style="font-family:Microsoft Yahei, Hiragino Sans GB, Helvetica, Helvetica Neue, 微软雅黑, Tahoma, Arial, sans-serif">char:  | a | b | a | b | a | b | c | a |<br>index: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | <br>value: | 0 | 0 | 1 | 2 | 3 | 4 | 0 | 1 |</span>

La ligne value est la valeur du tableau de correspondance partielle.

Sous-ensemble

Pour l'exemple de chaîne ci-dessus, si nous observons la position où index est 2, alors nous obtenons un sous-ensemble de la chaîneaba, si on observe la position où index vaut 7, il est évident qu'on obtient la chaîne entière. Lorsque la position que nous observons est différente, cela signifie que le sous-ensemble de la chaîne auquel nous prêtons attention est différent car la sous-chaîne a changé.

Préfixe et suffixe

Pour une chaîne donnée, supprimez un ou plusieurs caractères de la fin, et la partie restante est appelée la vraie valeur du préfixe de chaîne (propre préfixe), ci-après dénommé préfixe. "Vrai" ici ne signifie pas "vrai préfixe". Pensez au "sous-ensemble approprié" d'un ensemble en mathématiques. Par exemple, banana, son préfixe est :

• <span style="font-family:Microsoft Yahei, Hiragino Sans GB, Helvetica , Helvetica Neue, 微软雅é»', Tahoma, Arial, sans-serif">b<code style="white-space: nowrap;"><span style="font-family:Microsoft Yahei, Hiragino Sans GB, Helvetica, Helvetica Neue, 微软雅黑, Tahoma, Arial, sans-serif">b</span>
• ba<code style="white-space: nowrap;"><span style="font-family:Microsoft Yahei, Hiragino Sans GB, Helvetica, Helvetica Neue, 微软雅黑, Tahoma, Arial, sans-serif">ba</span>
• <span style="font-family:Microsoft Yahei, Hiragino Sans GB, Helvetica, Helvetica Neue, 微软雅é»' , Tahoma , Arial, sans-serif">ban<code style="white-space: nowrap;"><span style="font-family:Microsoft Yahei, Hiragino Sans GB, Helvetica, Helvetica Neue, 微软雅黑, Tahoma, Arial, sans-serif">ban</span>
• <span style="font-family:Microsoft Yahei, Hiragino Sans GB , Helvetica, Helvetica Neue, 微软雅é»', Tahoma, Arial, sans-serif">bana<code style="white-space: nowrap;"><span style="font-family:Microsoft Yahei, Hiragino Sans GB, Helvetica, Helvetica Neue, 微软雅黑, Tahoma, Arial, sans-serif">bana</span>
• <span style="font-family:Microsoft Yahei, Hiragino Sans GB, Helvetica, Helvetica Neue, 微软雅é»', Tahoma, Arial, sans-serif">banan<code style="white-space: nowrap;"><span style="font-family:Microsoft Yahei, Hiragino Sans GB, Helvetica, Helvetica Neue, 微软雅黑, Tahoma, Arial, sans-serif">banan</span> code>

De même, en commençant par l'en-tête, supprimez un ou plusieurs mots, et la partie restante est le vrai suffixe (Suffixe approprié) de la chaîne. Ou banana, son suffixe est :

• <span style="font-family:Microsoft Yahei, Hiragino Sans GB, Helvetica, Helvetica Neue, 微软雅黑, Tahoma, Arial, sans-serif">anana</span>
• <span style="font-family:Microsoft Yahei, Hiragino Sans GB, Helvetica, Helvetica Neue, 微软雅黑, Tahoma, Arial, sans-serif">nana</span>
• <span style="font-family:Microsoft Yahei, Hiragino Sans GB, Helvetica, Helvetica Neue, 微软雅黑, Tahoma, Arial, sans-serif">ana</span>
• <span style="font-family:Microsoft Yahei, Hiragino Sans GB, Helvetica, Helvetica Neue, 微软雅黑, Tahoma, Arial, sans-serif">na</span>
• <span style="font-family:Microsoft Yahei, Hiragino Sans GB, Helvetica, Helvetica Neue, 微软雅黑, Tahoma, Arial, sans-serif">a</span>

Valeur de correspondance partielle

On peut voir que tous les préfixes et suffixes sont symétriques en quantité, nous pouvons alors en trouver un dans le préfixe pour correspondre au suffixe, d'abord Ne je me soucie de l’intérêt de faire ce match. Prenons le texte initial abababca comme exemple.

Si l'on observe la position où index est 2, la sous-chaîne est aba, et ses suffixes et suffixes sont :

• Préfixe : a, ab
• suffixe : ba, a

Faites correspondre les préfixes du suffixe à tour de rôle. Ici, le seul sous-caractère pouvant correspondre dans la liste des suffixes est <.> La longueur de la chaîne est de 1, alors remplissez le résultat de l'observation dans le tableau et notez-le, qui correspond au tableau de correspondance partielle que vous avez vu au début. a

Pour un autre exemple, regardez la position où

est 3. La sous-chaîne obtenue à ce moment est index, et le préfixe et le suffixe à ce moment sont : abab

Préfixe :
• , a, ababa
suffixe :
• , bab, abb

À ce moment, on peut l'observer que l'élément correspondant est

, La longueur est 2, ce qui est également cohérent avec la valeur du tableau de correspondance partielle ci-dessus. ab

Pour un autre exemple, observons la position où

est 5. A ce moment, la sous-chaîne est index, et le suffixe et le suffixe sont : ababab

Préfixe :
• , a , ab, aba, ababababa
Suffixe :
• , babab, abab, bab, abb

puis prenez Chaque élément du préfixe est mis en correspondance avec l'élément du suffixe, et deux éléments correspondants sont finalement trouvés,

<span style="font -family:Microsoft Yahei, Hiragino Sans GB, Helvetica, Helvetica Neue, 微软雅é»', Tahoma, Arial, sans-serif">ab<li> code><code style="white-space: nowrap;"><span style="font-family:Microsoft Yahei, Hiragino Sans GB, Helvetica, Helvetica Neue, 微软雅黑, Tahoma, Arial, sans-serif">ab</span> abab
• <span style="font-family:Microsoft Yahei, Hiragino Sans GB, Helvetica, Helvetica Neue, 微软雅黑, Tahoma, Arial, sans-serif">abab</span>

On prend le plus long

, sa longueur est de 4. abab

Regardons maintenant le tableau de correspondance partielle ci-dessus. Premièrement, nous pouvons comprendre d'où vient sa valeur, et deuxièmement, nous pouvons comprendre la signification de sa représentation, c'est-à-dire la longueur la plus longue parmi tous les préfixes et. le suffixe correspond à la longueur de celui-ci.

Lorsque nous continuons jusqu'à ce que

soit 6, la sous-chaîne est index et, comme on pouvait s'y attendre, aucune correspondance n'est trouvée dans le préfixe et le suffixe. Parce que tous les préfixes ne contiennent pas abababc, et tous les suffixes contiennent c. La valeur de correspondance partielle est donc 0 à ce moment. c

Si vous continuez, vous atteindrez la fin de la chaîne, c'est-à-dire la chaîne entière

. On s'attend également à ce que puisque tous les préfixes commencent par abababca et que tous les suffixes se terminent par a, la valeur de correspondance partielle à ce moment est d'au moins 1. Vous continuerez à constater que parce que les suffixes suivants commencent à avoir a ajouté, tous les suffixes contiennent c, et le seul préfixe qui peut contenir ca est c, et la longueur de 7 est la même que celle du suffixe abababc de la même longueur ne correspond pas. À ce stade, on peut conclure que le résultat de la correspondance est 1 et qu’il n’y a plus de correspondance. bababca

Utilisation d'une table de correspondance partielle

En utilisant la valeur de correspondance partielle ci-dessus, lorsque nous effectuons une recherche de chaîne, nous n'avons pas besoin de nous déplacer d'un seul bit après chaque échec, mais plusieurs bits peuvent être déplacés pour supprimer certaines correspondances redondantes. Il y a ici une formule comme suit :

Si une correspondance partielle de longueur partial_match_length est trouvée et table[partial_match_length] > personnages

如果匹配过程中，匹配到了部分值为 partial_match_length，即目前找出前 partial_match_length 个字符是匹配的，将这个长度减一作为部分匹配表格中的 index 代入，查找其对应的 value 即 table[partial_match_length-1]，那么我们可以向前移动的步长为 partial_match_length - table[partial_match_length - 1]。

下面是本文开始时的那个部分匹配表:

<span style="font-family:Microsoft Yahei, Hiragino Sans GB, Helvetica, Helvetica Neue, 微软雅黑, Tahoma, Arial, sans-serif">char:  | a | b | a | b | a | b | c | a |<br>index: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | <br>value: | 0 | 0 | 1 | 2 | 3 | 4 | 0 | 1 |</span>

假设需要从 bacbababaabcbab 中查找 abababca，根据上面的公式我们来走一遍。

首次匹配发生在总字符串的第二个字符，

<span style="font-family:Microsoft Yahei, Hiragino Sans GB, Helvetica, Helvetica Neue, 微软雅黑, Tahoma, Arial, sans-serif">bacbababaabcbab |<br> abababca</span>

此时匹配的长度为 1，部分匹配表中索引为 1-1=0 的位置对应的部分匹配值为 0，所以我们可以向前移动的距离是 1-0 1。其实也相当于没有跳跃，就是正常的本次匹配失败，索引后移一位的情况。这里没有节省任何成本。

继续直到再次发生匹配，此时匹配到的情况如下：

<span style="font-family:Microsoft Yahei, Hiragino Sans GB, Helvetica, Helvetica Neue, 微软雅黑, Tahoma, Arial, sans-serif">bacbababaabcbab    |||||<br>    abababca</span>

现在匹配到的长度是 5，部分匹配表中 5-1=4 对应的部分匹配值为 3，所以我们可以向前移动 5-3=2，此时一下子就可以移动两位了。

<span style="font-family:Microsoft Yahei, Hiragino Sans GB, Helvetica, Helvetica Neue, 微软雅黑, Tahoma, Arial, sans-serif">    上一次的位置    | 最新移动到的位置    | |bacbababaabcbab<br>    xx|||<br>      abababca</span>

此时匹配到的长度为 3， 查找到 table[partial_match_length-1] 即 index 为 2 对应的值为 1，所以可向前移动的距离为 

3-1=2。

<span style="font-family:Microsoft Yahei, Hiragino Sans GB, Helvetica, Helvetica Neue, 微软雅黑, Tahoma, Arial, sans-serif">bacbababaabcbab<br>      xx|<br>        abababca</span>

此时我们需要查找的字符串其长度已经超出剩余可用来匹配的字符串了，所以可直接结束匹配，得到结论：没有查找到结果。

Javascript 中的实现

以下是来自 trekhleb/javascript-algorithms 中 JavaScript 版本的 KMP 算法实现：

相关教程：Javascript视频教程

<span style="font-family:Microsoft Yahei, Hiragino Sans GB, Helvetica, Helvetica Neue, 微软雅黑, Tahoma, Arial, sans-serif">//**<br/> * @see https://www.youtube.com/watch?v=GTJr8OvyEVQ<br/> * @param {string} word<br/> * @return {number[]}<br/> */<br/>function buildPatternTable(word) {<br/>  const patternTable = [0];<br/>  let prefixIndex = 0;<br/>  let suffixIndex = 1;<br/><br/>  while (suffixIndex < word.length) {<br/>    if (word[prefixIndex] === word[suffixIndex]) {<br/>      patternTable[suffixIndex] = prefixIndex + 1;<br/>      suffixIndex += 1;<br/>      prefixIndex += 1;<br/>    } else if (prefixIndex === 0) {<br/>      patternTable[suffixIndex] = 0;<br/>      suffixIndex += 1;</span><span style="font-family:Microsoft Yahei, Hiragino Sans GB, Helvetica, Helvetica Neue, 微软雅黑, Tahoma, Arial, sans-serif"><br/></span><span style="font-family:Microsoft Yahei, Hiragino Sans GB, Helvetica, Helvetica Neue, 微软雅黑, Tahoma, Arial, sans-serif">    } else {<br/>      prefixIndex = patternTable[prefixIndex - 1];<br/>    }<br/>  }<br/><br/>  return patternTable;<br/>}<br/><br/>/**<br/> * @param {string} text<br/> * @param {string} word<br/> * @return {number}<br/> */<br/>export default function knuthMorrisPratt(text, word) {<br/>  if (word.length === 0) {<br/>    return 0;</span><span style="font-family:Microsoft Yahei, Hiragino Sans GB, Helvetica, Helvetica Neue, 微软雅黑, Tahoma, Arial, sans-serif"><br/>  }<br/><br/>  let textIndex = 0;<br/>  let wordIndex = 0;<br/><br/>  const patternTable = buildPatternTable(word);<br/><br/>  while (textIndex < text.length) {<br/>    if (text[textIndex] === word[wordIndex]) {<br/>      // We&#39;ve found a match.<br/>      if (wordIndex === word.length - 1) {<br/>        return (textIndex - word.length) + 1;<br/>      }<br/>      wordIndex += 1;<br/>      textIndex += 1;<br/>    } else if (wordIndex > 0) {<br/>      wordIndex = patternTable[wordIndex - 1];<br/>    } else {<br/>      wordIndex = 0;<br/>      textIndex += 1;<br/>    }<br/>  }<br/><br/>  return -1;<br/>}<br/></span>

时间复杂度

因为算法中涉及两部分字符串的线性对比，其时间复杂度为两字符串长度之和，假设需要搜索的关键词长度为 k，总字符串长度为 m，则时间复杂度为 O(k+m)。

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!