문자열 검색 알고리즘 2편 (Boyer Moore)

저번 문자열 검색 알고리즘 1편에서 Naive, Rabin Karp, KMP를 알아보았었다.

 

2020/04/16 - [알고리즘] - 문자열 검색 알고리즘 1편 (Naive, Rabin Karp, KMP)

문자열 검색 알고리즘 1편 (String searching algorithm)

이번 시간에는 Boyer Moore 알고리즘을 알아보도록 하자.

 

실제로 가장 많이 사용되고 있는 문자열 검색 알고리즘이 바로 Boyer Moore 알고리즘이라고 한다.

 

Boyer Moore 알고리즘도 앞서 다뤘던 문자열 알고리즘처럼

 

미리 생성한 문자열 정보를 토대로 효율적인 검색을 수행한다.

 

다른 점이 몇가지 있다면 문자열을 비교할 때 뒤에서부터 비교한다.

 

매번 본문과 패턴을 비교할 때 마지막 문자부터 시작해 첫 문자까지 비교하는 방식으로 진행한다.

 

그리고 미리 생성한 문자열 정보를 보다 적극적으로 사용한다.

 

구체적으로 알아보자.

 

먼저 나쁜 문자(Bad character)라는 것이 있다.

 

그렇다. 문자열을 비교할 때 불일치가 발생한 위치의 본문 문자를 가리킨다. (네이밍 참 단순 명쾌하다ㅋㅋ)

 

아래 예시의 빨간 문자가 나쁜 문자이다.

 

[본문]

A

B

C

A

C

C

[패턴]

A

C

C

A

 

그리고 착한 접미부(Good suffix)라는 것도 있다.

 

문자열 비교를 뒤에서부터 시작하기 때문에 본문과 패턴의 일치하는 부분은 접미부가 되고 이를 착한 접미부라고 한다.

 

위 예시에서는 파란색으로 표시한 "CA"가 되겠다.

 

(여기서 용어 혼동이 있을 수 있는데 접두사 = 접두부, 접미사 = 접미부라고 생각하자)

 

마지막으로 착한 접미부의 접미부가 이루는 가장 긴 경계(필자가 지음)가 있다.

 

말이 좀 길지만 해석하면 별 것 아니다.

 

경계(Border)란 용어는 앞서 1편에서 KMP 알고리즘을 다룰 때 언급했다.

 

간단하게 상기해보자면 문자열의 접두사와 접미사가 같은 이 쌍을 경계라고 한다.

 

다만 문자열 전체와 같은 접두사와 접미사가 이루는 경계는 제외한다고 했다.

 

(그냥 문자열과 접두사, 접미사 모두가 똑같은 경우를 경계로 취급하지 않는다는 얘기)

 

위의 패턴에서 예를 들자면 맨 앞의 "A"와 맨 끝 "A"가 접두사와 접미사로 경계를 이룬다.

 

다시 돌아와서 앞서 착한 접미부는 "CA"이다.

 

이 착한 접미부의 접미부는 "CA"와 "A"가 있다.

 

이 중 패턴에서 가장 긴 경계를 이루는 접미부를 찾으면 된다.

 

위 예시에서는 딱 한가지 경우로 맨 앞의 "A"와 맨 끝 "A"가 경계를 이루고

 

이것이 착한 접미부의 접미부가 이루는 가장 긴 경계가 된다.

 

이것들을 어떻게 사용하는 것일까?

 

본문과 패턴을 비교하는 도중에 나쁜 문자가 생길 것이다.

 

그리고 나쁜 문자가 패턴에 있다면 나쁜 문자가 있는 위치를 불일치가 발생한 위치와 비교해야 한다.

 

여러 개의 나쁜 문자가 패턴에 있을 수도 있다.

 

그럴 때는 가장 오른쪽에 있는 문자만 취급하면 된다.

 

패턴 내 나쁜 문자가 불일치가 발생한 위치보다 오른쪽에 있다면

 

아쉽게도 나쁜 문자는 패턴을 이동시키는데 더이상 도움이 되지 않는다.

 

왼쪽에 있다면 쓸모가 있지만 아직 바로 쓰기 전에 한 가지 더 고려해야 할 것이 있다.

 

바로 착한 접미부이다.

 

패턴에서 이 착한 접미부와 동일한 문자열이 착한 접미부 앞에 있는지 찾아야 한다.

 

예를 들어 아래와 같이 본문과 패턴을 비교 중에 있다고 하자.

 

[본문]

A

A

C

A

B

A

C

A

[패턴]

C

A

B

A

B

A

 

위에서 본문의 빨간색 문자 "C"가 나쁜 문자이고 파란색 문자열 "ABA"가 착한 접미부이다.

 

착한 접미부 앞에 착한 접미부와 동일한 문자열이 존재하는가?

 

패턴의 두 번째 문자부터 네 번째 문자까지 비록 일부가 겹치긴 하더라도 착한 접미부와 동일한 문자열이 존재한다.

 

그리고 착한 접미부와 동일한 문자열이 여러 번 나타날 수 있다.

 

패턴에서 나쁜 문자를 찾을 때와 마찬가지로 가장 오른쪽에 나타난 문자열을 취급하면 된다.

 

그 다음으로 이 문자열 위치와 패턴에 나오는 나쁜 문자의 위치를 비교해야 한다.

 

애초에 착한 접미부가 존재하지 않거나 착한 접미부와 동일한 문자열이 존재하지 않거나

 

나쁜 문자의 위치가 이 문자열 위치랑 같거나 더 앞에 있다면

 

패턴 내 나쁜 문자를 본문의 나쁜 문자의 위치에 오도록 패턴을 이동시키면 된다.

 

착한 접미부와 동일한 문자열이 패턴 내 나쁜 문자보다 더 앞에 있다면

 

이 문자열과 착한 접미부가 일치하도록 패턴을 이동시키면 된다.

 

왜 이렇게 하는 것일까?

 

일단 공통적으로 패턴과 본문의 동일한 문자/문자열을 맞춰주도록 이동시키는 것은 개념상 같다.

 

이동시키는 것 즉, 몇 칸 건너 뛰는 것은 구해놓은 정보를 토대로 애초에 불일치가 발생될 것을 알기 때문에 건너 뛰는 것이다.

 

그리고 위와 같이 비교하는 이유는 불일치 위치 기준으로 더 멀리(왼쪽)있는 문자/문자열에 맞추기 위해서다.

 

왜 더 멀리 있는 문자/문자열로 맞춰주는 것일까?

 

가까이 있는 문자/문자열로 맞춰주면 무조건 더 멀리 있는 문자/문자열이 불일치하기 때문이다.

 

아래 간단한 예를 보자.

 

[본문]

B

A

C

A

D

A

B

D

E

[패턴]

A

B

C

D

E

A

B

 

나쁜 문자는 빨간색으로 표시한 "D"이고 착한 접미부는 파란색으로 표시한 "AB"이고

 

착한 접미부와 동일한 문자열은 초록색으로 표시한 "AB"이다.

 

더 가까이 있는 나쁜 문자 "D"를 맞추기 위해 패턴을 1칸 이동한다 하더라도

 

본문의 착한 접미부 "AB"는 패턴과 맞지 않을 것이 뻔하다.

 

왜냐하면 착한 접미부와 맞는 문자열은 훨씬 앞에 있고 이것을 이미 알고 있기 때문이다.

 

그래서 더 멀리 있는 문자/문자열에 맞춰주는 것이다.

 

그리고 위에서 빨간 글씨로 "같거나" 라는 조건을 추가했다.

 

패턴에서 나쁜 문자의 위치와 착한 접미부와 동일한 문자열의 위치가 같을 수 있다.

 

이 때는 나쁜 문자가 일치하도록 패턴을 이동시키는데

 

이유는 본문에서 발견되는 패턴을 최대한 앞에서 찾기 위해서다.

 

이제 마지막으로 아까 얘기 하다 말았던 패턴에서 불일치 위치보다 앞에 나오는 나쁜 문자가 없을 때가 남았다.

 

여기서 착한 접미부의 접미부가 이루는 가장 긴 경계를 이용한다.

 

가장 긴 경계를 이루는 접두사를 접미부에 오도록 패턴을 이동시키면 된다.

 

경계가 없으면 패턴의 길이만큼 패턴을 이동시키면 된다.

 

바로 이해하기엔 아무래도 예시가 최고인 것 같다.

 

[본문]

A

B

C

D

D

B

C

A

B

[패턴]

B

C

A

E

D

B

C

 

나쁜 문자는 빨간색으로 표시한 "D"이고 착한 접미부는 파란색으로 표시한 "DBC"이다.

 

나쁜 문자 "D"는 패턴에서 불일치 위치 이전에 나타나지 않고 있다.

 

바로 위에 언급한 마지막 조건을 생각하지 말고 이 상황에서 패턴을 이동시킨다면 어떻게 이동시키는 것이 좋을까?

 

앞에 보이는 "BC"를 뒤에 있는 "BC"로 맞춰주도록 패턴을 이동시키는게 좋아 보인다.

 

그렇다. 뒤에 있는 "BC"가 착한 접미부의 접미부이고 앞에 있는 "BC"와 경계를 이루고 있다.

 

이제 실제 구현한 코드를 보자.

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

	std::string haystack = this->haystack.substr(startIndex);
	const std::size_t patternSize = pattern.size();

	// preprocessing for bad char table
	std::vector<std::size_t> badCharTable(CHAR_MAX + 1, patternSize);
	for (std::size_t i = 0; i < patternSize; ++i)
		badCharTable[pattern[i]] = i;
	
	// preprocessing for good suffix table 1
	// good suffix table 1 index : incorrect index
	// good suffix table 1 value : left good suffix index
	std::vector<std::size_t> goodSuffixTable1(patternSize, patternSize);
	std::size_t index = 0;
	// i : beginning index of right good suffix
	for (std::size_t i = 1; i < patternSize; ++i)
	{
		// j : index for finding left good suffix
		for (std::size_t j = 0; j < i; ++j) 
		{
			// index : index for comparing those strings
			for (index = 0; index < patternSize - i; ++index)
				if (pattern[j + index] != pattern[i + index])
					break;
			if (patternSize - i == index)
				goodSuffixTable1[i - 1] = j;
		}
	}

	// preprocessing  for good suffix table 2
	// good suffix table 2 index : incorrect index
	// good suffix table 2 value : suffix index of the longest border
	std::vector<std::size_t> goodSuffixTable2(patternSize, patternSize);
	std::size_t longestBorderIdx = patternSize;
	// i : border length
	for (std::size_t i = 1; i < patternSize; ++i)
	{
		std::size_t beginningIdxOfPfx = 0;
		const std::size_t beginningIdxOfSfx = patternSize - i;
		for (; beginningIdxOfPfx < i; ++beginningIdxOfPfx)
			if (pattern[beginningIdxOfPfx] != pattern[beginningIdxOfSfx + beginningIdxOfPfx])
				break;
		if (i == beginningIdxOfPfx)
		{
			goodSuffixTable2[beginningIdxOfSfx - 1] = beginningIdxOfSfx;
			longestBorderIdx = beginningIdxOfSfx;
		}
		else
			goodSuffixTable2[beginningIdxOfSfx - 1] = longestBorderIdx;
	}

	int idx = 0;
	std::size_t i = 0, badCharIdx, leftGoodSfxIdx;
	while (i <= haystack.size() - patternSize)
	{
		for (idx = (int)(patternSize - 1); idx >= 0; --idx)
			if (haystack[i + idx] != pattern[idx])
				break;
		if (0 > idx)
			return startIndex + i;

		badCharIdx = badCharTable[haystack[i + idx]];
		leftGoodSfxIdx = goodSuffixTable1[idx];

		if (badCharIdx < idx)
		{
			if (badCharIdx <= leftGoodSfxIdx)
				i += (idx - badCharIdx);
			else
				i += ((std::size_t)idx + 1 - leftGoodSfxIdx);
		}
		else
			i += goodSuffixTable2[idx];
	}

	return std::string::npos;
}

 

badCharTable은 나쁜 문자가 발견되었을 때 패턴에서 가장 오른쪽에 나타나는 인덱스를 저장하고 있다.

 

나쁜 문자의 범위는 본문에 있는 문자들의 종류로 하면 좋겠지만

 

미리 조사하는 것은 비효율적이기 때문에 그냥 아스키코드 값들에 대해 모두 저장하는 것으로 한다.

 

그리고 이 테이블에 들어가는 기본값은 패턴의 크기이다.

 

즉, 패턴에 없는 문자는 패턴 크기값이 들어가 있는 것이다.

 

그리고 goodSuffixTable1은 인덱스가 불일치가 발생된 위치이고 값은 착한 접미부와 동일한 문자열의 위치이다.

 

마찬가지로 기본값은 패턴의 크기가 저장된다.

 

goodSuffixTable2는 인덱스가 불일치가 발생한 위치이고

 

값은 착한 접미부의 접미부가 이루는 가장 긴 경계의 접미사의 위치이다.

 

불일치가 발생한 위치를 패턴 끝(정확히는 패턴 끝에서 두번째)부터 처음으로 이동하며 값을 조사한다.

 

그리고 조사에 실패하면 이전에 찾았던 가장 긴 경계를 재사용한다.

 

마지막 반복문(while문)에서 미리 생성한 문자열 정보를 토대로 검색을 수행한다.

 

제일 먼저 나쁜 문자를 찾고 패턴에서의 나쁜 문자의 위치와 불일치 위치를 비교한다.

 

나쁜 문자의 위치가 유효하다면 착한 접미부와 동일한 문자열의 인덱스와 비교한다.

 

앞서 설명한대로 착한 접미부와 동일한 문자열의 위치 >= 나쁜 문자의 위치 이면

 

패턴의 나쁜 문자를 본문의 나쁜 문자와 일치하도록 패턴을 이동시킨다.

 

그렇지 않으면 착한 접미부와 동일한 문자열의 위치가 착한 접미부에 오도록 패턴을 이동시킨다.

 

마지막으로 나쁜 문자가 발견된 위치가 유효하지 않으면

 

착한 접미부의 접미부가 이루는 가장 긴 경계의 접두부가 접미부에 오도록 이동시킨다.

 

가장 긴 경계가 없다면 기본값으로 저장한 패턴 크기만큼 이동하게 된다.

 

 

끝으로 시간 복잡도는 O(n * m)이 되겠다. (n : 본문 길이, m : 패턴 길이)

 

최악의 경우는 본문이 모두 단일 문자로 되어 있고

 

패턴도 본문과 같은 문자로 이루어져 있지만 맨 앞의 문자만 다를 경우이다.

 

-- 여담 --

여러 사이트를 돌아다니며 참고해 봤는데 조금씩 내용이 다른 것 같다.

그래도 가장 믿을 만한 사이트는 위키나 출처가 좀 명확한 곳들인 것 같다.

위키 : https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string-search_algorithm

Boyer–Moore string-search algorithm - Wikipedia

참고 사이트 : https://www-igm.univ-mlv.fr/~lecroq/string/node14.html

Boyer-Moore algorithm

 

사실 필자가 쓴 것과 위 두개 출처에서의 내용이 조금 다르다.

필자는 나쁜 문자가 유효하지 않으면 착한 접미부의 접미부가 이루는 가장 긴 경계를 사용했지만

출처에서는 그 가장 긴 경계를 착한 접미부에서 착한 접미부와 동일한 문자열을 찾지 못했을 때 사용한다.

그래서 나쁜 문자와 착한 접미부가 이동할 수 있는 거리 중 더 큰 값을 사용하도록 설명되어 있다.

 

이 밖에도 쓸 내용이 더 있다.

문자열 알고리즘의 성능을 따질 때 패턴이 본문에 나타나는지 안 나타나는지의 여부도 따지고

만약 나타났을 때 이어서 계속 검색하는 경우의 성능도 따져야 한다.

마지막으로 테이블 생성의 시간 복잡도가 O(m)인지도 조사해봐야 한다.