보이어-무어 알고리즘(문자열 검색, Python)

보통 문자열이 일치하는 방식을 생각하면 아래와 같이 나옵니다.

def pattonmatch(a, b):
    for i in range(len(b) - len(a) + 1):
        for j in range(len(a)):
            if b[i+j] != a[j]:
                break
        else:
            return i
    return -1

 

하나씩 비교하며 틀릴시 옆으로 쉬프트하여 비교합니다.

시간복잡도는 O(N^2)이 됩니다.

---

문자열 탐색범위가 작다면 괜찮지만 탐색범위가 커진다면 위와 같은방식은 부담스럽습니다.

그래서 문자열 탐색 알고리즘을 사용하게 되는데

보통 KMP와 보이어-무어 알고리즘을 사용한다고 합니다.

---

이번에는 보이어-무어 알고리즘에 대해 포스팅하겠습니다.

보이어-무어 알고리즘의 특징:

1. 오른쪽 끝부터 왼쪽으로 비교한다.

2. (중요)뒤에서부터 비교하다가 틀리는(다른) 부분이 나온다면 마지막글자와 

   찾는문자열중 일치하는 글자가 있는곳까지 쉬프트를 합니다.

3.   2. 에서일치하는 부분이 하나도 없다면 찾는 문자열의 길이만큼 이동합니다.

(따라서 찾는 문자열이 길다면 그만큼 건너뛰는 길이가 깁니다.)

4. 현재 상용프로그램에서 많이 채용하고있는 방식입니다.

---

예시:

abdefabc 라는 문자열에서

abc라는 문자열을 찾을때

(그림으로 나중에 넣겠습니다.)

abdefabc

abc

와 d와c를 비교합니다. 다르기때문에 이동할 분량을 찾습니다.

d와 abc를 비교하고 일치하는 부분이 없으므로 3만큼 쉬프트합니다.

abdefabc

     abc

a와 c를 비교하게 됩니다.

다르므로 이동할 분량을 찾습니다.

a와 abc를 비교하고 a가 일치하므로 2칸만큼쉬프트 합니다.

abdefabc

       abc

c와 c, b와b a,a가 비교되고 모두일치하므로 일치한다고 리턴합니다.

---

#문자열 검색하는 보이어 무어 알고리즘
def boyer_moore(pattern, text):
    #길이를 자주쓰므로 길이를 받아둔다.
    M = len(pattern)
    N = len(text)
    i = 0
    #반복은 최대 긴텍스트 길이 - 작은텍스트 길이
    while i <= N-M:
        #보이어 무어 알고리즘은 뒤에서부터 접근하므로 pattern길이의 -1을 해준다.
        #-1을 해주는 이유는 인덱스가 0부터 시작하기 때문이다.
        j = M - 1
        #뒤에서부터 검사하고 인덱스를 감소하는 형식이므로 0보다 이상일때만 동작한다.
        while j >= 0:
            #끝글자부터 비교하면서 같다면 하나씩 감소하면서 비교한다.
            if pattern[j] != text[i+j]:
                #글자가 틀리다면 제일마지막 글자 기준으로 find 함수를 호출한다.
               move = find(pattern, text[i + M - 1])
                break
            j = j - 1
        #인덱스가 -1이라는 뜻은 모든 글자가 맞았다는 이야기이다.
        if j == -1:
            #찾았으므로 true를 리턴한다.
            return True
            #인덱스 위치를 찾는다면
            #return i
        else:
            #-1이 아니라면 글자를 못찾은 것이므로 find에서 넘겨준 값만큼 옆으로 이동한다.
            i += move
    #여기까지 왔다면 끝까지 찾지 못한것이므로 False를 리턴한다.
    return False
    #인데스 위치로 한다면
    #return -1
 
#불필요한 비교를 건너뛰기 위한 함수
def find(pattern, char):
    #마지막 부분과 일치하는 부분이 있는지 검색한다.
    #마지막 부분은 이미 가능성이 없으므로 그전부터 검사한다.
    for i in range(len(pattern)-2, -1, -1):
        #마지막글자와 패턴중 일치하는 숫자가 있다면 그만큼 이동한다.
        if pattern[i] == char:
            return len(pattern) -i -1
    #일치하는 글자가 없다면 패턴의 길이만큼 이동한다.
    return len(pattern)

---

최악의 경우 시간복잡도는 N^2이 되며,

입력에 따라 다르지만 일반적으로 n보다 시간이 덜든다고 합니다.