문자열 찾기(매칭)_라빈 카프 알고리즘 [2/2]

[ 라빈 카프 알고리즘이란? ]

• 찾을 문자열을 해쉬(hash)값으로 변환하여 문자열을 찾음

※ 해쉬(해시, hash)
- 특정 규칙을 이용해 데이터를 하나의 값으로 변경한 값을 의미
- 데이터의 일부분만 바껴도 해쉬값이 변경됨
- 낮은 확률로 다른 데이터가 같은 해쉬값으로 표현될 수도 있음
- 해쉬의 중복 확률이 낮을 수록 좋은 규칙이라고 할 수 있음

 

---

 

예를 들어 이번 라빈 카프 알고리즘에서 사용할 가장 간단한 해쉬값은 아래와 같이 만들 수 있습니다. "각 문자의 아스키코드"에 "2^자릿수" 를 곱해주고 그 합을 해쉬값으로 지정해주는 방식입니다. 현재 "abab"의 해쉬값은 1,465입니다. 중간에 문자가 하나 바뀌거나 같은 문자라도 자릿수가 다르면 모두 다른 값이 되는 것을 알 수 있습니다.

​

문자가 많아서 값이 너무 커질 수 있다 싶으면 각 문자열에 13같은 숫자로 나누기를 해서 값을 짧게 줄이는 방법도 있습니다. 이번에는 그냥 사용하도록 하겠습니다.

 

 

이렇게 해쉬값을 구한 뒤, 원본 문자열에서도 하나씩 해쉬값을 구해나가면서 비교해봅니다. 먼저 찾을 문자열과 함께, 원본 문자열의 가장 첫 해쉬값을 구합니다. 마지막 자릿수인 2^3도 미리 구해둬야 합니다.

 

 

두 가지 해쉬값을 비교해서 일치하면 현재 i위치를 출력한 뒤, i와 w를 모두 한칸씩 이동한 후 다시 해쉬값을 구합니다. 하지만 처음부터 다시 해쉬값을 구하면 효율이 떨어지기 때문에, 이동한 후 첫번째 값을 빼준 뒤, 나누기 2를 하여 자릿수를 맞춰주고 다시 새로 들어온 숫자 하나를 계산해서 더해주는 방식으로 진행합니다.

​

나누기 2를 해주는 이유는 가장 처음은 항상 2^0으로 시작해야 같은 값이 나오는데 한칸 오른쪽으로 이동하면 첫 값이 2^1부터 시작하기 때문입니다. 나누기 2를 해주면 2^1 → 2^0, 2^2→2^1 등으로 자릿수가 맞춰집니다. 이 부분은 본인 성향에 맞게 어떻게 구현해도 상관 없으며 다른 숫자 또는 다른 규칙을 써도 무방합니다. 이동해도 자릿수만 맞을 수 있도록 해주면 됩니다.

​

이런식으로 연산을 진행하며 해쉬값을 맞춰보고, str[w]가 문자열의 마지막에 갈때까지 반복수행 합니다. 해쉬값을 한 번 구해두면 찾을 문자열은 더이상 확인할 필요가 없게 되는 것이죠.

 

 

---

 

요즘 핫한 블록체인을 비롯해 데이터를 처리하는 많은 알고리즘이 이런 해쉬값을 사용하고 있다고 합니다. 해쉬값을 정하는 규칙이 복잡할 수록 원본 데이터를 추론하기가 어려워지니 그만큼 보안 수준도 향상될 수 있구요.

​

아래는 구현 코드입니다. 간단한거고 각자 스타일에 맞게 짜면 되는거라 제가 짠 코드만 올립니다.

 

#include <stdio.h>
#include <string.h>

int main()
{
	int count = 0; // 반복문 카운트
	char str[] = "abcabdabcabca";
	char find[] = "abca";
	int hash_str = 0, hash_find = 0;

	/* 원본문자열이 찾을 문자열보다 짧지 않고, 찾을 문자열 0이 아닐 때 수행*/
	if (strlen(str) >= strlen(find) && strlen(find) > 0)
	{
		/* 찾을 문자열과 원본 문자열의 최초 해쉬값 계산 */
		int i = 0, j = 1;
		while (find[i] != '\0')
		{
			hash_find += find[i] * j;
			hash_str += str[i] * j;
			i++;
			j *= 2;
		}
		
		printf("\n  일치점 : ");
		/* 라빈 카프 알고리즘 수행 */		
		i = 0, j /= 2;	// i는 시작점으로, j는 2로 나눠서 자릿수 맞춰줌
		int w = strlen(find) - 1;
		while (str[w] != '\0')
		{
			if (i == 0 && hash_str == hash_find)
				printf("%d ", i);
			
			else if (i > 0)
			{
				hash_str = (hash_str - str[i - 1]) / 2 + str[w] * j;
				if (hash_str == hash_find)
					printf("%d ", i);
			} 
			i++;
			w++;
			count++;
		}
		printf("\n  count : %d\n", count);
	}

	return 0;
}

 

---

 

자바 공부하면서 짜봤는데 아래와 같이 응용해서 사용할 수 있습니다. 문자열의 끝에서 시작점으로 역순으로 탐색하며 처음 일치한 문자열을 다른 문자열로 바꿔주는 함수입니다. 자바도 C랑 문법이 거의 비슷합니다.

 

package study.first;

public class Study {

	public static void main(String[] args) {

		String a = new String("Apple");
		String b = replaceEnd(a, "p", "XX");
		
		if (b != null)
			System.out.println(b);
		else 
			System.out.println("찾는 문자열이 없습니다.");

	}
	
	/* 끝 → 시작점 순서로 문자열 찾아서 첫 검색 값을 바꿔줌 */
	/* 원본 문자열, 찾을 문자열, 바꿔줄 문자열 */ 
	static String replaceEnd(String oldStr, String findStr, String newStr) {

		int findPoint = findStr.length();  // 찾을 문자열 길이
		int oldPoint = oldStr.length();  // 원본 문자열 길이

		/* 찾을 문자열이 더 길면 null값 반환 */
		if (findPoint > oldPoint)
			return null;

		/* 초기 해시값 생성 */
		int j = 2;
		int oldHash = 0, findHash = 0;
		for (int i = 0; i < findStr.length(); i++) {

			findHash += findStr.charAt(--findPoint) * j;
			oldHash += oldStr.charAt(--oldPoint) * j;
			j *= 2;
		}
		j /= 2;  // 자리값 맞춰줌

		int w, f = oldStr.length();
		/* 뒤에서부터 같은 문자열 찾기 */
		while (oldPoint >= 0) {

			/* 찾을 경우 */
			if (findHash == oldHash) {

				/* 임시 저장소 생성 */
				char[] temp = new char[oldStr.length() + newStr.length()];
				int start2 = oldPoint + findStr.length();

				/* 검색 앞 문자 복사 */
				for (w = 0; w < oldPoint; w++)
					temp[w] = oldStr.charAt(w);

				/* 새로운 문자 복사 */
				for (int i = 0; i < newStr.length(); i++, w++)
					temp[w] = newStr.charAt(i);

				/* 남은 문자 복사 */
				for (int i = start2; i < oldStr.length(); i++)
					temp[w++] = oldStr.charAt(i);

				return String.valueOf(temp, 0, w);
			}
			
			/* 해시값 재계산 */
			oldHash -= oldStr.charAt(--f) * 2;
			oldHash /= 2;
			oldHash += oldStr.charAt(--oldPoint) * j;			
		}

		/* 못찾았을 경우 */
		return null;
	}
}