추상적으로 말하면, 동형 사상은 어떤 구조가 부여된 두 집합 사이에서 그 구조를 보존하는 가역 사상(전단사)을 말합니다.
예를 들어, 한 그래프의 정점들을 다른 그래프의 정점들에 대응시켜 첫 번째 그래프에서 연결된 정점들이 두 번째 그래프에서도 연결된 정점들에 대응하고, 그 역도 성립하도록 할 수 있으면 두 그래프를 동형이라고 합니다. 다시 말해, 두 그래프가 정점의 이름을 바꾸는 것을 제외하면 「같다」면 두 그래프는 동형입니다.
동형성을 검사하는 좋은 일반적인 방법은 객체의 이름을 바꾸어도 값이 변하지 않는 어떤 해시 함수를 계산하고 그 값을 비교하는 것입니다.
#집합
숫자나 문자열의 집합이 순서를 무시했을 때 같은지 비교하는 방법을 알아보고자 한다고 합시다.
예를 들어 다음과 같습니다.
$$ \{1, 2, 3\} = \{2, 1, 3\} \\ \{"lal", "abc"\} = \{"abc", "lal"\} \\ \{4, 5\} \neq \{5, 6\} \\ \{"lal", "abc"\} \neq \{"abc", "all"\} $$이 문제는 이 집합을 정렬한 뒤 그 결과로 얻은 수열의 다항식 해시를 계산하면 해결할 수 있습니다. 결과는 원소의 처음 순서에 의존하지 않으므로, 이렇게 하면 문제를 $O(n \log n)$에 해결할 수 있습니다. 하지만 이 문제는 선형 시간에도 해결할 수 있습니다.
가능한 모든 키에 서로 다른 64비트 난수를 대응시키고(이를 키의 해시라고 부르겠습니다), 집합의 해시는 그 집합에 속한 모든 키의 해시의 xor-합으로 정의합시다. 그러면 xor의 교환법칙 때문에 순열을 무시하면 같은 집합들의 해시는 동일해지고, 충돌 확률은 정확히 $\frac{1}{2^{64}}$이 됩니다.
키에 해시를 대응시키는 방법으로는 해시 함수를 사용하는 방법이 있고, 서로 다른 키 값의 개수가 많지 않다면 미리 계산해 둔 난수 테이블을 사용하는 방법도 있습니다. 두 경우 모두 집합의 해시를 계산하려면 키의 해시를 $O(n)$번 계산해야 합니다.
이 방법은 또한 원소를 집합에 추가하거나, 집합에서 원소를 제거하거나, 서로소인 두 집합을 합치는 것과 같은 특정한 변경이 있을 때 집합의 해시를 $O(1)$에 다시 계산할 수 있다는 점에서도 주목할 만합니다.
#게임
마지막 방법은 체스나 체커 같은 추상 게임에서 포지션을 해싱하는 데에도 일반화하여 적용할 수 있습니다.
포지션의 해시를 빠르게 재계산하는 방법은 이러한 게임의 컴퓨터 전략을 구현하는 데 매우 중요합니다. 대부분의 전략은 가능한 모든 수를 탐색하는 방식에 기반하는데, 결과를 기억해 두고 같은 정점에서 탐색을 두 번 실행하지 않으면 탐색이 더 빠르게 동작하기 때문입니다. 이를 위해서는 해시 테이블을 만들어 방문한 포지션의 해시와 계산된 결과를 저장해야 하며, 그러기 위해서는 다시 해시를 빠르게 재계산할 수 있어야 합니다.
체스를 예로 들면, $8 \times 8 = 64$개의 칸이 있고, 각 칸은 $6 \times 2 + 1 = 13$가지 가능한 상태 중 하나에 있을 수 있습니다(두 색 중 한쪽의 킹, 퀸, 룩, 나이트, 비숍 또는 폰이 놓여 있거나, 아무것도 놓여 있지 않을 수 있습니다). $64 \times 13 = 832$개의 무작위 64비트 수를 생성합시다. 각 수는 어떤 위치에 어떤 기물이 놓여 있다는 사실에 대응합니다. 이제 모든 칸을 순회하며 xor-합을 계산합시다. 이렇게 얻은 64비트 수가 바로 포지션의 해시가 됩니다.
이 해시는 계산하기 쉬울 뿐만 아니라(lookup 테이블을 64번 조회하는 것이 모듈러 다항식 해시를 계산하는 것보다 빠릅니다), 포지션의 변화가 작다면 매우 빠르게 다시 계산할 수도 있습니다. 즉, 수를 한 번 두면 영향을 받는 칸은 두 개뿐이므로, 포지션의 해시를 정확히 4개의 수와 XOR하면 됩니다(기존 값 두 개는 제거하기 위해, 새 값 두 개는 추가하기 위해).
캐슬링 가능 여부, 앙파상, 색상 대칭, 폰을 첫 번째 랭크와 마지막 랭크에 놓을 수 없다는 점, 그 밖의 몇 가지 체스 특유의 세부 사항을 감안하면, 지금까지 설명한 것이 바로 조브리스트 해싱이라고 불리는 방법입니다.
#부분 행렬
문제. 수로 이루어진 크기 $n \times m$의 행렬 $A_{i, j}$가 주어집니다. 부분 행렬 $A_{x_1:x_2, y_1:y_2}$와 $A_{x_3:x_4, y_3:y_4}$가 같은지 묻는 쿼리에 답해야 합니다.
행렬을 행들의 집합으로 보면, 부분 행렬을 비교하는 것은 부분 문자열들의 집합이 같은지 비교하는 것과 같으며, 이는 이미 해시로 할 수 있는 작업입니다. 행렬의 각 행에 대한 다항 해시 배열을 미리 계산해 두고 해시를 상수 시간에 비교하면, 각 쿼리는 $O(n)$에 동작합니다. 이는 그다지 빠르지는 않지만, 적어도 $O(n^2)$보다는 낫습니다.
#2차원 해시
문자열의 다항식 해싱 아이디어를 행렬로 일반화해 봅시다. 이를 위해서는 서로 다른 두 개의 $k$, 즉 「수평」 $k_h$와 「수직」 $k_v$가 필요합니다. 이제 다음과 같이 둡시다.
$$ h(A_{x_1:x_2, y_1:y_2}) = \sum_{i=x_1}^{x_2} \sum_{j=y_1}^{y_2} A_{i,j} \cdot k_h^i \cdot k_v^j $$ 이러한 해시를 모든 모서리 부분행렬에 대해 미리 계산해 둡시다(문자열의 접두사 개념을 일반화한 것입니다): $$ h(x, y) = h(A_{:x, :y}) $$첫 번째 행 또는 첫 번째 열만 포함하는 모든 모서리 부분행렬에 대해서는 해시의 정의가 문자열의 다항 해시 정의와 일치하므로, 이러한 해시는 선형 시간에 미리 계산할 수 있음에 주목합시다.
이제 나머지 모든 부분행렬에 대해서는 다음이 성립함에 주목합시다
$$ h(x, y) = A_{x, y} k_h^x k_v^y + h(x - 1, y) + h(x, y - 1) - h(x - 1, y - 1) $$따라서 2차원 누적 합과 같은 방법으로 해시를 $O(n^2)$에 계산할 수 있습니다.
이제 부분 행렬의 해시를 누적 합으로 계산하여 $O(1)$에 동등성 검사를 수행할 수 있습니다. 유일하게 남은 미묘한 점은 이 해시가 $k_h^{x_1} \cdot k_v^{y_1}$만큼 “밀려” 있다는 것입니다. 이는 모듈러 연산으로 이 값으로 나누거나, 부분 행렬의 해시에 $k_h^{n-x_1} \cdot k_v^{m-y_1}$을 곱하여 바로잡을 수 있습니다.
참고. 행렬의 모든 행을 머릿속으로 하나로 이어 붙인다고 생각하면, 서로 다른 $k_h$와 $k_v$ 두 개를 정하는 대신 하나만 정해도 됩니다. 이는 $k_h = k_v^m$으로 두는 것과 같습니다.
#루트 있는 트리
이제 우리는 루트 트리의 동형 여부, 즉 정점 번호를 다시 매기는 것을 제외하면 같은지를 판별하는 방법을 배우려고 합니다. 이때 한 트리의 루트는 반드시 다른 트리의 루트로 대응된다는 것이 알려져 있습니다.
#정점의 해시
정점 번호에 의존할 수 없으므로, 우리가 사용할 수 있는 유일한 정보는 트리의 구조뿐이라는 점에 주목하십시오.
그러면 자식이 없는 정점의 해시는 어떤 상수(예를 들어, 179)로 두고, 자식이 있는 정점의 해시로는 자식들의 해시를 정렬한(자식들이 와야 하는 참된 순서를 우리는 알지 못하므로, 이들을 동일한 형태로 맞춰야 합니다) 목록에 대한 어떤 함수를 둡시다.
루트 트리의 해시는 루트의 해시로 간주하겠습니다. 구성에 대한 귀납법으로 동형인 루트 트리들의 해시가 일치함을 보일 수 있습니다.
유일한 문제점은 자식들의 해시를 집계하는 데 표준 다항식 해시가 적합하지 않다는 것입니다. 예를 들어, 다음 2개의 트리를 살펴봅시다:
$$ \begin{aligned} T_1 &= \{ (1, 2), (1, 3), (1, 4) \} \\ T_2 &= \{ (1, 2), (1, 3), (3, 4), (3, 5) \} \end{aligned} $$ 자식들에 대한 함수로 다항식 해시를 사용하면 다음과 같은 결과를 얻습니다: $$ h(T_1) = 179 + 179p + 179p^2 = 179 + p(179 + 179p) = h(T_2) $$ 괜찮은 해시 함수로는 예를 들어 다음과 같은 것을 사용할 수 있습니다 $$ h(v) = 42 + \sum_u \log(h(u)) $$이 해시 함수의 경우 자식들의 해시를 정렬하지 않아도 될 것처럼 보일 수 있지만, 그렇지 않습니다. 부동소수점 수를 계산할 때 오차가 발생하므로, 동형인 트리에 대해 합산 결과가 같아지도록 하려면 자식들도 같은 순서로 합산해야 하기 때문입니다.
더 복잡한 해시 함수의 예는 다음과 같습니다:
$$ h(v) = \sum_u h(u)^2 + h(u) \cdot p^i + 42 \bmod m $$어느 경우든 점근 복잡도는 $O(n \log n$이 됩니다. 각 정점에서 해야 할 일은 자식들을 해시 기준으로 정렬하고 합산하는 것뿐이기 때문입니다. 같은 해시를 가진 두 개의 동형인 자식이 있을 수 있으므로, xor 합이나 다른 합을 이용하는 트릭은 통하지 않으며, 따라서 이보다 빠르게 할 수는 없습니다.
#무근 트리
루트가 없는 트리의 경우 센트로이드를 찾은 뒤, 그 센트로이드를 루트로 삼아 루트 있는 트리처럼 탐색을 시작하면 됩니다. 센트로이드가 두 개라면 두 센트로이드 각각에서 탐색을 시작하여 해시 두 개를 계산하고, 이를 정렬한 다음(hash_a가 hash_b보다 작으면 서로 바꿉니다), 두 값으로부터 미니 해시(hash = hash_a + k * hash_b)를 계산하면 됩니다.