[문자열 검색 알고리즘] 보이어 무어(BM)법

보이어 무어법의 특징

• 이 알고리즘을 고안한 보이어와 무어의 이름을 따서 BM법이라고도 함
• KMP법보다 효율적이어서 실제 문자열 검색에서 주로 사용
• 패턴의 끝 문자에서 시작하여 앞쪽을 향해 검사를 수행
• 일치하지 않는 문자를 발견하면 미리 준비한 표를 바탕으로 패턴이 이동하는 값을 결정함
• 시간복잡도는 최악의 경우라도 O(n)이고 평균 O(n / m)이다. 보이어 무어법은 배열을 1개만 사용해도 충분히 빠르다.

보이어 무어법의 진행 과정

예를 들어 보이어 무어법으로 텍스트 'ABCXDEZCABACABAC' 에서 패턴 'ABAC' 를 검색하는 과정을 살펴보자.

먼저 위 그림처럼 텍스트와 패턴의 첫 문자를 위 아래로 나란히 놓고 패턴의 마지막 문자 'C'에 주목한다. 같은 위치에 있는 텍스트의 'X'는 패턴 안에 포함되어 있지 않다. 따라서 패턴을 이동해도 텍스트의 문자 'X'와 패턴의 문자가 일치하지 않는다.

 

위 그림처럼 패턴에 포함되지 않는 문자를 텍스트에서 발견하면 그 위치까지는 건너뛸 수 있다. 그러므로 패턴을 비교하는 1~4번째 과정을 생략하고 패턴을 오른쪽으로 한번에 4칸 밀면 다음 그림과 같이 된다.

 

여기서 패턴의 마지막 문자 'C'를 텍스트와 비교하면 일치하므로 1칸 앞의 문자 'A'로 되돌아가서 위 그림과 같은 상태로 만든다.

 

하지만 위 그림에서 패턴의 문자 'A'는 텍스트의 문자 'Z'와 일치하지 않고, 패턴을 1칸 또는 2칸 밀어도 텍스트의 문자 'Z'와 패턴의 문자는 일치하지 않는다. 

 

그래서 패턴을 한 번에 3칸 밀어 다음 그림과 같은 상태로 만든다.

위 그림에서 패턴의 마지막 문자 'C'는 텍스트 문자 'A'와 일치하지 않는다. 그런데 문자 'A'는 패턴의 1번째와 3번째에 포함되어 있다. 그래서 패턴의 두번째 그림과 마찬가지로 뒤쪽에 있는 'A'가 위아래로 겹치도록 패턴을 오른쪽으로 1칸 밀어내서 아래 그림의 상태와 같이 만들 수 있다. 하지만 위 그림에서 패턴 4번째의 그림과 같이 패턴 앞쪽에 있는 'A'가 위아래로 겹치도록 오른쪽으로 한번에 3칸만큼 밀어내면 안된다.

 

이후 위의 그림처럼 맨 끝부터 문자를 차례로 비교하면 모든 문자가 일치하므로 검색에 성공한다.

 

보이어 무어법 알고리즘도 KMP법과 마찬가지로 각각의 문자를 만났을 때 패턴의 이동할 크기를 저장하는 표(건너뛰기 표)를 미리 만들어 둘 필요가 있다. 패턴 문자열의 길이가 n일 때 이동할 크기(이동량)는 다음과 같이 결정한다.

 

패턴에 포함되지 않는 문자를 만난 경우

• 패턴 이동량이 곧 n이다. 위 과정에서와 마찬가지로 'X'는 패턴에 포함되지 않으므로 4문자만큼 밀어낸다.

패턴에 포함되는 문자를 만난 경우

• 마지막에 나오는 위치의 인덱스가 k이면 이동량은 n - k - 1이다. 위 과정에서 살펴본 그림처럼 'A'는 패턴 안의 두 곳에 있다. 패턴을 오른쪽으로 1칸 밀어낸다.
• 같은 문자가 패턴 안에 중복해서 존재하지 않으면 패턴의 맨 끝 문자의 이동량은 n이다. 예를 들어 'ABAC'의 'C'를 만나면 이동할 필요가 없으므로 이동량은 n이다.

위 과정을 진행할 때 건너뛰기 표는 다음과 같이 완성된다.

텍스트: "ABACXDEZCABACABAC" 패턴: "ABAC"

아래 코드는 보이어 무어법을 구현한 프로그램이다. bm_match( ) 함수가 전달받는 인수와 반환값은 브루트 포스법의 bf_match( ) 함수와 KMP 법의 kmp_match( ) 함수와 같다. 패턴 안에 존재할 수 있는 모든 문자의 이동량을 계산해야 하므로 이 건너뛰기 표에서 사용하는 원소는 256개이다.

여기에서는 배열 하나를 사용하여 보이어 무어법을 간략하게 나타냈다. 원래의 보이어 무어법은 배열 2개를 사용해서 검사한다.

 

보이어 무어법 코드

# 보이어 무어법으로 문자열 검색하기(문자열 길이는 0~255개)

def bm_match(txt: str, pat: str) -> int:
    """보이어 무어법으로 문자열 검색"""
    skip = [None] * 256 # 건너뛰기 표

    # 건너뛰기 표 만들기
    for pt in range(256):
        skip[pt] = len(pat)
    for pt in range(len(pat)):
        skip[ord(pat[pt])] = len(pat) - pt - 1

    # 검색하기
    while pt < len(txt):
        pp = len(pat) - 1
        while txt[pt] == pat[pp]:
            if pp == 0:
                return pt
            pt -= 1
            pp -= 1
        pt += skip[ord(txt[pt])] if skip[ord(txt[pt])] > len(pat) - pp \
            else len(pat) - pp

    return -1

if __name__ == "__main__":
    s1 = input("텍스트를 입력하세요.: ") # 텍스트용 문자열
    s2 = input("패턴을 입력하세요.: ")  # 패턴용 문자열

    idx = bm_match(s1, s2)  # 문자열 s1 ~ s2를 보이어 무어법으로 검색

    if idx == -1:
        print("텍스트 안에 패턴이 존재하지 않습니다.")
    else:
        print(f"{idx + 1}번째 문자가 일치합니다.")

 

실행 결과

텍스트를 입력하세요.: ABABCDEFGHA
패턴을 입력하세요.: ABC
3번째 문자가 일치합니다.

Process finished with exit code 0

 

 

보이어 무어법 코드의 진행 과정

1. 건너뛰기 표 만들기(찾는 문자열의 범위만큼)
   • 예를 들면 영문 대문자 또는 소문자만 있으면 26개, 영문 대문자와 소문자는 52개, ASCII코드값만큼이면 256개
   • 건너뛰기 표를 패턴의 길이로 전부 초기화
   • 찾을 대상이 되는 패턴의 문자열의 대상 배열만 len(pat) - pt - 1로 초기화
2. 검색하기(pt가 txt의 길이보다 작은 동안 = 검색이 끝나지 않을 조건인 동안)
   • 패턴의 가장 끝부터 비교하기 때문에 pp는 len(pat) - 1부터 시작
   • 문자가 일치하는 경우, 즉 txt[pt] == pat[pp]일 때 
     • pp가 가장 첫 문자[0]를 가리키고 있다면 반복을 끝내고 반환
     • 아니면 pt -= 1, pp -= 1해서 한칸씩 앞의 문자와 비교
   • 만약 건너뛰기 표의 [ord(txt[pt])]가 len(pat) - pp보다 크면 pt += skip_table[ord(txt[pt])]를 리턴하고, 아니면 len(pat) - pp를 반환
3. 찾는 값이 없다면 -1을 반환

 

문자열 검색 알고리즘의 시간 복잡도

지금까지 구현한 3가지 문자열 검색 알고리즘의 시간 복잡도를 살펴보자.(텍스트의 길이 = n, 패턴의 길이 = m)

 

브루트 포스법

• 이 알고리즘의 시간 복잡도는 O(mn)이지만 일부러 꾸며낸 패턴이 아니라면 O(n)이 된다고 알려져 있다. 단순한 알고리즘이지만 실제로는 아주 빠르게 동작한다.

KMP법

• 이 알고리즘의 시간 복잡도는 최악의 경우에도 O(n)이다. 다만 처리하기 복잡하고 패턴 안에 반복이 없으면 효율은 좋지 않다. 그러나 검색 과정에서 주목하는 곳을 앞으로 되돌릴 필요가 전혀 없으므로 파일을 차례로 읽어 들이면서 검색할 때 사용하면 좋다.

보이어 무어법

• 이 알고리즘의 시간 복잡도는 최악의 경우라도 O(n)이고 평균 O(n / m)이다. 위 코드에서는 배열을 1개만 사용했지만 배열 2개로 알고리즘을 구현하면 KMP법과 마찬가지로 배열을 만드는 데 복잡한 처리 과정이 필요하므로 효율성이 떨어진다. 보이어 무어법은 배열을 1개만 사용해도 충분히 빠르다.

일반적으로 파이썬에서 문자열 검색을 하려면 표준 라이브러리를 사용하는 것을 추천한다. 만약 표준 라이브러리를 사용하지 않는다면 보이어 무어법(또는 개선한 방법)이나 상황에 따라서 브루트 포스법을 사용하는 경우가 많다.

 

문자 코드를 다루는 ord( ) 함수와 chr( ) 함수

위 코드에서 사용한 내장 함수 ord( )는 단일한 문자를 전달받아 그 문자의 유니코드 코드 포인트를 정수로 반환한다. 예를 들어 ord('a')는 정수 97을 반환한다. 

또 이 함수의 변환을 거꾸로 수행하는 내장 함수는 chr( )이다. 예를 들어 chr(97)은 문자 'a'를 반환한다.

유니코드 코드 포인트는 유니코드 체계에서 문자마다 부여한 고유한 숫자의 값을 뜻한다.