快捷導(dǎo)航

JavaScript中數(shù)據(jù)結(jié)構(gòu)與算法(四)：串(BF)

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

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

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

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

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

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

BF(Brute Force)算法

Brute-Force算法的基本思想：

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

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

可見BF算法是一種暴力算法，又稱為樸素匹配算法或蠻力算法。

主串 BBC ABB ABCF

子串 ABC

在主串中找出子串的位置，對(duì)應(yīng)了其實(shí)就是javascript的indexOf查找方法的實(shí)現(xiàn)了

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)的次數(shù)
 //BBC ABB ABCF =>ABC => 搜索9次
 for (var i = 0; i <= padding; i++) {
  //如果滿足了第一個(gè)charAt是相等的
  //開始子循環(huán)檢測
  //其中sourceStr的取值是需要疊加i的值
  if (sourceStr.charAt(i) == searchStr.charAt(0)) {
   //匹配成功的數(shù)據(jù)
   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母串的每一個(gè)字符的下表取出來與模式串的第一個(gè)字符匹配，如果相等就進(jìn)去字串的再次匹配

這里值得注意：

1：最外圍循環(huán)的次數(shù)sourceLength - searchLength，因?yàn)槲覀兤ヅ涞哪复辽僖笥诘扔谧哟?/p>

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

3：通過一個(gè)條件判斷是否完全匹配complete，BBC ABB ABCF中，我們?cè)贏BB的時(shí)候就需要跳過去

上面是最簡單的一個(gè)算法了，代碼上還有更優(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;
}

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

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

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

優(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 { // 兩字母不等則角標(biāo)后退重新開始匹配 
     i = i - j + 1; // i 回退到上次匹配首位的下一位 
     j = 0; // j 回退到子串的首位 
    }

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

  }
}

i就是主串的下標(biāo)定位，j就是子串的下標(biāo)定位

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

當(dāng)主串子串不相等的時(shí)候，就需要把主串的下標(biāo)往后移一位，當(dāng)然i的時(shí)候，因?yàn)榭赡芙?jīng)過子串的處理，所以需要i-j+1, 然后復(fù)位子串

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

基于BF算法的四種結(jié)構(gòu),for/while/遞歸

<!doctype html>由于電腦性能的不斷提高，測試的數(shù)據(jù)量的大小，可能會(huì)導(dǎo)致得到的結(jié)果不太準(zhǔn)確;<script type="text/javascript">

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

  //BBC ABB ABCF =>ABC => 搜索9次
  for (var i = 0; i <= padding; i++) {
   //如果滿足了第一個(gè)charAt是相等的
   //開始子循環(huán)檢測
   //其中sourceStr的取值是需要疊加i的值
   if (sourceStr.charAt(i) == searchStr.charAt(0)) {
    //匹配成功的數(shù)據(jù)
    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 { // 兩字母不等則角標(biāo)后退重新開始匹配 
      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 + ",耗時(shí)" + (+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也是經(jīng)典的前綴匹配算法，前綴還包括KMP，我們可見這種算法最大缺點(diǎn)就是字符匹配失敗指針就要回溯，所以性能很低，之后會(huì)寫一下KMP與BM算法針對(duì)BF的的升級(jí)

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

您可能感興趣的文章: