JavaScript中數據結構與算法(四)：串(BF)

更新時間：2015年06月19日 09:39:59 投稿：junjie

這篇文章主要介紹了JavaScript中數據結構與算法(四)：串(BF),串是由零個或多個字符組成的有限序列,又叫做字符串,本文著重講解了BF(Brute Force)算法,需要的朋友可以參考下

串是由零個或多個字符組成的有限序列，又叫做字符串

串的邏輯結構和線性表很相似的，不同的是串針對是是字符集，所以在操作上與線性表還是有很大區(qū)別的。線性表更關注的是單個元素的操作CURD，串則是關注查找子串的位置，替換等操作。

當然不同的高級語言對串的基本操作都有不同的定義方法，但是總的來說操作的本質都是相似的。比如javascrript查找就是indexOf, 去空白就是trim,轉化大小寫toLowerCase/toUpperCase等等

這里主要討論下字符串模式匹配的幾種經典的算法：BF、BM、KMP

BF(Brute Force)算法

Brute-Force算法的基本思想：

從目標串s 的第一個字符起和模式串t的第一個字符進行比較，若相等，則繼續(xù)逐個比較后續(xù)字符，否則從串s 的第二個字符起再重新和串t進行比較。

依此類推，直至串t 中的每個字符依次和串s的一個連續(xù)的字符序列相等，則稱模式匹配成功，此時串t的第一個字符在串s 中的位置就是t 在s中的位置，否則模式匹配不成功

可見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; //循環(huán)的次數
 //BBC ABB ABCF =>ABC => 搜索9次
 for (var i = 0; i <= padding; i++) {
  //如果滿足了第一個charAt是相等的
  //開始子循環(huán)檢測
  //其中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：最外圍循環(huán)的次數sourceLength - searchLength，因為我們匹配的母串至少要大于等于子串

2：在子串的繼續(xù)匹配中，母串的起點是需要疊加的(i+j)

3：通過一個條件判斷是否完全匹配complete，BBC ABB ABCF中，我們在ABB的時候就需要跳過去

上面是最簡單的一個算法了，代碼上還有更優(yōu)的處理，比如在自串的匹配上可以采取取反的算法

優(yōu)化算法（一）

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

我們不需要判斷為真的情況，我們只要判斷為假的情況就可以了，當子匹配結束后match沒有被修改過的話，則說明此匹配是完全匹配

以上2種方法我們都用到了子循環(huán)，我們能否改成一個循環(huán)體呢？

其實我們可以看到規(guī)律，主串每次都只會遞增+1，子串每次匹配也是從頭開始匹配，所以我們可以改成一個while，控制下標指針就可以了

優(yōu)化算法（二）

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

  while (i < sourceStr.length) {
    // 兩字母相等則繼續(xù) 
    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;
    }

  }
}

i就是主串的下標定位，j就是子串的下標定位

當主串子串相等的時候，就進入了子串的循環(huán)模式，當子循環(huán)的次數j滿足子串長度時，就驗證是完全匹配

當主串子串不相等的時候，就需要把主串的下標往后移一位，當然i的時候，因為可能經過子串的處理，所以需要i-j+1, 然后復位子串

具體我們可以看看代碼比較

基于BF算法的四種結構,for/while/遞歸

<!doctype html>由于電腦性能的不斷提高，測試的數據量的大小，可能會導致得到的結果不太準確;<script type="text/javascript">

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

  //BBC ABB ABCF =>ABC => 搜索9次
  for (var i = 0; i <= padding; i++) {
   //如果滿足了第一個charAt是相等的
   //開始子循環(huán)檢測
   //其中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;
 }


 /////////
 //暴力算法 //
 //優(yōu)化版
 /////////
 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;
 }


  ////////
  //優(yōu)化版 //
  //while
  ////////
 function BF_Optimize_2(sourceStr, searchStr) {
  var i = 0,
    j = 0;

   while (i < sourceStr.length) {
     // 兩字母相等則繼續(xù) 
     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 “l(fā)ike” 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 “l(fā)ike.” 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 “l(fā)ike” 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 “l(fā)ike.” 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 “l(fā)ike” 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 “l(fā)ike.” 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 “l(fā)ike” 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 “l(fā)ike.” 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 “l(fā)ike” 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 “l(fā)ike.” 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 “l(fā)ike” 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 “l(fā)ike.” 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 “l(fā)ike” 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 “l(fā)ike.” 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 “l(fā)ike” 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 “l(fā)ike.” 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 “l(fā)ike” 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 “l(fā)ike.” 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 “l(fā)ike” 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 “l(fā)ike.” 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 “l(fā)ike” 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 “l(fā)ike.” 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?” 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>

BF也是經典的前綴匹配算法，前綴還包括KMP，我們可見這種算法最大缺點就是字符匹配失敗指針就要回溯，所以性能很低，之后會寫一下KMP與BM算法針對BF的的升級

git代碼下載: https://github.com/JsAaron/data_structure

您可能感興趣的文章: