(Boyer Moore) 보이어 무어 알고리즘 - 문자열 패턴 매칭

이번 포스팅에서 다룰 보이어 무어 Boyer Moore 알고리즘은 패턴 문자열의 오른쪽에서 왼쪽으로 비교하고, 불일치할 경우 정해진 이동거리만큼 점프해가며 비교하는 문자열 패턴 매칭 알고리즘입니다. 보이어 무어 알고리즘 시간 복잡도, 장단점, 파이썬 예제에 대해 알아보겠습니다.

 

보이어 무어 알고리즘이란? (Boyer Moore)

패턴 문자열의 오른쪽 끝 부분에서부터 왼쪽 앞부분 방향으로 문자를 비교하는 방식입니다.

보통 상황에서 문자열 앞부분보다 뒷부분이 불일치가 일어날 확률이 높다는 성질을 이용한 알고리즘입니다.

 

패턴 문자열에 대한 이동거리 skip 테이블을 만들어놓고 적절한 이동 거리만큼 점프해가며 비교합니다.

 

Boyer Moore 비교 과정

찾을 패턴 : bye

탐색할 문자열 : heyhibye

 

1. 패턴 문자열에 대한 이동거리 skip 테이블을 만듭니다. 패턴의 역순으로 이동 거리를 정합니다.

오른쪽 끝과 불일치하고, 패턴 내에 해당 문자가 있거나 없을 때 몇 칸을 점프해야 하는 지를 알려주는 테이블

문자	e	y	b	이외의 문자
이동 거리	0	1	2	3

2. 패턴의 오른쪽 끝 문자부터 이동거리 테이블을 이용하여 본문 문자열과 비교합니다.

보이어-무어-알고리즘

1. y와 e가 불일 치 한데, y는 패턴 내에 있는 문자이므로 이동거리 테이블을 참고하여 다음 비교를 위해 1칸 점프합니다.
2. h와 e가 불일치하는데, h는 패턴 이외의 문자이므로 3칸을 점프합니다.
3. y와 e가 불일 치 한데, y는 패턴 내에 있는 문자이므로 1칸 점프합니다.
4. e와 e가 일치하므로 바로 왼쪽 문자와 비교합니다.
5. y와 y가 일치하므로 바로 왼쪽 문자와 비교합니다.
6. b와 b가 일치하여 패턴이 일치하므로 검색을 종료합니다.

시간 복잡도와 장단점

• 시간 복잡도: 일반적으로 O(n)보다 적음
• 최악의 경우: O(mn)
• 찾으려는 문자열 패턴의 길이 m, 총 문자열 길이 n
• 장점: 원본 문자열을 모두 보지 않아도 검색 가능합니다.
• 단점: 구현이 비교적 복잡합니다.

 

보이어 무어 알고리즘 파이썬 예제

[Python] SW Expert Academy - 4864. 문자열 비교

[Python] SW Expert Academy - 4864. 문자열 비교

---

Boyer Moore 알고리즘 파이썬 예제와 Boyer Moore 알고리즘 시간 복잡도, 장단점, 비교 과정까지 알아보았습니다.