[python] 보이어 무어 알고리즘 (Boyer Moore Algorithm)

보이어 무어 알고리즘은 텍스트에서 특정한 패턴(텍스트)을 탐색하는 알고리즘입니다.

또한 오른쪽에서 왼쪽으로 스트링 탐색을 진행합니다.

 

예를 들어 
텍스트 STRING STARTING CONSISTING에 대하여 패턴 STING을 탐색하는 수행과정을 본다면

먼저 STING이라는 패턴에 대한 skip 배열을 구하여야 합니다.
* STING 일 때의 skip 배열

G	N	I	T	S	다른 모든 문자
0	1	2	3	4	5

위와 같은 skip 배열의 숫자는 만약 텍스트가 일치하지 않을 경우 얼마만큼 건너뛰어야 하는지 표시한 것입니다.

* 오른쪽에서 왼쪽으로 탐색을 진행하기 대문에 먼저 N과 G를 비교해보면, 서로 다른 문자임을 알 수 있습니다

위에 N 이란 단어는 skip 배열에서 1이란 숫자를 표시하고 있으므로 한 칸을 뛰도록 합니다. 

1칸 이동 후

오른쪽부터 탐색해 봤을 때, G N I는 순서대로 일치하고 R과 T가 다른 것을 알 수 있습니다. 따라서 R은 skip 배열에서 정의하고 있지 않기 때문에 다른 모든 문자로 보고 5칸을 이동하도록 합니다.

5칸 이동 후

5칸 이동 후 탐색했을 때 R과 G 가 다르므로 또 R (다른 모든 문자) 값 5칸만큼 이동하도록 합니다

계속 이동해주도록 합니다.

I 값은 skip 배열에서 2로 정의되어 있기 때문에 2칸을 이동해 주도록 합니다.

T값은 3으로 정의되어 있으니 3만큼 이동하도록 합니다

탐색 완료

이제 보이어 무어 알고리즘을 파이썬으로 구현을 합니다

먼저 skip 배열을 만들어주는 initSkip() 함수를 구현합니다

def initSkip(p):
    NUM = 27  # 알파벳 수
    M = len(p) # 패턴의 길이
    skip = [M for i in range(NUM)] #skip 함수를 모두 M값으로 초기화
    for i in range(M):
        skip[ord(p[i]) - ord('A')] = M - i - 1 
    return skip # skip 배열 반환

print(initSkip("ATION")) # 임시로 ATION 이란 패턴을 입력

저는 여기서 skip[ord(p[i]) - ord('A')] = M - i - 1을 잘 이해하지 못해서 천천히 살펴봤습니다.

먼저, ord 함수는 특정 문자를 아스키 값으로 변환하는 함수입니다.
p [] 배열에는 A T I O N (문자열)이 순서대로 들어오게 됩니다.
여기서 ord 함수를 이용하여 아스키 값으로 변환하지 않는다면 문자에 정수 값을 대입하는 결과가 발생합니다
또 ord('A') 를 빼주는 이유는 skip 배열의 번호가 0번부터 시작되기 때문에 맞춰주기 위함입니다.

실행 결과

다음으로는 전체적인 보이어 무어 알고리즘 코드입니다. 

def BM(p, t):
    M = len(p)
    N = len(t)
    skip = initSkip(p)

    i = M-1
    j = M-1

    while j >= 0:
        while t[i] != p[j]:
            k = skip[ord(t[i]) - ord('A')]
            if M - j > k:
                i = i + M - j
            else:
                i = i + k
            if i >= N:
                return N
            j = M - 1
        i = i-1
        j = j-1
    return i+1

print(BM("ATION","VISOINQUESTIONONIONCAPTIONGRADUATION"))

* 이 코드는 공백처리를공백 처리를 하지 못한 코드입니다. 아직 공백 처리를 어떻게 해야 할지 몰라서 텍스트가 붙어져 있다는 가정하에 짰습니다.

* 아직 공부중인 학생이라 틀린 부분이 있으면 말씀해주세요~!