[Algorithms] String(Pattern) Matching

글 작성자: caputdraconis

String 이란

길이가 0 이상인 Character 들의 나열을 의미합니다.
길이가 0 인 String 은 "" 와 같이 표현할 수 있으며, Empty String 이라고 부릅니다.
그와 반대로, 길이가 1 이상인 String 은 Non-empty String 이라고 부릅니다.

String 의 예시

- C++ Program : C++ 로 작성한 .cpp 파일도 하나의 문자열이라고 할 수 있습니다.
- HTML Document : <html><h3>호호잇!!</h3></html> 과 같이 우리가 브라우저를 통해서 웹페이지를 이용할 때, 사용되는 HTML 파일도 하나의 문자열입니다.
- DNA Sequence : {A, C, G, T} 로 구성된 염기서열의 나열도 문자열입니다.
- Digitized Image : 디지털 이미지는 {0, 1} 로 구성된 바이너리 문자열입니다.

Substring

문자열 P 의 Substring 은, P[i, j] 와 같이 표현할 수 있습니다. i와 j는 Index 를 의미합니다.
즉 전체 문자열 P 의 일부분을 의미하며, 그 일부분이 P 에 포함되어야 합니다.

Prefix of P : P 의 접두사를 의미하며, P[i, j] 에서 i 가 0으로 고정된 경우를 의미합니다. P 의 앞부분을 잘라온 형태로 생각하면 됩니다. P의 길이가 m 이라고 할 때, P 의 접두사는 총 m 개 존재할 수 있습니다.

Suffix of P : P 의 접미사를 의미하며, P[i, j] 에서 j가 m-1 로 고정된 경우를 의미합니다. P 의 뒷부분을 잘라온 형태로 생각하면 됩니다.접미사 또한 총 m 개 존재할 수 있습니다.

Proper Prefix/Suffix of P : 앞에 Proper 이 붙으면 진접두사/진접미사 라고 해석되며, 이는 전체 문자열 P 를 제외한 경우들을 가리키게 됩니다. P[0, m-2] 까지만 Proper Prefix, P[1, m-1] 까지만 Proper Suffix 인 것입니다. 여기에 전체 문자열 P와 같은 P[0, m-1] 이 포함되면 이는 Proper Prefix/Suffix 라고 할 수 없습니다. 전체 문자열 P 인 경우 한 가지가 빠졌기에, 각각 m-1 개가 존재하게 됩니다.

Pattern Matching Problem 은 Text T 와 Pattern P 가 주어졌을 때, T의 Substring 중 P와 같은 것이 있는지를 확인하는 문제입니다.

Brute-Force Algorithm

모든 가능한 경우를 체크하는 방식의 알고리즘으로, Character-by-Character Comparison 을 합니다.
Mismatch 가 발생했을 때, 무조건 한 칸씩만 오른쪽으로 움직이고 다시 처음부터 비교를 하는 방식입니다.

Brute-Force Algorithm 을 C++ 코드로 나타내면 아래와 같습니다.

#include <iostream>
#include <string>

using namespace std;

int BruteForceMatch(string T, string P) {
	/*
		T : 길이가 n 인 Text
		P : 길이가 m인 Pattern
        
        Input Size : n + m
	*/
	int n = T.length(), m = P.length();

	for (int i=0; i<=n-m; i++) { // i 는 Text Index
		int j = 0; // Pattern index
		while (j < m && T[i + j] == P[j])
			j ++;
		if (j == m) // Pattern Matching!
			return i; // T[i] 부터 Pattern 발생
	}
	return -1; // No Match
}

Worst Case

T = aaaaaaaaaaaaah
P = aaah
입력으로 들어온 두 개의 문자열이 위와 같을 때, 바깥 반복문(i 반복문) 한 번의 사이클당 총 m 번의 비교를 수행해야 합니다. 총 사이클이 n-m 번이므로, O(m(n-m)) => O(nm) time 에 수행됩니다.

KMP Algorithm

풀네임은 Knuth-Morris-Pratt's Algorithm 입니다. 이 알고리즘은 Brute-Force Algorithm 에서 발생했던 중복되는 비교 연산을 줄이는 것을 목표로 하는 알고리즘입니다. 이를 위해서 한 칸씩만 Shift 했던 Brute-Force Algorithm 과 다르게, 여러 칸을 Shift 합니다.

Mismatch 가 발생했을 때, 중복 비교 연산이 발생하지 않으며 올바른 Pattern Matching 결과를 낼 수 있는 최대 Shift 를 진행합니다.

KMP 알고리즘은 패턴을 Preprocessing(전처리) 하며, Mismatch 발생 시 몇 칸을 Shift 할 수 있는지를 미리 계산해놓습니다. 이러한 작업을 수행하는 함수를 failureFunction F(j) 라고 합니다. 이 함수는, P[0, j] 의 Prefix 와 P[1, j] 의 Suffix 가 같은 것들 중 가장 큰 사이즈로 정의됩니다.

이렇게 mutiple shift 를 해도 괜찮은 이유(Correctness) 는, Longest 로 찾았기 때문입니다. 만약 shift 해서 넘어간 영역에 Pattern 이 발생할 수 있다면, failureFunction 에서 더 Largest Size 를 찾았어야 합니다.

KMP Algorithm 을 C++ 로 구현한 코드는 아래와 같습니다.

#include <iostream>
#include <string>

using namespace std;

int *failureFunction(string P)
{
	/*
    	Pattern Preprocessing Function
		O(2m) time => O(m) time
	*/
	int m = P.length(), i = 1, j = 0; // F[0] 은 이미 0으로 초기화를 했기에, i=1 부터 시작
	int *F = new int[m + 1];

	F[0] = 0; // index 0 은 항상 0으로 초기화

	while (i < m) // 반복 횟수 2m 번을 넘길 수 없음
	{
		if (P[i] == P[j]) // j+1 개의 문자가 일치했다!! 많아야 m 번 수행된다.
		{
			F[i] = j + 1; // update
			i++;
			j++; // 더 Longest 가 있나 체크
		}
		else if (j > 0) // 하나 이상이라도 맞췄다.. mismatch 가 발생한 상황
			j = F[j - 1]; // Use Failure Function to Shift P
		else // j == 0. mismatch 가 발생한 상황. 많아야 m 번
		{
			F[i] = 0; // No Match
			i++;
		}
	}
	return F;
}

int KMPMatch(string T, string P)
{
	/*
		O(m+n) time. <= O(m) time 은 failureFunction 수행 시간
	*/
	int *F = failureFunction(P); // Pattern Preprocessing => O(m) time
	int i = 0; // 현재 비교하고 있는 T의 Index. 비교 시작 지점이 아니다.
	int j = 0; // 현재 비교하고 있는 P의 Index
	int n = T.length(), m = P.length();

	while (i < n) // O(n) time. 
	{
		// Match
		if (T[i] == P[j]) // 지금 보고 있는 문자끼리는 맞구만
		{
			if (j == m - 1) // Pattern 다 맞았다.
				return i - j; // i 는 현재 T 에 존재하는 Pattern 의 마지막 인덱스. j 는 현재 P의 마지막 인덱스. 이 둘을 빼면 T 에 등장하는 Pattern 의 첫 인덱스를 구할 수 있다.
			i++; // 다음꺼도 비교해보자
			j++; // 다음꺼도 비교해보자
		}
		// MisMatch
		else if (j > 0) // 하나라도 맞았다..
			j = F[j - 1]; // i 증가 X
		else
			i++; j=0;
	}
	return -1; // No Match
}

Boyer-Moore Algorithm Variation Version

보이어 무어 알고리즘에서는 Heuristic 이라는 새로운 개념이 등장합니다. 휴리스틱이란, 경험에 기반하여 문제를 해결, 학습, 발견해내는 방법을 의미합니다. Global Optimal Solution 을 찾는 것이 목표이지만, 가끔 오차가 발생할 수도 있는 알고리즘입니다. 보이어 무어 알고리즘에는 2개의 휴리스틱이 포함됩니다.

1. Looking-glass Heuristic
Looking-glass 란 거꾸로의, 반대의 라는 의미를 가지고 있습니다. 보이어 무어 알고리즘에서는, Pattern P를 T 의 일부분을 비교할 때 뒤에서부터 비교합니다.
2. Character-jump Heuristic
Text 의 index i 에서 Mismatch 가 발생했을 때, T[i] = c 라고 가정해보겠습니다.
만약 P 에 c 문자가 있다면, P 에서 가장 마지막에 위치한 c 와 T[i] 를 Align 하고 다시 P의 가장 뒤에서부터 비교를 시작합니다. P 에 c 문자가 없다면, P[0] 과 T[i+1] 이 정렬되도록 합니다. 이는 보이어 무어 알고리즘에서 가장 많이 Shift 하는 케이스가 됩니다.

대략.. 보이어 무어 알고리즘 플로우를 그려보면 위 (발로 그린)그림과 같습니다..

보이어 무어 알고리즘은 KMP 알고리즘과 비슷하게, 본격적인 Pattern Matching 전에 Pattern Preprocessing 이 필요합니다. 이 전처리에서는 Pattern 에서 특정 문자의 가장 마지막 위치를 찾는 작업이 수행됩니다. 함수 이름은 Last-Occurence Function 입니다. 특정 알파벳 c 에 대해서 P[i] = c 인 가장 큰 i 값을 저장하거나, 만약 Pattern 에 c 가 존재하지 않다면 -1 을 저장한 배열을 생성하는 함수입니다. 이 함수가 가장 먼저 하는 작업은 Pattern 에 포함될 수 있는 알파벳의 수(s) 만큼의 배열을 모두 -1로 초기화하는 것입니다. 여기서 O(s) time 이 필요합니다. 그 후에 Pattern 을 앞에서부터 스캔해가며, 등장하는 알파벳들의 가장 마지막 위치를 업데이트 하는 방식으로 수행됩니다. 여기서는 O(m) time 이 필요합니다. 그러므로 이 Last-Occurence Function 의 수행시간은 O(m + s) time 입니다.

보이어 무어 알고리즘의 C++ 코드입니다.

// Last-Occurence Function 구현 X

#include "bits/stdc++.h"

using namespace std;


int BoyerMooreMatch(string T, string P) {
    int *L = lastOccurenceFunction(P); // O(m+s) time
    int n = T.length();
    int m = P.length();

    int i=m-1, j=m-1;
    do {
        if (T[i] == P[j]) {
            if (j == 0) // Pattern 의 앞까지 비교 완료 => Match!!
                return i; // T에서 P 가 등장하는 맨 앞 index 리턴
            else {
                // 이제 그 앞에꺼 비교해보자!
                i = i-1;
                j = j-1; 
            }
        }
        else {
            // Character Jump
            int l = L[T[i]]; // Mismatch 가 발생한 Text 의 Character 가 Pattern 에서 가장 마지막에 등장하는 위치를 가져와!
            i = i + m - min(j, 1 + l); // 
            j = m - 1; // 다시 Pattern 의 맨 뒤부터 비교를 시작
        }
    } while (i >= n-1)

    return -1; // No match
}

[Algorithms] String(Pattern) Matching

String 이란

String 의 예시

Substring

Brute-Force Algorithm

Worst Case

KMP Algorithm

Boyer-Moore Algorithm Variation Version

Analysis

댓글

이 글 공유하기

티스토리툴바

String 이란

String 의 예시

Substring

Brute-Force Algorithm

Worst Case

KMP Algorithm

Boyer-Moore Algorithm Variation Version

Analysis

댓글

이 글 공유하기

다른 글

[Algorithms] Dynamic Programming

[C++] 백준 BOJ 21939 문제 추천 시스템 Version 1

[C++] 거리두기 확인하기(2021 카카오 채용연계형 인턴십 코딩테스트)

[Python] 숫자 문자열과 영단어(2021 카카오 채용연계형 인턴십 코딩테스트)

티스토리툴바