[C/C++] 문자열 검색 알고리즘 카프-라빈

 

파일을 참조하는 프로그램을 만들다 보면 문자열 분리나 검색의 필요성을 느낄 때가 많습니다.

 

 카프-라빈 알고리즘이나 보이어-무어 알고리즘 같이 특히 유용한 기법들을 공부하고 있는데, 제법 어렵더군요. 이번 글에선 복습 겸 카프-라빈 알고리즘에 대해 정리해봤습니다.

 

KarpRabin

// CP_ACP(ANSI) 
#include <stdio.h>
#include <tchar.h>
#include <math.h>

#define MAX_BUFFER 500

int KarpRabin(char* Buffer, char* Pattern){
	int i,j;
	int PatternSize = _tcslen(Pattern);
	int BufferSize = _tcslen(Buffer);

	int StartingHash = 0;
	int OriginHash = 0;
	int PatternHash = 0;

	// Conf Starting Hash Value
	for(i=0; i<PatternSize; i++){
		StartingHash+= Buffer[i] * pow(2.0, PatternSize-(1+i));
		PatternHash+= Pattern[i] * pow(2.0, PatternSize-(1+i));
	}

	for(i=0; i<BufferSize - PatternSize; i++){
		if(i==0){
			OriginHash = StartingHash;
		}else{
			OriginHash = Buffer[i+PatternSize - 1] +
				((OriginHash - Buffer[i-1] * pow(2.0, PatternSize-1))* 2);
		}

		if(OriginHash == PatternHash){
			for(j=0; j<PatternSize; j++){
				if(Buffer[i+j] != Pattern[j]){
					break;
				}
			}

			if(j>=PatternSize){
				return i;
			}
		}
	}
	return -1;
}

int _tmain(int argc, char** argv){
	FILE* fp;
	char* FilePath;
	char* Pattern;
	char Buffer[MAX_BUFFER];

	if(argc < 3){
		printf("Usage: %s <FilePath> <Pattern>", argv[0]);
		return 1;
	}

	Pattern = argv[2];
	FilePath = argv[1];

	if( (fp = fopen(FilePath, "r")) == NULL){
		printf("Cannot open file: %s\n", FilePath);
		return 1;
	}

	while(_fgetts(Buffer, MAX_BUFFER, fp) != NULL){
		int Position = KarpRabin(Buffer, Pattern);
		
		if(Position >= 0){
			printf("%s", Buffer);
		}
	}

	fclose(fp);

	return 0;
}

 

 카프-라빈 알고리즘은 문자열 검색을 위해 해시값을 이용하며 총 탐색 시간은 원본 문자열 길이, 즉 O(N)입니다.

 

 문자를 직접 비교하지 않고 패턴(사용자 입력)의 해시 값과 원본에 있는 하위 문자열의 해시값을 비교하여 탐색 성능이 굉장히 좋습니다.

 

 해시값은 이전 문자열의 해시값에서 선두에 있던 문자의 해시값을 뺀 값에 2를 곱한 후 이동한 후의 맨 끝 문자열이 갖는 해시값을 더한 것과 같습니다.

 

말로 하니 더 어려운데 수식으로 보면 다음과 같습니다.

Ex) "BACCE"(2047) -> "ACCEF" (2052) = (2(2047 - 'B' * 2^4) + 'F')

 

위 식을 컴퓨터 연산으로 풀어쓰면 다음과 같습니다.

CurrentHash =

(PrevHash - (pow(2.0, PatternSize-1) * CurrentString[First-1])) * 2 + CurrentString[First + PatternSize - 1];

 

 구현 자체가 간단해서 자주 사용되는데 메인 구조를 바꾸고 재귀 호출을 이용하면 전체 파일에 대한 문자열 검색도 가능합니다.

 

 아마 한동안은 또 알고리즘 공부에만 전념할 것 같은데, 이후에 추가로 기록해두고 싶은 알고리즘이 생기면 다시 글 쓰도록 하겠습니다.