亲宝软件园·资讯

展开

JavaScript中数据结构与算法(五):经典KMP算法

人气:2

KMP算法和BM算法

KMP是前缀匹配和BM后缀匹配的经典算法,看得出来前缀匹配和后缀匹配的区别就仅仅在于比较的顺序不同

前缀匹配是指:模式串和母串的比较从左到右,模式串的移动也是从 左到右

后缀匹配是指:模式串和母串的的比较从右到左,模式串的移动从左到右。

通过上一章显而易见BF算法也是属于前缀的算法,不过就非常霸蛮的逐个匹配的效率自然不用提了O(mn),网上蛋疼的KMP是讲解很多,基本都是走的高大上路线看的你也是一头雾水,我试图用自己的理解用最接地气的方式描述

KMP

KMP也是一种优化版的前缀算法,之所以叫KMP就是Knuth、Morris、Pratt三个人名的缩写,对比下BF那么KMP的算法的优化点就在“每次往后移动的距离”它会动态的调整每次模式串的移动距离,BF是每次都+1,

KMP则不一定

如图BF与KMP前置算法的区别对比

我通过图对比我们发现:

在文本串T中搜索模式串P,在自然匹配第6个字母c的时候发现二等不一致了,那么BF的方法,就是把整个模式串P移动一位,KMP则是移动二位.

BF的匹配方法我们是知道的,但是KMP为什么会移动二位,而不是一位或者三位四位呢?

这就上一张图我们讲解下,模式串P在匹配了ababa的时候都是正确的,当到c的时候才是错误,那么KMP算法的想法是:ababa是正确的匹配完成的信息,我们能不能利用这个信息,不要把"搜索位置"移回已经比较过的位置,继续把它向后移,这样就提高了效率。

那么问题来了, 我怎么知道要移动多少个位置?

这个偏移的算法KMP的作者们就给我们总结好了:

复制代码 代码如下:

移动位数 = 已匹配的字符数 - 对应的部分匹配值

偏移算法只跟子串有关系,没文本串没毛线关系,所以这里需要特别注意了

那么我们怎么理解子串中已匹配的字符数与对应的部分匹配值?

已匹配的字符:

复制代码 代码如下:

T : abababaabab
p : ababacb

p中红色的标记就是已经匹配的字符,这个很好理解

部分匹配值:

这个就是核心的算法了,也是比较难于理解的

假如:

复制代码 代码如下:

T:aaronaabbcc
P:aaronaac

我们可以观察这个文本如果我们在匹配c的时候出错,我们下一个移动的位置就上个的结构来讲,移动到那里最合理?
复制代码 代码如下:

aaronaabbcc
     aaronaac

那么就是说:在模式文本内部,某一段字符头尾都一样,那么自然过滤的时候可以跳过这一段内容了,这个思路也是合理的

 

知道了这个规律,那么给出来的部分匹配表算法如下:

首先,要了解两个概念:"前缀"和"后缀"。 "前缀"指除了最后一个字符以外,一个字符串的全部头部组合;"后缀"指除了第一个字符以外,一个字符串的全部尾部组合。

"部分匹配值"就是"前缀"和"后缀"的最长的共有元素的长度”

我们看看aaronaac的如果是BF匹配的时候划分是这样的

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

aaron      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.lenght = 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实现(一):缓存匹配表的KMP

KMP实现(二):动态计算next的KMP


KMP实现(一)

匹配表

KMP算法中最重要的就是匹配表,如果不要匹配表那就是BF的实现,加上匹配表就是KMP了

匹配表决定了next下一个位移的计数

针对上面匹配表的规律,我们设计一个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中的匹配表的算法的实现,通过str.substring(0, i + 1) 分解a->aa->aar->aaro->aaron->aarona->aaronaa-aaronaac

然后在每一个分解中通过前缀后缀算出共有元素的长度

回退算法

KMP也是前置算法,完全可以把BF那一套搬过来,唯一修改的地方就是BF回溯的时候直接是加1,KMP在回溯的时候我们就通过匹配表算出这个next值即可

//子循环
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/JsAaronhttps://img.qb5200.com/download-x/data_structure

加载全部内容

相关教程
猜你喜欢
用户评论