4.5 Boyer Moore Algorithm(보이어-무어 알고리즘)

CS - 4. String Search and Manipulations - 4.5. Boyer Moore Algorithm

Boyer Moore Algorithm

💡Boyer Moore algorithm is a string searching algorithm that is used to find the index of a substring in a string. It is a very efficient algorithm that is used in many applications. It is used in text editors, compilers, and many other applications.

보이어 무어 알고리즘은 문자열에서 하위 문자열의 인덱스를 찾는 데 사용되는 문자열 검색 알고리즘입니다. 많은 애플리케이션에서 사용되는 매우 효율적인 알고리즘입니다. 텍스트 편집기, 컴파일러 및 기타 여러 애플리케이션에서 사용됩니다.

 

 

보이어-무어 알고리즘은 문자열 검색 알고리즘 중 하나로, 특히 긴 문장에서 짧은 패턴을 찾아내는 데 매우 효율적입니다. 1977년에 Robert Boyer와 J Strother Moore에 의해 개발되었습니다.

보이어-무어 알고리즘의 핵심 개념은 '오른쪽에서 왼쪽으로' 탐색하는 것이며, 이는 대부분의 다른 문자열 검색 알고리즘과는 반대 방향입니다. 또한, 이 알고리즘은 불일치가 발생할 경우 최대한 많이 건너뛰는 것을 목표로 하며, 이를 통해 검색 속도를 높입니다.

이 알고리즘은 두 가지 주요 휴리스틱, 즉 '나쁜 문자 휴리스틱'과 '좋은 접미사 휴리스틱'을 사용합니다.

나쁜 문자 휴리스틱: 패턴에서 불일치가 발생한 문자가 패턴 내에 존재하지 않으면 패턴 전체를 오른쪽으로 이동합니다. 만약 패턴 내에 존재한다면, 불일치가 발생한 문자를 패턴의 가장 오른쪽에 있는 동일한 문자에 맞추어 이동합니다.
좋은 접미사 휴리스틱: 패턴에서 일치하는 접미사가 발견되면, 이 접미사가 패턴 내에서 다시 발견될 위치로 패턴을 이동합니다.
이 두 가지 휴리스틱은 결합되어 사용되며, 두 이동 중에서 더 멀리 이동하는 쪽을 선택합니다. 이를 통해 보이어-무어 알고리즘은 문자열 검색 과정을 매우 빠르게 수행할 수 있습니다.

그러나 이 알고리즘이 효율적이기 위해서는 전처리 과정이 필요합니다. 이 전처리 과정에서 '나쁜 문자 테이블'과 '좋은 접미사 테이블'을 생성하고 이를 바탕으로 문자열 검색을 수행합니다. 이러한 전처리 과정 때문에 짧은 문자열이나 단일 검색에는 다른 알고리즘들이 더 효율적일 수 있습니다.

 

 

 

In Python

def generate_bad_char_shift(term):
    skip_list = {}
    for i in range(0, len(term)-1):
        skip_list[term[i]] = len(term)-i-1
    return skip_list

def search_boyer_moore(text, pattern):
    bad_char_shift = generate_bad_char_shift(pattern)
    i = 0
    while i < len(text)-len(pattern)+1:
        j = len(pattern)
        while j > 0 and pattern[j-1] == text[i+j-1]:
            j -= 1
        if j > 0:
            bad_char_shift_value = bad_char_shift.get(text[i+j-1], len(pattern))
            i += bad_char_shift_value
        else:
            return i
    return -1

 

하나 찾을수 있는데, 이게 좀 여러개를 찾으려면 함수를 수정해야한다.

 

 

def search_boyer_moore(text, pattern):
    bad_char_shift = generate_bad_char_shift(pattern)  # 나쁜 문자 휴리스틱에 사용할 skip_list 생성
    i = 0  # 검색 시작 위치
    positions = []  # 패턴이 발견된 위치를 저장할 리스트
    while i < len(text)-len(pattern)+1:  # 텍스트를 오른쪽으로 이동하면서
        j = len(pattern)  # 패턴의 마지막 문자부터 비교 시작
        while j > 0 and pattern[j-1] == text[i+j-1]:  # 패턴의 문자와 텍스트의 문자가 일치하는 동안
            j -= 1  # 패턴을 왼쪽으로 이동
        if j > 0:  # 불일치 발생 시
            # 나쁜 문자 휴리스틱에 따라 텍스트의 이동 거리 계산
            bad_char_shift_value = bad_char_shift.get(text[i+j-1], len(pattern))
            i += bad_char_shift_value  # 텍스트를 오른쪽으로 이동
        else:  # 패턴의 모든 문자가 일치하는 경우
            positions.append(i)  # 현재 위치를 리스트에 추가
            i += 1  # 다음 위치로 이동
    return positions  # 모든 위치 반환

 

이런식으로 보이어-무어 알고리즘으로 문자열을 찾을수 있다.

 

 

Appendix

보이어-무어 알고리즘은 문자열 탐색 문제를 해결하는 데 활용됩니다. 특히, 긴 텍스트에서 짧은 패턴을 찾는 경우에 효율적입니다. 이는 보이어-무어 알고리즘이 불일치가 발생할 경우 가능한 한 많이 건너뛰어 탐색 속도를 높이기 때문입니다.

 

KMP 랑 비교한다면.

 

방향성

- KMP 알고리즘은 텍스트를 왼쪽에서 오른쪽으로 스캔합니다.

- 보이어-무어 알고리즘은 오른쪽에서 왼쪽으로 스캔합니다.

효율성

보이어-무어 알고리즘은 일반적으로 KMP 알고리즘보다 더 빠르며, 특히 대상 텍스트가 아주 클 때 더욱 효율적입니다. 이는 보이어-무어 알고리즘이 불일치를 발견하면 최대한 많이 건너뛰기 때문입니다. 반면, KMP 알고리즘은 텍스트를 한 번만 통과하며, 패턴에 대한 부분적인 일치를 활용하기 때문에 불필요한 비교를 최소화합니다.

전처리

두 알고리즘 모두 패턴을 전처리하는 단계를 포함합니다. KMP 알고리즘은 패턴의 접두사와 접미사가 일치하는 길이를 계산하는 전처리 테이블을 만듭니다. 반면에 보이어-무어 알고리즘은 '나쁜 문자 휴리스틱'과 '좋은 접미사 휴리스틱'을 이용한 전처리 테이블을 만듭니다.