Boyer-Moore 문자열 검색 알고리즘: 효율적인 텍스트 검색 기법

작성일 : 2024-06-22

Boyer-Moore 문자열 검색 알고리즘: 효율적인 텍스트 검색 기법

개요

Boyer-Moore 문자열 검색 알고리즘은 텍스트 내에서 특정 패턴을 찾는 가장 효율적인 알고리즘 중 하나입니다. R.S. Boyer와 J.S. Moore가 1977년에 개발한 이 알고리즘은 머신러닝, 데이터 압축, 생명과학 및 정보 보안 등 다양한 분야에서 널리 사용됩니다. 이 글에서는 Boyer-Moore 알고리즘의 동작 원리 및 구현 방법, 장단점에 대해 설명하겠습니다.

알고리즘의 동작 원리

Boyer-Moore 알고리즘은 주어진 텍스트와 패턴을 매칭할 때, 비교를 오른쪽에서 왼쪽으로 수행하며, 불일치가 발생할 경우 다음 가능한 위치로 빠르게 이동하는 방법을 사용합니다. 이 알고리즘은 Bad Character Rule과 Good Suffix Rule 두 가지 주요 규칙을 이용하여 불필요한 비교를 최소화합니다.

Bad Character Rule

Bad Character Rule은 텍스트 내에서 패턴과 일치하지 않는 문자가 발견될 때, 해당 문자를 기준으로 패턴을 이동시키는 규칙입니다. 만약 일치하지 않는 문자가 패턴 내에 존재한다면 가장 오른쪽에 위치한 해당 문자로 패턴을 이동시킵니다. 패턴 내에 존재하지 않는 경우 패턴을 다음 위치로 이동시킵니다.


python
# Bad Character Rule 예제 코드
text = "ABABABACD"
pattern = "ABAC"
def bad_character_rule(text, pattern):
    m = len(pattern)
    n = len(text)
    bad_char_table = [-1] * 256
    for i in range(m - 1):
        bad_char_table[ord(pattern[i])] = i
    shift = 0
    while shift <= n - m:
        j = m - 1
        while j >= 0 and pattern[j] == text[shift + j]:
            j -= 1
        if j < 0:
            print(f"Pattern found at index {shift}")
            shift += (m - bad_char_table[ord(text[shift + m])] if shift + m < n else 1)
        else:
            shift += max(1, j - bad_char_table[ord(text[shift + j])])
bad_character_rule(text, pattern)

Good Suffix Rule

Good Suffix Rule은 패턴 내에서 부분적으로 일치하는 접미사가 발견될 때, 전체 패턴을 왼쪽으로 이동시키는 규칙입니다. 즉, 이미 매칭된 접미사를 기반으로 나머지 부분이 일치할 수 있는지 검사하여 필요한 만큼만 이동시킵니다.


python
# Good Suffix Rule 예제 코드
text = "ABABABACD"
pattern = "ABAC"
def good_suffix_rule(text, pattern):
    m = len(pattern)
    n = len(text)
    good_suffix_table = [0] * (m + 1)
    borders = [0] * (m + 1)
    i, j = m, m + 1
    borders[i] = m + 1
    while i > 0:
        while j <= m and pattern[i - 1] != pattern[j - 1]:
            if good_suffix_table[j] == 0:
                good_suffix_table[j] = j - i
            j = borders[j]
        i -= 1
        j -= 1
        borders[i] = j
    j = borders[0]
    for i in range(m + 1):
        if good_suffix_table[i] == 0:
            good_suffix_table[i] = j
        if i == j:
            j = borders[j]
    shift = 0
    while shift <= n - m:
        j = m - 1
        while j >= 0 and pattern[j] == text[shift + j]:
            j -= 1
        if j < 0:
            print(f"Pattern found at index {shift}")
            shift += good_suffix_table[0]
        else:
            shift += good_suffix_table[j + 1]
good_suffix_rule(text, pattern)

알고리즘의 장점과 단점

장점

높은 효율성: Boyer-Moore 알고리즘은 최악의 경우에도 O(n + m) 시간 복잡도를 가지며, 보통의 경우 대부분의 문자 비교를 건너뛰므로 매우 빠르게 동작합니다.
적은 비교 횟수: 패턴의 뒤쪽부터 비교를 시작하기 때문에, 정확한 매칭이 이루어지지 않는 경우 많은 비교를 피할 수 있습니다.

단점

준비 시간: Bad Character Rule 및 Good Suffix Rule을 적용하기 위해 초기 테이블 구성을 필요로 하며, 이는 초기 알고리즘 준비 시간이 다소 길어질 수 있습니다.
메모리 사용량: 테이블을 생성하고 저장해야 하기 때문에 추가적인 메모리 공간이 필요합니다.

실제 구현 예제


python
# Boyer-Moore 전체 알고리즘 구현 예제
text = "HERE IS A SIMPLE EXAMPLE"
pattern = "EXAMPLE"
def boyer_moore(text, pattern):
    m = len(pattern)
    n = len(text)
    bad_char_table = [-1] * 256
    for i in range(m - 1):
        bad_char_table[ord(pattern[i])] = i
    good_suffix_table = [m] * (m + 1)
    borders = [0] * (m + 1)
    i, j = m, m + 1
    borders[i] = m + 1
    while i > 0:
        while j <= m and pattern[i - 1] != pattern[j - 1]:
            if good_suffix_table[j] == m:
                good_suffix_table[j] = j - i
            j = borders[j]
        i -= 1
        j -= 1
        borders[i] = j
    j = borders[0]
    for i in range(m + 1):
        if good_suffix_table[i] == m:
            good_suffix_table[i] = j
        if i == j:
            j = borders[j]
    shift = 0
    while shift <= n - m:
        j = m - 1
        while j >= 0 and pattern[j] == text[shift + j]:
            j -= 1
        if j < 0:
            print(f"Pattern found at index {shift}")
            shift += good_suffix_table[0]
        else:
            shift += max(1, j - bad_char_table[ord(text[shift + j])], good_suffix_table[j + 1])
boyer_moore(text, pattern)

결론

Boyer-Moore 문자열 검색 알고리즘은 높은 효율성 덕분에 다양한 분야에서 매우 유용하게 사용되고 있습니다. Bad Character Rule과 Good Suffix Rule을 통해 불필요한 비교를 최소화하며 빠른 검색을 제공합니다. 하지만 초기 테이블의 구성을 위해 필요한 시간과 추가적인 메모리 사용량이 단점으로 작용할 수 있습니다. 이를 충분히 고려하여 상황에 맞는 알고리즘을 선택하는 것이 중요합니다.