문자열을 정수로 해싱하기 + 사전순 비교까지 (String to unique integer hashing)

문자열을 정수로?

이 글에서 다루는 내용은, 문자열의 형태로 적혀있는 "112223"과 같은 문자열을 말하는 것이 아닙니다.

영어 소문자로만 이루어진 "aaabbb" 또는 대문자로만 이루어진 "ABCCDD" 같은 문자열을 정수형 변수 하나에 담는 것을 말합니다.

왜?

보통 해싱은 작은 크기로 우겨넣기 때문에 데이터 손실이 일어나는 형태가 많습니다. 그래서 그대로 저장하면 충돌 해결 이슈가 따라오죠. (resolving collisions in hash tables)

정수로 바꾸어서 다룬다면 문자열 비교를 길이만큼인 \(O(|s|)\) 가 아닌 정수 비교 시간인 \(O(1)\) 으로 줄일 수 있습니다. 조건만 가능하다면 데이터의 손실 없이 그대로 담을 수도 있죠.

26진법

소문자 26개 혹은 대문자 26개만 사용하는 상황에서 a=0, b=1, ..., y=24, z=25 로 대응시켜서 변환한다면. 문자열을 26진법이라고 생각하면 됩니다.

이를 다시 10진수로 변환하여 저장하면 정수 하나로 표현이 가능합니다. 단, 문자열이 13자를 넘기면 오버플로우가 일어납니다.

\(26^{13} = 2,481,152,873,203,736,576\) 으로  \(2^{63}-1 = 9,223,372,036,854,775,808\) 보다 작기 때문에, C++의 경우에는 64비트 자료형인 long long 변수 하나로 표현이 가능합니다.

대신 여기에는 문제가 있죠.

"a" 는 0 입니다.

근데, "aa" 도 0 입니다.

a=0 이기 때문에, "aa" = 0 * 26 + 0 * 1 = 0 이라서 "aa" == "a" 인 상황이 생겨버리죠.

27진법

27진법을 쓰면 해결됩니다. 조금의 낭비는 있겠지만 숫자 0을 사용하지 않고, 1부터 26까지를 사용하면 됩니다.

즉, a=1, b=2, ..., y=25, z=26 으로 바꾸는거죠.

이제 "a" = 1 이고, "aa" = 1 * 26 + 1 * 1 = 27 이라 겹치지 않네요.

이 방법도 문제는 있습니다.

이대로는, 문자열의 사전순 대소 비교가 불가능합니다.

위의 그림에서 "ab"를 27진법으로 보고 10진수로 바꿨을 때 결과는 29 였습니다. 그럼 "aab"는 어떨까요?

"aab" 는 758 로 저장되기 때문에, 사전순으로는 "aab" < "ab" 이지만 이대로는 758 < 29 로 비교를 하게 되네요.

사전순 비교가 가능하도록

모두 같은 길이라고 생각하고 비교하면 대소 비교가 가능해집니다.

숫자를 가장 큰 자리부터 채운다고 생각하면 되겠네요.

코드입니다.

다시 생각해보니, 패딩하느라 반복문을 매번 돌 필요가 없었네요.

가장 큰 자리의 값부터 오른쪽으로 채워가면 문자열의 길이만큼 변환하고 끝납니다.