Algorithm. 문자열 - 문자열 매칭

1. 문자열 처리

예제) 다음 중 x안에 y가 존재하는지 찾아보자.

 

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

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

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

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

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

# t : 텍스트
# p : 패턴
# N : 텍스트의 길이
# M : 패턴의 길이

def BruteForce(t, p):
    N = len(t); M = len(p)
    i = 0 # 텍스트 인덱스
    j = 0 # 패턴 인덱스
    while i < N and j < M:
    	if t[i] != p[i]: # 다르면
            i = i - j # i를 시작 위치로 되돌린다.
            j = -1 # j를 -1로 설정
        i += 1
        j += 1
    if j == M : # 패턴을 찾음
        return i - M # 패턴이 시작하는 위치를 반환
    else : return -1

최악의 경우 텍스트의 모든 위치에서 패턴을 비교해야 하므로 O(MN)이 된다.

 

4. 카프-라빈(Karp-Rabin) 알고리즘

• 문자열 검색을 위해 해시 함수 이용
• 패턴의 해시 값과 텍스트 내의 패턴의 길이 만큼의 문자열에 대한 해시 값을 비교한다.
• 최악의 사간 복잡도는 O(MN)이지만 평균적으로 선형에 가까운 빠른 알고리즘이다.

 

패턴의 해시값 계산

• 각 자리수에 자리 값을 곱하여 더한다
• 4*10^3 + 3*10^2 + 2*10 + 1 = 4321
• 패턴 4 3 2 1의 해시값은 정수 값 4321이 된다.

 

• 텍스트의 문자열에서 해시값을 구할 때
• 새로 추가되는 문자와 그전에 읽었던 값을 이용하여 해시 값을 구한다.
• 이전 해시 값을 이용해서 다음 해시 값을 구한다.

 

고려사항

• 처음 해시 값을 구할 때는 패턴 길이 만큼 읽어서 구한다.
• 패턴의 길이가 커지면 일정 자리수를 맞추기 위해 모듈러 연산을 사용한다.
• 해시 값이 일치해도 실제 문자열이 일치하는지 검사해야한다.

5. KMP(Knuth-Morris-Pratt) 알고리즘

 

# 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 : 텍스트
# p : 패턴
# N : 텍스트의 길이
# M : 패턴의 길이
# next : 불일치가 발생하면 이동할 위치를 저장

def KMP_Search(t, p, next):
    N = len(t); M = len(p)
    i = 0; j = 0
    
    while i < N:
    	while j >= 0 and t[i] != p[j]
            j = next[j]
        
        i += 1; j += 1
        if j == M
            return i - j;
        return -1

6. 보이어-무어 알고리즘

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

 

시간 복잡도 비교