초급 2회차 문자열

1회차에는 시간 복잡도의 개념 등 기본적인 이야기가 많아 정리를 생략하였다.

 

2회차에서는 문자열 비교 시에 해싱을 사용하는 방법을 알려주었다. 아직까지 학교 수업에서는 해싱을 개념적으로 배우고 수학적인 예시를 풀어보았을 뿐, 코드에 적용한 적은 없었다. 실제로 구현해보니 굉장히 흥미로웠다.

이번 강의에서는 비교적 쉽고 사용하기 편한 Polynimial Rolling Hash 기법을 배웠다.

 

새로 알게 된 표기

문자열의 길이는 절대값기호로 표기.

 

문자열 해싱을 통한 비교란?

문자열을 한 글자씩 일일이 비교하는 대신,

문자열마다의 고유 값을 도출하여 그 값을 비교하는 방식이다.

 

서로 다른 문자열끼리 해시값이 겹치는 경우가 발생하면, 다중 해시를 사용하여 해결할 수 있다.

(하나의 대상에게 다른 기준으로 만들어진 여러 개의 해시값을 부여. 모든 해시값들이 일치하는 대상끼리만 동일한 것으로 취급.)

 

해싱이 왜 필요한가?

내가 해싱을 구현하는 법을 몰랐을 때, 문자열 비교 시 쓸데없는 연산을 조금이라도 줄이기 위해 아스키코드의 총합을 비교하여 거르는 방식을 사용한 적이 있다.

각 문자가 고유의 아스키코드값을 가지므로,

문자열에 포함된 모든 문자의 아스키코드 값을 더한 값이 서로 다를 경우 그 내용물도 같을 수가 없기 때문이다.

 

그런데 이 방법에는 치명적인 맹점이 있다.

서로 다른 문자열끼리 아스키코드의 총합이 같은 경우가 빈번하다는 것이다.

 

이런 문제점을 해결할 수 있는 것이 바로 해싱이다.

해싱에서는 서로 다른 문자열끼리 같은 해시값을 가지지 못하도록 한다.

 

그럼 알고리즘의 효율이 크게 개선된다.

비교할 때 그냥 해시값만 딱 비교하면 되므로(상수 시간만 소요되므로)

해시값을 만드는 과정의 시간복잡도만 신경 쓰면 되기 때문이다.

 

Polynomial Rolling Hash

해싱의 방법 중 하나.

다항식 형태의 함수식을 이용하여 문자열의 해시값을 만들어낸다. (polynomial)

그리고 인접한 부분문자열의 해시값을 마치 바퀴가 굴러가듯이 연속적으로 편리하게 구한다. (rolling)

 

다음과 같은 다항식을 사용한다.

 

해싱할 문자열을 s라 한다.
그 다음, 각 알파벳마다(마치 아스키코드처럼) 하나씩 값을 부여해준다.
예를 들어, s[i] 의 알파벳 순서 상 순위를 \( s_i \)라 하자. s[5] = 'c'라면 \( s_5 = 3 \)이다.

그럼 길이가 \( k+1 \)인 문자열 s의 해시값 $p(x)$는 아래와 같다.

\( p(x) = (s_0 \times x^k) + (s_1 \times x^{k-1}) + (s_2 \times x^{k-2}) + (s_3 \times x^{k-3}) + ... + (s_{k-1} \times x) + (s_k) \)

이때 $x$로는 문자열에 사용될 수 있는 문자의 종류 수보다 살짝 큰 정도의 정수를 사용하는 것이 좋다.

 

인접한 부분문자열의 해시값을 연속적으로 구하는 과정은 다음과 같다.

 

긴 문자열 A와 짧은 문자열 B가 있다.
A 안에 B가 등장하는지 알아내야 한다.
그럼 일단 B의 해시값을 구하고,
A의 부분문자열 중 B와 길이가 같은 것의 해시값을 모조리 구해야 한다.

그런데 이 때,
A[0...k]의 해시값을 알고 있다면
A[1...(k+1)]의 해시값은 매우 적은 횟수의 연산으로 알아낼 수 있다.

예를 들어보자.

A[0]부터 A[3]까지의 부분문자열의 해시값은 다음과 같다.

\( (A_0 \times x^3) \) + \( (A_1 \times x^2) + (A_2 \times x) + (A_3) \)

A[1]부터 A[4]까지의 부분문자열의 해시값은 다음과 같다.

\( (A_1 \times x^3) + (A_2 \times x^2) + (A_3 \times x) + (A_4)
 \)  ...(1)
\( = \) { \( (A_1 \times x^2) + (A_2 \times x) + (A_3) \) } \( \times x + (A_4) \)  ...(2)

부분문자열의 개수만큼 (1)과 같은 연산을 반복할 필요 없이,
(2)처럼 한 글자 앞의 문자열의 해시값에 간단한 연산만 하여 효율적으로 모든 부분문자열의 해시값을 구할 수 있다.

 

코드로 구현하면 다음과 같다.

//Rolling 부분을 뺀 간단한 해싱 함수 구현.
import java.io.*;

public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String s = br.readLine();
				
		System.out.println(hash(s));
		
	}
	
	static int hash(String s) {
		int hashed = 0;
		int x = 27;
		int power = 0;
		
		for(int i = 0; i<s.length(); i++) {
			char c = s.charAt(s.length() - i - 1);
			
			hashed += (c - 'a' + 1) * Math.pow(x, power);
			
			power++;
		}
		
		return hashed;
	}

}

 

문자의 순서와 관계 없이 비교할 때의 해싱

백준 #10840 문제와 같이, 문자열에 포함된 문자의 종류와 개수만 비교하면 되는 경우도 있다.

이럴 땐, 위의 Polynomial Hash와 유사한 형태의 다항식을 사용하되 계수를 각 알파벳의 갯수로 설정하면 된다.

(a의 갯수)$x^0 + $(b의 갯수)$x^1 + $(c의 갯수)$x^2 + $...$ + $(z의 갯수)$x^{25}$

 

코드로 구현하면 다음과 같다.

import java.io.*;

public class Main {
	
	static int[] cnt;	//알파벳별 개수를 세는 배열
	static int h;		//해시에 쓰일 정수
	
	static int hash(String str) {
		cnt = new int[27];	//cnt[0]은 사용하지 않음. cnt[1]은 a 담당 ... cnt[26]은 z담당.
		int hashed = 0;
		int pow = 0;
		for(int i = 0; i<str.length(); i++) {
			cnt[str.charAt(i) - 'a' + 1]++;
			}
		for(int i = 1; i<27; i++) {
			hashed += cnt[i]*Math.pow(h, pow);
			pow++;
		}
		return hashed;
	}

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		h = 27;
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str1 = br.readLine();
		String str2 = br.readLine();
		
		if(hash(str1) == hash(str2)) System.out.print("성분이 일치합니다");
		
	}

}