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의 작성자는 이를 요약했습니다.
일치하는 문자:
부분 일치 값:
이것이 핵심 알고리즘인데, 이해하기도 어렵습니다만약:
즉, 패턴 텍스트 내에서 특정 문자 단락의 시작과 끝이 동일하면 자연 필터링 중에 해당 단락을 건너뛸 수 있습니다.
이 규칙을 알면 주어진 부분 일치 테이블 알고리즘은 다음과 같습니다.
먼저 "접두사"와 "접미사"라는 두 가지 개념을 이해해야 합니다. "접두사"는 마지막 문자를 제외한 문자열의 모든 머리 조합을 나타내고 "접미사"는 첫 번째 문자를 제외한 문자열의 모든 꼬리 조합을 나타냅니다.
"부분 일치 값"은 "접두사"와 "접미사" 사이의 가장 긴 공통 요소의 길이입니다."
BF전이라면 아로나크의 디비전을 살펴보겠습니다
BF의 변위: a,aa,aar,aaro,aaron,aarona,aaronaa,aaronaac
그렇다면 KMP의 부서는 어떨까요? 여기서 접두사와 접미사를 소개해야 합니다
먼저 KMP 부분 매칭 테이블의 결과를 살펴보겠습니다.
확실히 헷갈리는데 걱정하지 마세요, 접두사, 접미사로 풀어보겠습니다
부분 매칭 테이블 분해
KMP의 일치 테이블 알고리즘, 여기서 p는 접두사, n은 접미사, r은 결과를 나타냅니다.
aa, p=>[a], n=>[a], r = a.length =>
aar, p=>[a,aa], n=>[r,ar] ,r = 0aaro, 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
그래서 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 알고리즘 완성
<!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>
![[웹 프런트엔드] Node.js 빠른 시작](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
