[알고리즘] 문자열 매칭

1. 원시적인 매칭 방법

- 문자열 매칭 : 텍스트 문자열이 패턴 문자열을 포함하고 있는지 알아보는 것.

- 원시적인 방법으로는 순서대로 비교해나감.

- 패턴을 총 n-m+1번 비교하면 작업이 완료됨.

naiveMatching(A[], P[])
{
    for i <- 1 to n-m+1 {
        if ( P[1 ... m] = A[i ... i+m-1)
            then A[i] 매칭 발견됨;
    }
}

- 문자열 비교 중 불일치가 일어나도 무조건 한칸씩 이동하면서 비교해나감.

- 이 부분을 개선할 수 있음. 문자열의 일부가 같다는 정보를 알면 불일치가 일어난 곳의 문자와 패턴의 위치를 바로 비교할 수 있음.

 

2. 오토마타를 이용한 매칭

 오토마타

- 여러개의 상태로 표현됨. 문제 해결 절차를 상태간의 이동으로 나타낸 것.

- 여기서 상태는 문제 해결 과정의 문맥을 반영함.

 

오토마타의 다섯 가지 구성 요소

( Q, q₀, F, ∑,δ)

Q : 상태들의 집합

q₀ : 오토마타의 작동이 시작되는 상태

F : 목표 상태(목적이 달성된 상태)들의 집합

∑ : 입력 가능한 문자 집합

δ : 상태 전이 함수

 

Q = { 0, 1, 2, 3 }, q₀ = 0, F = {7}, ∑ = {H,E,L,L,O,W,O,R,O,O,R,L,D}

- 각 상태는 문자열 "ORL" 중 얼마만큼 일치했는가를 나타냄.

- 상태 0은 아무 것도 찾지 못한 상태, 상태 2는 "OR"까지 찾은 상태, 상태 3은 "ORL"를 전부 나타낸 상태

 

상태 전이 함수 δ의 표현

- 이 테이블에서 (1,R)의 자리는 2, 이것은 δ(1,R) = 2임을 뜻함. 상태 1에서 문자 'R'를 입력으로 받으면 상태 4로 이동함을 의미함.

 

오토마타가 주어졌을 때 매칭 여부를 체크하는 알고리즘

FA-Matcher( A[], δ[][], F )
{
    q <- 0;
    for i <- 1 to n {
        q <- δ(q,A[i]);
        if ( q ∈ F ) then A[i-m+1] 자리에서 매칭이 발생했음을 알림;
    }
}

 

수행시간 분석

- 알고리즘은 단순하게 for 루프를 n번 반복하는 것.

- 따라서 전체 수행 시간은 Θ(n)

- 하지만 이것은 오토마타의 상태 전이 함수를 준비하는 시간을 고려하지 않음.

- 상태 전이 함수 테이블을 가장 효율적으로 만들면 Θ(|∑|m)의 시간이 필요함.

- 따라서 오토마타를 이용하는 매칭 알고리즘의 총 수행 시간은 Θ(n+|∑|m)이 됨.

 

개선 방법

- 테이블을 만들 때 매칭에 사용하는 패턴에 포함된 문자들의 집합 ∑'만으로 테이블을 만들고 나머지 문자들은 하나로 처리할 수 있음.

- 이 테이블을 이용할 때는 인덱스 변환 테이블 i[]를 사용함.

- 상태 s에서 문자 r을 만나는 경우, 상태 전이 함수 계산을 할 때는 δ(s,r) 대신 δ(s,i[r])을 사용함.

- 이 경우에는 상태 전이 함수를 만드는 데 Θ(|∑'|m + |∑|)의 시간이 걸림.

 

3. 라빈-카프 알고리즘

- 문자열 패턴을 수치로 바꾸어 문자열의 비교를 수치 비교로 전환해 매칭을 하는 방법.

- 라빈-카프 알고리즘은 수치화 알고리즘의 골격을 사용하면서 수치화 알고리즘의 오버플로 문제를 해결한 알고리즘.

- aᵢ를 직접 다루는 대신 나머지 연산인 모듈러(mod) 연산의 결과를 이용함.

- 컴퓨터 레지스터가 감당할 수 있는 범위에서 충분히 큰 소수 q를 하나 잡아 aᵢ 대신 bᵢ = aᵢ mod q를 사용함.

- 이 계산은 상수 시간에 행해지고, bᵢ의 크기는 모듈러 연산으로 q 미만으로 제한됨.

 

RabinKarp(A[],P[],d,q)
// n : 배열 A[]의 길이, m: 배열 P[]의 길이
{
    p <- 0; b₁ <- 0;
    for i <- 1 to m {
        p <- (dp + P[i]) mod q;
        b₁ <- (db₁ + A[i]) mod q ;
    }
    h <- dᵐ⁻¹ mod q;
 ①for i <- 1 to n-m + 1 {
        if ( i ≠ 1 ) then bᵢ <- (d ((bᵢ₋₁ -hA[i-1])mod q) + A[i+m-1]) mod q;
     ②if (p = bᵢ) then
         ③if (P[1 ... m ] = A[ i ... i+m-1])
            then A[i] 자리에서 매칭이 발견되었음을 알림;
    }
}

- ①의 for 루프는 알고리즘의 시간을 좌우함. n-m+1회 반복됨. m ≪ n이므로 이것은 Θ(n)

- ②의 p = bᵢ가 참이 되면 ③의 비교를 하는 데 O(m)의 시간이 듦. 매치가 되면 이 시간은 Θ(m)이 됨.

- 매치가 일어나는 횟수가 k라면 이 알고리즘의 수행 시간은 Θ(n+km)이 됨.

- 매치가 아주 많이 일어나는 특이한 경우가 아니라면 보통 Θ(n)과 같음.

 

4. KMP 알고리즘

- 오토마타를 이용한 매칭에서는 문자열을 차례로 훑음.

- 그리고 어느 지접에서 매칭이 성공하진 못했어도 그 지점을 기준으로 마지막 몇 개의 부분 문자열이 찾으려는 패턴 문자열의 앞부분과 일치한다면 그 정보를 이용함.

- KMP 알고리즘도 같은 동기에서 출발. 오토마타에서처럼 전처리 비용이 많이 들지 않음.

- KMP 알고리즘의 핵심은 패턴의 각 위치에 대해 매칭에 실패했을 때 돌아갈 곳을 알려주는 일차원 배열을 준비하고 이를 이용해 텍스트 문자열을 훑어나감.

- 이는 패턴 문자열에 대해 오토마타를 만들어두는 것과 유사함.

 

- 수행과정의 한 순간. 패턴의 앞부분 "ABCDABC"까지는 텍스트와 일치하였고 패턴의 문자 'W'가 텍스트의 문자 'D'와 일치하지 않음을 확인한 직후.

- 텍스트의 문자 'D' 직전의 문자열 'ABC'는 패턴의 맨 앞부분 세 문자와 일치하므로 이 정보를 이용하면 텍스트의 문자 'D'와 패턴의 4번째 문자를 비교하면 됨.

 

- 텍스트에서 불일치가 일어난 부분을 패턴의 어느 부분과 비교하면 되는지에 대한 정보.

- 패턴의 8번 문자와 불일치가 일어나면 패턴의 4번 문자와 비교를 하면 됨.

 

KMP 알고리즘

KMP( A[], P[] )
// n : 배열 A[]의 길이, m : 배열 P[]의 길이
{
    preprocessing(P);
    i <- 1; // 본문 문자열 포인터
    j <- 1; // 패턴 문자열 포인터
 ①while ( i ≤ n ) {
        if ( j = 0 or A[i] = P[j] )
            ②then { i++; j++;}
            ③else j <- π[j];
        if ( j = m + 1 ) then {
            A[i-m]에서 매칭되었음을 알림;
           ④j <- π[j];
        }
    }
}

preprocessing(P[])
// m : 배열 P[]의 길이
{
    j <- 1;
    k <- 0;
    π[1] <- 0;
    while ( j ≤ m ) {
        if ( k = 0 or P[j] = P[k] ) then { j++; k++; π[j] <- k;}
            else k <- π[k];
}

 

수행 시간 분석

- 함수 KMP()에서 시간을 좌우하는 것은 ①의 while 루프.

- 루프가 한 번 반복될 때마다 배열 A[]에서 한 칸 오른쪽으로 진행하거나(i++), 패턴 배열 P[]에서 뒷걸음침. ( j <- π[j] )

- 매 while 루프에서 하는 일은 상수 시간 작업이크로 while 루프와 관련된 수행시간은 Θ(n).

- 함수 preprocessing()은 i+(i-j) 대신 j + ( j - k )를 사용해 같은 방법으로 분석하면 수행 시간은 Θ(m).

- KMP 알고리즘의 총 수행 시간은 Θ(n).

 

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

- 앞에서 나온 알고리즘은 모든 문자를 적어도 한 번씩은 확인해야 하지만, 보이어-무어 알고리즘에서 일부 문자는 보지 않아도 됨.

- 두 문자열을 맨 뒤부터 비교함.

- A[1 ... m]의 맨 오른쪽 문자 A[m]이 P[1 ... m]에 존재하지 않는다면 A[2], ..., A[m-1]로 시작하는 문자열들은 P[1 .. m]과 매치될 가능성이 없음.

- 따라서 바로 A[m+1 ... 2m]과 P[1...m]을 비교하면 됨. 이 경우에는 텍스트에서 m-1개의 문자는 보지 않고 점프할 수 있음.

- 한 텍스트 내의 마지막 문자(P[m]과 대응되는 자리에 있는 문자)가 P[1 ...m]에 포함되어 있다면 P[1 ... m]이 이 문자를 완전히 지나갈 때 까지는 매칭될 가능성이 없음.

- 보이어-무어 알고리즘은 이런 경우를 한 번에 점프해버림.

 

- 방금 패턴과 비교를 한 텍스트 내의 마지막 문자가 P[1 ... m]에 포함되어 있는 문자라 해도 그것이 P[1 ... m]의 몇 번째 문자인지에 따라 한 번에 2칸이상 점프할 수 있음.

 

보이어-무어-호스풀 알고리즘

- 보이어-무어 알고리즘에서 등장하는 점프 : 꽤 까다로운 알고리즘.

- 까다로운 부분을 좀 간단하게 처리한 알고리즘 : 보이어-무어-호스풀 알고리즘. (전체 성능에는 거의 영향 없음)

BoyerMooreHorspool( A[], P[] )
// n : 배열 A[]의 길이, m : 배열 P[]의 길이
{
 ①computeJump(P,jump);
    i <- 1;
 ②while ( i ≤n-m+1) {
        j <- m; k <- i+m-1;
     ③while ( j > 0 and P[j] = A[k] ) {
            j--; k --;
        }
        if ( j = 0 ) then A[i] 자리에서 매칭이 발견되었음;
     ④i <- i + jump[A[i+m-1]];
    }
}

수행 시간 분석

- ①의 계산은 Θ(m)의 시간이 소요됨.

- ②의 while 루프는 최악의 경우 n-m+1회(O(n)회) 반복되고, ③의 while 루프는 O(m)의 시간이 소요됨.

- 그러므로 총 수행 시간은 O(mn)

- 최악의 경우는 텍스트 전체가 동일한 문자로 채워져 있는 경우, 이때는 정확히 Θ(mn)의 시간이 소요됨.

- 보이어-무어 알고리즘은 이론상으로는 라빈-카프나 KMP보다 비효율적, 일반적인 상황에서 가장 빨라 현장에서 많이 사용함.

- ③의 while 루프는 보통 몇 번 반복하다 끝나고, ②의 while 루프도 ④의 점프에 의해 n-m+1회보다 훨씬 작은 횟수만큼 반복하기 때문.

- 오른쪽부터 비교하는 것과 점프에서 이득을 얻으면 최선의 경우 수행시간은 Θ(n/m)이 됨.

 

완전한 보이어-무어 알고리즘

- 위의 알고리즘에서 ③의 while 루프가 끝났을 때, j=0이라면 P[1 ... m]과 A[i ... i+m-1]이 일치하며, 그렇지 않으면 j와 k는 각각 P[1 ... m]과 A[i ... i+m-1]을 비교할 때 처음으로 일치하지 않는 인덱스를 갖게됨.

- j가 m보다 r번째 왼쪽에 있다면 텍스트에서 jump[A[K]] - r 만큼 점프할 수 있음. 보이어-무어 알고리즘에서도 이를 이용하는데 불일치 문자 휴리스틱이라 함.

- 불일치가 일어났더라도 P[m]에서 P[j+1]까지, 즉 P[j+1 ... m]은 일치된 것. 보이어-무어 알고리즘에서는 맨 마지막 문자만 고려하는 ④대신 오른쪽부터 일치가 일어난 부분 문자열도 고려함.

- P[1 ... m]의 다른 부분에서 P[j+1 ... m ]과 일치하는 부분 문자열이 없으면 한번에 점프할 수 있음.

- P[j + 1 ...m]과 일치하는 부분 문자열이 있으면 그 부분이 A[i ... i +m-1]과 나란해지도록 점프할 수 있음. 이를 일치 접미부 휴리스틱이라 함.

- 이 두 휴리스틱을 적용하기 위해 2개의 일차원 배열을 준비해두어야 함.

- 불일치 문자를 위한 점프는 배열 jump[]을 그대로 사용하면 되고, 일치 접미부 관련 배열을 만드는 과정은 좀 까다롭지만 원리는 간단함.

 

참고 : http://www.yes24.com/Product/Goods/58154784