Algorithm_06

패턴 매칭

패턴 매칭에 사용되는 알고리즘들

• 고지식한 패턴 검색 알고리즘
• 카프-라빈 알고리즘
• KMP 알고리즘
• 보이어-무어 알고리즘

고지식한 알고리즘(Brute Force)

• 본문 문자열을 처음부터 끝까지 차례대로 순회하면서 패턴 내의 문자들을 일일이 비교하는 방식으로 동작

p = "is" # 찾을 패턴
t = "This is a book ~ !" # 전체 텍스트
M = len(p) # 찾을 패턴의 길이
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 = i - j
            j = -1
         i = i + 1
         j = j + 1
     if j == M : return i - M # 검색성공
     else: return -1 # 검색실패

알고리즘 시간 복잡도

• 최악의 경우 시간 복잡도는 O(MN)이 됨.(전체 순회)
• Ex) 10,000(문자열 전체 길이) * 80(찾고자하는 패턴 길이) = 800,000 번의 비교

KMP 알고리즘

• 불일치가 발생한 텍스트 스트링의 앞 부분에 어떤 문자가 있는지를 미리 알고 있으므로, 불일치가 발생한 앞부분에 대하여 다시 비교하지 않고 매칭을 수행

• 패턴을 전처리하여 배열 next[M]을 구해서 잘못된 시작을 최소화 함

• 시간 복잡도 : O(M+N)

• 매칭 실패시 되돌아 갈 곳을 기억해둔다.

보이어-무어 알고리즘

• 맨 오른쪽에서 왼쪽으로 비교
• 대부분의 상용 소프트웨어에서 채택하고 있는 알고리즘
• 보이어-무어 알고리즘은 패터에 오른쪽 끝에 있는 문자가 불일치 하고 이 문자가 패턴 내에 존재하지 않는 경우, 이동 거리는 무려 패턴의 길이 만큼이 된다.

문자열 매칭 알고리즘 비교

• 찾고자 하는 문자열 패턴의 길이 : m, 총 문자열 : n

  고지식한 패턴	카프-라빈	KMP
  O(mn)	Θ(n)	Θ(n)

• 보이어 - 무어 알고리즘

  • 최선의 경우 : Ω(n)
  • 최악의 경우 : Θ(mn)
  • 평균적으로 Θ(n) 덜 걸린다