[알고리즘] 스트링 매칭

스트링 매칭

주어진 텍스트에서 주어진 패턴이 어디에 나타나는지를 알아내는 문제를 스트링 매칭 문제라고 한다.

어떤 문서에서 특정 단어를 찾을 때 이것이 스트링 매칭이 되고 여기서 문서를 텍스트라 하고 찾아낼 특정 단어를 패턴 이라고 합니다.

즉 텍스트에서 패턴과 일치하는 모든 부분을 찾아내는 문제이죠.

직선적 알고리즘

텍스트의 매 위치에서 패턴 일치가 발생하는지를 조사하는 방법입니다. 

T에서 P가 나타나는 부분을 찾는 직선적인 방법이 하나하나 차례대로 비교해 나가는 것 입니다. 즉T[0]과 P[0]으로부터 하나씩

비교해 나가는데 이를 불일치가 발생할 때까지 반복합니다. 위예의 경우 처음부터 불일치가 발생하는데 다시 오른쪽으로

한 번 이동시켜서 패턴의 처음부터 비교를 다시 반복합니다. 

직선적 스트링 매칭 방법의 시간 복잡도는 O(mn)이며 좀 더 정확하게는 O(m(n-1m+1)) 입니다.

라빈-카프 알고리즘

라빈-카프 알고리즘은 스트링을 숫자값으로 바꾸어 해시 값을 계산하여 매칭하는 알고리즘 입니다. 최악의 시간 복잡도는

O(m(n-1m+1)) 이며 평균적으로 매우 빠른 알고리즘이죠. 특징을 조금 더 알아보면

- 스트링을 | 합계 | = d 진법의 숫자로 바꾸어 이 숫자를 비교한다. 이게 주요 방법

- mod 연산을 이용하는데 숫자가 너무 커져서 오버플로우 발생하는 것을 피하기 위함이다.

- 기대치는 O(n+m)이 된다.

- 접두부와 접미부를 간단히 설명하면 스트링의 앞부분과 뒷부분을 말한다.

유한상태 자동장치 , 스트링 매칭

- S : 상태의 유한 집합

- 합계 : 입력 알파벳의 집합

- f : S 합계에서 합계로의 전이함수

- A : 수락 상태의 집합. S의 부분집합

스트링 매칭 정리 

- 상태(원 안에 있는 숫자)와 전이(선)로 구성

- 2가지 전이 

-일치 전이 : 오른쪽으로 가는 >

- 불일치 전이 : 왼쪽으로 가는 <

- 현재 문자 x와 패턴이 일치하면 일치 전이를 수행하고, 그렇지 않다면 불일치 전이를 수행한다.

- 시간 복잡도 : O(n + m|합계|)

     -시간 복잡도에 알파벳의 크기도 포함됨. 알파벳의 크기가 작은 경우가 아니면 실용 X

- 자동장치가 문자열의 인식기로 쓰일 수 있으므로 스트링 매칭 이용 가능하고 간단함.

KMP 알고리즘

Knuth/Morris/Pratt 3명의 이름을 따서 만들어 KMP 알고리즘이다. 요거는 최저의 시간으로 문자열 속의 패턴을 찾아내는 것인데

패턴의 최대 접미부와 접두부 쌍을 구하여 불일치 발생 시 텍스트의 앞부분으로 안돌아가고 패턴 매칭을 하는 방법을 사용한다.

그래서 이미 비교한 텍스트의 앞부분을 다시 비교하는 일이 없게 된다.

KMP 알고리즘의 시간 복잡도는 O(m+n)이다. 

그리고 접두부와 접미부에 대해서 설명하자면 우선 접두부는 머리부분이고 접미부는 꼬리 부분이라고 생각하면 쉽다.

BAABABAA 라는 문자가 있다고 하자.  여기서 BAABABAA 빨강색은 접두부이고 파랑색은 접미부 이다.

가운데 BA는 경계라고 합니다.

스트링 매칭	수행시간
	평균	최악
직선적 알고리즘	O(nm)
라빈-카프 알고리즘	O(n+m)	O(m(n-1m+1))
KMP 알고리즘	O(n+m)
보이어-무어 알고리즘	O((n-m+1)m+|합계| )

스트링 매칭 성능 정리