보이어-무어-호스풀 알고리즘
Boyer–Moore– |
컴퓨터 과학 분야에서는 보이어-무어-Horspool 알고리즘 또는 Horspool의 알고리즘은 문자열에서 서브스트링을 찾기 위한 알고리즘이다.Nigel Horspool에 의해 1980년에 SBM으로 출판되었다.[1]
Knuth-Morris-Pratt 알고리즘과 관련된 Boyer-Moore 문자열 검색 알고리즘을 단순화한 것이다.알고리즘은 패턴의 길이가 m이고 검색 문자열의 길이가 n인 최악의 경우 O(nm)가 있지만 랜덤 텍스트에서 O(n)의 평균 사례 복잡성을 얻기 위해 시간 동안 공간을 거래한다.
설명
보이어-무어, 보이어-무어처럼-호스풀은 알파벳의 각 기호에 대해 안전하게 건너뛸 수 있는 문자 수를 포함하는 표를 만들기 위해 패턴을 미리 처리한다.사전 처리 단계(가명 코드)는 다음과 같다(256 기호, 즉 바이트의 경우).
원래와 달리 여기서는 제로 기반 지수를 사용한다.함수 preprocess(패턴) T ← 0 ~ 256 배타적 T[i] ← 길이(패턴) - 1 배타적 T[i] ← 길이(패턴) - 1 - i return T
패턴 검색은 다음과 같이 진행된다.절차검색 결과 건초더미에서 바늘이 처음 발생하는 지수를 보고한다.
함수 same(str1, str2, len) 첫 번째 렌 문자까지 두 문자열을 비교하십시오.i ← len - 1 while str1[i] = str2[i] 참고: 이것은 !memmp(str1, str2, len)과 동일하다.i = 0 원본 알고리즘이 여기서 스마트하게 재생하려고 시도함: 반환 참 마지막 문자를 확인한 다음 첫 번째 문자부터 두 번째 문자까지 시작함.i ← i - 1 return false function search(needle, 건초 스택) T prep preprocess(needle) while(헤이 스택) 동안 0 ← 생략 - ≥ 길이(needle) 건초 더미[skip:] --subring "skip"으로 시작하는 하위 문자열. &haystack[skip] in C. (Haystack[skip:], 바늘, 길이(needle)) 반환 스킵 스킵 + T[Haystack[skip + 길이(needle) - 1] 반환 불가
퍼포먼스
알고리즘은 긴 바늘 문자열로 가장 잘 작동하는데, 건초더미에서 현재 위치의 최종 바이트 또는 그 근처에 비매칭 문자를 일관되게 치고 바늘의 최종 바이트는 바늘 내의 다른 곳에서 발생하지 않는다.예를 들어, 'z' 바이트가 없는 255바이트 건초 더미를 통해 검색하는 "z"로 끝나는 32바이트 바늘은 최대 224바이트 비교가 필요하다.
가장 좋은 경우는 Boyer-Moore 문자열 검색 알고리즘의 경우 초기화와 각 루프의 지속적인 오버헤드는 작지만 큰 O 표기법과 동일하다.
최악의 경우, 나쁜 문자 스킵이 지속적으로 낮을 때(하한은 1바이트 이동으로), 바늘의 많은 부분이 건초더미와 일치할 때 발생한다.나쁜 문자 스킵은 부분 일치에서 바늘의 최종 문자 또한 바늘 내의 다른 곳에서 발생할 때 낮을 뿐이며, 동일한 바이트가 마지막 두 위치 모두에 있을 때 1바이트 이동이 일어난다.
위의 "최상의" 사례와 유사한 표준적인 퇴행형 케이스는 255 'z' 바이트로 구성된 건초더미에서 31 'z' 바이트가 이어지는 'a' 바이트의 바늘이다.이것은 31개의 성공적인 바이트 비교, 실패 후 1바이트 앞으로 이동하는 1바이트 비교를 할 것이다.이 과정은 223회(255 - 32회)를 더 반복하여 총 바이트 비교가 7,168회(32 × 224)로 된다. (다른 바이트 비교 루프는 다른 동작을 가질 것이다.
최악의 경우는 보이어-무어 문자열 검색 알고리즘보다 훨씬 높지만, 이는 분명히 정상적인 사용 사례에서는 달성하기 어렵다.이 최악의 경우 역시 순진무구한(그러나 평상시)에게는 최악의 경우라는 점도 주목할 필요가 있다.memcmp()알고리즘, 비록 구현이 상당히 최적화되는 경향이 있지만(그리고 캐시 친화적이다).
비교 루프 조정
원래의 알고리즘은 더 정교한 () 루프를 가지고 있었다.긍정적인 방향으로 진행하기 전에 추가 사전 점검을 사용한다.[1]
함수 same_origin(str1, str2, len) i str str[len] = str2[len - 1]인 경우 str1[i] = str2[i] = len - 2 return true i i i + 1 return false
BMH 알고리즘의 튜닝된 버전은 Raita 알고리즘이다.이것은 마지막 첫 번째 중간 순서로 중간 캐릭터에 대한 사전 확인을 추가한다.알고리즘은 체크가 통과할 때만 전체 루프를 입력한다.[2]
함수 same_raita(str1, str2, len) i ← 0 mid len len / 2 3 prechecks. i len if 3 if str[mid] != str[0]!= str2[mid] len if 2가 false를 반환하면 false를 반환한다. 오래된 비교 루프.리턴 렌 < 3 또는 SEAST(&str1[1], &str2[1], 렌 - 2)
이 1992년 튜닝이 여전히 현대 기계에서 그것의 성능 우위를 유지하고 있는지는 불분명하다.저자들의 근거는 실제 텍스트는 대개 이 세 문자에 의해 효과적으로 사전 필터링될 수 있는 몇몇 패턴을 포함하고 있다는 것이다.라이타는 옛 마지막 글자의 사전점검(뒤쳐지는 일상이 호스풀 시행이라고 믿었던 것)을 모르고 있는 것 같아 독자들에게는 그 결과를 뼈저리게 받아들이라고 충고한다.[2]
현대의 기계에서, memcmp와 같은 라이브러리 기능은 손으로 작성한 비교 루프보다 더 나은 처리량을 제공하는 경향이 있다.libstdc++와 libc++ 모두 "SFC" 루프(Horspool의 용어)의 동작은 현대의 Raita 구현에는 데이터 정렬에 해로운 영향을 미치기 때문에 단문자 교대조도 포함해서는 안 된다는 것을 시사하는 것 같다.[3][4]다른 문자열 검색 알고리즘에 대한 자세한 분석이 있는 문자열 검색 알고리즘도 참조하십시오.
참조
- ^ a b Horspool, R. N. (1980). "Practical fast searching in strings". Software: Practice and Experience. 10 (6): 501–506. CiteSeerX 10.1.1.63.3421. doi:10.1002/spe.4380100608. S2CID 6618295.
- ^ a b Raita, Timo (1992). "Tuning the boyer-moore-horspool string searching algorithm". Software: Practice and Experience. 22 (10): 879–884. doi:10.1002/spe.4380221006. S2CID 14193323.
- ^ "⚙ D27068 Improve string::find". LLVM Code Review.
- ^ "[PATCH] improve string find algorithm". GCC.
