JavaScriptのデータ構造とアルゴリズム (4): 文字列(BF)_javascriptスキル-jsチュートリアル-php.cn

文字列は 0 個以上の文字の有限シーケンスであり、文字列

とも呼ばれます

文字列の論理構造は線形テーブルの論理構造に非常に似ていますが、違いは文字列が文字セットであるため、その操作は線形テーブルの論理構造とはまったく異なります。線形テーブルは単一要素の CURD 操作に重点を置きますが、文字列は部分文字列の位置の検索や置換などの操作に重点を置きます。

もちろん、高級言語が異なれば基本的な文字列操作の定義は異なりますが、一般に操作の本質は似ています。たとえば、JavaScript の検索はindexOf、空白の削除はtrim、大文字と小文字のLowerCase/toUpperCaseへの変換などです。

ここでは主に、文字列パターンマッチングのためのいくつかの古典的なアルゴリズム、BF、BM、KMP について説明します

BF (ブルートフォース) アルゴリズム

ブルートフォースアルゴリズムの基本的な考え方:

ターゲット文字列 s の最初の文字とパターン文字列 t の最初の文字を比較します。等しい場合は、後続の文字を 1 つずつ比較し続けます。そうでない場合は、文字列 s の 2 番目の文字から開始して再開します。文字列 t を比較します。

以下同様に、文字列 t の各文字が文字列 s の連続する文字列と等しくなるまで、この時点で、文字列 s 内の文字列 t の最初の文字の位置がパターンマッチングに成功したと見なされます。 s 内の t 位置、それ以外の場合はパターンマッチングが失敗します

BF アルゴリズムは、単純マッチングアルゴリズムまたはブルートフォースアルゴリズムとしても知られるブルートフォースアルゴリズムであることがわかります。

メイン文字列 BBC ABB ABCF

部分文字列 ABC

メイン文字列内の部分文字列の位置の検索は、JavaScript の IndexOf 検索メソッドの実装に対応します

var sourceStr = "BBC ABB ABCF";
var searchStr = "ABC";

function BF_Ordinary(sourceStr, searchStr) {
 var sourceLength = sourceStr.length;
 var searchLength = searchStr.length;
 var padding   = sourceLength - searchLength; //循环的次数
 //BBC ABB ABCF =>ABC => 搜索9次
 for (var i = 0; i <= padding; i++) {
  //如果满足了第一个charAt是相等的
  //开始子循环检测
  //其中sourceStr的取值是需要叠加i的值
  if (sourceStr.charAt(i) == searchStr.charAt(0)) {
   //匹配成功的数据
   var complete = searchLength;
   for (var j = 0; j < searchLength; j++) {
    if (sourceStr.charAt(i + j) == searchStr.charAt(j)) {
     --complete
     if (!complete) {
      return i;
     }
    }
   }
  }
 }
 return -1;
}

ログイン後にコピー

BF アルゴリズムは単純かつ粗雑です。BBC ABB ABCF 親文字列の各文字について下の表を直接取り出し、それをパターン文字列の最初の文字と照合します。それらが等しい場合、その文字列は再度照合されます。

ここで注目してください:

1: 最も外側のループの回数 sourceLength - searchLength。これは、一致する親文字列が少なくとも部分文字列

以上である必要があるためです。

2: 部分文字列の継続的なマッチングでは、親文字列の開始点を重ね合わせる必要があります (i j)

3: 条件によって完全に一致するかどうかを判断します。BBC ABB ABCF では、ABB

にいるときにジャンプする必要があります。

上記は最も単純なアルゴリズムであり、コード内にはさらに優れた処理方法があります。たとえば、反転アルゴリズムを使用して自己文字列を照合できます。

最適化アルゴリズム (1)

function BF_Optimize(sourceStr, searchStr) {
  var mainLength  = sourceStr.length;
  var searchLength = searchStr.length;
  var padding   = mainLength - searchLength;
  for (var offset = 0; offset <= padding; offset++) {
   var match = true;
   for (var i = 0; i < searchLength; i++) {
    //取反,如果只要不相等
    if (searchStr.charAt(i) !== sourceStr.charAt(offset + i)) {
     match = false;
     break;
    }
   }
   if (match) return offset;
  }
  return -1;
}

ログイン後にコピー

状況を真と判断する必要はなく、状況を偽と判断するだけで済みます。サブマッチが完了した後にマッチが変更されない場合、マッチは完全マッチであることを意味します。 >

上記の2つの方法ではサブループを使用していますが、これをループ本体に変更できますか?

実際、メイン文字列は毎回 1 ずつ増加するだけであり、サブ文字列は毎回最初から一致するため、それを while に変更して添え字ポインタを制御できることがわかります。 🎜>

最適化アルゴリズム (2)

i はメイン文字列の添字の位置、j はサブ文字列の添字の位置です

function BF_Optimize_2(sourceStr, searchStr) {
 var i = 0,
   j = 0;

  while (i < sourceStr.length) {
    // 两字母相等则继续 
    if (sourceStr.charAt(i) == searchStr.charAt(j)) {
     i++;
     j++;
    } else { // 两字母不等则角标后退重新开始匹配 
     i = i - j + 1; // i 回退到上次匹配首位的下一位 
     j = 0; // j 回退到子串的首位 
    }

    if (j == searchStr.length) {
     return i - j;
    }

  }
}

ログイン後にコピー

主文字列と部分文字列が等しい場合、部分文字列のループモードに入り、サブループの数 j が部分文字列の長さを満たした場合、完全一致であることが検証されます。

主文字列と部分文字列が等しくない場合、主文字列の添え字を 1 ビット戻す必要があります。もちろん、i を使用する場合は部分文字列で処理される可能性があるため、i-j 1 が必要になります。そして部分文字列がリセットされます

詳細については、コードの比較をご覧ください

BF アルゴリズムに基づく 4 つの構造、for/while/recursion

BF も古典的なプレフィックスマッチングアルゴリズムです。プレフィックスには KMP も含まれています。このアルゴリズムの最大の欠点は、文字マッチングが失敗した場合にポインタをバックトラックする必要があるため、パフォーマンスが非常に低いことがわかります。 BF の KMP および BM アルゴリズムのアップグレードについては後で書きます

<!doctype html>由于电脑性能的不断提高，测试的数据量的大小，可能会导致得到的结果不太准确;<script type="text/javascript">

 /////////
 //暴力算法 //
 //普通版
 /////////
 function BF_Ordinary(sourceStr, searchStr) {
  var sourceLength = sourceStr.length;
  var searchLength = searchStr.length;
  var padding   = sourceLength - searchLength; //循环的次数

  //BBC ABB ABCF =>ABC => 搜索9次
  for (var i = 0; i <= padding; i++) {
   //如果满足了第一个charAt是相等的
   //开始子循环检测
   //其中sourceStr的取值是需要叠加i的值
   if (sourceStr.charAt(i) == searchStr.charAt(0)) {
    //匹配成功的数据
    var complete = searchLength;
    for (var j = 0; j < searchLength; j++) {
     if (sourceStr.charAt(i + j) == searchStr.charAt(j)) {
      --complete
      if (!complete) {
       return i;
      }
     }
    }
   }
  }
  return -1;
 }


 /////////
 //暴力算法 //
 //优化版
 /////////
 function BF_Optimize_1(sourceStr, searchStr) {
   var mainLength  = sourceStr.length;
   var searchLength = searchStr.length;
   var padding   = mainLength - searchLength;
   for (var offset = 0; offset <= padding; offset++) {
    var match = true;
    for (var i = 0; i < searchLength; i++) {
     //取反,如果只要不相等
     if (searchStr.charAt(i) !== sourceStr.charAt(offset + i)) {
      match = false;
      break;
     }
    }
    if (match) return offset;
   }
   return -1;
 }


  ////////
  //优化版 //
  //while
  ////////
 function BF_Optimize_2(sourceStr, searchStr) {
  var i = 0,
    j = 0;

   while (i < sourceStr.length) {
     // 两字母相等则继续 
     if (sourceStr.charAt(i) == searchStr.charAt(j)) {
      i++;
      j++;
     } else { // 两字母不等则角标后退重新开始匹配 
      i = i - j + 1; // i 回退到上次匹配首位的下一位 
      j = 0; // j 回退到子串的首位 
     }

     if (j == searchStr.length) {
      return i - j;
     }

   }
 }


 /////////
 //暴力算法
 //递归版本
 /////////
 function BF_Recursive(sourceStr, searchStr, offset) {
   var mainLength = sourceStr.length;
   var searchLength = searchStr.length;
   if (searchLength > mainLength - offset) {
    return -1;
   }
   offset = offset || 0;
   for (var i = 0; searchLength > i; i++) {
    if (searchStr.charAt(i) !== sourceStr.charAt(offset + i)) {
     return BF_Recursive(sourceStr, searchStr, offset + 1)
    }
   }
   return offset;
 }


 
 var sourceStr = "There are some times wThere are some times when clicking “like” on a friend's Facebook status doesn't feel appropriate. A bad day. A loved one lost. A break up. It only seems natural that a “dislike” button could solve the conundrum of wanting to empathize but not seem inappropriate by clicking “like.” Mark Zuckerberg Puts the Rest of Us to Shame by Speaking Fluent Chinese. Mark Zuckerberg: Facebook Founder and Animal Butcher. Mark Zuckerberg and That Shirt. The idea has been on Mark Zuckerberg's radar for a while, he said. In 2010, he told ABC News' Diane Sawyer that that Facebook would “definitely thinkThere are some times when clicking “like” on a friend's Facebook status doesn't feel appropriate. A bad day. A loved one lost. A break up. It only seems natural that a “dislike” button could solve the conundrum of wanting to empathize but not seem inappropriate by clicking “like.” Mark Zuckerberg Puts the Rest of Us to Shame by Speaking Fluent Chinese. Mark Zuckerberg: Facebook Founder and Animal Butcher. Mark Zuckerberg and That Shirt. The idea has been on Mark Zuckerberg's radar for a while, he said. In 2010, he told ABC News' Diane Sawyer that that Facebook would “definitely thinkThere are some times when clicking “like” on a friend's Facebook status doesn't feel appropriate. A bad day. A loved one lost. A break up. It only seems natural that a “dislike” button could solve the conundrum of wanting to empathize but not seem inappropriate by clicking “like.” Mark Zuckerberg Puts the Rest of Us to Shame by Speaking Fluent Chinese. Mark Zuckerberg: Facebook Founder and Animal Butcher. Mark Zuckerberg and That Shirt. The idea has been on Mark Zuckerberg's radar for a while, he said. In 2010, he told ABC News' Diane Sawyer that that Facebook would “definitely thinkThere are some times when clicking “like” on a friend's Facebook status doesn't feel appropriate. A bad day. A loved one lost. A break up. It only seems natural that a “dislike” button could solve the conundrum of wanting to empathize but not seem inappropriate by clicking “like.” Mark Zuckerberg Puts the Rest of Us to Shame by Speaking Fluent Chinese. Mark Zuckerberg: Facebook Founder and Animal Butcher. Mark Zuckerberg and That Shirt. The idea has been on Mark Zuckerberg's radar for a while, he said. In 2010, he told ABC News' Diane Sawyer that that Facebook would “definitely thinkThere are some times when clicking “like” on a friend's Facebook status doesn't feel appropriate. A bad day. A loved one lost. A break up. It only seems natural that a “dislike” button could solve the conundrum of wanting to empathize but not seem inappropriate by clicking “like.” Mark Zuckerberg Puts the Rest of Us to Shame by Speaking Fluent Chinese. Mark Zuckerberg: Facebook Founder and Animal Butcher. Mark Zuckerberg and That Shirt. The idea has been on Mark Zuckerberg's radar for a while, he said. In 2010, he told ABC News' Diane Sawyer that that Facebook would “definitely thinkThere are some times when clicking “like” on a friend's Facebook status doesn't feel appropriate. A bad day. A loved one lost. A break up. It only seems natural that a “dislike” button could solve the conundrum of wanting to empathize but not seem inappropriate by clicking “like.” Mark Zuckerberg Puts the Rest of Us to Shame by Speaking Fluent Chinese. Mark Zuckerberg: Facebook Founder and Animal Butcher. Mark Zuckerberg and That Shirt. The idea has been on Mark Zuckerberg's radar for a while, he said. In 2010, he told ABC News' Diane Sawyer that that Facebook would “definitely thinkhen clicking “like” on a friend's Facebook status doesn't feel appropriate. A bad day. A loved one lost. A break up. It only seems natural that a “dislike” button could solve the conundrum of wanting to empathize but not seem inappropriate by clicking “like.” Mark Zuckerberg Puts the Rest of Us to Shame by Speaking Fluent Chinese. Mark Zuckerberg: Facebook Founder and Animal Butcher. Mark Zuckerberg and That Shirt. The idea has been on Mark Zuckerberg's radar for a while, he said. In 2010, he told ABC News' Diane Sawyer There are some times when clicking “like” on a friend's Facebook status doesn't feel appropriate. A bad day. A loved one lost. A break up. It only seems natural that a “dislike” button could solve the conundrum of wanting to empathize but not seem inappropriate by clicking “like.” Mark Zuckerberg Puts the Rest of Us to Shame by Speaking Fluent Chinese. Mark Zuckerberg: Facebook Founder and Animal Butcher. Mark Zuckerberg and That Shirt. The idea has been on Mark Zuckerberg's radar for a while, he said. In 2010, he told ABC News' Diane Sawyer that that Facebook would “definitely thinkThere are some times when clicking “like” on a friend's Facebook status doesn't feel appropriate. A bad day. A loved one lost. A break up. It only seems natural that a “dislike” button could solve the conundrum of wanting to empathize but not seem inappropriate by clicking “like.” Mark Zuckerberg Puts the Rest of Us to Shame by Speaking Fluent Chinese. Mark Zuckerberg: Facebook Founder and Animal Butcher. Mark Zuckerberg and That Shirt. The idea has been on Mark Zuckerberg's radar for a while, he said. In 2010, he told ABC News' Diane Sawyer that that Facebook would “definitely thinkThere are some times when clicking “like” on a friend's Facebook status doesn't feel appropriate. A bad day. A loved one lost. A break up. It only seems natural that a “dislike” button could solve the conundrum of wanting to empathize but not seem inappropriate by clicking “like.” Mark Zuckerberg Puts the Rest of Us to Shame by Speaking Fluent Chinese. Mark Zuckerberg: Facebook Founder and Animal Butcher. Mark Zuckerberg and That Shirt. The idea has been on Mark Zuckerberg's radar for a while, he said. In 2010, he told ABC News' Diane Sawyer that that Facebook would “definitely thinkThere are some times when clicking “like” on a friend's Facebook status doesn't feel appropriate. A bad day. A loved one lost. A break up. It only seems natural that a “dislike” button could solve the conundrum of wanting to empathize but not seem inappropriate by clicking “like.” Mark Zuckerberg Puts the Rest of Us to Shame by Speaking Fluent Chinese. Mark Zuckerberg: Facebook Founder and Animal Butcher. Mark Zuckerberg and That Shirt. The idea has been on Mark Zuckerberg's radar for a while, he said. In 2010, he told ABC News' Diane Sawyer that that Facebook would “definitely think that that Facebook would “definitely think about” adding a dislike button. “People definitely seem to want it,” Zuckerberg said. Four years later — Zuckerberg says Facebook is still “thinking about” adding the oft-requested sdfafd button, Zuckerberg says Facebook is still “thinking about” adding the oft-requested button. At a town hall meeting on Thursday, the CEO revealed he has some reservations about the feature. “There are two things that it can mean,” Zuckerberg said of the potential button, which could be used in a mean spirited way or to express empathy. Finding how to limit it to the latter is the challenge. Zuckerberg said he doesn't want the button to turn into a “voting mechanism” or something that isn't “socially valuable.” “Often people will tell us they don't feel comfortable pressing ‘like,'” Zuckerberg said. “What's the right way to make it so people can easier express a wide range of emotions&#63;” One suggestion percolating online: Aaron Roll out the feature under a different name. However, an “empathy button” just may not have the same ring to it as “dislike.”";
 var searchStr = "adding the oft-requested sdf";



 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.body.appendChild(div);
 }

 show('BF_Ordinary',function() {
  return BF_Ordinary(sourceStr, searchStr)
 })

 show('BF_Optimize_1',function() {
  return BF_Optimize_1(sourceStr, searchStr)
 })

 show('BF_Optimize_2',function() {
  return BF_Optimize_2(sourceStr, searchStr)
 })

 show('BF_Recursive',function() {
  return BF_Recursive(sourceStr, searchStr)
 })

</script>

ログイン後にコピー

git コードのダウンロード:

https://github.com/JsAaron/data_structor