12강. 스트링 알고리즘 (1)

1. 스트링 알고리즘 관련 기본 개념

• 스트링( string )이란?
  • 문자가 연속적으로 나열된 문자열
  • 예시
    • ATATCGCCCACTAT
    • 001011010001110101
• 알파벳 ( alphabet, Σ )
  • 스트링에 사용되는 문자들의 집합
  • 예시
    • DNA 서열 ➝ Σ = { A, C, G, T }
    • 이진 데이터 ➝ Σ = { 0, 1 }

2. 스트링 알고리즘

• 스트링에 대한 다양한 문제를 해결하는 알고리즘을 통칭
  • 스트링 매칭
  • 스트링 압축
  • 최장 공통 부분 수열
  • 최장 반복 서브스트링
  • 최장 회문 서브스트링
  • 접미부 트리
  • 접미부 배열
  • …

3. 스트링 매칭

• 텍스트에서 패턴이 나타나는 위치를 찾는 것
  • 텍스트 T = t₀t₁t₂⋯tₙ₋₁ → 긴 스트링, 길이 n
  • 패턴 P = p₀p₁p₂⋯pₘ₋₁ → 짧은 스트링, 길이 m
  • n ≥ m
• 예시
  • T = a a b a a b a a a
  • P = a a b a a
  • 0번째와 3번째 위치에서 패턴을 확인할 수 있음

4. 브루트-포스 스트링 매칭 알고리즘

BruteForce(n, T[ ], m, P[ ]) {
    for (i = 0; i <= n - m; i++) {       // 텍스트의 가능한 모든 위치에서 O(n)
        flag = true;
        for (j = 0; j < m; j++) {        // 패턴의 길이만큼 O(m)
            if (T[i + j] != P[j]) {     // 텍스트와 패턴의 문자를 비교
                flag = false;           // 일치하지 않으면 표시 지움
                break;
            }
        }
        if (flag) 위치 i 출력;           // 표시가 남아있으면 매치
    }
}

• Brute-force algorithm 또는 Naïve algorithm
  • 텍스트의 각 위치에서부터 패턴의 길이만큼 문자를 비교하며 매치를 찾는 방법
• 시간 복잡도 : O(nm)
  • 외부 반복문 : 텍스트의 가능한 시작 위치는 n - m + 1개 → O(n)
  • 내부 반복문: 패턴 길이만큼 최대 m번 문자 비교 → O(m)
  • 따라서 최악의 경우 시간 복잡도는 O(nm)

5. 스트링 매칭 알고리즘

• 패턴을 전처리
  • 라빈-카프 알고리즘
  • KMP 알고리즘
  • 보이어-무어 알고리즘
• 텍스트를 전처리
  • 접미부 트리
  • 접미부 배열

6. 라빈-카프 Rabin-Karp 알고리즘

• 패턴의 해시값으로 매치의 후보를 찾고, 후보에 대해서만 문자별로 비교해서 매치를 찾는 방법
  • 해시 함수 : 문자열을 위한 가중 합 h(S) = ( ∑[i=0 to m-1] sᵢ' × |Σ|^(m-1-i) ) mod M
• 예시
  • Σ={a,b,c,d,e,f,g,⋯,x,y,z}, M = 101
  • P( 패턴 ) = aabaa
  • h( aabaa ) = (0 × 26⁴ + 0 × 26³ + 1 × 26² + 0 × 26¹ + 0 × 26⁰) mod 101 = 70

7. 텍스트 위치별 해시값 계산 (Rabin-Karp)

• 위치 0 ( 시간복잡도 : O(m) )
  • h(aabaa) = (0 × 26⁴ + 0 × 26³ + 1 × 26² + 0 × 26¹ + 0 × 26⁰) mod 101 = 70
• 위치 1~n−m ( 시간복잡도 : O(1) )
  • 해시 함수의 특징을 이용
    • 위치 0에서 0 ~ m 자리까지 계산한 것에서 1 ~ m까지의 계산을 가져와 * 26만 하면 된다.
    • 즉, 위치 0에서 계산한 것에서 - 위치 0의 값만 하면 된다.
  • h(abaab) = (0 × 26⁴ + 1 × 26³ + 0 × 26² + 0 × 26¹ + 1 × 26⁰) mod 101 = (26 × h(aabaa) − 0 × 26⁵ + 1 × 26⁰) mod 101 = (26 × 70 − 0 + 1) mod 101 = 1821 mod 101 = 3

8. Rabin-Karp 알고리즘 성능과 특징

RabinKarp(n, T[], m, P[]) {
    int hp = 0, ht = 0;
    int dm = pow(26, m) % M;

    for (j = 0; j < m; j++) {
        hp = (hp × 26 + P[j] - 97) % M;  // 패턴의 해시값
        ht = (ht × 26 + T[j] - 97) % M;  // 텍스트의 위치 0 해시값
    }

    for (i = 0; i <= n - m; i++) {
        if (hp == ht) {  // 해시값 일치하는 위치에 대해
            flag = true;
            for (j = 0; j < m; j++) {  // 패턴의 길이만큼
                if (T[i + j] != P[j]) {  // 텍스트와 패턴의 문자를 비교
                    flag = false;  // 일치하지 않으면 표시 지움
                    break;
                }
            }
            if (flag) 출력(i);  // 표시가 남아있으면 매치
        }

        if (i < n - m) {
            ht = (ht × 26 - dm × (T[i] - 97) + (T[i + m] - 97)) % M;  // 다음 위치 해시값
        }
    }
}

• hp: 패턴 문자열 P의 해시값
• ht: 현재 텍스트 위치의 해시값
• dm = 26ᵐ mod M: 위치 i+1 해시 계산 시 곱해지는 26의 제곱항 ( 지수 표기 반영 )
• % M: 해시 충돌 방지를 위한 소수 모듈러 연산
• 성능 → O(n + k·m)
  • 전처리: O(m)
  • 텍스트에서 해시값 계산: O(n)
  • 후보 위치에서 문자열 직접 비교 (매치 개수 k): O(k·m)
• 매치 개수가 상수일 경우 → O(n)
• 모든 위치에서 매치되는 경우 ( 최악 ) → O(n·m)

9. KMP 알고리즘

• Knuth-Morris-Pratt 알고리즘이란?
  • 패턴 내의 문자들의 관계를 이용하여, 매칭 시 중복된 비교를 줄임
  • 텍스트의 첫 위치에서 패턴의 앞부분부터 문자 비교
• 일치한 서브스트링에 대한 접두부와 접미부의 최대 일치 정보 활용
  • fᵢ : 패턴의 서브스트링 p₀ p₁ ... pᵢ에서 최대 일치한 접두부의 끝 문자 위치
    • 접두부와 접미부의 최대 일치가 없으면 -1
      • ex. f₀ = -1

10. KMP 알고리즘 - 전처리

PreKMP(m, P[ ]){
    int F[m], idx = -1;
    F[0] = -1;

    for (i = 1; i < m; i++) {
        while (idx >= 0 && P[i] != P[idx + 1])
            idx = F[idx];           // 최대 접두부 찾기

        if (P[i] == P[idx + 1])
            idx++;                 // 마지막 문자 일치

        F[i] = idx;                // i에서의 최대 접두부 설정
    }
    return (F);
}

11. KMP 알고리즘 성능과 특징

KMP(n, T[ ], m, P[ ]) {
    F[0..m-1] = PreKMP(m, P);      // 패턴의 전처리
    int j = -1;

    for (i = 0; i < n; i++) {
        while (j >= 0 && T[i] != P[j+1])
            j = F[j];

        if (T[i] == P[j+1])
            j++;

        if (j == m - 1) {          // 패턴의 마지막 문자까지 일치하면
            위치 i-j 출력;         // 매치 발견
            j = F[j];
        }
    }
}

• 전처리 → O(m)
  • idx 값은 최대 m-1 증가
  • while 문은 최대 m-1만큼 수행
• 매칭 → O(n)
  • j 값은 최대 n 증가
  • while 문은 최대 n만큼 수행
• n ≥ m → 전체 성능 O(n)

12. 정리하기

• 기본 개념
  • 스트링 매칭: 텍스트(길이 n)에서 패턴(길이 m)이 나타나는 위치를 찾는 문제
  • 브루트-포스 스트링 매칭 알고리즘 – 성능 O(nm)
• 라빈-카프 알고리즘
  • 패턴의 해시값으로 매치의 후보를 찾고, 후보에 대해서만 문자별로 비교
  • 성능–매칭 O(n+km) (k: 매치의 개수)
  • 매치의 개수에 따라
    • 최선 O(n)
    • 최악 O(nm)
• KMP 알고리즘
  • 패턴 내의 문자들의 관계를 이용하여 매칭 시 중복된 비교를 줄임
  • 텍스트의 첫 위치에서 패턴의 앞부분부터 문자 비교
  • 전처리 – 패턴의 각 위치별로 접두부와 접미부의 최대 일치 정보를 구함
  • 성능 O(n)
    • 전처리 O(m)
    • 매칭 O(n) (단, n ≥ m)