[파이썬] 문자열(String) 알고리즘 정리 - 보이어 무어(Boyer-moore) 알고리즘

보이어 무어(Boyer-moore) 알고리즘

• 참고 자료 링크
  https://www.cs.jhu.edu/~langmea/resources/lecture_notes/boyer_moore.pdf

정의

• Boyer-Moore 알고리즘은 패턴의 마지막 문자부터 역순으로 검사를 진행하면서 비교하는 알고리즘
• 기존의 방법이 왼쪽에서 오른쪽으로 했다면, 보이어-무어 알고리즘은 오른쪽에서 왼쪽으로 비교 (단, 이동(skip) 할 때는 왼쪽에서 오른쪽)
• 대표적으로 Bad Character Rule과 Good shuffix Rule
•  

반응형

BAD Character Rule

방법

• Step1

1. 문자열과 패턴을 오른쪽에서 왼쪽으로 문자가 일치하는지 확인
2. 문자열과 패턴의 문자가 b 부분에서 다른 것을 확인 (C / T)
3. 이때의 Bad character = C
4. 이후 패턴의 문자열 중 Bad Character가 있는지 확인 (여러개 일경우 가장 오른쪽에 있는 것을 선택)
5. 2번째에 존재하는 C의 위치로 패턴의 C를 일치 시킨다

• Step 2

1. 일치 시킨 C에서 부터 문자열 패턴을 오른쪽에서 왼족으로 문자 일치를 다시 확인
2. 문자열과 패턴의 문자가 b 부분에서 다른 것을 확인 (A/G)
3. 이때의 Bad character = A
4. 이후 패턴의 문자열 중 Bad character가 있는지 확인 (없다면 패턴의 문자열을 현재 A보다 뒤로 이동)

관련 코드

def skip_table(text, pattern):
    d = defaultdict(int)
    for letter in set(text):
        d[letter] = pattern.rfind(letter)
 
    return d
 
def boyer_moore(text, pattern):
 
    d = skip_table(text, pattern)
 
    m = len(pattern)
    n = len(text)
    i = m - 1
    j = m - 1
    result = []
 
    while i < n:
        if text[i] == pattern[j]:
            if j == 0:
               result.append(i+1)
            i -= 1
            j -= 1
        else:
            i = i + m - min(j, d[text[i]]+1)
            j = m - 1
 
    return -1

Good suffix rule

방법

• step 1

1. 문자열과 패턴을 오른쪽에서 왼쪽으로 일치하는지 확인
2. 불일치 지점이 발생했을 경우(T:C P:T) 일치한 지점(t)의 접미부와 대응되는 접두부를 찾아 패턴의 위치를 이동 시킴(뒤 TAC와 앞에 TAC 일치)

step 2.

1. 이동 시킨후 다시 오른쪽에서 왼쪽으로 일치하는지 확인
2. 불일치 지점이 발생했을 경우 (T:C, P:T) 일치한 지점(t)의 접미부와 대응되는 접두부를 찾음
3. 일치하는 지점 (t)과 대응되는 접두부의 길이가 다를 경우, 일부까지만 일치되는 지점을 찾음 (뒤의 TTAC와 앞에 TTAC 일치)

def preprocess_strong_suffix(shift, bpos, pat, m):

	i = m # 패턴의 길이
	j = m + 1
	bpos[i] = j

	while i > 0:
	# i-1 위치와 j-1의 위치가 일치 하지 않을 경우 우측부터 탐색
		while j <= m and pat[i - 1] != pat[j - 1]:
	# 앞에서 발생한 t의 패턴 P가 일치하지 않는 P와 다를경우, 건너 뛰는 것을 멈추고 i에서 j로 옮김.
			if shift[j] == 0:
				shift[j] = j - i
			j = bpos[j] # 다음 경계로 위치 변경
	#p[i-1]이 p[j-1]과 일치하는 부분을 찾을 경우, 그 부분을 시작 지점으로 저장
		i -= 1
		j -= 1
		bpos[i] = j


def preprocess_case2(shift, bpos, pat, m):
	j = bpos[0]
	for i in range(m + 1):
		# 패턴의 첫 문자의 위치를 이동하여 모든 인덱스를 shift[i] = 0인 지점으로 설정 
		if shift[i] == 0:
			shift[i] = j
		# 접미사가 bps[0]보다 짧아지고, 다음으로 넓은 테두리의 위치를 j 값으로 사용
		if i == j:
			j = bpos[j]
# good suffix rule이 있는 보이어-무어 알고리즘을 사용해 주어진 문자안에서 패턴 검색
def search(text, pat):

	s = 0
	m = len(pat)
	n = len(text)

	bpos = [0] * (m + 1)
	shift = [0] * (m + 1)

	preprocess_strong_suffix(shift, bpos, pat, m)
	preprocess_case2(shift, bpos, pat, m)

	while s <= n - m:
		j = m - 1
	# 패턴의 인덱스 j를 변경하는 패턴과 문자와 일치하는 s를 찾을때까지 감소
		while j >= 0 and pat[j] == text[s + j]:
			j -= 1
	# 만약 패턴이 현재 shift에 존재한다면, 인덱스 j는 루프 후 -1로 입력
		if j < 0:
			print("pattern occurs at shift = %d" % s)
			s += shift[0]
		else:
			s += shift[j + 1]

if __name__ == "__main__":
	text = "ABAAAABAACD"
	pat = "ABA"
	search(text, pat)

개인 의견

코딩 테스트때 특정 문자열을 찾아야 한다면 find()를 믿고 쓰는게 더 빠르고 메모리 효율적

Good suffix rule의 경우 원리는 알겠지만 코드 구현에 대해선 이해하기 어려움

Good suffix rule의 코드 같은 경우 구글에서 한글로 찾아보다가 안보여서 영어로 검색해서 찾아온걸 번역해서 옮긴건데 사실 무슨말인지 잘모르겠다. 대충 이런게 있다 정도로 이해하거나 나중에 따로 디테일하게 좀 더 찾아볼 필요가 있을거같다