JavaScript의 데이터 구조 및 알고리즘(4): String(BF)_javascript 기술
- WBOY원래의
- 2016-05-16 15:54:101554검색
문자열은 0개 이상의 문자로 구성된 유한한 시퀀스이며 문자열이라고도 합니다.
문자열의 논리적 구조는 선형 테이블과 매우 유사합니다. 차이점은 문자열이 문자 집합이므로 동작이 선형 테이블과 상당히 다르다는 것입니다. 선형 테이블은 단일 요소의 CURD 작업에 더 중점을 두는 반면, 문자열은 하위 문자열의 위치를 찾고 교체하는 등의 작업에 중점을 둡니다.
물론 고급 언어마다 기본 문자열 연산에 대한 정의가 다르지만 일반적으로 연산의 본질은 유사합니다. 예를 들어 자바스크립트 검색은 indexOf, 공백 제거는 Trim, 대소문자 변환은 LowerCase/toUpperCase 등입니다.
여기에서는 문자열 패턴 일치를 위한 몇 가지 기본 알고리즘인 BF, BM, KMP에 대해 주로 논의합니다
BF(Brute Force) 알고리즘
Brute-Force 알고리즘의 기본 개념:
대상 문자열 s의 첫 번째 문자를 패턴 문자열 t의 첫 번째 문자와 비교합니다. 동일하면 계속해서 다음 문자를 하나씩 비교합니다. 그렇지 않으면 문자열 s의 두 번째 문자부터 시작하여 다시 시작합니다. 문자열 t를 비교합니다.
등, 문자열 t의 각 문자가 문자열 s의 연속된 문자 시퀀스와 동일할 때까지 패턴 매칭이 성공했다고 합니다. 이때 문자열 s에서 문자열 t의 첫 번째 문자 위치는 다음과 같습니다. s의 t 위치, 그렇지 않으면 패턴 일치가 실패합니다
BF 알고리즘은 순진한 일치 알고리즘 또는 무차별 알고리즘이라고도 알려진 무차별 알고리즘임을 알 수 있습니다.
주요 문자열 BBC ABB ABCF
하위 문자열 ABC
메인 문자열에서 하위 문자열의 위치를 찾는 것은 자바스크립트의 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; //循环的次数
//BBC ABB ABCF =>ABC => 搜索9次
for (var i = 0; i <= padding; i++) {
//如果满足了第一个charAt是相等的
//开始子循环检测
//其中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: 가장 바깥쪽 루프 sourceLength - searchLength의 횟수. 일치하는 상위 문자열은 적어도 하위 문자열보다 크거나 같아야 하기 때문입니다.
2: 부분 문자열의 지속적인 일치에서 상위 문자열의 시작점을 겹쳐야 합니다(i j)
3: 조건을 통해 완전 일치 여부를 확인합니다. BBC ABB ABCF에서는 ABB에 있을 때 뛰어넘어야 합니다.
위의 알고리즘은 가장 간단한 알고리즘이며 코드에 더 나은 처리 방법이 있습니다. 예를 들어 반전 알고리즘을 사용하여 자체 문자열을 일치시킬 수 있습니다.
최적화 알고리즘(1)
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;
}
상황을 사실이라고 판단할 필요는 없고, 서브 매치가 완료된 후 매치가 수정되지 않으면 매치가 완전 매치라는 의미입니다.
위 두 가지 방법으로 하위 루프를 사용했는데, 루프 본문으로 변경할 수 있나요?
실제로 패턴을 보면 메인 문자열은 매번 1씩만 증가하고 하위 문자열은 매번 처음부터 일치하므로 잠시 동안 변경하여 첨자 포인터를 제어할 수 있습니다. 🎜>
최적화 알고리즘(2)
function BF_Optimize_2(sourceStr, searchStr) {
var i = 0,
j = 0;
while (i < sourceStr.length) {
// 两字母相等则继续
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;
}
}
}
메인 문자열과 하위 문자열이 같으면 하위 문자열의 루프 모드로 진입합니다. 하위 루프 수 j가 하위 문자열의 길이를 만족하면 완전히 일치하는지 확인합니다
주 문자열과 하위 문자열이 같지 않은 경우에는 주 문자열의 첨자를 한 비트 뒤로 이동해야 합니다. 물론 i를 사용할 경우 하위 문자열로 처리될 수도 있으므로 i-j 1이 필요합니다. 그런 다음 하위 문자열이 재설정됩니다
자세한 내용은 코드 비교를 참조하세요
BF 알고리즘 기반의 4가지 구조, for/while/recursion
<!doctype html>由于电脑性能的不断提高，测试的数据量的大小，可能会导致得到的结果不太准确;<script type="text/javascript">
/////////
//暴力算法 //
//普通版
/////////
function BF_Ordinary(sourceStr, searchStr) {
var sourceLength = sourceStr.length;
var searchLength = searchStr.length;
var padding = sourceLength - searchLength; //循环的次数
//BBC ABB ABCF =>ABC => 搜索9次
for (var i = 0; i <= padding; i++) {
//如果满足了第一个charAt是相等的
//开始子循环检测
//其中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;
}
/////////
//暴力算法 //
//优化版
/////////
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;
}
////////
//优化版 //
//while
////////
function BF_Optimize_2(sourceStr, searchStr) {
var i = 0,
j = 0;
while (i < sourceStr.length) {
// 两字母相等则继续
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 “like” 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 “like.” 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 “like” 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 “like.” 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 “like” 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 “like.” 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 “like” 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 “like.” 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 “like” 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 “like.” 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 “like” 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 “like.” 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 “like” 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 “like.” 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 “like” 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 “like.” 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 “like” 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 “like.” 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 “like” 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 “like.” 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 “like” 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 “like.” 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>
git 코드 다운로드:
성명：
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.