보이어-무어 문자열 검색 알고리즘

컴퓨터 과학에서 보이어-모어 문자열 검색 알고리즘은 실용적인 문자열 검색 문헌의 표준 벤치마크인 효율적인 문자열 검색 알고리즘이다.^[1]그것은 로버트 S에 의해 개발되었다. 보이어와 J 스트로터 무어는 1977년에 태어났다.^[2]원본 논문에는 패턴 이동을 어떻게 생산해야 하는지에 대한 설명 없이 패턴 이동을 계산하기 위한 정적 표가 수록되어 있었다.표 제작 알고리즘은 후속 논문으로 발표되었다. 이 논문은 1980년에 Wojciech Rytter에 의해 수정된 오류를 포함하고 있다.^[3][4]알고리즘은 검색되는 문자열(패턴)을 사전 처리하지만 검색되는 문자열(텍스트)은 사전 처리하지 않는다.따라서 텍스트보다 패턴이 훨씬 짧거나 여러 검색에서 패턴이 지속되는 애플리케이션에 적합하다.Boyer-Moore 알고리즘은 사전 처리 단계에서 수집된 정보를 사용하여 텍스트의 섹션을 건너뛰어 다른 많은 문자열 검색 알고리즘보다 상수 인자가 낮다.일반적으로 알고리즘은 패턴 길이가 증가할수록 더 빨리 실행된다.알고리즘의 핵심 특징은 머리보다는 패턴의 꼬리에 매치하고, 텍스트의 모든 문자를 검색하기보다는 여러 문자의 점프에서 텍스트를 따라 건너뛰는 것이다.

정의들

• T는 검색할 입력 텍스트를 나타낸다.그것의 길이는 n이다.
• P는 검색할 문자열을 나타내며, 패턴이라고 한다.그것의 길이는 m이다.
• S[i]는 문자열 S의 index i에 있는 문자를 나타내며 1부터 계산한다.
• S[i..j]는 인덱스 i에서 시작하여 j에서 끝나는 문자열 S의 하위 문자열을 의미한다.
• S의 접두사는 [1, l] 범위의 일부 i에 대한 하위 문자열 S[1..i]이며, 여기서 l은 S의 길이입니다.
• S의 접미사는 [1, l] 범위의 일부 i에 대한 하위 문자열 S[i..l]이며, 여기서 l은 S의 길이입니다.
• P 대 T의 정렬은 P의 마지막 문자가 T의 인덱스 k와 정렬되도록 T의 인덱스 k이다.
• P가 T[(k-m+1)와 같으면 정렬 k에서 P가 일치하거나 발생한다.k.

설명

Boyer-Moore 알고리즘은 다른 선형에서 명시적 문자 비교를 수행하여 T에서 P 발생을 검색한다.Boyer-Moore는 모든 $선형{\displaystyle (m}$ - n${\displaystyle }$+ ${\displaystyle 1}$(\$displaystyle m-n+1})$에 대한 강제 검색 대신 P를 사전 처리하여 얻은 정보를 사용하여 가능한 많은 선형을 생략한다.$$

이 알고리즘의 도입 이전에, 텍스트 내에서 검색하는 일반적인 방법은 패턴의 첫 번째 문자에 대해 텍스트의 각 문자를 검사하는 것이었다.일단 그것이 발견되면 텍스트의 후속 문자는 패턴의 문자와 비교될 것이다.일치하는 항목이 없을 경우 일치하는 항목을 찾기 위해 텍스트가 문자별로 다시 확인될 것이다.따라서 본문의 거의 모든 문자를 검사할 필요가 있다.

이 알고리즘의 핵심 통찰은 패턴의 끝을 텍스트와 비교한다면 텍스트의 모든 문자를 체크하기 보다는 텍스트에 따라 점프를 할 수 있다는 것이다.이것이 효과가 있는 이유는 텍스트에 대한 패턴의 줄을 서면서 패턴의 마지막 문자를 텍스트의 문자와 비교하기 때문이다.문자가 일치하지 않으면 텍스트를 따라 뒤쪽으로 계속 검색할 필요가 없다.텍스트의 문자가 패턴의 문자와 일치하지 않는 경우, 확인할 텍스트의 다음 문자는 텍스트를 따라 더 멀리 m 문자(m은 패턴의 길이)에 위치한다.텍스트의 문자가 패턴에 있으면 텍스트에 따라 패턴의 부분적인 이동이 수행되어 일치하는 문자를 따라 정렬되고 프로세스가 반복된다.본문의 모든 문자를 체크하기보다 본문을 따라 점프하여 비교하는 것은 알고리즘의 효율성의 핵심인 비교의 횟수를 줄인다.

보다 형식적으로, 알고리즘은 $정렬{\displaystyle k}$ = m$${\$displaystyle k=$m$\}$에서 시작되므로 P의 시작은 T의 시작과 정렬된다.그런 다음 P와 T의 문자를 P의 지수 m과 T의 지수 k에서 시작하여 뒤로 이동하면서 비교한다.현은 P의 끝에서 P의 시작까지 일치한다.비교는 P의 시작(일치가 있음을 의미)에 도달하거나(일치가 있음을 의미), 또는 여러 규칙에서 허용하는 최대값에 따라 정렬이 앞으로(우측으로) 이동하는 불일치가 발생할 때까지 계속된다.비교는 새 정렬에서 다시 수행되며, 정렬이 T의 끝을 지나 이동될 때까지 프로세스가 반복되므로 더 이상의 일치점을 찾을 수 없다.

시프트 규칙은 P의 사전 처리 중에 생성된 테이블을 사용하여 상시 테이블 조회로 구현된다.

시프트 규칙

시프트는 나쁜 문자 규칙과 좋은 접미사 규칙의 두 가지 규칙을 적용하여 계산한다.실제 이동 오프셋은 이 규칙에 의해 계산된 이동의 최대값이다.

나쁜성격규칙

설명

나쁜 문자 규칙은 비교과정이 실패한 T의 문자를 고려한다(그런 실패가 발생한 것으로 가정한다).P에서 왼쪽 문자의 다음 발생이 발견되고, T에서 일치하지 않는 발생과 일치하도록 그 발생을 가져오는 이동이 제안된다.P에서 불일치 문자가 왼쪽으로 발생하지 않을 경우, P 전체를 불일치 지점을 지나 이동하는 시프트가 제안된다.

사전 처리

방법은 잘못된 문자 규칙에 대한 테이블이 취해야 하는 정확한 형태에 따라 다르지만, 간단한 상시 검색 솔루션은 알파벳에서 문자 c의 인덱스로 먼저 인덱싱되고 패턴에서 색인 i로 인덱싱되는 2D 테이블을 만드는 것이다.이 검색은 다음으로 높은 지수 < ${\displaystyle$ j$<i}$ 또는 -1이 없는 경우 p에서 c의 발생을 반환한다.그런 다음 제안된 시프트는 길이가 k인 유한 알파벳을 $가정$하여 O (${\displaystyle 1}$) ${\displaystyle O(1)}$ 조회$$ 시간과 $O{\displaystyle }$( k ${\displaystyle m}$) ${\displaystyle O(km)}$ 공간을$$ 가진 $i{\displaystyle }$- ${\displaystyle j}$ ${\displaystyle i-j$가 된다.

아래의 C 및 Java 구현에는 $O{\displaystyle }$( ${\displaystyle k}$) ${\displaystyle O(k)}$개의$$ 공간 복잡성이 있다(make_delta1, makeCharTable).이것은 원래의 델타1과 BMH 불량 문자표와 같다.이 표는 ${\displaystyle \mathrm{len}}$ ${\displaystyle (p}$)${\displaystyle }$- ${\displaystyle 1}$- ${\displaystyle i}$ ${\displaystyle \operatorname {len}(p)-1-i}$이$($가)의 위치 $i{\displaystyle }$ ${\displaysty style$ i$}$에 있는 문자를 가장 적은 시프트 양으로 우선하여 매핑한다$$.사용되지 않는 모든 문자는 sentinel 값으로$$ ${\displaystyle \mathrm{len}}$ ${\displaystyle }$(${\displaystyle p}$) ${\displaystyle \operatorname {len} (p)}($으)로 설정된다.

좋은 접미사 규칙

설명

좋은 접미사 규칙은 나쁜 문자 규칙보다 개념과 실행 모두에서 현저하게 더 복잡하다.나쁜 문자 규칙처럼 패턴의 끝에서 시작하여 패턴의 시작을 향해 나아가는 알고리즘의 비교 기능도 활용한다.다음과 같이 설명할 수 있다.^[5]

주어진 P와 T의 정렬에 대해 T의 하위 문자열 t는 P의 접미사와 일치하지만, 다음에 왼쪽과 비교했을 때 불일치가 발생한다고 가정하자.그런 다음, 존재하는 경우, t'가 P의 접미사가 아닌 것처럼 p에서 t의 가장 오른쪽 복사 t'가 되며, p에서 t의 왼쪽 문자는 문자에서 t의 왼쪽까지의 문자와 다르다.P의 하위 문자열 t'가 T의 하위 문자열 t와 정렬되도록 P를 오른쪽으로 이동시킨다.t'가 존재하지 않는 경우, 이동된 패턴의 접두사가 T의 접미사와 일치하도록 최소 양만큼 P의 왼쪽 끝을 T의 왼쪽 끝을 이동시킨다.그러한 이동이 불가능할 경우 P를 오른쪽으로 n개씩 이동시킨다.P의 발생이 발견되면, 이동된 P의 적절한 접두사가 T의 발생 접미사와 일치하도록 최소의 양만큼 P를 이동시킨다.그러한 이동이 불가능할 경우, P를 n개 장소, 즉 P를 t를 지나 이동시킨다.

사전 처리

좋은 접미사 규칙에는 두 개의 테이블이 필요하다. 하나는 일반 사례에 사용하기 위한 것이고 다른 하나는 일반 사례에서 의미 있는 결과를 반환하지 않거나 일치하는 경우가 발생할 때 사용하기 위한 것이다.이 표들은 각각 L과 H로 지정될 것이다.이들의 정의는 다음과 같다.^[5]

각 ${\displaystyle i}$에 대해 $L{\displaystyle }$[ i ${\displaystyle ]}$ ${\displaystyle L[$${\displaystyle i}$$]}$은(는) $P{\displaystyle }$ [${\displaystyle }$.${\displaystyle m}$ ${\displaystyle ]}$ ${\displaystyle P[i..m]}$이(가) $P{\displaystyle }$[ ${\displaystyle 1}$의 접미사와 일치하도록$$ m보다 작은 최대 위치다${\displaystyle \mathrm{.}}$$[\displaystyle P[1..$$L[i]}$ 및$$ 그 접미사 앞의 문자가 P${\displaystyle }$[ $i{\displaystyle }$- ${\displaystyle 1}$ ${\displaystyle ]}$ ${\displaystyle P[i-1]}$과 같지 않은 경우$,$ 조건을 $만족$하는 위치가 없을 경우 L [ i$]$ {\$displaystyle L[i$]}은$($는) 0으로 정의된다$$.

$Let{\displaystyle }$ H${\displaystyle }$[ ${\displaystyle i}$ ${\displaystyle ]}$ ${\displaystyle H[i]}$은(는) $P{\displaystyle }$[. ${\displaystyle i.}$ ${\displaystyle m}$ ${\displaystyle ]}$ ${\displaystyle P[i]$의 가장 큰 접미사의 길이를 나타낸다$$.또한 P의 접두사(있는 경우)인$$ m$]}.$$없으면{\displaystyle }$ H [${\displaystyle i}$ $]$ {\$displaystyle H[i$]}을$($를) 0으로 두십시오$$.

이 두 테이블 모두 $O{\displaystyle }$( ${\displaystyle m}$) ${\displaystyle$ O$(m)}$ 시간 내에$$ 구성할 수 있으며 O (${\displaystyle m}$) ${\displaystyle O(m)}$ 공간을$$ 사용한다.P에서 지수 i의 정렬 $시프트$는 $m{\displaystyle }$- ${\displaystyle L}$[ ${\displaystyle i}$ ${\displaystyle ]}$ ${\displaystyle m-L[i]}$ $또는$ m${\displaystyle }$- ${\displaystyle H}$[ i ${\displaystyle ]}$ ${\displaystyle m-H[i$$]}$이$($) 0이거나$$ 일치하는 것을 발견한 경우에만 사용해야 한다$.$

갈릴법칙

보이어-무어의 단순하지만 중요한 최적화는 1979년 즈비 갈릴에 의해 발표되었다.^[6]갈릴 법칙은 이동과 반대로 각 정렬에서 일치하는 것으로 알려진 구간을 건너뛰어 실제 비교를 가속화하는 것을 다룬다.선형 k에서₁ P를 T의 문자 c와 하향 비교한다고 가정한다.그런 다음 P가 k로₂ 전환되어 왼쪽 끝이 c와₁ k 사이에 있게 되면 다음 비교 단계에서 P의 접두사는 하위 문자열 T[(k₂ - n)..k₁]와 일치해야 한다.따라서 비교가 T의 위치 k까지₁ 내려간다면 과거 k를₁ 명시적으로 비교하지 않고도 P의 발생을 기록할 수 있다.보이어-무어의 효율을 높이는 것 외에, 최악의 경우 선형 실행의 증명에 갈릴 규칙이 요구된다.

갈릴 규칙은 원래 버전에서 여러 일치 항목을 출력하는 버전에만 유효하다.c = 0(즉, 전체 일치)에서만 하위 문자열 범위를 업데이트한다.1985년에 아포톨리코-지안카를로 알고리즘으로 잠수정을 다루는 일반화된 버전이 보고되었다.^[7]

퍼포먼스

원본 문서에 제시된 보이어-모어 알고리즘은 텍스트에 패턴이 나타나지 않는 경우에만$$ 최악의 $경우{\displaystyle }$ O${\displaystyle (n}$+ m $){\displaystyle O(n+m)}$의 실행 시간을 갖는다.이는 1977년 크누스, 모리스, 프랫에 의해 처음 증명되었고,^[8] 1980년에는^[9] 기바스와 오드리츠코가 최악의 경우 5n 비교의 상한선을 두고 그 뒤를 이었다.리처드 콜은 1991년 최악의 경우 3n 비교의 상한선이 있는 증거를 제시했다.^[10]

텍스트에서 패턴이 발생하는 경우, 원본 알고리즘의 실행 시간은 최악의 경우$$ $O{\displaystyle (n}$ m${\displaystyle }$) ${\displaystyle O(nm)}$이다.이는 패턴과 텍스트가 모두 동일한 반복 문자로만 구성되었을 때 쉽게 볼 수 있다.그러나 갈릴 규칙을 포함하면 모든 경우에 걸쳐 선형 런타임이 발생한다.^[6][10]

구현

다양한 구현이 다른 프로그래밍 언어로 존재한다.C++에서 C++17 이후 표준 라이브러리의 일부인 Boost는 또한 알고리즘 라이브러리 아래에 일반적인 Boyer-Moore 검색 구현을 제공한다.Go(프로그래밍 언어)에는 search.go에 구현이 있다.D(프로그래밍 언어)는 Phobos Runtime Library의 일부로 범위 내의 술어 기반 일치를 위해 BoyerMooreFinder를 사용한다.

보이어-모어 알고리즘은 GNU의 grep에도 사용된다.^[11]

파이썬 구현

로부터 타자 치기 수입하다 * # 이 버전은 대/소문자를 구분하지 않는 일치를 위해 ASCII의 영어 알파벳에 민감하다. # 이 기능을 제거하려면 알파벳_index를 순서(c)로 정의하고 "26" 인스턴스를 교체하십시오. # "256" 또는 원하는 최대 코드 포인트.유니코드의 경우 UTF-8에서 일치시키십시오. 0x10을 생성하는 대신 바이트 수FFFF 크기의 테이블.  알파벳_SIZE = 26  반항하다 알파벳_index(c: 발을 동동 구르다) -> 인트로:     """"영문자에서 주어진 문자의 색인을 0에서 세어 반환하라."     발랄하게 하다 = 서품을 하다(c.더 낮게()) - 서품을 하다("a")     주장하다 발랄하게 하다 >= 0 그리고 발랄하게 하다 < 알파벳_SIZE     돌아오다 발랄하게 하다  반항하다 match_length(S: 발을 동동 구르다, idx1: 인트로, idx2: 인트로) -> 인트로:     """IDx1과 idx2에서 시작하는 S의 서브스트링 일치 길이를 반환한다."""     만일 idx1 == idx2:         돌아오다 렌(S) - idx1     match_count = 0     하는 동안에 idx1 < 렌(S) 그리고 idx2 < 렌(S) 그리고 S[idx1] == S[idx2]:         match_count += 1         idx1 += 1         idx2 += 1     돌아오다 match_count  반항하다 basic_process(S: 발을 동동 구르다) -> 리스트[인트로]:     """S의 근본적인 전처리인 리턴 Z.  Z[i]는 i에서 시작하는 하위 문자열의 길이로서, 또한 S의 접두어이기도 하다. 이 전처리는 O(n) 시간에 이루어지며, 여기서 n은 S의 길이다. """     만일 렌(S) == 0:  # 빈 문자열 대소문자 처리         돌아오다 []     만일 렌(S) == 1:  # 단일 문자 문자열의 대소문자 처리         돌아오다 [1]     z = [0 을 위해 x 에 S]     z[0] = 렌(S)     z[1] = match_length(S, 0, 1)     을 위해 i 에 범위(2, 1 + z[1]):  # 연습으로 인한 최적화 1-5         z[i] = z[1] - i + 1     # z-box 하한 및 상한 정의     l = 0     r = 0     을 위해 i 에 범위(2 + z[1], 렌(S)):         만일 i <= r:  # 기존 z-box에 속함             k = i - l             b = z[k]             a = r - i + 1             만일 b < a:  # b 기존 z-box 내 종료                 z[i] = b             다른:  # b z-box 종료 후 또는 종료 후 z-box 오른쪽과 명시적으로 일치해야 함                 z[i] = a + match_length(S, a, r + 1)                 l = i                 r = i + z[i] - 1         다른:  # 기존 z-box 내에 상주하지 않음             z[i] = match_length(S, 0, i)             만일 z[i] > 0:                 l = i                 r = i + z[i] - 1     돌아오다 z  반항하다 bad_paracter_table(S: 발을 동동 구르다) -> 리스트[리스트[인트로]]:     """ S에 대해 R을 생성하며, 이는 에서 일부 문자 c의 위치에 의해 인덱싱된 배열이다. 영어 알파벳.R의 해당 인덱스에서 길이 S +1의 배열로, 각각에 대해 지정한다. Index i in S(S 이후의 인덱스 포함)에서 다음 위치인 문자 c가 발견될 때 i에서 시작하여 S를 오른쪽에서 왼쪽으로 가로지르는 것.이것은 상수 시간 조회에 사용된다. Boyer-Moore 문자열 검색 알고리즘에 잘못된 문자 규칙이 있지만 비파워 타임 솔루션보다 훨씬 큰 크기 """     만일 렌(S) == 0:         돌아오다 [[] 을 위해 a 에 범위(알파벳_SIZE)]     R = [[-1] 을 위해 a 에 범위(알파벳_SIZE)]     알파의 = [-1 을 위해 a 에 범위(알파벳_SIZE)]     을 위해 i, c 에 열거하다(S):         알파의[알파벳_index(c)] = i         을 위해 j, a 에 열거하다(알파의):             R[j].덧셈을(a)     돌아오다 R  반항하다 good_suffer_table(S: 발을 동동 구르다) -> 리스트[인트로]:     """ 강력한 양호한 접미사 규칙의 구현에 사용되는 배열인 S에 대해 L을 생성한다. L[i] = k, S[i:](i에서 시작하는 S의 접미사)가 일치하는 S에서 가장 큰 위치 S[:k]의 접미사(k로 끝나는 S의 하위 문자열).보이어 무어에서 사용되며 L은 다음 양을 준다. T에서 P의 인스턴스(instance)를 건너뛰지 않고 P[:]의 접미사가 없는 T를 기준으로 P를 이동시킨다.L[i] 이전 매치 시도에서 P의 접미사와 일치하는 T의 하위 문자열을 일치시킨다. 특히, P의 위치 i-1에서 불일치가 발생한 경우, 이동 크기가 주어진다. len(P) - L[i] 등식으로L[i] = -1일 경우 전체 교대조가 사용된다. 적절한 접미사만 중요하므로 L[0] = -1. """     L = [-1 을 위해 c 에 S]     N = basic_process(S[::-1])  # S[:-1] 반전 S     N.역행의()     을 위해 j 에 범위(0, 렌(S) - 1):         i = 렌(S) - N[j]         만일 i != 렌(S):             L[i] = j     돌아오다 L  반항하다 풀_shift_테이블(S: 발을 동동 구르다) -> 리스트[인트로]:     """ Boyer-Moore에서 좋은 접미사 규칙의 특별한 경우에 사용되는 배열인 S에 대해 F 생성 문자열 검색 알고리즘.F[i]는 S[i:]의 가장 긴 접미사 길이이기도 하며, 이 역시 S[i:]이다. S의 접두사사용되는 경우, P 패턴의 이동 크기는 텍스트 T는 i-1에서 발생하는 불일치에 대해 len(P) - F[i]이다. """     F = [0 을 위해 c 에 S]     Z = basic_process(S)     가장 긴 = 0     을 위해 i, zv 에 열거하다(뒤바뀐(Z)):         가장 긴 = 맥스.(zv, 가장 긴) 만일 zv == i + 1 다른 가장 긴         F[-i - 1] = 가장 긴     돌아오다 F  반항하다 string_search(P, T) -> 리스트[인트로]:     """ Boyer-Moore 문자열 검색 알고리즘 구현.P의 모든 발생을 찾음 T에, 그리고 최적값을 결정하기 위해 패턴을 사전 처리하는 여러 방법을 통합한다. 문자열 이동 및 비교 건너뛰기 양.실제로 그것은 O(m)로 달린다 (그리고 심지어 sublinear) 시간, 여기서 m은 T의 길이다.이 구현은 대/소문자를 구분하지 않고 수행됨 ASCII 알파벳 문자로 검색, 공백 포함 안 함. """     만일 렌(P) == 0 또는 렌(T) == 0 또는 렌(T) < 렌(P):         돌아오다 []      성냥 = []      # 전처리     R = bad_paracter_table(P)     L = good_suffer_table(P)     F = 풀_shift_테이블(P)      k = 렌(P) - 1      # T에 상대적인 P 끝의 정렬을 나타낸다.     이전_k = -1     # 이전 단계의 정렬을 나타낸다(갈릴의 규칙)     하는 동안에 k < 렌(T):         i = 렌(P) - 1  # P에서 비교할 캐릭터         h = k           # T에서 비교할 캐릭터         하는 동안에 i >= 0 그리고 h > 이전_k 그리고 P[i] == T[h]:  # P 끝부터 시작되는 매치             i -= 1             h -= 1         만일 i == -1 또는 h == 이전_k:  # 성냥개비 발견 (갈릴의 법칙)             성냥.덧셈을(k - 렌(P) + 1)             k += 렌(P) - F[1] 만일 렌(P) > 1 다른 1         다른:  # 일치 없음, 나쁜 문자와 좋은 접미사 규칙의 최대값으로 이동             char_shift = i - R[알파벳_index(T[h])][i]             만일 i + 1 == 렌(P):  # 첫 시도 시 불일치 발생                 접미사_shift = 1             엘리프 L[i + 1] == -1:  # 일치하는 접미사가 P 어디에도 나타나지 않음                 접미사_shift = 렌(P) - F[i + 1]             다른:               # 일치하는 접미사가 P에 표시됨                 접미사_shift = 렌(P) - 1 - L[i + 1]             교대시키다 = 맥스.(char_shift, 접미사_shift)             이전_k = k 만일 교대시키다 >= i + 1 다른 이전_k  # 갈릴의 법칙             k += 교대시키다     돌아오다 성냥 

C 구현

#include <stdint.h> #include <stddef.h> #include <stdbool.h> #include <stdlib.h>  #알파브 정의ET_LEN 256 #define max(a, b) ((a < b) ? b : a)  // 잘못된 문자 규칙. // delta1 테이블: delta1[c]에 마지막 간격 포함 // 팻의 성격과 팻에서 c가 가장 오른쪽을 차지한다. // // c가 pat에서 발생하지 않으면 delta1[c] = patlen. // c가 문자열[i]과 c !=패틀[patlen-1]에 있으면 안전하게 i를 옮길 수 있다. // delta1[c]을 통해 이동하는데 필요한 최소 거리 // 앞으로 두드려 어떤 인물과 함께 줄을 서게 한다. // c == pat[patlen-1] 반환 0은 BMH의 걱정거리일 뿐이다. // 델타2가 없는 경우.BMH는 그러한 경우에 가치를 patlen으로 만든다. // 원래 0 대신 이 선택을 따르는데, 이는 건너뛰기 때문이다. // 그 이상.(정확성?) // // 이 알고리즘은 알파벳_len+patlen 시간으로 실행된다. 공허하게 하다 make_make1(ptrdiff_t *델타1, uint8_t *쓰다듬다, size_t 패틀린) {     을 위해 (인트로 i=0; i < 알파벳_LEN; i++) {         델타1[i] = 패틀린;     }     을 위해 (인트로 i=0; i < 패틀린; i++) {         델타1[쓰다듬다[i]] = 패틀린-1 - i;     } }  // 단어[pos]에서 시작하는 단어의 접미사가 접두사일 경우 true // 단어의 바가지 긁다 is_message(uint8_t *단어, size_t 단어의, ptrdiff_t 양치류) {     인트로 접미사의 = 단어의 - 양치류;     // 여기서 strncmprobrary 기능을 사용할 수도 있음     // return ! strncmp(word, &word[pos], 접미사);     을 위해 (인트로 i = 0; i < 접미사의; i++) {         만일 (단어[i] != 단어[양치류+i]) {             돌아오다 거짓의;         }     }     돌아오다 진실의; }  // 단어의 가장 긴 접미사 길이[pos] // 접미사_lengthdddbcabc", 8, 4) = 2 size_t 접미사_길이(uint8_t *단어, size_t 단어의, ptrdiff_t 양치류) {     size_t i;     // 첫 번째 불일치 또는 시작까지 접미사 길이 i 증가     // 단어의     을 위해 (i = 0; (단어[양치류-i] == 단어[단어의-1-i]) && (i < 양치류); i++);     돌아오다 i; }  // 좋은 접미사 규칙. // 델타2 테이블: pat[pos]에 불일치가 있는 경우, 우리는 정렬하기를 원한다. // 다음 번 풀매치가 가능한 경우, 우리가 무엇을 기준으로 할 수 있는지. // 쓰다듬을[pos+1]에 대해 알고 있다[patlen-1]. // // 사례 1: // 패트[pos+1]에서 패트[patlen-1]는 다른 패트에서는 발생하지 않는다. // 다음 그럴듯한 일치는 불일치 시점 또는 이후에 시작한다. // 만약, 변전소 내에[pos+1 ..patlen-1], 접두사 표시 // 패트의 다음 그럴듯한 일치가 여기에 있다(여러 개가 있는 경우). // 하위 문자열의 접두사, 가장 긴 항목 선택).그렇지 않으면 더 // 다음 그럴싸한 일치는 다음과 같이 정렬된 문자를 지나 시작한다. // 쓰다듬다[patlen-1]. // // 사례 2: // 패트[pos+1]를 패트로 패트[patlen-1]하는 경우는 다른 곳에서 발생한다.그 // 불일치는 우리가 성냥의 끝을 보고 있지 않다는 것을 말해준다. // 그러나 우리는 경기 중반부를 볼 수 있다. // // 사례 1을 돌보는 첫 번째 루프는 // KMP 테이블, 를 사용하여 '뒤로' 스캔 순서에 맞게 조정됨 // 그것이 생각하는 하위 문자열의 추가 제한 // 전위 접두사는 모두 접미사다.최악의 경우 // pat은 같은 글자 반복으로 구성되므로, 모든 접미사는 // 접두사.그러나 이 루프만으로는 충분하지 않다. // 패트가 "ABYXCDBYX"이고 텍스트가 "....."라고 가정하자.ABYXCDEYX". // 우리는 X, Y를 일치시키고 B !=E를 찾을 것이다.팻말의 접두사가 없다. // 접미사 "YX"에서 첫 번째 루프는 앞으로 건너뛰라고 알려준다. // 9자. // 표면적으로는 KMP 테이블과 유사하지만, KMP 테이블 // 부분 일치 시작에 대한 정보에 의존 // BM 알고리즘에 없는. // // 두 번째 루프는 사례 2를 다룬다.suffix_length가 아닐 수 있으므로 // 독특함, 최소값을 취하고자 함. 이 값을 통해 // 가장 가까운 잠재적 일치점이 얼마나 멀리 떨어져 있는지. 공허하게 하다 make_make2(ptrdiff_t *델타2, uint8_t *쓰다듬다, size_t 패틀린) {     ssize_t p;     size_t last_message_index = 패틀린-1;      // 첫 번째 루프     을 위해 (p=패틀린-1; p>=0; p--) {         만일 (is_message(쓰다듬다, 패틀린, p+1)) {             last_message_index = p+1;         }         델타2[p] = last_message_index + (패틀린-1 - p);     }      // 두 번째 루프     을 위해 (p=0; p < 패틀린-1; p++) {         size_t 살코기를 하다 = 접미사_길이(쓰다듬다, 패틀린, p);         만일 (쓰다듬다[p - 살코기를 하다] != 쓰다듬다[패틀린-1 - 살코기를 하다]) {             델타2[패틀린-1 - 살코기를 하다] = 패틀린-1 - p + 살코기를 하다;         }     } }  // 포인터를 첫 번째 일치 항목으로 되돌린다. // glibc memmem()(비 BM) 및 std:::boyer_moore_searcher(첫 번째 일치)를 참조하십시오. uint8_t* boyer_boyd (uint8_t *끈을 매다, size_t 현악기의, uint8_t *쓰다듬다, size_t 패틀린) {     ptrdiff_t 델타1[알파벳_LEN];     ptrdiff_t 델타2[패틀린]; // C99 VLA     make_make1(델타1, 쓰다듬다, 패틀린);     make_make2(델타2, 쓰다듬다, 패틀린);      // 빈 패턴은 특별히 고려되어야 한다.     만일 (패틀린 == 0) {         돌아오다 끈을 매다;     }      size_t i = 패틀린 - 1;        // str-idx     하는 동안에 (i < 현악기의) {         ptrdiff_t j = 패틀린 - 1; // pat-idx         하는 동안에 (j >= 0 && (끈을 매다[i] == 쓰다듬다[j])) {             --i;             --j;         }         만일 (j < 0) {             돌아오다 &끈을 매다[i+1];         }          ptrdiff_t 교대시키다 = 맥스.(델타1[끈을 매다[i]], 델타2[j]);         i += 교대시키다;     }     돌아오다 NU LL; } 

자바 구현

    /** * 이 문자열 내에서 첫 번째 발생의 인덱스를 반환함 * 지정된 하위 문자열.하위 문자열이 아닌 경우 -1을 반환하십시오. * * 갈릴은 성냥을 하나만 생성하기 때문에 없다. * * @param 건초 스택 검색할 문자열 * @param needle 검색할 대상 문자열 * @return 하위 문자열의 시작 인덱스 */     공중의 정태의 인트로 인덱스오프(마를 뜨다[] 건초 더미, 마를 뜨다[] 바늘을 꿰다) {         만일 (바늘을 꿰다.길이 == 0) {             돌아오다 0;         }         인트로 charTable[] = makeCharTable(바늘을 꿰다);         인트로 간격띄우기[] = MakeOffsetTable(바늘을 꿰다);         을 위해 (인트로 i = 바늘을 꿰다.길이 - 1, j; i < 건초 더미.길이;) {             을 위해 (j = 바늘을 꿰다.길이 - 1; 바늘을 꿰다[j] == 건초 더미[i]; --i, --j) {                 만일 (j == 0) {                     돌아오다 i;                 }             }             // i += needle.length - j; // 순진한 방법의 경우             i += 수학.맥스.(간격띄우기[바늘을 꿰다.길이 - 1 - j], charTable[건초 더미[i]]);         }         돌아오다 -1;     }      /** * 일치하지 않는 문자 정보를 기반으로 점프 테이블을 만든다. */     사유의 정태의 인트로[] makeCharTable(마를 뜨다[] 바늘을 꿰다) {         최종의 인트로 알파벳_SIZE = 캐릭터.MAX_VALUE + 1; // 65536         인트로[] 테이블 = 새로운 인트로[알파벳_SIZE];         을 위해 (인트로 i = 0; i < 테이블.길이; ++i) {             테이블[i] = 바늘을 꿰다.길이;         }         을 위해 (인트로 i = 0; i < 바늘을 꿰다.길이; ++i) {             테이블[바늘을 꿰다[i]] = 바늘을 꿰다.길이 - 1 - i;         }         돌아오다 테이블;     }      /** * 일치하지 않는 스캔 오프셋을 기준으로 점프 테이블을 만든다. * (나쁜 문자 규칙). */     사유의 정태의 인트로[] MakeOffsetTable(마를 뜨다[] 바늘을 꿰다) {         인트로[] 테이블 = 새로운 인트로[바늘을 꿰다.길이];         인트로 마지막 사전 수정위치 = 바늘을 꿰다.길이;         을 위해 (인트로 i = 바늘을 꿰다.길이; i > 0; --i) {             만일 (isprefix(바늘을 꿰다, i)) {                 마지막 사전 수정위치 = i;             }             테이블[바늘을 꿰다.길이 - i] = 마지막 사전 수정위치 - i + 바늘을 꿰다.길이;         }         을 위해 (인트로 i = 0; i < 바늘을 꿰다.길이 - 1; ++i) {             인트로 살코기를 하다 = 접미사길이(바늘을 꿰다, i);             테이블[살코기를 하다] = 바늘을 꿰다.길이 - 1 - i + 살코기를 하다;         }         돌아오다 테이블;     }      /** * 바늘은 바늘의 접두사인가? */     사유의 정태의 부울 isprefix(마를 뜨다[] 바늘을 꿰다, 인트로 p) {         을 위해 (인트로 i = p, j = 0; i < 바늘을 꿰다.길이; ++i, ++j) {             만일 (바늘을 꿰다[i] != 바늘을 꿰다[j]) {                 돌아오다 거짓의;             }         }         돌아오다 진실의;     }      /** * p에서 끝나는 하위 문자열의 최대 길이를 반환하며 접미사다. * (좋은 접미사 규칙) */     사유의 정태의 인트로 접미사길이(마를 뜨다[] 바늘을 꿰다, 인트로 p) {         인트로 렌 = 0;         을 위해 (인트로 i = p, j = 바늘을 꿰다.길이 - 1;                  i >= 0 && 바늘을 꿰다[i] == 바늘을 꿰다[j]; --i, --j) {             렌 += 1;         }         돌아오다 렌;     } 

변형

보이어-무어-Horspool 알고리즘은 Boyer-Moore 알고리즘을 나쁜 문자 규칙만을 사용하여 단순화한 것이다.

아포토리코-지안카를로 알고리즘은 명시적 문자 비교를 건너뛰어 주어진 정렬에서 일치가 발생했는지 확인하는 과정을 가속화한다.이는 각 매치 시도에서 기록된 접미사 일치 길이와 함께 패턴의 사전 처리 중에 수집된 정보를 사용한다.접미사 일치 길이를 저장하려면 검색 중인 텍스트와 크기가 같은 추가 테이블이 필요하다.

라이타 알고리즘은 보이어-무어-호스풀 알고리즘의 성능을 향상시킨다.주어진 문자열에서 특정 하위 문자열의 검색 패턴은 Boyer-Moore-Horspool 알고리즘과 다르다.

메모들

참조

외부 링크

위키미디어 커먼스는 보이어-무어 문자열 검색 알고리즘과 관련된 미디어를 보유하고 있다.

• Boyer-Moore 알고리즘에 대한 원본
• J Strother Moore 홈페이지의 Boyer-Moore 알고리즘의 예, 알고리즘의 공동 발명자
• 런타임 선형성을 증명하는 리처드 콜의 1991년 논문
• Boyer-Moore 문자열 검색 알고리즘 설명 및 CBMC를 사용한 공식 확인