JavaScript의 데이터 구조 및 알고리즘(5): 클래식 KMP 알고리즘_javascript 기술

KMP 알고리즘과 BM 알고리즘

KMP는 접두사 일치와 BM 접미사 일치에 대한 고전적인 알고리즘으로 접두사 일치와 접미사 일치의 차이는 비교 순서에만 있음을 알 수 있습니다

접두사 일치 의미: 패턴 문자열과 상위 문자열의 비교는 왼쪽에서 오른쪽으로 이루어지며, 패턴 문자열의 이동도 왼쪽에서 오른쪽으로 이루어집니다

접미사 일치를 의미합니다. 패턴 문자열과 상위 문자열의 비교는 오른쪽에서 왼쪽으로 이루어지며, 패턴 문자열의 이동은 왼쪽에서 오른쪽으로 이루어집니다.

이전 장을 통해 BF 알고리즘도 접두사 알고리즘임이 분명하지만 일대일 매칭의 효율성은 매우 오만합니다. 당연히 O(는 언급할 필요가 없습니다. mn). 온라인에서 짜증나는 KMP는 기본적으로 높은 수준의 경로를 취하고 있으며 가장 현실적인 방법으로 설명하려고 노력했습니다. >

KMP

KMP도 접두사 알고리즘의 최적화된 버전입니다. KMP라고 불리는 이유는 Knuth, Morris, Pratt 세 이름의 약어입니다. BF와 비교할 때 KMP 알고리즘의 최적화 포인트는 "the"입니다. 각 후진 이동 거리" 각 패턴 문자열의 이동 거리를 동적으로 조정합니다. BF는 매번 1입니다.

꼭 KMP일 필요는 없습니다

그림과 같이 BF와 KMP 사전 알고리즘의 차이점을 비교합니다

사진을 비교해 보니 다음과 같습니다.

텍스트 문자열 T에서 패턴 문자열 P를 검색합니다. 여섯 번째 문자 c와 자연스럽게 일치하면 두 번째 수준이 일치하지 않음을 발견합니다. 그러면 BF 방법은 전체 패턴 문자열 P를 한 자리 이동하는 것입니다. 그리고 KMP는 두 곳씩 옮기는 것입니다.

우리는 BF의 매칭 방식을 알고 있는데 왜 KMP는 한 자리, 세 자리, 네 자리가 아닌 두 자리를 이동하는 걸까요?

이전 그림을 설명하자면, 패턴 문자열 P는 ababa와 일치하면 정확하고, c와 일치하면 틀리게 됩니다. 그러면 KMP 알고리즘의 아이디어는 다음과 같습니다. 우리는 이 정보를 사용하여 "검색 위치"를 비교된 위치로 다시 이동하는 것이 아니라 계속해서 뒤로 이동하므로 효율성이 향상됩니다.

그럼 질문은 이동해야 할 직위가 몇 개인지 어떻게 알 수 있느냐는 것입니다.

이 오프셋 알고리즘 KMP의 작성자는 이를 요약했습니다.

코드 복사 코드는 다음과 같습니다.

자리 이동 = 일치하는 문자 수 - 해당 부분 일치 값

오프셋 알고리즘은 텍스트 문자열이 아닌 하위 문자열에만 관련되므로 여기서는 특별한 주의가 필요합니다
그렇다면 하위 문자열에서 일치하는 문자 수와 해당 부분 일치 값을 어떻게 이해할 수 있을까요?

일치하는 문자:

코드 복사 코드는 다음과 같습니다.

T : 아바바바바밥
p :아바백

p의 빨간색 표시는 일치하는 문자이므로 이해하기 쉽습니다

부분 일치 값:

이것이 핵심 알고리즘인데, 이해하기도 어렵습니다

만약:

코드 복사 코드는 다음과 같습니다.

T：aaronaabbcc
P：아로나크

이 텍스트를 관찰하면 c를 일치시킬 때 오류가 발생하면 이전 구조를 기반으로 다음 이동이 어디에 있을까요?

코드 복사 코드는 다음과 같습니다.

aaronaabbcc
아로나악

즉, 패턴 텍스트 내에서 특정 문자 단락의 시작과 끝이 동일하면 자연 필터링 중에 해당 단락을 건너뛸 수 있습니다.

이 규칙을 알면 주어진 부분 일치 테이블 알고리즘은 다음과 같습니다.

먼저 "접두사"와 "접미사"라는 두 가지 개념을 이해해야 합니다. "접두사"는 마지막 문자를 제외한 문자열의 모든 머리 조합을 나타내고 "접미사"는 첫 번째 문자를 제외한 문자열의 모든 꼬리 조합을 나타냅니다.

"부분 일치 값"은 "접두사"와 "접미사" 사이의 가장 긴 공통 요소의 길이입니다."

BF전이라면 아로나크의 디비전을 살펴보겠습니다

BF의 변위: a,aa,aar,aaro,aaron,aarona,aaronaa,aaronaac

그렇다면 KMP의 부서는 어떨까요? 여기서 접두사와 접미사를 소개해야 합니다

먼저 KMP 부분 매칭 테이블의 결과를 살펴보겠습니다.

코드 복사 코드는 다음과 같습니다.

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

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.길이) = 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, i 1) aaronaa-aaronaac

그런 다음 각 분해에서 접두사와 접미사를 통해 공통 요소의 길이를 계산합니다

백오프 알고리즘

KMP도 BF를 완전히 전송할 수 있습니다. 유일한 수정 사항은 KMP가 역추적할 때 BF가 직접 1을 추가한다는 것입니다.

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