보이어 무어 알고리즘
보이어-무어 알고리즘은 ‘이동’ 은 왼쪽에서 오른쪽으로 하지만 문자열을 오른쪽에서 왼쪽으로 비교해 나간다.
•
패턴에 오른쪽 끝에 있는 문자가 불일치하고 이 문자가 패턴 내에 존재하지 않는 경우, 이동거리는 무려 패턴의 길이 만큼 이동한 뒤 비교를 재개한다.
INDEX : 0 1 2 3 4 5 6 7 8
TEXT : B A A C A B B A C ...
| (불일치)
PATTERN : B B A B
(패턴의 길이만큼 -> 이동)
NEXT : . . . . B B A B
C
Bad Character Shift (나쁜 문자 이동)
본문과 패턴 사이를 불일치 시키는 나쁜 문자를 이동시킨다.
1.
패턴에서 나쁜 문자를 찾는다.
2.
찾아낸 패턴의 나쁜 문자의 위치가 본문의 나쁜 문자 위치와 일치하게 패턴을 이동시킨다.
// 1. 패턴의 가장 오른쪽 문자가 불일치 함.
INDEX : 0 1 2 3 4 5 6 7 8
TEXT : B A A B A B B A C ...
| (불일치)
PATTERN : B B A C
// 2. 패턴 내에서 나쁜 문자를 찾음 (본문과 불일치 하는 문자)
INDEX : 0 1 2 3 4 5 6 7 8
TEXT : B A A B A B B A C ...
| (불일치)
PATTERN : B B A C
// 3. 본문과 패턴의 불일치 문자가 같은 위치에 오도록 패턴을 이동
INDEX : 0 1 2 3 4 5 6 7 8
TEXT : B A A B A B B A C ...
| (일치)
PATTERN : . . B B A C
// 불일치 문자 B가 패턴에서 0, 1 번에서 발견 되었으나 발견된 문자중 1번 문자가 가장 오른쪽에 있으므로 패턴의 1번에 있는 B 문자를 본문의 나쁜 문자의 위치에 일치하도록 패턴을 이동시킨다.
C
나쁜 문자의 이동이 실패하는 경우 (착한 접미부 이동)
패턴이 오른쪽이 아니라 왼쪽으로 이동하는 경우
Good Suffix Shift (착한 접미부 이동)
보이어-무어 알고리즘은 패턴을 오른쪽에서부터 비교하기 때문에 패턴에는 본문과 일치하는 접미부가 나타난다.
이렇게 일치하는 접미부를 가리켜 착한 접미부 (Good Suffix) 라고 한다.
착한 접미부 이동 상황 1
불일치가 일어났을 때 착한 접미부와 동일한 문자열이 패턴의 착한 접미부 왼쪽에 존재하는 경우
INDEX : 0 1 2 3 4 5 6 7 8 ...
TEXT : B A A A B B B A C ... (착한 접미부 A B)
| . . (불일치 발생)
PATTERN : A B B A B (착한 접미부와 일치하는 문자열)
NEXT : . . . A B B A B
패턴의 착한 접미부와 일치하는 부분을 착한 접미부에 일치하도록 이동
C
착한 접미부 이동 상황 2
INDEX : 0 1 2 3 4 5 6 7 8 ...
TEXT : B A A A B B B A C ... (착한 접미부 A A B)
| . . . (불일치 발생)
PATTERN : A B A A B
패턴에 착한 접미부와 일치하는 부분이 없음
C
INDEX : 0 1 2 3 4 5 6 7 8 ...
TEXT : B A A A B B B A C ... (착한 접미부 A A B의 접미부 AB)
| . . . (불일치 발생)
PATTERN : A B A A B
패턴에 착한 접미부의 접미부 AB는 패턴의 접두부와 일치한다.
INDEX : 0 1 2 3 4 5 6 7 8 ...
TEXT : B A A A B B B A C ... (착한 접미부 A A B의 접미부 AB)
PATTERN : . . . A B A A B
패턴의 착한 접미부와 일치하는 부분을 착한 접미부에 일치하도록 이동
C
