[Java] 문자열 패턴 매칭

1. 문자열 패턴 매칭

 

문자열 패턴 매칭은 주어진 문자열에서 특정 패턴이 어디에 위치하는지 찾는 알고리즘.

 

예를 들어, "나는 전선을 간다"라는 문자열에서 "전선"라는 패턴을 찾는 경우가 문자열 패턴 매칭의 한 예다.

 

검색 엔진, 텍스트 편집기, 데이터베이스 등에서 이용된다.

 

여러 가지 알고리즘들이 있으며, 각각의 알고리즘은 다른 상황에서 장점을 가짐.

 

 

문자열 패턴 매칭 알고리즘	설명	장점	단점
Brute force	주어진 문자열을 처음부터 하나씩 검사하며 패턴과 일치하는지 확인	구현이 간단하다	문자열이 길 경우 비효율적이다
라빈 카프	해시 함수를 이용하여 패턴의 해시값과 문자열의 해시값을 비교	평균적으로 빠른 검색 속도	해시 충돌로 인해 오동작할 가능성이 있다
KMP	패턴 내에서의 반복을 찾아내어 검사 횟수를 줄임	중복 검사를 없애기 때문에 효율적이다	알고리즘이 복잡하여 구현이 어렵다
보이어-무어	패턴의 끝에서 시작하여 검사하고, 불일치 시 건너뛰는 방식을 사용	뒤에서부터 비교하므로 빠른 검색 속도	알고리즘이 복잡하여 구현이 어렵다

 

---

2. Brute force

 

일치하지 않으면 한 칸 뒤로 이동해서 다시 확인한다.

 

public class NaiveSearch {
    public static void search(String txt, String pat)
    {
        int M = pat.length();
        int N = txt.length();

        /* 한 개씩 모든 문자열의 인덱스를 이동 */
        for (int i = 0; i <= N - M; i++) {

            int j;

            /* 패턴의 모든 문자들에 대해 현재 인덱스 i의 텍스트를 검사 */
            for (j = 0; j < M; j++)
                if (txt.charAt(i + j) != pat.charAt(j))
                    break;

            if (j == M) // 패턴이 발견되면
                System.out.println("패턴 발견 " + " 위치 " + i);
        }
    }
}

• 시간 복잡도 : O(MN) (M과 N은 비교할 두 문자열의 크기를 의미)

 

---

3. 라빈 카프 알고리즘

 

가. Hash

 

해시

 

 

라빈 카프 알고리즘은 효율적인 문자열 패턴 매칭을 위해서 Hash값을 활용한다.

 

해시 : 가변 길이 데이터를 그 데이터를 표현하기 위한 고정길이의 데이터로 변환하는 것.
해시함수 : 해시를 만들어 내는 함수.

 

 

출처 : 파이썬 알고리즘 인터뷰, 나무위키

 

해시를 인덱스로 활용하여 정보를 저장할 수 있다.

 

이때 해시 충돌이 발생할 수 있는데, 해시 충돌은 두 개 이상의 키가 동일한 해시 값을 생성할 때 발생한다.

 

예를 들어, '윤아'와 '서현'이라는 키가 동일한 해시 값을 가리킬 수 있다.

 

이런 상황을 해시 충돌이라고 한다.

 

해시 충돌을 해결하는 두 가지 일반적인 방법이 있다

 

• 오픈 어드레싱(open addressing)
  : 충돌이 발생한 해시 버킷 다음에 빈 버킷을 찾아 그곳에 키-값 쌍을 저장하는 방식.
  : 여기서 빈 버킷을 찾는 방법은 선형 탐색, 이차 탐색 등 다양하게 존재.
• 분리 체이닝(separate chaining)
  : 각 해시 버킷이 하나의 연결 리스트를 가지고, 충돌이 발생하면 연결 리스트에 키-값 쌍을 추가하는 방식.
  : 이 방식은 메모리를 추가적으로 사용하지만, 해시 테이블이 꽉 찬 상태에서도 충돌을 관리할 수 있는 장점이 있다.

open addressing, seperate chaining 설명, 출처 : 파이썬 알고리즘 인터뷰, 나무위키

 

해시와 해시 충돌에 대한 자세한 내용은 따로 공부하자.

 

---

나. 라빈-카프 알고리즘

 

• Rabin-Karp algorithm
• 문자열 검색을 위해 해시를 이용.
• 문자가 아닌 해시 값을 비교.
• 시간복잡도 : 최악의 경우 O(MN)지만 평균적으론 선형에 가까운 빠른 속도를 가짐.

 

 

슬라이딩 윈도우 활용해서 시간복잡도를 줄일 수 있다.

 

나가는 값은 제외하고 들어오는 값은 포함해서 해시를 구한다.

 

이 해시값과 패턴의 해시값을 비교한다.

 

단, 해시 충돌이 발생할 수 있다.

 

그래서 해시 값이 같아도 문자열이 일치하는지 확인해야 한다.

 

최악의 경우 모든 해시 값이 같아서 Brute force와 다를 바 없어져 O(MN)의 시간 복잡도를 가진다.

// 아래 프로그램은 CLRS 책에서 제공하는
// Rabin Karp 알고리즘의 Java 구현입니다

public class Main {
    // d는 입력 알파벳의 문자 수입니다
    public final static int d = 256;

    /* pat -> 패턴
        txt -> 텍스트
        q -> 소수
    */
    static void search(String pat, String txt, int q)
    {
        int M = pat.length();
        int N = txt.length();
        int i, j;
        int p = 0; // 패턴의 해시 값
        int t = 0; // 텍스트의 해시 값
        int h = 1;

        // h의 값은 "pow(d, M-1)%q"가 됩니다
        for (i = 0; i < M - 1; i++)
            h = (h * d) % q;

        // 패턴과 텍스트의 첫 번째 윈도우의 해시 값을 계산합니다
        for (i = 0; i < M; i++) {
            p = (d * p + pat.charAt(i)) % q;
            t = (d * t + txt.charAt(i)) % q;
        }

        // 패턴을 텍스트 위에 하나씩 슬라이드합니다
        for (i = 0; i <= N - M; i++) {

            // 현재 텍스트 윈도우와 패턴의 해시 값을 확인합니다
            // 해시 값이 일치하면 문자를 하나씩 확인합니다
            if (p == t) {
                /* 문자를 하나씩 확인합니다 */
                for (j = 0; j < M; j++) {
                    if (txt.charAt(i + j) != pat.charAt(j))
                        break;
                }

                // 만약 p == t 그리고 pat[0...M-1] = txt[i, i+1, ...i+M-1]이면
                if (j == M)
                    System.out.println("Pattern found at index " + i);
            }

            // 다음 텍스트 윈도우의 해시 값을 계산합니다: 앞자리 수를 제거하고, 뒷자리 수를 추가합니다
            if (i < N - M) {
                t = (d * (t - txt.charAt(i) * h) + txt.charAt(i + M)) % q;

                // t의 값이 음수가 될 수 있으므로
                // 양수로 변환합니다
                if (t < 0)
                    t = (t + q);
            }
        }
    }

    /* 위 함수를 테스트하는 드라이버 프로그램 */
    public static void main(String[] args)
    {
        String txt = "GEEKS FOR GEEKS";
        String pat = "GEEK";
        int q = 101; // 소수
        search(pat, txt, q);
    }
}

// 이 코드는 nuclode가 제공했습니다

// 실행 결과
// Pattern found at index 0
// Pattern found at index 10

• d
  : 입력되는 알파벳의 문자 종류를 나타내는 변수입니다.
  : 256인 이유는 ASCII 코드를 기반으로 한 문자열 검색에서 총 256가지의 문자(0부터 255까지)가 가능하기 때문.
• q
  : 소수를 나타내는 변수로, 해시 함수에서 사용됩니다.
  : 해시 함수의 결과를 다양하게 분포시키는 데 도움을 줍니다. 해시 충돌을 줄이기 위해 사용되며, 이는 검색 시간을 효율적으로 만드는 데 중요한 요소.
• h
  : 해시 함수에서 사용되는 변수로, pow(d, M-1)%q를 계산한 값입니다.
  : 슬라이딩 윈도우에서 제외되는 부분에 대한 가중치를 계산하는 데 사용됩니다. 이 값은 주어진 문자열의 해시 값을 업데이트할 때 사용되며, 제외되는 문자의 해시 값을 빠르게 제거하고 새로 추가되는 문자의 해시 값을 계산하는 데 도움이 됩니다.

 

---

4. KMP 알고리즘

 

알고리즘 - KMP 알고리즘 : 문자열 검색을 위한 알고리즘

 

• Knuth-Morris-Pratt algorithm
• 시간복잡도 : O(M+N)
• 불일치가 발생하기 직전까지 같았던 부분은 다시 비교하지 않고 패턴 매칭(검색)을 진행.

 

import java.util.Arrays;

public class KnuthMorrisPratt {
    public static void main(String[] args) {
        String string = "ABCABAB ABABABAABAAC";
        String pattern = "ABABAABA";

        int[] pi= fail(pattern);
        System.out.println("pi Table: " + Arrays.toString(pi));

        kmp(string, pattern, pi);
    }

    // Method to build lookup table using pattern
    private static int[] fail(String pattern) {
            // 일치하는 문자열의 길이에 따른 경계의 길이를 저장.
            // 일치하는 문자열이 4개 -> buildLookupTable[4]에 저장
              int m = pattern.length();
        int[] pi= new int[m];
        int j = 0; // 접두사 끝 좌표
        // 일치하는 문자열이 하나도 없으면 무조건 0이라 1부터 시작.
        for(int i=1; i<m; i++){ // 접미사 끝 좌표, 일치하는 문자열의 길이
            while(j>0 && pattern.charAt(i) != pattern.charAt(j))
                j = pi[j-1]; // ABABAA(1)
            // 굳이 확인하지 않아도 접두부와 접미부가 같다는 것을 보장할 수 있다.
            // j를 새로운 접두부 바로 뒤로 옮긴다.
            if(pattern.charAt(i) == pattern.charAt(j))
                pi[i] = ++j; // ABA, ABAB, ABABA, ABABAA(2), ABABAAB, ABABAABA
              // 접두부, 점미부가 일치하는 부분이 없음. 그냥 통과.
              // AB
        }
        return pi;
    }

    // KMP string search method
    private static void kmp(String parent, String pattern, int[] pi) {
            int n = parent.length(), m = pattern.length();
        int j = 0; // pattern index
        for(int i=0; i<n; i++){ // parent index
            while(j > 0 && parent.charAt(i) != pattern.charAt(j))
                j = pi[j-1]; // 불일치
              if(parent.charAt(i) == pattern.charAt(j)){ // 일치
                  if(j==m-1){ // 찾음
                      break;
                    }else{ // 다음 글자
                        j++;
                    }
                  }
                }
                if (j == m-1) {
            System.out.println("Found pattern at index: " + (i - j));
        } else {
            System.out.println("Could not find pattern");
        }
    }
}

fail() 실패함수라고 부른다.

 

문자열과 특정 패턴이 불일치하면 어떻게 행동할지 결정해야 한다.

 

이때 최대 경계 테이블을 참고하는데 이를 fail() 함수에서 초기화한다.

 

 

Knuth-Morris-Pratt Algorithm

 

• 관련 문제

백준 1786번: 찾기

 

 

---

5. 보이어-무어 알고리즘

 

알고리즘 - 보이어-무어 알고리즘 : 문자열 검색을 위한 또다른 알고리즘

 

 

뒤에서부터 비교한다.

 

불일치 시 몇 칸을 이동할지 미리 결정해 놓는다.

public class BoyerMoore {
    public static void main(String[] args) {
        String text = "ABAAABCDABC";
        String pattern = "ABC";
        char[] textArr = text.toCharArray();
        char[] patternArr = pattern.toCharArray();

        int pos = boyerMoore(textArr, patternArr);
        if (pos == -1) {
            System.out.println("Pattern not found");
        } else {
            System.out.println("Pattern found at position: " + pos);
        }
    }

    static int SIZE = 256;

    static int max(int a, int b) {
        return (a > b) ? a : b;
    }

    static void badCharHeuristic(char[] str, int size, int badchar[]) {
        int i;

        for (i = 0; i < SIZE; i++)
            badchar[i] = -1;

        for (i = 0; i < size; i++)
            badchar[(int) str[i]] = i;
    }

    static int boyerMoore(char txt[], char pat[]) {
        int m = pat.length;
        int n = txt.length;

        int badchar[] = new int[SIZE];

        badCharHeuristic(pat, m, badchar);

        int s = 0;

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

            while (j >= 0 && pat[j] == txt[s + j])
                j--;

            if (j < 0) {
                return s;
            } else
                s += max(1, j - badchar[txt[s + j]]);
        }
        return -1;
    }
}

 

---