9. 문자열 매칭 (패턴 매칭)

문자열 매칭(패턴 매칭)

텍스트 문자열 t에 패턴 문자열 p 포함 여부를 찾는것

 

알고리즘

• 부르트 포스 검색 알고리즘 O(MN)
• 카프-라빈 알고리즘 O(M+N)
• KMP 알고리즘 O(M+N)
• 보이어-무어 알고리즘 O(N), 최악 O(MN)
• 파이썬의 패턴 매칭 

---

부르트 포스 검색 알고리즘

텍스트 문자열을 처음부터 끝까지 차례대로 순회하면서 일일이 비교

알고리즘

# t : 텍스트
# N : 텍스트의 길이 

def BruteForce(t, p):
    N = len(t)
    M = len(p)
    i, j = 0, 0
    while i<N and j<M:
        if t[i] != p[j]:
            i -= j   # 원래 시작 위치로 되돌림
            j = -1
        i += 1
        j += 1
    if j==M:
        return i - M   # 패턴의 시작 위치
    else:
        return -1

시간 복잡도

최악의 경우 모든 위치에서 패턴을 비교해야 하므로 O(MN)이 됨

 

카프-라빈 알고리즘

문자열 검색을 위해 해시 함수 사용

패턴의 해시 값과 텍스트 내의 패턴의 길이 만큼의 문자열에 대한 해시 값을 비교

최악의 시간 복잡도는 O(MN)이지만 평균적으로는 선형에 가까운 바른 속도를 가지는 알고리즘

아이디어

1. 일반 문자열 대신 숫자열로 생각해보자.
   

   

2. 패턴의 해시 값 계산
   

   

3. 찾고자 하는 문자열에서 4자리씩 해시값 계산
   

   

   4. 텍스트 문자열에서 다음 해시값을 구할 경우

   

고려할 사항

• 처음 해시 값을 구할 때는 찾고자 하는 문자열에서 패턴 길이만큼 읽어서 구함
• 패턴의 길이가 커지면 길이를 일정 자리수로 맞추기 위해 모듈러 연산 진행
• 해시 값이 일치하면 실제 문자열이 일치하는지 검사

 

KMP 알고리즘

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

불일치가 발생하면 다음 비교할 위치를 미리 계산해서, 불필요한 시작 최소화

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

아이디어

 

매칭이 실패했을 때 돌아갈 곳 계산하기

알고리즘 코드

# p : 패턴, M : 패턴의 길이
# next : 불일치가 발생하면 이동할 위치를 저장
def KMP_Preprocess(p, next):
    M = len(p)
    i=0; j=-1
    
    while i<M:
        next[i] = j
        while j>=0 and p[i] != p[j]:
            j = next[j]
            
        i+=1; j+=1


# t : 텍스트, N : 텍스트의 길이
def KMP_Search(t, p, next):
    N = len(t)
    M = len(p)
    i, j = 0, 0
    
    while i < N:
        while j >= 0 and t[i] != p[j]:
            j = next[j]
        if j == M-1:            
            j = next[j]
        else:
            i+=1;j+=1

    return cnt

 

 

보이어-무어 알고리즘

패턴의 오른쪽 끝에서 왼쪽으로 비교

패턴의 오른쪽 끝에 있는 문자가 불일치하고 이 문자가 패턴 내에 존재하지 않는 경우 이동 거리는 패턴 길이 만큼 됨

아이디어

텍스트 b와 패턴 r이 다르고, b가 패턴 안에 없으므로 5칸을 한번에 점프함

만약, 패턴내에 존재한다면? 패턴에서 일치하는 문자를 찾아서 서로 일치되도록 점프함

예제

 

파이썬의 패턴 매칭

in

pattern in text

find() > 보이어-무어 알고리즘

text.find(pattern)