[Algorithm] 패턴 매칭 알고리즘 - KMP, 보이어-무어

고지식한 패턴 검색 알고리즘 (Brute Force)

• 본문 문자열을 처음부터 끝까지 차례대로 순회하면서 패턴 내의 문자들을 일일이 비교
• 시간 복잡도
  • O(MN) -> 최악의 경우 텍스트의 모든 위치 패턴 비교해야하므로

p = 'is' # 찾을 패턴 (target) 
M = len(p) 
t = 'This is a book~!' # 전체 텍스트 
N = len(t) 

def BruteForce(p, t):
    i = 0 # t의 인덱스
    j = 0 # p의 인덱스 
    
    while j < M and i < N: 
        if t[i] != p[j]:
            i -= j
            j = -1 
        i += 1 
        j += 1 
        
    if j == M: return i - M # 검색성공 
    else: return -1 # 검색실패

 

카프-라빈 알고리즘

• 고지식한 패턴 검색 알고리즘과 같이 하나씩 문자를 이동하며 일치하는지 확인하지만, 해시 값을 사용
• 시간 복잡도 : Θ(n)

 

KMP 알고리즘

• 고지식한 패턴 알고리즘의 시간 복잡도를 더 줄이는 방법?
• 불일치가 발생한 텍스트 스트링의 앞 부분에 어떤 문자가 있는지를 미리 알고 있으므로, 불일치가 발생한 앞 부분에 대하여 다시 비교하지 않고 매칭 수행
• 매칭에 실패했을 때 돌아갈 곳을 준비
• 패턴을 전처리하여 배열 next[M]을 구해서 잘못된 시작을 최소화
  • next[M] : 불일치가 발생했을 경우 이동할 다음 위치
• 이 경우 시간 복잡도 : O(M+N)

 

 

보이어-무어 알고리즘

• 오른쪽에서 왼쪽으로 비교
• 패턴의 오른쪽 끝 문자가 불일치하고 이 문자가 패턴 내에 존재하지 않는 경우, 이동 거리는 패턴의 길이 만큼
• 앞의 두 매칭 알고리즘은 텍스트 문자열의 문자를 적어도 한 번씩 훑음(최선의 경우에도 Ω(n))
• 보이어-무어 알고리즘은 텍스트 문자를 다 보지 않아도 됨 (패턴의 오른쪽부터 비교)
• 최악의 경우 수행시간 : Θ(mn)
• 입력에 따라 다르지만 일반적으로 Θ(n)보다 시간이 덜 든다.

 

패턴 매칭 알고리즘 이해하기

http://whocouldthat.be/visualizing-string-matching/

Visualizing String Matching Algorithms