알고리즘 – KMP

by

안녕하세요. 오랜만에 문어를 시작해서 학부 때 배웠을 수도 있고 안 배웠을 수도 있는 다양한 알고리즘과 데이터 구조 이론을 정리하려고 합니다. 설명 과정에서 잘못된 부분이나 추가해야 할 부분이 있다면 언제든지 답변해주시면 감사하겠습니다.

오늘 알고리즘 배우기 KMP 알고리즘보지마. 문자를 검색하는 가장 간단한 방법은 패턴을 하나씩 무작위로 비교하는 것이지만 이 방법을 사용하면 긴 패턴(M) 또는 문자(N)의 시간 복잡도가 O(NM)입니다. (bruteforce 방법은 여기서 설명하지 않습니다.)

Knuth Morris(KMP)의 부분 알고리즘

이미 언급한 바와 같이 무차별 대입 방식으로 구현할 때 시간 복잡도는 O(NM)입니다. KMP 알고리즘은 무차별 대입 알고리즘의 불필요한 부분을 건너뛰고 비교해야 할 부분만 비교함으로써 성능을 향상시키는 알고리즘이다. KMP 알고리즘의 시간복잡도는 O(N+M)이다. 그러나 패턴에 반복이 없으면 효율성이 떨어집니다.

그럼 불필요한 부분을 건너뛰는 방법을 알아보겠습니다.(두 가지 용어가 사용됨 접두사 접미사보이지 않는다.)

  1. 먼저 검색 문자열에 대한 건너뛰기 테이블을 가져와야 합니다.
    • 스킵 테이블은 검색 문자열의 하위 문자열 중 접두어와 접미어가 있고 둘이 같을 때 건너뛸 수 있는 양을 나타내는 테이블이다.
    • 그러나 이 테이블도 무차별 대입되면 시간 복잡도는 O(M^2)가 됩니다. 따라서 KMP 알고리즘을 사용하여 홉 테이블을 얻어야 합니다.
  2. KMP에는 두 가지 변수가 필요합니다.
    • 하나는 원래 문자열에서 검색의 시작 위치가 될 시작입니다.
    • 일치하는 다른 하나는 비교가 시작되어야 하는 위치를 나타냅니다.

1. GetSkipTable(테이블 건너뛰기)

vector<int> getSkipTable(string pattern)
{
	int p = pattern.size();
	vector<int> skipTable(p, 0);

	int begin = 1, matched = 0; // matched는 몇개가 맞는지 length를 나타낸다.

	while(begin + matched < p)
	{
		if(pattern(matched) == pattern(begin + matched)) // matched는 접두부,begin+matched는 접미부를 나타낸다.
		{ 
			matched++;
			skipTable(begin + matched - 1) = matched;
		}
		else
		{
			if(matched == 0)
			{
				begin++;
			}
			else
			{
				// KMP 문자열 탐색 알고리즘 과 동일하게 불일치 발생 시
				// 매칭을 진행하면서 구했던 접두 접미사 길이 만큼 탐색을 건너뛸 수 있다
				begin += matched - skipTable(matched - 1);
				matched = skipTable(matched - 1);
			}
		}
	}
	return skipTable;
}

위 코드는 KMP를 이용하여 스킵 테이블을 찾는 방법입니다. 간단한 설명은 주석을 참조하십시오. 아래 그림은 패턴 삽입 시 생성된 점프 테이블의 결과입니다. 즉, 주어진 패턴의 하위 문자열의 접두사와 접미사를 비교하고 일치하는 하위 문자열의 길이를 저장하는 테이블입니다. 이 테이블이 필요한 이유는 아래에서 자세히 설명합니다.


2. KMP 검색

이제 원래 문자열의 검색 문자열에 일치 항목이 있는지 확인하고 일치하는 경우 시작 위치를 반환하는 KMP를 구현해 보겠습니다. 아래 그림은 KMP 구현 방법을 간단한 그림으로 나타낸 것입니다.


먼저 begin과 Matched를 모두 0으로 초기화하고 (원래 문자열 길이 – 검색 문자열 길이)만큼 반복한다. 이 과정에서 스킵 테이블을 활용해 비교 횟수를 줄일 계획이다.

vector<int> kmpSearch(string s, string pattern)
{
	vector<int> ret;
	vector<int> skip_table;

	int originLength = s.size(), patternLength = pattern.size();
	int begin = 0, matched = 0; // begin: 원본 문자열 탐색 시작 위치, matched: 비교를 시작할 위치

	skip_table = getSkipTable(pattern); // 위에서 구현한 스킵테이블 저장

	//원본 문자열의 시작위치가 범위를 벗어나기 전까지 반복
	while(begin <= originLength - patternLength)
	{
    	// 비교위치가 패턴 길이를 넘지 않으면서 원본 문자열과 탐색 문자열을 비교해준다.
        // 이를 통해 탐색 문자열의 어디까지가 원본 문자열과 일치하는지 알 수 있다.
		if(matched < patternLength && s(begin + matched) == pattern(matched))
		{
			matched++;
			
            // 패턴과 일치하다면 그 때의 원본 문자열에서 탐색 시작 위치를 저장한다.
			if(matched == patternLength)
			{
				ret.push_back(begin);
			}
		}
		else
		{
        	//비교 위치가 0이라면 탐색 위치를 증가시켜준다. 
            //이는 접두부, 접미부는 최소 크기가 2 이상인 문자열 일때 표현이 가능하기 때문이다.
			if(matched == 0)
			{
				begin++;
			}
			else //0이 아니라면 스킵테이블을 확인하여 차이만큼 원본 문자열의 탐색 위치를 스킵을 해주고, 비교 위치를 스킵테이블을 이용하여 조정해준다.
			{
				begin += matched - skip_table(matched - 1);
				matched = skip_table(matched - 1);
			}
		}
	}
	return ret;
}

위의 코드는 KMP 구현의 일부입니다. 설명하기 위해 검색어 무늬나는 그것을 쓸 것이다.

위의 이미지를 보면 녹색 점선과 노란색 점선이 각각 일치하는 부분과 일치하지 않는 부분입니다. 이제 가장 중요한 Skip 부분을 설명하겠습니다.

위의 그림 상황에서 시작과 일치를 체크하면 각각 시작 = 0과 일치 = 5,

코드에 if(일치 < patternLength && s(시작 + 일치) == 패턴(일치)) 교체하면 해당 위치의 원래 문자열 값은 “A”이지만 검색 문자열은 “C”임을 알 수 있습니다. 이 상황에서 우리의 추측은 현재 시작 부분에서 일치하는 패턴을 찾을 수 없다는 것입니다. 그렇다면 다음 패턴의 시작점을 어떻게 찾을 수 있을까요?

스킵 테이블로 begin의 시작점을 건너뛰자.

이미지를 보면 일치하는 항목이 최대 -1개임을 알 수 있습니다. 그렇다면 해당 부분에서 얼마나 건너뛸 수 있을까요? 이 메서드는 앞서 저장한 점프 테이블을 사용하여 쉽게 호출할 수 있습니다.

코드 내부 시작 += 일치 – skip_table(일치 – 1); 이 부분을 보면 홉 테이블에서 일치하는 패턴의 접두어와 접미어의 길이를 빼서 현재 일치하는 패턴의 길이에서 건너뛸 수 있는 길이를 뺀다.

점프 테이블 결과 이미지를 보면 idx 4는 동일한 접두사와 접미사를 가진 AB의 길이를 ABCAB에 저장합니다. 따라서 전체 길이 5에서 매칭 패턴 길이 2를 빼서 3씩 건너뛸 수 있습니다.

다음으로 사용자 지정해야 합니다. 현재는 5개가 일치하지만 스킵 후에는 일치하는 길이가 2로 줄어듭니다. 여기서 2는 건너뛰기 테이블에서 직접 사용할 수 있습니다.

이것으로 KMP 알고리즘에 대한 설명을 마칩니다.

나는 알고리즘을 먼저 이해하는데 왜 이것이 작동합니까? 세부 사항을 따라 스킵 테이블이 필요한 이유와 스킵 테이블을 가져오는 데 KMP 알고리즘이 사용되는 이유를 알 수 있었습니다.

다른 분들이 쓰신 블로그들을 보면 제가 해결한 것과 다르게 해결하신 분들이 있는 것 같습니다. 제 솔루션이 꼭 정답은 아니기 때문에 KMP 알고리즘이 어떻게 동작하는지 이해해주시고 넘어가주시면 감사하겠습니다.