[edx] Pattern matching 알고리즘

Hyeon Soo·2022년 5월 24일
0

1. 개요

  • 주어진 text에서 주어진 특정 pattern이 존재하는지, 필요시 몇번 등장하는지를 알 수 있는 알고리즘들을 말한다.

  • Brute-force의 발상을 따르면, 텍스트의 1번 string부터 시작하여 패턴과 일치하는지 일일히 비교하는 방법을 쓸 수 있다. 이 경우, 패턴의 길이가 m, text의 길이가 n이면 시간복잡도는 O(mn)이 필요하다.

  • 이보다 조금 더 발전한 알고리즘은 Boyer-Moore, Knuth-Morris-Pratt, Rabin-Karp등 다양하나, 이 글에서는 Boyer-Moore, Knuth-Morris-Pratt 알고리즘을 다룰 것이다.

2. Boyer-Moore

  • Brute-Force에 기반한 알고리즘은 text의 1번 string부터 끝에 이르기까지 하나하나 전부 탐색한다. 하지만, pattern과 text의 1번 string이 일치하지 않는다면, 이후의 몇몇 string은 통째로 건너뛰어도 되는 경우가 많다.

  • Boyer-Moore는 불일치가 발생했을 경우, 얼마나 건너뛰어도 되는지를 계산하여 건너뛰는 것을 통해 시간복잡도를 일부 개선하려는 시도를 한 알고리즘이다.

  • 우선, pattern에 있는 문자가 마지막으로 나타난 것이 몇번째 index이었는지 확인할 수 있는 HashMap을 만든다. 이를 Last occurance table이라고 한다. 예를 들어, pattern으로 테이블을 만들 경우, <p, 0> <a, 1> <t, 3>, <e, 4> <r, 5> <n, 6>이 기본이고, 존재하지 않는 문자는 <*, -1>로 만든다. Pseudo code는 다음과 같다.

LOT(pattern)
	m = pattern.length
    last = HashMap<character, index>
    for 0~m-1
    	last = put(pattern[i], i)
    return last
  • 이때 HashMap에서는 패턴에 존재하는 문자면 index를 반환하고, 존재하지 않는 문자면 -1을 반환하도록 method를 짜주어야 한다.

  • 이 상태에서, pattern의 뒷부분부터 text와 비교한다. 일치하면 계속 비교하지만, 불일치가 발생할 경우, 불일치가 발생한 text의 문자를 LOT에 넣어 반환값을 확인한다. 반환 값이 -1이면은 완전 불일치이므로, 문자를 기준으로 pattern을 통째로 건너뛰어 다시 비교한다. 반환값이 -1이 아니면, 반환된 숫자를 index로 하여, pattern의 해당 index로 이동하여 다시 비교한다.

BoyerMoore(text, pattern)
	last = LOT(pattern)
    i = 0
    while i <= text.length - pattern.length
    	j = pattern.length - 1
        while j >= 0 && text[i+j] = pattern[i]
        	j = j-1
        if j = -1
        	return i //pattern found
        else
        	shift = last[text[i+j]]
            if shift < j
            	i = i+j-shift
            else
            	i = i + 1
    return pattern not found
  • 위의 code에서, 패턴을 찾았을 경우 return을 바로하는 것이 아니라, array, 혹은 그 외의 자료구조를 따로 선언하고 여기에 i를 add 하도록 한 후, 최종적으로 array를 반환하도록 하면, 패턴이 일치하는 모든 텍스트 index를 얻을 수 있다.

  • 기본적으로 시간복잡도는 O(mn)이지만, 최선의 경우 O(m+(n/m))으로 끝낼 수 있으며, 평균적으로도 brute-force에 비해 나은 성능을 보인다.

3. Knuth-Morris-Pratt

  • 이 알고리즘 또한 발상은 Boyer-Moore와 비슷하다. 패턴을 비교하는 과정을 좀 더 개선하는 것이 목표이다.

  • 우선 패턴을 기반으로 failure table을 만들어야 한다. 패턴의 첫 문자를 0으로 하고, 두번째 문자부터 첫번째 문자와 비교를 한다. 이때, 일치하면 1을 부여함과 동시에, 이후의 문자 그 다음 문자와 같으면 2, 그다음과도 같으면 3을 부여한다.

r e v r e v a b c r e v r
0 0 0 1 2 3 0 0 0 1 2 3 4

  • 위와 같은 방식이다. Pseudo code는 다음과 같다.
FailureTable(pattern)
	ft[0] = 0
    i = 0
    j = 1
    while j < pattern.length
    	if pattern[i] = pattern[j]
        	ft[j] = i + 1
            i = i + 1
            j = j + 1
        else if pattenr[i] != pattern[j] && i = 0
        	ft[j] = 0
            j = j + 1
        else
        	i = ft[i-1]
    return ft
  • Failure table을 작성한 이후, 실제 알고리즘에서 패턴과 text를 비교할 때, 비교가 진행되는 만큼 테이블의 index도 하나씩 올린다. 불일치가 발생했을 때, 테이블의 index-1번째 값을 패턴의 index로 하여 비교를 다시 진행한다.
KMP(text, pattern, ft)
	j = 0
    k = 0
    while k < text.length
    	if p[j] = text[k]
        	if j = pattern.length - 1
            	return k // pattern match
            else
            	j = j + 1
                k = k + 1
        else if p[j] != text[k] && j = 0
        	k = k + 1
        else
        	j = ft[j - 1]
  • 시간복잡도가 O(m + n)으로, 마찬가지로 brute-force보다 효율적이다.

출처: https://learning.edx.org/course/course-v1:GTx+CS1332xIV+2T2020/home

이상의 내용은 edx 플랫폼을 통해 GTx에서 제공하는 Data Structures & Algorithms 강의의 내용을 개인적으로 정리한 것입니다. 그렇기 때문에, 부정확한 내용 혹은 잘못 이해하고 있는 내용이 있을 수 있으니 양해 부탁드립니다.

0개의 댓글