문자열 처리 알고리즘(3) - 보이어-무어 알고리즘 개념, 원리, 장단점, C언어, Java, Python 예제코드

보이어 무어 알고리즘 총 정리

 

 

 

 

보이어-무어 알고리즘은 문자열 검색 문제를 해결하는 데 있어 매우 효율적인 알고리즘으로, 텍스트(T)에서 패턴(P)을 찾는 데 사용됩니다. 이 알고리즘은 오른쪽에서 왼쪽으로 비교하며, 미스매치 시 가능한 만큼 건너뛰는 특성을 가집니다.

---

 

 

 

1. 개념

 

보이어-무어 알고리즘은 두 가지 주요 규칙을 활용합니다:

1. 불일치 문자 규칙 (Bad Character Rule): 미스매치가 발생하면 패턴에서 해당 문자의 가장 오른쪽 위치로 점프합니다.
2. 좋은 접미사 규칙 (Good Suffix Rule): 미스매치가 발생한 접미사와 일치하는 부분을 기준으로 점프합니다.

이 규칙을 조합해 텍스트를 효과적으로 탐색합니다.

---

반응형

 

 

2. 원리

보이어-무어 알고리즘은 텍스트에서 패턴을 탐색할 때 다음 단계를 따릅니다:

1. 패턴의 끝에서부터 시작하여 비교합니다.
2. 미스매치가 발생하면 두 규칙 중 하나를 사용해 점프합니다.
3. 패턴과 텍스트가 완전히 일치하면 위치를 반환합니다.

---

 

 

 

3. 동작 예시

 

텍스트(T): HERE IS A SIMPLE EXAMPLE

패턴(P): EXAMPLE

 

(1) 초기 상태:

텍스트:   HERE IS A SIMPLE EXAMPLE
패턴:                    EXAMPLE

 

(2) 첫 번째 비교:

패턴의 끝에서부터 시작하여 E와 E를 비교합니다. 일치합니다. 다음으로 L과 L을 비교합니다. 일치합니다. 모든 문자(EXAMPLE)가 일치하면 위치를 반환합니다.

 

(3) 결과:

패턴이 텍스트에서 시작하는 위치는 17입니다.

---

 

 

4. 장단점

장점:

1. 일반적으로 매우 빠른 속도를 제공합니다.
2. 불필요한 비교를 피하며, 긴 텍스트에서 효과적입니다.

단점:

1. 패턴이 짧거나 자주 반복되는 경우 효율성이 떨어질 수 있습니다.
2. 사전처리 과정이 필요하여, 코드 구현이 복잡할 수 있습니다.

---

 

 

5. 구현 코드

C 코드:

#include <stdio.h>
#include <string.h>
#define ALPHABET_SIZE 256

void preprocessBadChar(char *pattern, int size, int badChar[ALPHABET_SIZE]) {
    for (int i = 0; i < ALPHABET_SIZE; i++)
        badChar[i] = -1;

    for (int i = 0; i < size; i++)
        badChar[(int)pattern[i]] = i;
}

void boyerMoore(char *text, char *pattern) {
    int m = strlen(pattern);
    int n = strlen(text);
    int badChar[ALPHABET_SIZE];

    preprocessBadChar(pattern, m, badChar);

    int shift = 0;
    while (shift <= (n - m)) {
        int j = m - 1;

        while (j >= 0 && pattern[j] == text[shift + j])
            j--;

        if (j < 0) {
            printf("Pattern occurs at shift %d\n", shift);
            shift += (shift + m < n) ? m - badChar[(int)text[shift + m]] : 1;
        } else {
            shift += (j - badChar[(int)text[shift + j]] > 1) ? j - badChar[(int)text[shift + j]] : 1;
        }
    }
}

int main() {
    char text[] = "HERE IS A SIMPLE EXAMPLE";
    char pattern[] = "EXAMPLE";
    boyerMoore(text, pattern);
    return 0;
}

 

Java 코드:

import java.util.Arrays;

public class BoyerMoore {
    private static final int ALPHABET_SIZE = 256;

    public static void boyerMoore(String text, String pattern) {
        int[] badChar = preprocessBadChar(pattern);
        int m = pattern.length();
        int n = text.length();

        int shift = 0;
        while (shift <= (n - m)) {
            int j = m - 1;

            while (j >= 0 && pattern.charAt(j) == text.charAt(shift + j)) {
                j--;
            }

            if (j < 0) {
                System.out.println("Pattern occurs at shift " + shift);
                shift += (shift + m < n) ? m - badChar[text.charAt(shift + m)] : 1;
            } else {
                shift += Math.max(1, j - badChar[text.charAt(shift + j)]);
            }
        }
    }

    private static int[] preprocessBadChar(String pattern) {
        int[] badChar = new int[ALPHABET_SIZE];
        Arrays.fill(badChar, -1);

        for (int i = 0; i < pattern.length(); i++) {
            badChar[pattern.charAt(i)] = i;
        }

        return badChar;
    }

    public static void main(String[] args) {
        String text = "HERE IS A SIMPLE EXAMPLE";
        String pattern = "EXAMPLE";
        boyerMoore(text, pattern);
    }
}

 

Python 코드:

def preprocess_bad_char(pattern):
    bad_char = [-1] * 256
    for i, char in enumerate(pattern):
        bad_char[ord(char)] = i
    return bad_char

def boyer_moore(text, pattern):
    m = len(pattern)
    n = len(text)
    bad_char = preprocess_bad_char(pattern)

    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 occurs at shift {shift}")
            shift += m - bad_char[ord(text[shift + m])] if shift + m < n else 1
        else:
            shift += max(1, j - bad_char[ord(text[shift + j])])

text = "HERE IS A SIMPLE EXAMPLE"
pattern = "EXAMPLE"
boyer_moore(text, pattern)