크 누스 - 모리스 - 프랫 알고리즘의 중복 명령어

Question

Knuth-Morris-Pratt algorithm은 문자열에서 부분 문자열의 첫 번째 (그리고 아마도 다음) 어커런스를 찾는 것을 목표로합니다. 하위 문자열은 반복되는 부분을 포함 할 수 있으므로 어떤 종류의 역 추적 메커니즘을 사용합니다. 이것은 의사 코드의 알고리즘입니다 :

let m ← 0, i ← 0 
while m + i < length(S) do 
     if W[i] = S[m + i] then 
      if i = length(W) - 1 then 
       return m 
      let i ← i + 1 
     else 
      if T[i] > -1 then 
       let m ← m + i - T[i], i ← T[i] 
      else 
       let i ← 0, m ← m + 1 

(위키 백과에서 제공). W 부분 문자열과 S 검색 할 문자열 (모두 0부터 시작 함).

내가 알고리즘의 마지막 if 절에 대한 질문이 : if T[i] > -1 then의 T - 벡터 건설 알고리즘에 기반을, T[i] 인덱스 i = 0에 0보다 작은임을에서만 가능 보인다. 이 경우 인덱스에서 더 빠른 "확인"을 수행 할 수 있습니다. 배열 액세스는 추가 명령입니다 (특히 캐시 오류을 고려한 경우). i ← 0과 동일합니다.

T의 구조는 다음과 같은 알고리즘에 의해 수행됩니다

let pos ← 2, cmd ← 0 
let T[0] ← -1, T[1] ← 0 
while pos < length(W) do 
    if W[pos-1] = W[cnd] then 
     let cnd ← cnd + 1, T[pos] ← cnd, pos ← pos + 1 
    else if cnd > 0 then // (*) 
     let cnd ← T[cnd] 
    else 
     let T[pos] ← 0, pos ← pos + 1 

(위키 백과).

이제는 알고리즘이 0 또는 cnd에서 T으로 기록됩니다. 첫 번째 유형의 과제의 경우 진술은 사실입니다. 두 번째 경우에는 cmd 값에 따라 다릅니다.

이제는 cmd을 줄일 수있는 유일한 방법은 두 번째 경우 (*)입니다.이 경우 cmd는 값이 0 이하가 될 때까지 작고 작아집니다. 그러나 cmd은 배열의 이미 초기화 된 부분에서 값을 취하므로 0 또는 -1이 될 수 있습니다. cmd이 실제로 -1 인 경우 값을 설정하기 전에 증가가 있기 때문에 은 0으로 설정됩니다. cmd이 0 일 경우 아무런 문제가 없습니다.

A는보다 효율적인 알고리즘이 이렇게 될 것이다 비트 :

let m ← 0, i ← 0 
while m + i < length(S) do 
    if W[i] = S[m + i] then 
     if i = length(W) - 1 then 
      return m 
     let i ← i + 1 
    else 
     if i > 0 then 
      let m ← m + i - T[i], i ← T[i] 
     else 
      let m ← m + 1 

이 문 맞습니까? 그렇지 않다면, 배열에 두 개 이상의 -1이 나타나는 부분 문자열을 줄 수 있습니까?

Answer 1

실제로 나에게 얼마나 많은 차이가 있는지 알지 못하지만, 나에게는 잘 어울립니다. 일반적인 시나리오에서 대다수의 루프는 i이 0이고 위치가 S[m] ≠ W[0] 인 문자와 정확히 일치합니다.

위키 피 디아의 알고리즘이 "공식적인"것이거나 최적화 된 것으로 생각하지 않습니다. 그것은 교훈적인 의도가 있습니다.

if의 두 번째 분기는 후보 일치 항목을 확장 할 수없고 문자를 검색 할 단어의 첫 번째 문자가 아닌 경우 발생합니다. 이 경우 그 캐릭터 위로 이동해야합니다. (그것은 이전에 언급 된 일반적인 경우입니다.)

실패 분기가 입력되는 다른 모든 경우에는 m+i이 변경되지 않습니다. 성공 사례와 최종 실패 사례에서 m+i은 정확히 1 씩 증가합니다. min 및 max 많은 CPU에서 지점이없는 op 코드이기 때문에

, 다른 최적화 대신 -1의 0에 T[0]를 설정하고에 루프를 변경하는 것입니다 :

let m ← 0, i ← 0 
while m + i < length(S) do 
    if W[i] = S[m + i] then 
     if i = length(W) - 1 then 
      return m 
     let i ← i + 1 
    else 
     let m ← m + max(1, i - T[i]), i ← T[i] 

을하지만 더 나은 최적화하는 것입니다 세 가지 다른 루프를 사용하십시오. 일반적인 경우 (i = 0 및 S[m]은 W[0]과 일치하지 않습니다). 문자가 일치하는 경우 하나. 하나는 실패 사례입니다. (고장의 경우는 입력 길이 대하여 m + i를 비교할 필요가 없다 만 i이 0인지 여부를 확인해야 함) 참고로

(citeseer시) 원본 용지 제공은 다음과 같은 간단한 알고리즘 :

(* Note: here, m is the length of pattern and n is the length of the input *) 
j := k := 1; 
while j ≤ m and k ≤ n do 
    begin 
     while j > 0 and text[k] ≠ pattern[j] 
      do j := next[j]; 
     k := k + l; j := j + l; 
    end; 

그러나 저자는 위의 간단한 알고리즘이 불필요하게 비효율적이며 최적화를 탐구하는 데 몇 페이지를 투자한다고 불평합니다.

반드시 Fast Matching in Strings, 1974, Knuth, Morris & Pratt