Boyer-moore 알고리즘

Boyer-Moore 알고리즘이란

Boyer-Moore 알고리즘은 문자열 검색을 위한 효율적인 알고리즘 중 하나로, 특히 긴 텍스트에서 패턴을 빠르게 찾는 데 사용됩니다. 이 알고리즘은 1977년에 Robert S. Boyer와 J Strother Moore에 의해 개발되었습니다. Boyer-Moore 알고리즘은 다른 문자열 검색 알고리즘과 비교하여 대부분의 상황에서 빠른 속도를 보이며, 특히 긴 텍스트에서 긴 패턴을 검색하는 경우에 강점을 가집니다.

동작방식

1. Bad Character Heuristic (나쁜 문자 휴리스틱): 패턴 내의 각 문자에 대해, 패턴 내에서 그 문자의 오른쪽 끝에서부터 가장 멀리 있는 위치를 미리 계산합니다. 만약 텍스트 내에서 패턴의 해당 문자와 일치하지 않는 위치에서 패턴을 이동시킬 수 있습니다.
2. Good Suffix Heuristic (좋은 접미사 휴리스틱): 패턴의 끝에서부터 일치하지 않는 부분 문자열을 찾아 해당 부분 문자열을 패턴의 뒤쪽으로 이동시킵니다. 이것은 패턴 내에서 일치하는 부분을 재활용하여 검색 범위를 줄이는 데 도움이 됩니다.

이 두 휴리스틱을 결합하여 패턴을 텍스트 내에서 효율적으로 이동시키며, 불필요한 비교를 최소화하여 검색 속도를 빠르게 합니다.

장점

• Boyer-Moore 알고리즘은 텍스트 내에서 여러 위치에서 패턴을 동시에 비교하면서 이동하기 때문에, 다른 알고리즘보다 대부분의 상황에서 더 빠른 검색 속도를 보입니다.
• 특히 패턴이 길거나 텍스트와 패턴이 긴 경우에 강점을 발휘합니다.
• 미리 계산된 휴리스틱 정보를 사용하여 검색 속도를 최적화할 수 있어서, 실제 구현이 비교적 간단하고 효율적입니다.

단점

• 패턴이 짧거나 텍스트와 패턴의 길이가 모두 짧은 경우에는 다른 알고리즘이 더 효율적일 수 있습니다.
• 휴리스틱 정보를 미리 계산해야 하기 때문에, 패턴 변경이 빈번한 경우에는 계산 비용이 추가될 수 있습니다.
• Boyer-Moore 알고리즘은 최악의 경우에도 선형 시간 복잡도를 보장하지 못합니다. 최악의 경우에도 보다 느린 검색 속도를 보일 수 있습니다.

코드 구현

def bad_character_heuristic(pattern):
    bad_char = {}
    for i in range(len(pattern)):
        bad_char[pattern[i]] = i
    return bad_char

def good_suffix_heuristic(pattern):
    m = len(pattern)
    suffixes = [0] * m
    for i in range(m - 1, -1, -1):
        j = i
        while j >= 0 and pattern[j] == pattern[m - 1 - (i - j)]:
            j -= 1
            suffixes[i] = i - j
    return suffixes

def boyer_moore_search(text, pattern):
    n = len(text)
    m = len(pattern)
    bad_char = bad_character_heuristic(pattern)
    suffixes = good_suffix_heuristic(pattern)
    
    i = 0
    while i <= n - m:
        j = m - 1
        while j >= 0 and pattern[j] == text[i + j]:
            j -= 1
        if j < 0:
            print("패턴이 텍스트에서 발견됨: 인덱스", i)
            i += suffixes[0]
        else:
            bad_char_shift = max(1, j - bad_char.get(text[i + j], -1))
            suffix_shift = suffixes[j + 1]
            i += max(bad_char_shift, suffix_shift)

text = "ABAAABCDABCABCDABCDABDE"
pattern = "ABCDABD"
boyer_moore_search(text, pattern)

요약

Boyer-Moore 알고리즘은 대부분의 상황에서 효율적인 문자열 검색을 제공하는 강력한 알고리즘입니다. 그러나 패턴과 텍스트의 길이가 짧을 때는 다른 알고리즘과 비교하여 효율성이 떨어질 수 있습니다.