2025.04.16
TIL(TODAY I LEARN)
-
오늘한 내용 : 문자열 알고리즘 - Trie, Kmp, 보이어-무어
-
WEEK05: C Pointer(&, * 연산자), 동적 메모리 할당, Linked List, Stack, Queue, Binary Tree, Binary Search Tree, 동적 프로그래밍, 그리디 알고리즘
-
보이어 무어 알고리즘의 Good Suffix Rule이 너무 어렵다.
trie (트라이) 알고리즘
트라이는 문자열을 트리 구조로 저장하는 자료구조.
특히 여러 개의 문자열 집합에서 공통 접두사 처리에 매우 강력.
| 특징 | 설명 |
|---|---|
| 구조 | 문자 하나하나를 노드로 가진 트리 형태 |
| 목적 | 빠른 문자열 검색, 자동완성, 사전 구성 등 |
| 시간 복잡도 | 검색/삽입/삭제 = O(문자열 길이) |
["apple", "app", "apricot", "bat"]
(root)
/ \
a b
/ \
p a
/ \ \
p r t
/ \
l i
/ \
e c
\
o
\
t| 용도 | 예시 |
|---|---|
| 문자열 사전 | T9, 자동완성, 사전 검색 |
| 문자열 필터링 | 금지어 필터 |
| 접두사 기반 그룹화 | 전화번호, 도메인 주소 등 |
class TrieNode:
def **init**(self):
self.children = {}
self.is_end = False # 단어 끝인지 표시KMP 알고리즘
KMP는 패턴 내부의 구조를 이용해서 불일치가 생겨도, 이미 확인한 문자를 다시 비교하지 않게 하는 알고리즘.
Prefix Table (LPS 배열)
패턴 : a b c a b d
| 인덱스 | 부분 문자열 | 접두사 = 접미사 | 길이(LPS) |
|---|---|---|---|
| 0 | a | 없음 | 0 |
| 1 | ab | 없음 | 0 |
| 2 | abc | 없음 | 0 |
| 3 | abca | a = a | 1 |
| 4 | abcab | ab = ab | 2 |
| 5 | abcabd | 없음 | 0 |
형님, 이거 이해되셨으면 다음엔 이걸로 KMP 검색 흐름도 직접 해보실래요?
lps[i] = 이전까지 일치한 길이를 얼마나 "재활용"할 수 있는지
비교 중에 불일치가 발생한 패턴 인덱스[j]
이동량 = 현재 j+1 - lps[ j ]
- 패턴의 0 ~ j-1까지는 일치했음
pattern[j]에서 불일치 발생
보이어-무어 알고리즘(Boyer-Moore algorithm)
문자열 검색에 사용되는 알고리즘
- 불필요한 것은 건너뛰고 검색하자
- 검색 대상이 길고, 찾을 패턴이 짧을 때 효과적
- 뒤에서부터 비교하며, 필요 없으면 건너뛰기
시간 복잡도
- 최악의 경우: O(n × m) (매우 드물게 발생)
- 평균적인 경우: O(n) 에 가까움 → 매우 빠름
두 가지 핵심 규칙
1. Bad Character Rule (나쁜 문자 규칙)
- 비교 중 불일치한 문자 하나에 대해
- 패턴 내 가장 마지막에 등장한 위치를 기준으로 패턴을 앞으로 점프시킴
- 많이 알려진 그 skip 테이블이 이 규칙용임
2. Good Suffix Rule (좋은 접미사 규칙)
- 패턴 오른쪽에서 일치했던 접미사가 있음
- 이 접미사가 앞쪽에 다시 나오는 위치나 패턴의 접두사와 겹치는 부분을 찾아 멀리 점프함
- 훨씬 더 똑똑하고 강력하지만, 구현이 복잡함
Bad Character Rule 이용한 정석 형태
SKIP 배열
- skip의 값은 ’각 문자의 마지막 등장 인덱스'
- 중복된 문자 존재 시 → 마지막 등장 인덱스 저장
ex) 패턴 “ABCAD”
| 문자 | A | B | C | D | 다른 모든 문자 |
|---|---|---|---|---|---|
| skip 값 | 3 | 1 | 2 | 4 | -1 |
| 문자 | p | h | o | n | e | 다른 모든 문자 |
|---|---|---|---|---|---|---|
| skip 값 | 0 | 1 | 2 | 3 | 4 | -1 |
불일치 시 이동량(Bad Character Rule)
이동량 = max(1, 현재 비교 중인 패턴 인덱스 - last[불일치한 문자])
패턴의 시작 비교 위치
텍스트 시작 비교 위치 = 패턴 길이 - 1
1) a b c a n e c z b p h o n e
p h o n e
문자열 / 패턴
n과 e 비교 -> 불일치
문자열의 n의 값 = 3
이동량 = max(1,4-3) = 1 칸 이동
2) a b c a n e c z b p h o n e
p h o n e
e와 e 비교 -> 일치
n과 n 비교 -> 일치
a와 o 비교 -> 불일치
문자열의 a, skip 배열에 존재 x
이동량 = max(1,2-(-1)) = 3 칸 이동
3) a b c a n e c z b p h o n e
p h o n e
b와 e 비교 -> 불일치
문자열의 b, skip 배열에 존재 x
이동량 = max(1,4-(-1)) = 5 칸 이동
3) a b c a n e c z b p h o n e
p h o n e
e와 e 비교 -> 일치
n과 n 비교 -> 일치
o와 o 비교 -> 일치
h와 h 비교 -> 일치
p와 p 비교 -> 일치
검색 완료!
뒤에 문자열이 더 있다면 패턴 길이만큼 점프 후
계속 검색을 수행함보이어-무어-호스풀 알고리즘(Boyer-Moore-Horspool Algorithm)
- Bad Character Rule만 사용한 더 단순화된 버전
SKIP 배열
- skip의 값은 '패턴 문자열의 길이 - 각 패턴 문자의 인덱스 - 1'
| 문자 | p | h | o | n | e | 다른 모든 문자 |
|---|---|---|---|---|---|---|
| skip 값 | 4 | 3 | 2 | 1 | 0 | 5 |
1) a b c a n e c z b p h o n e
p h o n e
문자열 / 패턴
n 과 e 비교 -> 불일치
문자열의 n, skip 배열에 존재 -> 1 칸 이동
2) a b c a n e c z b p h o n e
p h o n e
e와 e 비교 -> 일치
n과 n 비교 -> 일치
a와 o 비교 -> 불일치
문자열의 a, skip 배열에 존재 X -> 5 칸 이동
3) a b c a n e c z b p h o n e
p h o n e
h와 e 비교 -> 불일치
문자열의 h, skip 배열에 존재 -> 3 칸 이동
4) a b c a n e c z b p h o n e
p h o n e
e와 e 비교 -> 일치
n과 n 비교 -> 일치
o와 o 비교 -> 일치
h와 h 비교 -> 일치
p와 p 비교 -> 일치
검색 완료!
뒤에 문자열이 더 있다면 패턴 길이만큼 점프 후
계속 검색을 수행함Good Suffix Rule 을 적용한 보이어-무어
-
Good Suffix?
- 패턴의 문자 일부와 일치하는 텍스트의 부분 문자열
-
3가지 경우 존재
- Case 1. Good Suffix가 패턴의 다른 곳에도 있는 경우
- Case2. Good Suffix의 일부만 패턴의 시작 부분에 있는 경우
- Case3. Good Suffix가 패턴의 다른 곳에 없는 경우
- Case 1. Good Suffix가 패턴의 다른 곳에도 있는 경우
- 위 세가지 경우를 고려 후 이동량 = max(bad character heuristics, good suffix heuristics)
- Good Suffix는 이해와 구현이 어려움.
shift 테이블 예시 만들기
패턴: a b c a b
길이 = 5
접미사 후보군:
1. b
2. a b
3. c a b
4. b c a b
5. a b c a b접미사 길이 i | 접미사 | 이동 거리 shift[i] | 케이스 종류 | 설명 |
|---|---|---|---|---|
| 0 | (없음) | 5 | Case 3 | 접미사 없음 → 전체 밀기 |
| 1 | b | 3 | Case 1 | b가 앞에 있음 (index 1) |
| 2 | ab | 3 | Case 1 | ab가 앞에 있음 (index 0-1) |
| 3 | cab | 3 | Case 2 | cab 가 접두사 일부ab랑 매치 가능 |
| 4 | bcab | 5 | Case 3 | bcab는 패턴 내 없음 |
| 5 | abcab | 5 | 특수 처리 | 검색 끝 다음 문자열 이동 |
이걸 보고 각 접미사가 패턴 내 앞부분에 다시 등장하는지 확인
→ 등장한다면 해당 위치로 점프 → Case 1
→ 없다면 접두사와 맞는 부분 있는지 확인 → Case 2
→ 그것도 없다면 전체 밀기 → Case 3
