유한 오토마타와 일치하는 문자열

Question

Cormen의 "Introduction to Algorithms"에서 문자열 알고리즘에 대해 읽었습니다. 아래 표시된 Transition의 경우.

내 질문 : 왜 우리가 min(m+1, q+2)을하고 왜 우리가 2

다음 링크로 (1)와 q에 의해 m를 증가하는 위의 질문에 땅을 다시 가지고있다.

http://people.scs.carleton.ca/~maheshwa/courses/5703COMP/Fall2009/StringMatching.pdf

친절 간단한 예제 여기에 도움이됩니다. 때문에 다음 repeat 루프 k에

Algorithm Compute-Transition-Function(P, Sigma) 
m = length(P); 
for q = 0 through m do 
    for each character x in Sigma 
     k = min(m+1, q+2); 
     repeat k = k-1 // work backwards from q+1 
     until Pk 'is-suffix-of' Pqx; 
     d(q, x) = k; // assign transition table 
    end for; 
end for; 

return d; 
End algorithm. 

Answer 1

• 그것은 m + 1이다 먼저 감소된다.
• repeat에서 q + 1으로 시작하므로 최소 1 자 이상이므로 q + 2입니다.

  ---

다음 코드는, 을 경계 문제 (q는 == m가없는)을 가지고 있지만 인덱싱 조금 명확하게하고 싶어 할 수도 있습니다.

m = length(P); 
for q = 0 through m - 1 do // Loop through substrings [0, q+1] 
    for each character x in Sigma 
     k = q+1; 
     // work backwards from q+1 
     while not Pk 'is-suffix-of' Pqx; 
     do k = k-1; end do; 
     d(q, x) = k; // assign transition table 
    end for; 
end for; 

return d; 

Answer 2

전환 테이블의 항목 d(q,x)는 x을 소비하기 전에 가장 긴 일치 접두사 q 자라면, 문자 x를 소비 한 후 패턴의 가장 긴 일치 접두사의 길이를 포함합니다. 우리는 한 글자를 소비하기 때문에 q+1보다 클 수없고 길이가 m이기 때문에 또한 m 일 수 있습니다. 내부 루프는 repeat k = k-1 until condition(k)이므로 아무 것도 테스트하기 전에 k이 감소하므로 k은 가능한 가장 큰 결과 인 k = min(m,q+1) + 1보다 1 시작해야합니다. 내부 루프가 while negated_condition(k) { k = k-1; }이면 k = min(m,q+1)으로 시작합니다.

Knuth-Morris-Pratt 알고리즘의 테두리 표를 사용하면 전환 표를 훨씬 더 효율적으로 계산할 수 있습니다. 코드가 그래서 여기에 설명 된

Answer 3

는의 문자열이

그래서 우리는 우리의 주 패턴에 부분적으로 일치되고 싶어 나노

입니다 가정 해 봅시다

에 무슨 일이 일어나고 있는지 볼 수있는 예이다. "nano"과 일치하는 부분은 "", "n", "na", "nan", or (the complete match) "nano"입니다. 즉, 문자열의 접두사 일뿐입니다. 일반적으로 패턴에 m 문자가 있으면 m + 1 상태가 필요합니다. 여기서 m = 4이고 5 개의 상태가 있습니다.

방금 ​​"...nan"을보고 다른 문자 "x"을 보면 어떤 상태로 가야합니까? x가 경기의 다음 문자 (여기서 "o") 인 경우 분명히 다음 긴 접두어 (여기에서 "nano")로 이동해야합니다. 그리고 우리가 완전한 일치를 보았을 때, 우리는 단지 그 상태에 머물러 있습니다. 그러나 "a"과 같은 다른 문자가 있다고 가정합니다. 즉, 문자열은 "...nana"과 같습니다. 가장 긴 부분 일치는 단지 "na"이며 마지막 2 문자를 사용할 수 있습니다.따라서 상태가 "nan" 인 경우 "a"이라는 화살표를 그려서 "na"으로 표시해야합니다. "na"은 접두어가 "nano" (상태이므로)이고 접미어는 "nana"입니다. (부분적으로 일치하는 내용이므로 방금 본 내용과 일치합니다).

일반적으로 상태 + 문자에서 상태로의 전환은 원본 패턴의 접두사와 방금 본 상태 + 문자의 접미사 인 최장 문자열입니다. 이것은 모든 변화가 무엇인지 말해주기에 충분합니다. 우리는 패턴 "nano"을 찾고 있다면, 전환 테이블은

 n  a  o  other 
    ---  ---  ---  --- 
empty: "n"  empty empty empty  
"n": "n"  "na" empty empty 
"na": "nan" empty empty empty 
"nan": "n"  "na" "nano" empty //just as an illustration, nan + n = n because we can only use the last 'n', nan + a = na because now we can use the last two 'na' 
"nano": "nano" "nano" "nano" "nano" 

은 그래서 지금 우리가 실제로 패턴이 검색 할이 표를 사용하여 어떻게 될 것인가?

문자열 "banananona"에서이를 시뮬레이션하면 한 번에 한 문자 씩 이동하여 상태 시퀀스를 비워 둡니다. 빈 문자는 "n", "na", "nan", "na", "nan", "nano", "nano", "nano"입니다. 상태가 "nano"으로 끝나기 때문에이 문자열에는 어딘가에 "nano"이 포함되어 있습니다. 위의 표를 사용하는 방법을 확장하고 'b'에서 가능한 상태 중 하나가 아니기 때문에 'n', 'na', 'nan', 'nano'에 있습니다. 그래서 그것은 빈 것으로 간주됩니다 ... 우리가 'ba'에 도착할 때와 같습니다. 다음 문자 'n'을 치면 기본적으로 빈에서 n으로 바뀌므로 위에 나온 표를 사용하여 'n'으로 끝나는 것을 봅니다. 이제 우리는 banananona의 4 글자를 얻었습니다. 그래서 우리는 'n'에서 ... a를 추가하기로했습니다 ... 다시 우리는 테이블을 사용하여 'na'으로 끝나는 것을 볼 수 있습니다.