문자열 검색 알고리즘 1편 (Naive, Rabin Karp, KMP)

이번에 알아볼 알고리즘은 문자열 검색 알고리즘이다.

 

이름 그대로 본문 문자열(haystack)에서 찾고자 하는 특정 문자열(pattern)의 위치를 찾는 알고리즘이다.

 

문자열 검색 알고리즘으로 따로 언급할 만큼 많은 연구가 이뤄지고 있다.

 

종류는 대표적인 것들로 아래와 같이 4가지가 있다.

 

1. Naive
2. Rabin Karp
3. KMP (Knuth-Morris-Pratt)
4. Boyer Moore

1~3번 문자열 검색 알고리즘을 1편에서 설명하고

 

4번 문자열 검색 알고리즘을 2편에서 설명하려고 한다.

 

먼저 Naive부터 알아보자.

 

 

1. Naive

 

Naive 방식은 본문 처음부터 끝까지 문자 하나하나씩 패턴과 비교하여 찾는다.

 

따로 설명하지 않아도 쉽게 구현할 수 있을 것이다.

 

코드로 표현하면 아래와 같다.

 

std::size_t Naive::FindString(std::string pattern, std::size_t startIndex)
{
	if (false == CheckString(pattern, startIndex))
		return std::string::npos;

	std::string haystack = this->haystack.substr(startIndex);

	std::size_t index = std::string::npos;
	for (std::size_t i = 0; i <= haystack.size() - pattern.size(); ++i)
	{
		for (index = 0; index < pattern.size(); ++index)
		{
			if (pattern[index] != haystack[i + index])
				break;
		}

		if (index == pattern.size())
			return startIndex + i;
	}

	return std::string::npos;
}

 

문자열을 검색할 때 범위를 주의해야 한다.

 

본문의 처음 위치부터 패턴의 크기가 들어갈 마지막 위치까지 비교해야 한다.

 

위의 4가지 알고리즘에서 최악의 성능을 가지므로 실제로 많이 사용하진 않는다.

 

다만 다른 문자열 검색 알고리즘이 정상적으로 구현되었는지 확인하기 위한 표본으로 사용하는데 유용하다.

 

빅오 표기법(Big-O notation)으로 표현하면 O(n * m)이 되겠다. (n : 본문 길이, m : 패턴 길이)

 

 

2. Rabin Karp

 

Rabin Karp 방식은 문자의 아스키코드(ASCII Code) 값을 이용한 해시(Hash)를 사용한다.

 

본문에서 차례대로 패턴 크기만큼 문자열의 해시값을 구하고 미리 구해놓은 패턴의 해시값을 비교해본다.

 

이 알고리즘의 핵심은 문자들의 아스키코드 값을 가지고 어떻게 해시값을 만들어 내느냐가 관건이다.

 

해시 함수(Hash function)의 수식은 아래와 같다.

 

$$ H_i = S[i] × 2^{m-1} + S[i+1] × 2^{m-2} + ··· + S[i+m-2] × 2^1 + S[i+m-1] × 2^{0} $$

 

i 번째 H값은 본문에서 패턴 길이 크기 m 만큼의 문자열 S에 대한 해시 값을 나타낸다.

 

그러니까 첫 번째 H는 본문 첫 문자에서 패턴의 크기만큼의 부분 문자열에 대한 해시값을 의미한다.

 

위의 식은 마치 10진수로 표현된 숫자(실제로는 아스키코드 값이지만)를 2진수로 변환하는 과정과 거의 비슷하다.

 

여기까지만 놓고 보면 앞의 Naive 방식과 별로 다를 게 없어 보인다.

 

본문의 문자열 하나하나씩 해시함수를 계산하면 결국 Naive와 비교 횟수가 동일하기 때문이다.

 

아니 저 복잡한 수식을 계산하느라 더 오래 걸릴 것으로 예상할 수 있다.

 

하지만 일단 H의 i+1 번째 수식을 보자.

 

$$ H_{i+1} = S[i+1] × 2^{m-1} + S[i] × 2^{m-2} + ··· + S[i+m-1] × 2^1 + S[i+m] × 2^{0} $$

 

여기서 H의 i 수식에 2를 곱해보면 아래와 같이 된다.

 

$$ 2H_i = (2 × S[i] × 2^{m-1}) + S[i+1] × 2^{m-1} + ··· + S[i+m-2] × 2^2 + S[i+m-1] × 2^1 $$

 

$$ 2H_i = (2 × S[i] × 2^{m-1}) + H_{i+1} - S[i+m] × 2^0 $$

 

마지막으로 i+1 번째 H를 i 번째 H에 대해서 정리해보면 아래와 같다.

 

$$ H_{i+1} = 2(H_i - S[i] × 2^{m-1}) + S[i+m] $$

 

위의 수식을 토대로 우리가 알 수 있는 사실은

 

매번 본문의 문자열마다 패턴 크기만큼 문자 하나하나 계산하여 해시값을 구할 필요가 없이

 

이전 해시값과 양 끝 문자들로 다음 해시값을 구할 수 있는 것이다.

 

한 가지 주의할 점은 제일 첫 번째(i=0일 때) H값은 위의 수식으로 구할 수 없다. (-1번째 H는 존재하지 않기 때문)

 

그래서 제일 첫 번째 H값을 구할 때는 제일 처음 소개한 수식으로 구해야 한다.

 

여기까지 해시값을 구하는 부분을 코드로 표현하면 아래와 같다.

 

std::size_t RabinKarp::MakeHash(std::size_t index, std::size_t beforeHash, std::string& haystack, std::size_t patternSize)
{
	std::size_t ret = 0;
	if (0 == index) // first H
	{
		for (std::size_t i = 0; i < patternSize; ++i)
		{
			ret += (std::size_t)(haystack[i] * pow(2.f, patternSize - i - 1));
		}
		return ret % std::numeric_limits<std::size_t>::max();
	}
	else // H of i + 1
	{
		ret = (std::size_t)(2 * (beforeHash - haystack[index - 1] * pow(2.f, patternSize - 1)) + haystack[index + patternSize - 1]);
		return ret % std::numeric_limits<std::size_t>::max();
	}

	return std::string::npos;
}

 

첫 번째 매개변수는 다음 해시값을 구할 수식의 i이다.

 

두 번째 매개변수는 이전 해시값이다.

 

세 번째 매개변수는 본문 문자열이고 마지막 매개변수는 패턴의 크기이다.

 

이제 메인 알고리즘을 보면 위의 코드도 쉽게 이해할 수 있을 것이다.

 

std::size_t RabinKarp::FindString(std::string pattern, std::size_t startIndex)
{
	if (false == CheckString(pattern, startIndex))
		return std::string::npos;

	std::string haystack = this->haystack.substr(startIndex);

	std::size_t patternHash = MakeHash(0, 0, pattern, pattern.size());
	std::size_t haystackHash = MakeHash(0, 0, haystack, pattern.size());
	std::size_t index = 0;
	for (std::size_t i = 0; i <= haystack.size() - pattern.size(); ++i)
	{
		if (patternHash == haystackHash)
		{
			for (index = 0; index < pattern.size(); ++index)
				if (haystack[i + index] != pattern[index])
					break;
			if (pattern.size() == index)
				return startIndex + i;
		}

		if(i != haystack.size() - pattern.size())
			haystackHash = MakeHash(i + 1, haystackHash, haystack, pattern.size());
	}

	return std::string::npos;
}

 

초기에 패턴에 대한 해시값과 본문의 제일 첫 부분 문자열의 해시값을 구한다.

 

그리고 반복문 내부에서는 만약 두 해시값이 같다면 실제로 문자열이 같은지 직접 비교해본다.

 

이 작업은 해시 특성상 꼭 필요한 부분이다.

 

다른 문자열이더라도 같은 해시값을 가질 수 있기 때문이다.

 

패턴과 문자열이 같지 않다면 다음 해시값을 구해서 계속 비교한다.

 

성능은 Naive 방식보다 조금 나을 수 있다.

 

빅오 표기법으로 표현하면 O(n+m)이 되겠다.

 

 

3. KMP

 

Rabin Karp 방식부터 느꼈을지 모르겠지만 고급(?)스러운 알고리즘일수록 이전에 검색한 정보를 잘 활용하는 편이다.

 

Rabin Karp 방식은 이전의 해시 데이터를 사용하여 다음 해시값을 구하는데 중복되는 작업을 제거한 셈이다.

 

KMP 방식은 해시를 사용하지 않고 다른 방법으로 이전에 검색한 정보를 활용한다.

 

그리고 그 정보를 토대로 다음 검색할 몇 개의 문자를 건너뛸 수도 있다.

 

그 방법을 알아보기 앞서 접두사(prefix)와 접미사(suffix)에 대해 알고 넘어가자.

 

언어 문법을 공부하면서 많이 봤을 것이다.

 

접두사는 어근 앞에 접미사는 어근 뒤에 붙어서 뜻을 더하거나 강조하는 새로운 말을 만든다고 한다.

 

여기서 우리가 관심있는 것은 접두사가 단어의 앞에 존재하고 접미사가 단어 뒤에 위치한다는 것이다.

 

KMP 방식이 접두사와 접미사를 활용하는데 이 두개가 서로 같은 경우만 취급한다.

 

다만 접두사와 접미사가 단어의 전체 길이와 같은 경우는 제외한다.

 

예를 들면 "AABCDAAB" 라는 문자열이 있다.

 

여기서 접두사 "AAB"와 접미사 "AAB"가 같다.

 

여러 개가 같을 수도 있다.

 

예를 들면 "AAABBCAA"는 접두사와 접미사가 같은 경우는 "AA"와 "A"가 있다.

 

또 다른 예로 "ABABAB"가 있다면 제일 길이가 긴 경우는 "ABAB"일 것이다.

 

이처럼 접두사와 접미사가 서로 겹쳐도 된다.

 

이렇게 접두사와 접미사가 같은 쌍을 가리켜 경계(border)라고 한다.

 

이제 구체적인 방법을 알아보자.

 

본문의 문자열과 패턴을 비교하는 방식은 Naive 방식과 거의 동일하다.

 

하지만 Navie 방식은 무식하게 패턴을 무조건 한 칸씩 이동하면서 본문과 비교하지만

 

KMP 방식은 경계 정보를 바탕으로 한 칸 이상을 이동하면서 본문과 비교한다.

 

한 가지 예를 보자.

 

[본문]

A

B

C

A

B

C

A

B

E

[패턴]

A

B

C

A

B

E

 

처음 본문과 패턴을 비교할 때 본문의 "C"와 패턴의 "E"의 불일치가 발생한다.

 

여기서 불일치가 발생하기 전의 문자열 "ABCAB"가 동일하다.

 

이쯤만 설명해도 앞서 경계를 왜 먼저 짚고 넘어 왔는지 느낌이 올 것이다.

 

Naive 방식은 불일치가 발생하면 패턴을 한 칸 이동하여 다시 비교를 하지만

 

KMP 방식은 본문과 패턴의 비교된 문자열의 동일한 접두사의 가장 긴 경계를 바탕으로 패턴을 이동시킨다.

 

본문과 패턴의 비교된 문자열의 동일한 접두사(줄여서 동일한 접두사)의 의미를 풀어 써보면

 

위 과정에서 본문의 비교된 문자열은 "ABCABC"이고 패턴의 비교된 문자열은 "ABCABE"이다.

 

이 문자열들의 동일한 접두사가 바로 "ABCAB"이다.

 

그리고 동일한 접두사의 가장 긴 경계는 "AB"가 되겠다.

 

이제 이 경계 기준으로 접두사가 접미사에 오도록 패턴을 이동시켜 보자.

 

즉 "ABCAB" 문자열에서 접두사 "AB"가 접미사 "AB"에 오도록 패턴을 이동시키는 것이다.

 

[본문]

A

B

C

A

B

C

A

B

E

[패턴]

A

B

C

A

B

E

 

이런 방식으로 패턴을 이동시키는 것에 대해 왜 합리적인지 몇가지 고민해 봐야 한다.

 

첫 번째 고민해야 할 것은 왜 동일한 접두사의 경계를 기준으로 접두사를 접미사에 오도록 맞추는가? 이다.

 

이는 참으로 당연하다.

 

패턴을 본문과 비교하면서 맞지 않았을 때 패턴을 어떻게 얼마큼 이동해야 하는지에 대한 최적의 해이기 때문이다.

 

패턴의 앞부분 문자열(접두사)이 뒤에 또 나온다면 (그리고 거기까지 본문과 일치 했다면)

 

거기로 바로 이동시켜서 비교해 보는게 맞지 않겠는가?

 

두 번째 고민해야 할 것은 왜 가장 긴 경계여야 하는가? 이다.

 

어떻게 보면 가장 긴 경계가 패턴과 일치하는 문자열을 찾을 확률이 가장 높아 보이기도 하지만

 

실은 패턴과 일치하는 문자열을 본문의 제일 앞에서 찾기 위함이다.

 

예를 들어 동일한 접두사 "AABAA"가 있다고 하자.

 

여기서 경계는 "A"와 "AA"가 있다.

 

경계 "A"를 기준으로 이동한다면 패턴을 4칸 이동하게 된다.

 

경계 "AA"를 기준으로 이동한다면 패턴을 3칸 이동하게 된다.

 

이처럼 가장 긴 경계가 패턴을 본문의 제일 앞에서 찾도록 한다.

 

마지막으로 고민해야 할 것은 왜 꼭 동일한 접두사의 경계의 접두사와 접미사여야 하는가? 이다.

 

이를 다르게 생각해 보면 동일한 접두사에서 경계가 발견되지 않았을 때

 

동일한 접두사의 동일한 접두사의 경계를 사용하면 어떨까? 이다.

 

예를 들어 동일한 접두사 "ABCABD"가 있다고 하자.

 

여기서 경계는 없지만 눈에 띄는건 "AB"이다.

 

어? 그렇다면 앞에 "AB"를 뒤에 "AB" 오도록 패턴을 이동시키면 안되나? 라고 생각할 수 있다.

 

(나만 바보가 되고 싶진 않다 ㅋㅋ)

 

그런데 한 눈에 봐도 알 수 있듯이 "C"와 "D"가 달라서 어차피 불일치가 뜰 것이 분명하다.

 

그리고 이건 이미 경계가 구해지지 않은 것으로 불일치라는 것임을 알 수 있다. (제발 어? 했기를..ㅋㅋㅋ)

 

이제 실제로 구현할 때 이 개념을 어떻게 써먹을지에 대해 얘기해 보자.

 

먼저 동일한 접두사의 경계를 패턴을 이동할 때마다 매번 구해야 하는 것일까?

 

만약 그렇다면 최악의 경우 Naive보다 더 안좋을 것이다.

 

패턴을 본문과 비교하기 앞서 패턴 내에서 동일한 접두사들의 가장 긴 경계를 구하여

 

패턴을 이동시킬 거리를 미리 계산해 놓는 방법이 있다.

 

시나리오는 패턴의 특정 인덱스에서 본문과 불일치가 발생하면

 

그 인덱스로 미리 계산해 놓은 패턴의 이동 거리를 구하도록 한다.

 

이동 거리는 동일한 접두사 길이 -  가장 긴 경계 길이 이다.

 

동일한 접두사가 없는 경우 이동 거리가 1이 되고

 

경계 자체가 없으면 가장 긴 경계의 길이를 0으로 취급한다.

 

따라서 동일한 접두사의 문자열 길이가 1인 경우도 이동 거리가 1이 된다. (경계가 없으므로)

 

예를 들어 아래와 같은 패턴이 있다고 하자.

 

[패턴]

A

B

C

A

B

E

 

그리고 다음과 같이 불일치가 발생한 인덱스와 그에 따른 동일한 접두사 그리고 이동 거리를 구해보자.

인덱스	0	1	2	3	4	5
패턴	A	B	C	A	B	E
동일한 접두사	없음	"A"	"AB"	"ABC"	"ABCA"	"ABCAB"
이동 거리	1	1	2	3	3	3

 

이제 위 내용을 코드로 옮겨보자.

std::size_t KMP::FindString(std::string pattern, std::size_t startIndex)
{
	if (false == CheckString(pattern, startIndex))
		return std::string::npos;

	std::string haystack = this->haystack.substr(startIndex);

	std::vector<std::size_t> skipInfo(pattern.size(), 0);
	std::size_t index = 0;
	for (int i = 0; i < pattern.size(); ++i) // i : incorrect index when haystack and pattern are compared
	{
		for (int j = 0; j < i - 1; ++j) // j : index for finding the longest border in equivalent prefix of haystack and pattern
		{
			for (index = 0; index <= j; ++index)
				if (pattern[index] != pattern[(std::size_t)i - 1 - j + index])
					break;
			if (index > j)
				skipInfo[i] = (std::size_t)i - (j + 1);
		}
		if (0 == skipInfo[i])
			skipInfo[i] = 2 > i ? 1 : i;
	}

	std::size_t i = 0; // i : beginning index of comparison
	while (i <= haystack.size() - pattern.size())
	{
		for (index = 0; index < pattern.size(); ++index)
			if (haystack[i + index] != pattern[index])
				break;
		if (pattern.size() == index)
			return startIndex + i;
		i += skipInfo[index];
	}

	return std::string::npos;
}

 

첫 번째 반복문(for문)에서 패턴의 이동 거리를 구하고 있다.

 

제일 바깥 인덱스(i)는 불일치가 발생한 인덱스이다.

 

그리고 중간 인덱스(j)는 동일한 접두사의 가장 긴 경계를 구하기 위한 인덱스이다.

 

중간 인덱스의 반복 범위가 0부터 바깥 인덱스보다 2 작은 값까지인 것을 유의하자.

 

동일한 접두사의 길이는 불일치 인덱스보다 1만큼 작고

 

경계는 동일한 접두사와 같은 길이일 때 제외하므로

 

(접두사 및 접미사가 단어 전체 길이와 같은 경우는 제외한다고 앞서 설명했다)

 

1만큼 작게 되어 총 2만큼 작은 값까지 반복한다.

 

그리고 안쪽 인덱스(index)는 경계의 접두사와 접미사가 같은지 확인하기 위한 인덱스이다.

 

pattern 변수에 있는 문자를 비교하는 부분에서 겁먹지 말자.

 

그냥 경계의 접두사와 접미사 문자 하나 하나 비교하는 작업일 뿐이다.

 

skipInfo 변수가 패턴이 이동해야 할 이동 거리 값들을 담고 있다.

 

첫 번째로 할당하는 부분은 가장 긴 경계를 찾았을 때 위의 이동 거리 공식대로 값을 넣고 있다.

 

두 번째로 할당하는 부분은 경계를 찾지 못했을 때 동일한 접두사의 길이를 할당하고 있다.

 

두 번째 반복문(while문)은 패턴의 이동 거리를 토대로 문자열을 비교한다.

 

마지막으로 빅오 표기법으로 표현하면 O(n)이 되겠다.

 

나머지 Boyer Moore 알고리즘은 2편에서 알아보도록 하자.