일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 |
- 코틀린
- python
- 공부일지
- 시나공
- 프로그래머스
- java
- programmers
- 데이터베이스
- 문제풀이
- 스프링
- C++
- softeer
- BFS
- 자바
- 알고리즘
- 코딩교육봉사
- MYSQL
- 정보처리산업기사
- 백준 알고리즘
- CJ UNIT
- 소프티어
- SW봉사
- 파이썬
- kotlin
- 백준
- SQL
- 백준알고리즘
- 코딩봉사
- 1과목
- 회고
- Today
- Total
JIE0025
[문자열 매칭] 보이어무어(Boyer-Moore) - Good Suffix Heuristics 본문
✅ 개요
문자열 매칭 알고리즘 중 보이어무어에 대해 알게 된지 2일차...
보이어무어를 제대로 알기 위해 핵심 방식 2가지를 이해해야하는데,
어제는 나쁜문자이동방식을 공부했었다.
https://jie0025.tistory.com/537
오늘은 착한접미부이동방식에 대해 공부를 해보자.
✅ 보이어무어 (Boyer-Moore)
어떤 문자열에서 찾고자하는 패턴을 찾을때 효율적으로 처리할 수 있는 알고리즘
✍️ 보이어무어의 핵심
- 나쁜 문자 이동 방식 (Bad Character Method)
- 착한 접미부 이동 방식 (Good Suffix Method)
✍️ 보이어무어는 Skip 배열을 만들어둔다.
문자가 일치하지 않을 경우에 얼마만큼 이동시킬지 저장하는 배열
⏺ 착한 접미부 이동 방식 (Good Suffix Method)
😵 나쁜문자이동이 불가능한 케이스
어제 공부한 나쁜문자 이동방식에서 한가지 문제가 발생한다.
1. 만약 나쁜 문자를 발견하고
2. 그 문자가 패턴에 존재하는데
3. 패턴에 존재하는 나쁜문자가 이미 오른쪽에 존재하는 경우
나쁜문자이동방식을 활용할 수 없게 된다.
아래 예시를 보자.
text : BAABABBAC에서
pattern : ABAB를 찾고자
나쁜문자이동방식을 처리했을때
Text | B | A | A | B | A | B | B | A | C |
Pattern | A | B | A | B |
1) A와 B에서 불일치가 발생하여, 나쁜문자는 A가 된다.
2) Skip Table에서는 A의 위치를 가장 우측에 가까운 문자 기준으로 저장하기 떄문에,
이미 Pattern에 존재하는 이동시킬 A의 위치가 더 오른쪽에 존재한다.
😉 착한 접미부 이동
나쁜 문자 이동 방식의 경우 1칸만 이동하는 경우도 발생하는데,
착한접미부 이동을 사용하면, 그런 상황에서 최대 이동 거리를 선택할 수 있다.
나쁜 문자가 발생했다면, 그 오른쪽의 문자들은 일치했다는 것이다.
이 일치한 문자들을 착한 접미부라고 한다.
패턴에서 착한접미부와 일치하는게 존재하는지 찾는다.
✔️ 이때 존재하면, 착한 접미부와 일치시켜 오른쪽으로 Shift해주면 된다.
1️⃣ 착한접미부와 일치하는 문자열이 패턴에 존재하는지 찾음
Text | B | A | A | B | A | B | B | A | C |
Pattern | A | B | A | B |
2️⃣ 오른쪽으로 shift : 착한접미부와 자리가 일치하도록
Text | B | A | A | B | A | B | B | A | C |
Pattern | A | B | A | B |
3️⃣ 다시 우측부터 확인하고, 패턴이 모두 일치하는것을 발견
Text | B | A | A | B | A | B | B | A | C |
Pattern | A | B | A | B |
✔️ 만약 존재하지 않는다면?
✍️ 착한 접미부의 문자열을 왼쪽부터 하나씩 줄여가며 반복해서 조사한다.
Text : BCABCAABC이고,
Pattern은 CAABCA라고 가정
ABCA가 착한 접미부
C와 A에서 불일치가 발생
Text | B | C | A | B | C | A | A | B | C |
Pattern | C | A | A | B | C | A |
착한접미부보다 왼쪽에서 ABCA를 발견할 수 없다. -- CA
착한접미부의 왼쪽한개 (A) 를 지운다
BCA역시 발견할 수 없다.
Text | B | C | A | B | C | A | A | B | C |
Pattern | C | A | A | B | C | A |
착한접미부의 왼쪽한개 (B) 를 지운다
CA를 발견했다.
Text | B | C | A | B | C | A | A | B | C |
Pattern | C | A | A | B | C | A |
CA를 착한접미부 CA와 맞추어 Shift한다.
Text | B | C | A | B | C | A | A | B | C |
Pattern | C | A | A | B | C |
✍️ 만약 위의 과정을 했는데도 완전 불일치라면?
패턴의 길이만큼 이동시킨 후 비교한다.
아래와 같은 상황으로 변경시키면
위의 상황과는 다른, 완전 불일치가 일어난다.
Text : BCABCAABC
Pattern은 EDABC
ABC가 착한 접미부
C와 D에서 불일치가 발생
착한접미부보다 왼쪽에서 ABC 를 발견할 수 없다. -- 왼쪽에는 ED만 있다.
Text | B | C | A | B | C | A | A | B | C |
Pattern | E | D | A | B | C |
착한접미부의 왼쪽한개 (A) 를 지운다
BC 를 발견할 수 없다. - EDA
Text | B | C | A | B | C | A | A | B | C |
Pattern | E | D | A | B | C |
착한접미부의 왼쪽한개 (B) 를 지운다
C 를 발견할 수 없다. - EDAB
Text | B | C | A | B | C | A | A | B | C |
Pattern | E | D | A | B | C |
결국 완전불일치가 일어났으므로, Pattern의 길이만큼 우측으로 shift하고
다시 탐색을 시작하게 된다.
Text | B | C | A | B | C | A | A | B | C ... |
Pattern | E | D | A | B ... |
오늘은 착한 접미부 방식까지 공부를 했다.
보이어무어의 두가지 방식이 얼마나 문자열 탐색을 효율적으로 할 수 있는지 이해할 수 있는 계기가 되어서 좋다!
References
https://yoongrammer.tistory.com/95
'알고리즘' 카테고리의 다른 글
[문자열 매칭] 보이어무어(Boyer-Moore) - Bad Character Heuristic (0) | 2023.06.02 |
---|---|
[문자열 매칭] KMP (knuth-morris-prett) 동작방식,수도코드 (0) | 2023.06.01 |
[Python] 파이썬 코딩테스트대비용 복습 모음 (0) | 2023.04.15 |
[DP] 냅색 알고리즘 (0) | 2023.04.09 |
[기록용] 서브쿼리 이용하기 (MySQL) (0) | 2023.02.11 |