[자료구조] Text Processing

패턴 매칭 알고리즘 (Pattern Matching Algorithm)

이번 포스팅에서는 문자열 탐색에 사용되는 패턴 매칭 알고리즘(Pattern Matching Algorithm)에 대해 자세히 알아보겠다. 패턴 매칭 알고리즘은 텍스트 편집기, 검색 엔진, 생물학 연구 등 다양한 분야에서 핵심적인 역할을 하고 있으니 알아두면 유용할 것이다.

1. String과 Pattern Matching

String은 문자들의 순서(sequence)다. 예를 들어, 파이썬 프로그램, HTML 문서, DNA 염기서열, 디지털 이미지 등은 모두 문자열로 표현될 수 있다.

Alphabet은 특정 문자열 집합에 사용될 수 있는 가능한 모든 문자들의 집합이다. 예를 들어, ASCII, Unicode, {0, 1}, {A, C, G, T} 등은 모두 alphabet의 예시다.

Pattern Matching Problem은 텍스트 T와 패턴 P가 주어졌을 때, T에서 P와 동일한 부분 문자열(substring)을 찾는 문제다.

2. Brute-Force Algorithm (무차별 대입 알고리즘)

가장 간단한 패턴 매칭 알고리즘은 Brute-Force Algorithm(무차별 대입 알고리즘)이다. 이 알고리즘은 패턴 P를 텍스트 T의 모든 위치에 대해 비교하며, 일치하는 부분 문자열을 찾을 때까지 반복한다.

2.1. 시간 복잡도

Brute-Force 알고리즘의 시간 복잡도는 O(nm)이다. (n은 텍스트 T의 길이, m은 패턴 P의 길이) 최악의 경우, 텍스트의 모든 위치에서 패턴을 비교해야 하므로 시간이 오래 걸릴 수 있다.
가령 T = aaaaaa~h, P = aaaaah인 경우, 패턴 이동 O(n)과 패턴 매치 확인 O(m)이 소요되므로 worst case이다. 이는 문장에서 잘 나타나지 않으나, 이미지나 DNA에서 나타날 수 있다.

2.2. 구현 방법

def BruteForceMatch(T, P):
    n, m = len(T), len(P)
    for i in range(n - m + 1):
        j = 0
        while j < m and T[i + j] == P[j]:
            j += 1
        if j == m:
            return i  # match found at index i
    return -1  # no match found

Brute-force algorithm example

3. Boyer-Moore Algorithm (보이어-무어 알고리즘)

Boyer-Moore Algorithm(보이어-무어 알고리즘)은 Brute-Force 알고리즘보다 효율적인 패턴 매칭 알고리즘이다. 이 알고리즘은 두 가지 휴리스틱(heuristic)을 사용하여 패턴을 비교하고 이동시킨다.

Looking-Glass Heuristic: 패턴 P를 텍스트 T의 부분 문자열과 오른쪽에서 왼쪽으로 비교한다. 즉, 뒤에서부터 비교한다.
Character-Jump Heuristic: 불일치(mismatch)가 발생하면, 불일치 문자가 패턴 P에 존재하는 경우 마지막으로 나타나는 위치로 패턴을 이동시키고, 그렇지 않은 경우 패턴을 한 칸 오른쪽으로 이동시킨다.

3.1. Last Occurrence Function

Boyer-Moore 알고리즘은 Last Occurrence Function(마지막 발생 함수) L을 사용한다. L(c)는 패턴 P에서 문자 c가 마지막으로 나타나는 위치를 반환하며, 만약 c가 P에 존재하지 않으면 -1을 반환한다.

Boyer-Moore algorithm example

3.2. 시간 복잡도

Boyer-Moore 알고리즘의 시간 복잡도는 최악의 경우 O(nm+s)이다. T = aaaaa~a, P = baaa인 경우를 생각해보면, 계속 a가 매치되므로 한 칸 씩 이동하게 되어 Brute-Force 알고리즘과 비슷한 시간복잡도를 갖는다. 하지만 일반적인 문장에서는 이러지 않기에 Brute-Force 알고리즘보다 훨씬 빠르게 동작한다.

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

KMP Algorithm(Knuth-Morris-Pratt 알고리즘)은 Boyer-Moore 알고리즘과 마찬가지로 Brute-Force 알고리즘보다 효율적인 패턴 매칭 알고리즘이다. 이 알고리즘은 패턴 P를 전처리하여 KMP Failure Function(KMP 실패 함수) F를 생성한다. F(j)는 P[0..j]의 가장 긴 접두사(prefix)이면서 동시에 접미사(suffix)인 문자열의 길이를 나타낸다.

KMP failure function F(j)

4.1. KMP Failure Function

KMP Failure Function은 불일치가 발생했을 때, 패턴을 얼마나 이동시켜야 하는지를 알려준다. 불일치가 발생한 위치 j에서 F(j-1)만큼 패턴을 이동시켜 중복 비교를 피할 수 있다.

KMP algorithm example

4.2. 시간 복잡도

KMP 알고리즘에서 Failure function은 2m번의 iteration을 넘지 않고(O(m)), 패턴 이동은 2n번의 iteration을 넘지 않는다(O(n)). 따라서 KMP algorithm의 시간 복잡도는 O(n + m)으로, 최적의 시간 복잡도를 갖는다. 문자열 탐색에서 거의 최고의 성능을 보이므로 주된 알고리즘 중 하나이다.

마무리하며

이번 포스팅에서는 Brute-Force, Boyer-Moore, KMP 알고리즘과 같이 다양한 패턴 매칭 알고리즘에 대해 알아보았다. 각 알고리즘은 장단점을 가지고 있으며, 상황에 따라 적절한 알고리즘을 선택하여 사용해야 한다. 오늘로 자료구조 강의 포스팅도 마무리되었다. 앞으로도 컴퓨터 과학과 관련된 공부를 이어가며, 객체 지향 프로그래밍과 알고리즘 등의 주제로 찾아오도록 하겠다.

추천글 :
[자료구조] 왜 자료구조를 배우는가?
(https://hyeonb.blogspot.com/2024/03/blog-post.html)
[자료구조] Binary search tree
(https://hyeonb.blogspot.com/2024/05/binary-search-tree_20.html)