문자열 유사성 : Bitap은 정확히 어떻게 작동합니까?

Question

Bitap 알고리즘으로 머리를 감싸고 있지만 알고리즘의 단계에 대한 이유를 이해하는 데 문제가 있습니다. 이전 문자열 PATTERN.substring(0, i-1)이 성공적으로 일치하는 경우

영어 측면에서

Two strings:  PATTERN (the desired string) 
       TEXT (the String to be perused for the presence of PATTERN) 

Two indices:  i (currently processing index in PATTERN), 1 <= i < PATTERN.SIZE 
       j (arbitrary index in TEXT) 

Match state S(x): S(PATTERN(i)) = S(PATTERN(i-1)) && PATTERN[i] == TEXT[j], S(0) = 1 

, PATTERN.substring(0,i)의 텍스트 문자열을 일치 :

나는 (내가 틀렸다면 정정 해줘) 인 알고리즘의 기본적인 전제를 이해 PATTERN[i]에있는 문자는 TEXT[j]에있는 문자와 같습니다.

내가 이해할 수없는 것은 이것의 비트 이동 구현입니다. The official paper detailing this algorithm basically lays it out,하지만 계속 진행해야 할 부분을 시각화 할 수는 없습니다. 알고리즘 사양은 종이의 첫 번째 2 페이지,하지만 난 중요한 부분 강조합니다 : 다음은

: 여기

이 개념의 비트 이동 버전을 샘플 검색 문자열에 대한 T [텍스트] : 여기

그리고 알고리즘의 흔적이다.

특히, 나는 OR 뒤에 T 테이블의 의미, 그리고 이유는 현재 상태와 그것의 항목을 보내고 무엇을 이해하지 않습니다. 누군가가 나를 정확하게 다른 사람이 답변을 허용하지에 대한

Answer 1

죄송에 무슨 일이 일어나고 있는지 이해하는 데 도움이 할 수있는 경우

나는 감사하게 될 거라고,하지만 난 지금 그것을 알아 냈어요 확신 해요.

알고리즘을 알아내는 데 필수적인 개념은 이진 상태에서 일치 상태 (원래 게시물에서 정의 됨)를 나타내는 것입니다. 원래 게시물의 기사는 형식적으로 설명합니다. 나는 대변을 그리면서 손을 쓸 것입니다 :

STR은 주어진 알파벳의 문자로 생성 된 문자열입니다.

이진 자릿수가 인 STR으로 표시해 보겠습니다. 알고리즘은이 표현이 거꾸로되어 있어야합니다. 그래서 첫 번째 문자는 마지막 숫자에 해당하고, 두 번째 문자는 두 번째 숫자부터 마지막 ​​숫자까지와 같습니다.

RANDOM은 같은 알파벳의 임의 문자가있는 문자열을 나타냅니다. STR. 지정된 인덱스

STR_BINARY

에서, 0은 STR[0]에서 RANDOM 일치 STR 그

STR[(index of letter in STR that the 0 in STR_BINARY corresponds to)]에 나타낸다. 빈 칸은 성냥으로 간주됩니다. A 1은 RANDOM이 동일한 경계 안의 STR과 일치하지 않음을 나타냅니다.

이 알고리즘을 이해하면 알고리즘을 익히는 것이 더 간단 해집니다. 당신은 일반적으로 패턴 번호 위치가 왼쪽에서 오른쪽으로 것부터 때문에

Answer 2

T 약간 혼란 :

0 1 2 3 4 
a b a b c 

... 비트가 일반적으로 오른쪽에서 왼쪽으로 번호가 매겨집니다 반면.

그러나 거꾸로 비트 위의 패턴을 작성하는 것이 있습니다 분명히 :

 
    bit: 4 3 2 1 0 

     c b a b a 
T[a] = 1 1 0 1 0 

     c b a b a 
T[b] = 1 0 1 0 1 

     c b a b a 
T[c] = 0 1 1 1 1 

     c b a b a 
T[d] = 1 1 1 1 1 

비트 그렇지 않은 경우 x 위치 N, 또는 1 나타나는 경우 T[x]의 N이 0입니다.

동등하게, 당신은 말을 생각할 수있는 입력 문자열에서 현재의 문자 는 x, 당신은 당신 만 가능한 패턴의 경우 일치 할 수 , T[x]의 N 위치에 0가 표시되는 경우 경기는 이전에 n 자 으로 시작되었습니다.

---

이제 일치하는 절차를 수행하십시오. A 0의 비트 n은 패턴 n (여기서 0은 현재 문자 임)과 패턴 일치를 시작했음을 의미합니다. 처음에는 일치하는 항목이 없습니다. 우리는 문자가 일치하는 것을 시도 소비로

[start] 
1 1 1 1 1 

, 상태는 (비트 0, 하단 비트 에 0을 이동하는) 왼쪽으로 이동되어 현재의 문자 테이블 엔트리와 OR-에디션. 첫 번째 문자는 a입니다. 왼쪽 OR-보내고 T[a]에하는 수 있습니다 시프 팅 :

 a 
1 1 1 1 0 

a의 현재 문자가 패턴의 일치를 시작할 수 있기 때문에, 보존으로 이동 된 0 비트. 다른 문자의 경우 비트는 1으로 설정되었습니다.

상태의 비트 0이 현재 0이라는 사실은 의 패턴을 현재 문자와 일치시키기 시작했음을 의미합니다. 계속 우리가 얻을 :

 a b 
1 1 1 0 1 

... 0 비트가 왼쪽으로 이동했기 때문에 - 그것의 생각 우리가 1 개 문자 전 패턴과 일치하는 시작했다는 말을 - 그리고 T[b] 말하고, 같은 위치에서 0있다 전에 1 문자와 일치시키기 시작하면 현재 위치에 b이 표시되는 것이 좋습니다.

a b d 
1 1 1 1 1 

d 어디에도 일치하지 않습니다. 모든 비트는 1으로 다시 설정됩니다.

a b d a 
1 1 1 1 0 

이전과 동일합니다.

a b d a b 
1 1 1 0 1 

이전과 동일합니다.

b d a b a 
1 1 0 1 0 

a 일치하는 문자가 2 자 전이나 현재 문자로 시작되면 좋습니다.

d a b a b 
1 0 1 0 1 

b은 1 ~ 3 자 전에 시작되면 좋습니다. 비트 3의 0는

a b a b a 
1 1 0 1 0 

우리는 거의 모든 패턴을 일치 한 을 ... 의미 ...하지만 다음 문자는 일치 전에 4 자 시작하면 좋지 않습니다 a이다. 그러나 더 짧은 성냥은 여전히 ​​좋을 수 있습니다.

b a b a b 
1 0 1 0 1 

여전히 좋아 보인다. 경기 전에 4 자 시작하면

a b a b c 
0 1 1 1 1 

마지막으로, c는 좋다. 0이 최상위 비트까지 모든 것을 만들었다는 사실은 우리가 일치한다는 것을 의미합니다.