문자열 검색 - 브루트 포스, KMP, Boyer-Moore

문자열을 검색하는 알고리즘을 알아보자. 문자열 검색이란 어떤 문자열 안에 다른 문자열이 들어있는지를 조사하고 들어 있다면 그 위치를 찾아내는 것을 말한다.

예제를 설명할 때는 편의상 어떤 문자열의 문자를 말할 때 원래는 string.charAt(idx)라고 해야 하지만 string[idx]라고 쓰겠다. 

 

브루트-포스법

---

브루트 포스법으로 문자열을 검색하는 과정은 아래와 같다. 텍스트 "ABABCDEFGHA"에서 "ABC"를 찾는다고 가정했을 때, 다음과 같은 과정을 거치게 된다.

3번에서 4번으로 넘어가는 과정을 보면, 패턴의 문자와 다른 문자를 만나면 패턴을 1칸씩 뒤로 옮긴 다음 다시 패턴의 처음부터 비교하는 모습을 볼 수 있다. 이미 검사를 진행한 위치를 기억하지 못해 불필요한 검사를 진행하기 때문에 효율이 좋다고 할 수 없다. 시간 복잡도는 텍스트 길이 N, 패턴의 길이 M이면 O(NM)이다.

 

코드 구현 - Java

public class BFmatch {
	//브루트-포스법으로 문자열을 검색하는 메서드
	static int bfMatch(String txt, String pat) {
		int pt = 0; // txt 커서 
		int pp = 0; // pat 커서
		
		while(pt != txt.length() && pp != pat.length()) {
			if(txt.charAt(pt) == pat.charAt(pp)) {
				pt++;
				pp++;
			} else {
				pt = pt - pp + 1;
				pp = 0;
			}
		}
		
		if(pp == pat.length()) return pt - pp; //검색 성공
		return -1; //검색 실패 
	}
}

 

KMP법

---

D. E. Knuth, J. H. Morris, V. R. Pratt가 거의 같은 시기에 고안했기 때문에 이들의 앞글자를 각각 따서 KMP법이라고 부른다고 한다.

브루트 포스와 다르게 검사했던 위치 결과를 버리지 않고 효율적으로 활용하는 알고리즘이다.  시간 복잡도는 텍스트 길이 N, 패턴의 길이 M이면 O(N+M)로 브루트 포스보다 빠르다.

 

예를 들어, "ZABCABXACCADEF"에서 "ABCABD"를 검색해보자.

 

textIdx

0

1

2

3

4

5

6

7

8

9

10

11

12

13

text

Z

A

B

C

A

B

X

A

C

C

A

D

E

F

pattern

A

B

C

A

B

D

 

text[0] 'Z'는 패턴에 없는 문자이므로 일치하지 않는다.

 

textIdx

0

1

2

3

4

5

6

7

8

9

10

11

12

13

text

Z

A

B

C

A

B

X

A

C

C

A

D

E

F

pattern

A

B

C

A

B

D

 

패턴을 한 칸 옮긴 후 비교한다. text[6] 'X'는 패턴에 없는 문자이므로 일치하지 않는다. 하지만 text[4], text[5] 인덱스 문자가 pattern[ 0], pattern[1] 인덱스 글자와 동일한 것을 볼 수 있다.

 

이때, 다음 탐색으로 넘어갈때 브루트 포스라면 패턴을 한 칸 뒤로 이동시켜 다시 pattern[0]부터 비교할 것이다.

 

textIdx

0

1

2

3

4

5

6

7

8

9

10

11

12

13

text

Z

A

B

C

A

B

X

A

C

C

A

D

E

F

pattern

A

B

C

A

B

D

 

하지만 KMP 방법으로는 아래와 같다.

textIdx

0

1

2

3

4

5

6

7

8

9

10

11

12

13

text

Z

A

B

C

A

B

X

A

C

C

A

D

E

F

pattern

A

B

C

A

B

D

 

text[4],text[5]가 pattern[0], pattern[1]와 동일하므로 이전 단계에서 멈춰져 진 text[6]의 문자를 pattern[2]의 문자와 다시 비교한다. 이전의 탐색에서 text[4], text[5]가 pattern[0],pattern[1]과 동일하다는 것을 알 수 있었으므로 그 다음 단계에서는 필요 없는 과정을 반복하지 않는 것이다.

 

KMP는 '아하 비록 결국은 틀렸지만 건진 거라도 활용해보자!' 하는 애고, 브루트 포스는 '에잇 틀렸네! 그냥 다 엎고 다시 처음부터 해!'라고 하는 애라고 생각하면 된다.

 

위와 같이 KMP법은 텍스트와 패턴의 겹치는 부분을 찾아내어 검사를 다시 시작할 위치를 구하는 방법이다. 이런 방법으로 패턴을 최소한의 수로 옮겨 알고리즘의 효율을 높일 수 있다.

 

하지만 몇 번째 문자부터 다시 검색을 시작할지 패턴을 이동시킬 때마다 다시 계산하여야 한다면 높은 효율을 기대할 수 없다. '몇 번째 문자부터 다시 검색할지'에 대한 값을 미리 표로 만들어 두어 검색 시 사용할 수 있도록 한다. 표를 작성할 때는 패턴 안에서 중복되는 문자의 나열을 먼저 찾아야 한다. 

 

아래의 표는, 어떤 텍스트를 "ABCABD"의 패턴과 비교할 때, pattern의 어떤 문자 x까지 일치했을 때, 다음 탐색 비교 시 사용할 pattern의 인덱스라고 생각하면 된다.

 

A	B	C	A	B	D
0	0	0	1	2	0

 

- 첫 번째 행은 pattern의 문자를 의미한다.

- 두 번째 행은 pattern의 문자 x까지 일치했을 경우, 다음 탐색 비교 시 사용할 pattern의 index이다.

- 패턴의 4번째 문자 'A'까지 일치한다면 앞의 'A'를 건너뛰고 패턴의 두 번째 문자 'B'(pattern[1]) 와 텍스트의 문자를 비교하라는 뜻이다.

- 패턴의 5번째 문자 'B'까지 일치한다면 앞의 'AB'를 건너뛰고 패턴의 세 번째 문자 'C'(pattern[2])와 텍스트의 문자를 비교하라는 뜻이다. 

 

위의 예제 테이블을 다시 봐보자.

 

textIdx

0

1

2

3

4

5

6

7

8

9

10

11

12

13

text

Z

A

B

C

A

B

X

A

C

C

A

D

E

F

pattern

A

B

C

A

B

D

 

text[6]에서 틀렸고, pattern[4], 'B'에까지는 문자가 일치하는 것을 알 수 있다.

 

그렇다면 다음 탐색은?

위에서 패턴으로 추출한 표를 참고하면, 'pattern[4]인 'B'까지 일치했을 경우 다음 탐색 시에는 text의 문자를 pattern[2] 'C'와 비교하시오.'라는 뜻이다.

 

textIdx

0

1

2

3

4

5

6

7

8

9

10

11

12

13

text

Z

A

B

C

A

B

X

A

C

C

A

D

E

F

pattern

A

B

C

A

B

D

 

따라서 탐색이 멈췄던 text[6]과 pattern[3]을 바로 비교하여 탐색한다.

 

건너뛰기 표는 pattern안에서 중복되는 문자의 나열을 찾기 위해 패턴끼리 겹쳐놓고 만들 수 있다.

 

코드 구현 시, 검색하는 loop은 구현이 쉬운데 loop 돌리면서 사용한 pattern pointer를 바로 skip배열의 index로 쓸 수 있도록 만들어 줘야 하는데 구현된 코드를 봐도 머리에 잘 안 들어와서 꽤 고전했다. 알듯하면서도 엄청 헷갈림. 익숙해질 때까지 계속 봐야겠다.

 

코드구현 - Java

public class KMPMatch {
	static int kmpMatch(String txt, String pat) {
		int pt = 1; //txt 커서 
		int pp = 0;	//pat 커서 
		int[] skip = new int[pat.length() + 1];
		
		//건너 뛰기 표 만들기
		skip[pt] = 0;
		while(pt != pat.length()) {
			if(pat.charAt(pt) == pat.charAt(pp)) {
				skip[++pt] = ++pp;
			} else if(pp == 0) {
				skip[++pt] = pp;
			} else {
				pp = skip[pp];
			}
		}
		
		//검색 
		pt = pp = 0;
		while(pt != txt.length() && pp != pat.length()) {
			if(txt.charAt(pt) == pat.charAt(pp)) {
				pt++;
				pp++;
			} else if(pp == 0) {
				pt++;
			} else {
				pp = skip[pp];
			}
		}
		
		if(pp == pat.length()) return pt - pp;
		return -1;
		 
	}
	
}

 

Boyer-Moore법

---

다음은 R. S. Boyer와 J. S. Moore가 만든 Boyer-Moore법이다. 이 알고리즘은 패턴의 마지막 문자부터 앞쪽으로 검사를 진행하면서 일치하지 않는 문자가 있으면 미리 준비한 표에 따라 패턴을 옮길 크기를 정한다.

 

현재 읽고 있는 책을 활용해서 내용을 정리중인데, 검색해보니 책에서 설명해주는 방법은 bad-character라는 특징을 이용한 알고리즘인 것 같다. 책에 아래와 같이 문구가 달려있었는데, 원래는 1. Bad Character Shift (나쁜 문자 이동) 2. Good Suffix Shift (착한 접미부 이동)의 두 특징을 모두 이용해서 Boyer-Moore 알고리즘이 더 효율적으로 작동할 수 있게 사용하는 것으로 보인다.

여기서 설명한 하나의 배열만 사용해서 검사하는 방법은 간단하게 구현한 Boyer-Moore 알고리즘 입니다. 원래의 Boyer-Moore법은 2개의 배열로 문자열을 검사합니다.

이 포스트에서는 Bad Character Shift 방법만 다루니 참고 바란다.

 

과정을 보기 위해 예제로 텍스트 "ABCXDEZCABACABAC"에서 "ABAC"를 Boyer-Moore법으로 검색해보자.

 

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

A

B

C

X

D

E

Z

C

A

B

A

C

A

B

A

C

1

A

B

A

C

2

A

B

A

C

3

A

B

A

C

4

A

B

A

C

 

아까 설명 한것 처럼, 패턴의 마지막 문자 'C'부터 텍스트의 'X'와 비교한다. 일치하지 않아서 패턴을 한칸 씩 뒤로 옮겨가며 비교해봐도, 'X'가 패턴에 아예 없는 문자이기 때문에 일치하지 않는다. 이렇게 텍스트 안에서 패턴에 들어 있지 않은 문자를 찾으면 해당 위치(text[3])까지의 문자는 건너 뛸 수 있다. 이 방법을 사용하면, 위의 표에서 2~4번의 비교는 생략하고 단숨에 4칸 뒤로 옮겨 아래 표와 같은 상태가 된다.

 

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
	A	B	C	X	D	E	Z	C	A	B	A	C	A	B	A	C
1					A	B	A	C
2						A	B	A	C
3							A	B	A	C

 

그런데 패턴의 문자 'A'와 텍스트의 'Z'가 일치하지 않는다. 그리고, 'Z'는 패턴에 아예 없는 문자이다. 따라서 위의 표에서 2, 3번 비교처럼 패턴을 1~2칸 옮겨봐도 패턴과 일치하지 않는 것을 알 수 있다. 패턴을 한꺼번에 3칸 옮겨 아래 표와 같이 만들자.

 

이렇게 패턴의 길이를 n이라고 하면 현재 검사하고 있는 텍스트의 문자 위치로 부터 '다음에 검사할 패턴의 마지막 문자 위치'가 n만큼 떨어질 수 있도록 패턴을 옮기면 된다. 현재 검사하고 있는 텍스트 문자의 위치는 6이므로 아래의 표에서는 +4해서 10으로 이동한다.

 

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

A

B

C

X

D

E

Z

C

A

B

A

C

A

B

A

C

1

A

B

A

C

2

A

B

A

C

3

A

B

A

C

4

A

B

A

C

 

이렇게 옮긴 다음 다시 검사를 시작해도 텍스트의 'A'와 패턴의 'C'가 같지 않다. 하지만 텍스트의 문자 'A'는 패턴의 pattern[0], pattern[2] 문자이다. 이런 경우에는 패턴에서 문자열이 마지막으로 나오는 인덱스가 k, pattern의 문자열 수 n이면 n - k - 1만큼 패턴을 옮겨주어야 한다. 'A'는 패턴의 두 곳(0, 2)에 들어 있지만 마지막 인덱스를 기준(2)으로 하여 패턴을 1만큼 (4 - 2 - 1)만큼 옮겨주어야하고, 3번 옮기는 4번 방법은 유효하지 않은 옮김이다.

 

결론적으로 패턴 문자열의 길이가 n일 때 옮길 크기는 경우에 따라 아래와 같은 방법으로 결정한다.

패턴에 들어 있지 않은 문자를 만난 경우
1. 패턴을 옮길 크기는 n이다. 

패턴에 들어 있는 문자를 만난 경우
1. 마지막에 나오는 위치의 인덱스가 k이면 패턴을 옮길 크기는 n - k - 1이다. 
2. 같은 문자가 패턴 안에 중복해서 들어 있지 않다면 패턴을 옮길 크기는 n이다.

 

위의 규칙에 의해 이 알고리즘도 건너뛰기 표가 필요하다.

 

아래 코드 구현을 보면, pattern의 character로 들어 올 수 있는 모든 문자의 옮길 크기를 계산하고 저장한다.

이 때 Character.MAX_VALUE(char형으로 나타 낼 수 있는 문자 수)를 이용해서 배열을 만들어 주고 모든 배열의 값으로 pattern의 길이를 넣어준 후, pattern 문자열에 들어있는 문자만 옮길 크기를 계산해서 다시 값을 넣어준다. 어차피 pattern의 맨 마지막 문자부터 틀렸을 경우 n만큼 점프해야 하므로 두 번째 foor lopp에서 patLen-1까지만 돌려주었다. for loop을 돌릴 때 문자열의 0번부터 차례대로 돌리기 때문에 중복된 문자의 경우 뒷쪽 인덱스의 문자를 기준으로 값이 들어가게 된다.

 

코드구현 - Java

public class BMMatch {
	static int bmMatch(String txt, String pat) {
		int pt;
		int pp;
		int txtLen = txt.length();
		int patLen = pat.length();
		int[] skip = new int[Character.MAX_VALUE + 1];
		
		//건너뛰기 표 만들기
		//Character.MAX_VALUE는 char형으로 나타낼 수 있는 문자수
		for(pt = 0; pt <= Character.MAX_VALUE; pt++) 
			skip[pt] = patLen;
		for(pt = 0; pt < patLen-1; pt++) 
			skip[pat.charAt(pt)] = patLen - pt - 1;
		
		//검색 
		while(pt < txtLen) {
			pp = patLen - 1; //마지막 문자부터 비교 
			
			while(txt.charAt(pt) == pat.charAt(pp)) {
				if(pp == 0) return pt; //pattern의 문자열 크기가 1인 경우 검색 성공 
				pp--;
				pt--;
			}
			
			pt += (skip[txt.charAt(pt)] > patLen - pp)? 
					skip[txt.charAt(pt)] : patLen - pp;
		}
		
		return -1;
		
	}
}