[WEEK05] KMP법, 보이어-무어법

KMP 알고리즘

KMPKnuth-Morris-Pratt 알고리즘은 문자열 검색 알고리즘으로, 주어진 텍스트 내에서 특정 패턴을 효율적으로 찾기 위해 사용된다. 이 알고리즘은 문자 비교를 최소화하여 검색 속도를 향상시킨다.

 

브루트 포스법은 일치하지 않는 문자를 만나면 이전 단게에서 검사했던 결과를 버리코 패턴의 첫 문자부터 다시 검색을 수행하지만, KMP법은 검사했던 결과를 버리지 않고 효율적으로 활용하는 알고리즘이다.

[출처] https://pangtrue.tistory.com/303

주요 개념

• 부분 일치 테이블 (LPS 배열): 패턴의 접두사와 접미사가 일치하는 길이를 저장한다. 이를 통해 불필요한 비교를 줄일 수 있다.
• LPSLongest Prefix Suffix 배열은 주어진 패턴에서 접두사와 접미사가 일치하는 최대 길이를 저장한다. 이를 통해 패턴의 어느 부분까지 일치했는지를 기록하고, 불일치가 발생했을 때 패턴을 얼마나 이동해야 하는지를 결정한다.

LPS 배열 생성

• 현재 인덱스 i와 일치하는 문자가 있을 경우, j를 증가시켜 일치하는 길이를 업데이트하고 lps[i]에 저장한다.
• 일치하지 않을 경우, j를 LPS 배열을 참조하여 조정한다.

작동 원리

• LPS 배열 생성: 패턴을 순회하면서 각 위치에서의 LPS 값을 계산한다. 예를 들어, 패턴이 "ABABAC"이라면, LPS는 [0, 0, 1, 2, 0, 1]이 된다.
• 텍스트 검색: 텍스트를 순회하며 패턴과 비교한다. 만약 일치하지 않는 문자가 나타나면 LPS 배열을 참조하여 패턴을 이동시킨다. 이를 통해 불필요한 비교를 줄일 수 있다.

시간 복잡도

KMP 알고리즘의 최악의 경우 시간 복잡도는 O(N + M)이다.(여기서 N은 텍스트의 길이, M은 패턴의 길이다.) 그러나 보통의 경우, Worst-case에서도 O(N)이라고 알려져 있다. 다만 처리하기 복잡하고 패턴 안에 반복이 없으면 효율은 좋지 않다.

코드 구현

#include <stdio.h>
#include <string.h>

void computeLPSArray(char *pattern, int *lps, int M) {
    int length = 0;
    lps[0] = 0;
    int i = 1;

    while (i < M) {
        if (pattern[i] == pattern[length]) {
            length++;
            lps[i] = length;
            i++;
        } else {
            if (length != 0) {
                length = lps[length - 1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
}

void KMPSearch(char *text, char *pattern) {
    int M = strlen(pattern);
    int N = strlen(text);
    int lps[M];

    computeLPSArray(pattern, lps, M);

    int i = 0; // index for text
    int j = 0; // index for pattern
    while (i < N) {
        if (pattern[j] == text[i]) {
            i++;
            j++;
        }
        if (j == M) {
            printf("패턴이 텍스트의 인덱스 %d에서 발견됨\n", i - j);
            j = lps[j - 1];
        } else if (i < N && pattern[j] != text[i]) {
            if (j != 0) {
                j = lps[j - 1];
            } else {
                i++;
            }
        }
    }
}

int main() {
    char text[] = "ABABDABACDABABCABAB";
    char pattern[] = "ABABCABAB";
    KMPSearch(text, pattern);
    return 0;
}

---

보이어-무어법

보이어-무어법Boyer-Moore은 패턴 매칭 알고리즘으로, 패턴을 오른쪽 끝에서 왼쪽으로 비교한다. 이 알고리즘은 주로 두 가지 규칙(불일치 규칙과 좋은 접미사 규칙)을 사용하여 검색 과정을 최적화한다.

 

보이어-무어법은 이론이나 실제 효율 면에서 KMP법보다 뛰어난 알고리즘이다. 패턴의 끝 문자에서 시작해 앞쪽을 향해 검사를 수행한다. 이 과정에서 일치하지 않는 문자를 발견하면 미리 준비한 표를 바탕으로 패턴이 이동하는 값을 결정한다.

[출처] Medium - The Boyer Moore String Search Algorithm

주요 개념

• 불일치 규칙: 현재 비교 중인 문자와 패턴의 문자가 일치하지 않을 경우, 패턴을 이동할 위치를 결정한다.
• 좋은 접미사 규칙: 패턴의 접미사가 텍스트의 해당 부분에서 일치할 경우, 패턴을 더 멀리 이동할 수 있다.

작동 원리

• 불일치 테이블 생성: 패턴의 각 문자가 텍스트에서 얼마나 멀리 이동할지를 기록하는 테이블을 만든다.
• 텍스트 검색: 텍스트를 순회하면서 패턴과 비교한다. 불일치가 발생하면 두 규칙을 사용하여 패턴을 이동한다. 이 과정에서 최대한 많은 문자를 건너뛰므로 검색 속도가 매우 빠르다.

시간 복잡도

보이어-무어법의 최악의 경우 시간 복잡도는 O(N)이나, 평균적인 경우에는 O(N/M)로 매우 효율적이다.

코드 구현

#include <stdio.h>
#include <string.h>

#define ALPHABET_SIZE 256

void badCharHeuristic(char *str, 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)str[i]] = i;
    }
}

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

    badCharHeuristic(pattern, m, badchar);

    int s = 0; // shift of the pattern with respect to text
    while (s <= (n - m)) {
        int j = m - 1;

        while (j >= 0 && pattern[j] == text[s + j]) {
            j--;
        }

        if (j < 0) {
            printf("패턴이 텍스트의 인덱스 %d에서 발견됨\n", s);
            s += (s + m < n) ? m - badchar[text[s + m]] : 1;
        } else {
            s += max(1, j - badchar[text[s + j]]);
        }
    }
}

int main() {
    char text[] = "ABABDABACDABABCABAB";
    char pattern[] = "ABABCABAB";
    BoyerMooreSearch(text, pattern);
    return 0;
}

---

[참고자료]

• KMP 알고리즘(Knuth-Morris-Pratt Algorithm)

KMP 알고리즘(Knuth-Morris-Pratt Algorithm)

• [알고리즘] KMP(Knuth-Morris-Pratt) 알고리즘

[알고리즘] KMP(Knuth-Morris-Pratt) 알고리즘

• KMP 알고리즘

KMP 알고리즘

• The Boyer Moore String Search Algorithm

The Boyer Moore String Search Algorithm

• Boyer-Moore 문자열 탐색 알고리즘

Boyer-Moore 문자열 탐색 알고리즘