패턴 매칭 알고리즘

▶패턴 매칭

---

본문에서 특정 string(패턴)을 찾아야 하는 경우에 유용하게 쓰일 수 있다.

예시)

"asdgsadf"  "a"를 찾아서 "AAA"로 변경하라.

위와 같은 문제가 있을 때, 문제 해결을 위해서 우선 "a"의 위치를 찾아야한다.

이 때 본문이 되는 "asdgsadf"에서 "a"라는 패턴을 찾는 방법을 패턴 매칭이라고 한다.

▶패턴 매칭 알고리즘

---

- 고지식한 패턴 검색 알고리즘(Brute Force)

본문 string을 처음부터 끝까지 차례대로 순회하면서 패턴 내의 문자들을 일일이 비교하는 방식으로 동작한다.

(길이가 10000인 string에서 길이 80의 패턴을 찾는다면 10000*80 = 800000번의 비교가 일어남)

- KMP 알고리즘

: 불일치가 발생한 텍스트 스트링의 앞 부분에 어떤 문자가 있는지를 미리 알고 있으므로,

  불일치가 발생한 앞 부분에 대하여 다시 비교하지 않고 매칭을 수행함

• 패턴을 전처리하여 배열 next[M]을 구해서 잘못된 시작을 최소화함

      next[M] : 불일치가 발생했을 경우 이동할 다음 위치

• 시간복잡도 : O(M + N)

  

  패턴의 각 위치에 대해 매칭에 실패했을 때 돌아갈 곳을 준비해둔다.

   

- 보이어-무어 알고리즘

대부분의 상용 소프트웨어에서 채택하고 있는 알고리즘이다.

뒷쪽에서 앞쪽으로 비교해야 한다는 특징이 있다.

문자열의 인덱스를 저장하는 포인터 역할을 할 변수는

본문에서 처음 비교할 패턴의 끝 문자를 가리키며 시작한다.

본문 : "abcdefghijk"

찾는 패턴 : "bcd"

위와 같은 경우에 포인터 변수는 인덱스 2로 시작한다.

WHILE ( true )

{

IF ( 포인터가 본문의 인덱스 범위를 초과 ) {

break;

}

IF ( 포인터가 가리키는 문자와 찾는 패턴의 끝 문자가 불일치 ) {

IF ( 포인터가 가리키는 문자가 찾는 패턴 내에 존재하지 않는 경우 ) {

포인터를 찾는 패턴의 길이만큼 이동시킨다.

}

IF ( 포인터가 가리키는 문자가 찾는 패턴 내에 존재할 경우 ) {

포인터를 찾는 패턴 내에서 일치하는 문자와의 거리만큼만 이동시킨다.

}

}

ELSE {

찾는 패턴의 나머지 문자들을 본문 패턴의 나머지 문자들과 비교한다.

IF ( 모두 일치하는 경우 ) {

패턴을 찾았으므로 원하는 작업을 수행

포인터를 찾는 패턴의 길이만큼 이동시킨다.

}

ELSE {

포인터를 찾는 패턴의 길이만큼 이동시킨다.

}

}

}

• 예시

---

▶시간 복잡도

---

찾고자 하는 String 패턴의 길이 : M

총 String 길이 : N

 - 고지식한 패턴 검색 알고리즘  : 수행시간 O(MN)

 - 카프 라빈 알고리즘           : 수행시간 O(N)

 - KMP 알고리즘                 : 수행시간 O(N)

 - 보이어-무어 알고리즘         : 일반적으로 수행시간 O(N)보다 작음  

                                          (최악의 경우 O(MN))

2019. 04. 01.  11:56