패턴 매칭

패턴매칭

문자열에서 특정 단어나 문자열을 찾는 과정을 패턴매칭이라고 부른다. 문자열 패턴 매칭에 사용되는 대표적인 알고리즘은 아래와 같이 4가지가 있다.

 

• 고지식한 패턴 검색 알고리즘
• 카프-라빈 알고리즘
• KMP 알고리즘
• 보이어-무어 알고리즘

고지식한 패턴 검색 알고리즘

 고지식한 알고리즘(Brute Force)이란? 본문 문자열을 처음부터 끝까지 차례대로 순회하면서 패턴 내의 문자들을 일일이 비교하는 방식으로 동작하는 알고리즘이다.

 고지식한 패턴 검색 알고리즘의 시간 복잡도는 최악의 경우 시간 복잡도는 텍스트의 모든 위치에서 패턴을 비교해야 하므로 O(MN)이 된다. (10000 x 80 = 800000번의 비교가 일어난다. )

KMP 알고리즘

KMP 알고리즘이란? 불일치가 발생한 텍스트 스트링의 앞 부분에 어떤 문자가 있는지를 미리 알고 있으므로, 불일치가 발생한 앞 부분에 대하여 다시 비교하지 않고 매칭을 수행하는 알고리즘이다. 이 알고리즘은 패턴을 전처리하여 배열 next[M](불일치가 발생했을 경우 이동할 다음 위치)을 구해서 잘못된 시작을 최소화 할 수있다.

시간 복잡도는 O(M+N)이다.

 

보이어-무어 알고리즘

보이어-무어 알고리즘은 패턴에 오른쪽 끝에 있는 문자가 불일치 하고 이 문자가 패턴 내에 존재하지 않는 경우, 이동 거리는 무려 패턴의 길이만큼이 된다.

대부분의 문자열 매칭 알고리즘은 왼쪽에서부터 비교하지만, 이 알고리즘은 오른쪽에서 왼쪽으로 비교를 한다.

 

문자열 매칭 알고리즘 비교

• 찾고자 하는 문자열 패턴의 길이 m, 총 문자열 길이 n
• 고지식한 패턴 검색 알고리즘 : 수행시간 O(mn)
• 카프0라빈 알고리즘 : 수행시간 O(n)
• KMP 알고리즘 : 수행시간 O(n)
• 보이어-무어 알고리즘
• 앞의 두 매칭 알고리즘들의 공통점 텍스트 문자열의 문자를 적어도 한번씩 훑는다는 것이다. 따라서 최선의 경우에도 O(n)

보이어-무어 알고리즘은 텍스트 문자를 다 보지 않아도 된다.

발상의 전환 : 패턴의 오른쪽부터 비교한다.

최악의 경우 수행시간: O(mn)

입력에 따라 다르지만 일반적으로 O(n)보다 시간이 덜 든다.

 

출처 : SW Expert Academy