[알고리즘] 17. 보이어-무어 알고리즘

공부한 날짜: 2021. 11. 07

 

-(보이어-무어) 알고리즘: 문자열을 오른쪽에서 왼쪽으로 비교해 나가는 알고리즘, 패턴에 오른쪽 끝에 있는 문자가 불일치하고 이 문자가 패턴 내에 존재하지 않는 경우 패턴의 길이가 이동거리가 된다 

-종류 : 나쁜 문자 이동(Bad Character Shift), 착한 접미부 이동(Good Suffix Shift)

목적: 불일치가 발생할 때 최대의 효율로 이동하는 방법 정의(더 많이 움직일 수 있는 걸로 선택)

 

1. 나쁜문자 이동 (Bad Character Shift)

: 본문과 패턴 사이를 불일치 시키는 본문의 문자(나쁜 문자)를 이동시킨다 

 

-과정

(1) 패턴에서 나쁜 문자를 찾는다

(2) 찾아낸 패턴의 나쁜 문자의 위치가 본문의 나쁜 문자 위치와 일치하게 패턴을 이동시킨다 

(나쁜문자와 같은 문자가 패턴 내에서 두 개 이상 나오는 경우, 그 중에 가장 오른쪽에 있는 것을 본문의 나쁜문자에 맞추면된다)

 

2. 착한 접미부 이동 (Good Suffix Shift)

-착한 접미부: 패턴의 접미부와 일치하는 본문의 단어. 착한 접미부 이동을 하는 상황은 두 가지로 나뉜다

 

Case 1.

: 불일치가 일어났을 때 착한 접미부와 동일한 문자열이 패턴의 착한 접미부 왼쪽에 존재하는 경우 

 

Case 2.

: 착한 접미부가 패턴 안에 존재하지 않고 (착한 접미부의 접미부)가 (패턴의 접두부)와 일치하는 경우

 

-> 이런 이동을 하려면 사전에 가공된 정보(테이블)가 필요함 

패턴을 왼쪽에서 오른쪽으로 읽어나가면서 패턴에 있는 각 문자의 위치를 이 테이블에 기록해두면됨 

 

(1) 나쁜문자 이동 테이블 : 패턴에서 겹치는 문자 중 가장 오른쪽에 있는 문자의 인덱스를 테이블의 해당 문자 인덱스에 입력 

(A의 가장 오른쪽 위치 인덱스 3이면 테이블의 A 위치에 3입력)

패턴에 없는 문자는 -1 입력 

 

(2) 착한 접미부 이동 테이블: 이 테이블은 착한 접미부의 이동거리를 보관한다 

- 불일치가 일어났을 때 착한 접미부가 패턴안에 존재할 때

-

이해가 안가서 못하겠음