JavaScript のデータ構造とアルゴリズム (5): クラシック KMP アルゴリズム

KMP アルゴリズムと BM アルゴリズム

KMP はプレフィックスマッチングと BM サフィックスマッチングの古典的なアルゴリズムです。プレフィックスマッチングとサフィックスマッチングの違いは比較の順序のみであることがわかります。

前方一致とは、パターン文字列と親文字列の比較は左から右であり、パターン文字列の移動も左から右であることを意味します

サフィックスマッチングとは、パターン文字列と親文字列の比較は右から左へ、パターン文字列の移動は左から右へということを意味します。

前の章から、BF アルゴリズムもプレフィックスアルゴリズムであることは明らかですが、1 つずつのマッチングの効率は非常に傲慢です。当然、O( について言及する必要はありません。 mn) オンラインでは迷惑な KMP が多くのことを説明していますが、基本的には高レベルの方法を採用しているので、あなたは混乱するかもしれません。私はそれを最も現実的な方法で説明しようとしました。

KMP

KMP もプレフィックスアルゴリズムの最適化バージョンです。Knuth、Morris、Pratt の 3 つの名前の略称として KMP と呼ばれる理由は、BF と比較した場合の KMP アルゴリズムの最適化ポイントです。各パターン列の移動距離を動的に調整します。BF は毎回 1、

必ずしも KMP に当てはまるわけではありません

図に示すように、BF と KMP の事前アルゴリズムの違いを比較します

写真を比較して次のことがわかりました:

文字列 T 内のパターン文字列 P を検索します。自然に 6 番目の文字 c と一致すると、第 2 レベルが不一致であることがわかります。そこで、BF メソッドは、パターン文字列 P 全体を 1 桁移動します。 KMP はそれを 2 つ移動します。

BF のマッチング方法はわかっていますが、なぜ KMP は 1 桁、3 桁、または 4 桁ではなく 2 桁を移動するのでしょうか?

前の図を説明します。パターン文字列 P が ababa に一致する場合は正しく、c に一致する場合は誤りです。KMP アルゴリズムの考え方は、ababa が正しく一致するということです。この情報を使用して、「検索位置」を比較された位置に戻すのではなく、後方に移動し続けるため、効率が向上します。

そこで問題は、移動するポジションの数をどうやって知るかということです。

このオフセットアルゴリズム KMP の作成者は、次のように要約しています。

コードをコピーコードは次のとおりです:

シフト桁 = 一致した文字の数 - 対応する部分一致値

オフセットアルゴリズムはテキスト文字列ではなく部分文字列にのみ関連するため、ここでは特別な注意を払う必要があります

では、部分文字列内の一致する文字の数と、対応する部分一致の値を理解するにはどうすればよいでしょうか?

一致する文字:

コードをコピーコードは次のとおりです:

T : アババババブ

p:ababacb

p の赤いマークは一致した文字であり、わかりやすい

部分一致値:

これは核となるアルゴリズムですが、理解するのが難しいです

場合:

コードをコピーコードは次のとおりです:

T：アロナアbbcc

P：アーロナック

このテキストを観察すると、c のマッチング時にエラーが発生した場合、次の移動は前の構造に基づいてどこに行われるでしょうか?

コードをコピーコードは次のとおりです:

アーロナBBCC

アーロナック

つまり、パターンテキスト内で、文字の特定の段落の始まりと終わりが同じ場合、自然フィルタリング中にコンテンツのこの段落をスキップできます。この考えも合理的です。

このルールを知っていると、与えられる部分一致テーブルのアルゴリズムは次のようになります:

まず、「プレフィックス」と「サフィックス」という 2 つの概念を理解する必要があります。「プレフィックス」は、最後の文字を除く文字列の先頭のすべての組み合わせを指します。「サフィックス」は、最初の文字を除く文字列の末尾のすべての組み合わせを指します。

「部分一致値」は「prefix」と「suffix」の最も長い共通要素の長さです。

BF戦の場合のaaronaacの部門を見てみましょう

BF の変位: a,aa,aar,aaro,aaron,aarona,aaronaa,aaronaac

では、KMP の部門はどうなるのでしょうか?ここでプレフィックスとサフィックスを導入する必要があります

まず、KMP 部分一致テーブルの結果を見てみましょう:

コードをコピーコードは次のとおりです:

a a r o n a a c

[0、1、0、0、0、1、2、0]

間違いなく混乱しているので、心配しないでください。接頭辞と接尾辞を分けて説明しましょう

コードをコピーコードは次のとおりです:

一致文字列: 「Aaron」

接頭語: A、Aa、Aar、Aaro

サフィックス: aron、ron、on、n

移動位置: 実際には、一致した各文字の接頭辞と接尾辞を比較して等しいかどうかを確認し、合計の長さを計算します

部分一致テーブルの分解

KMP のマッチングテーブルアルゴリズム。p はプレフィックス、n はサフィックス、r は結果を表します

コードをコピーコードは次のとおりです:

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

アーロン 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.length = 1

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

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

BF アルゴリズムと同様に、まず、一致する可能性のある各添字の位置を分解し、キャッシュします。一致する場合は、この「部分一致テーブル」を使用して、移動する必要がある桁数を特定します。

aaronaac のマッチングテーブルの最終結果は 0,1,0,0,0,1,2,0 になります。

JS バージョンの KMP は以下に実装されます。2 種類あります

KMP 実装 (1): KMP キャッシュマッチングテーブル

KMP 実装 (2): 次の KMP を動的に計算します

KMP 実装 (1)

マッチングテーブル

KMP アルゴリズムで最も重要なのはマッチングテーブルです。マッチングテーブルが必要ない場合は、BF の実装が KMP です。

マッチングテーブルにより次の変位カウントが決定されます

上記のマッチングテーブルのルールに基づいて、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;
  }

ログイン後にコピー

KMP のマッチングテーブルアルゴリズムの実装に従って、a->aa->aar->aaro->aaron->aarona-> は str.substring(0,私 1) アロナア-アロナック

次に、各分解のプレフィックスとサフィックスを通じて共通要素の長さを計算します

バックオフアルゴリズム

KMP もフロントエンドアルゴリズムです。BF アルゴリズムを完全に転送できます。唯一の変更点は、KMP がバックトラックするときに、マッチングテーブルを通じて次の値を計算できることです。

//子循环
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;
  }
}

ログイン後にコピー

赤いマークは KMP の中心点です。next の値 = 一致した文字数 - 対応する部分一致値です。

完全な KMP アルゴリズム

<!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>

ログイン後にコピー

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;
}

ログイン後にコピー

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

完整的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>

ログイン後にコピー

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