Disjoint Set Union(DSU)을 쓸 일이 있어서 구현해봤다.
Disjoint Set은 서로소 집합을 뜻하는데, 다른말로는
- 공통원소가 없는 집합
- 교집합이 공집합인 집합
- 상호 배타적인 집합
을 의미한다.
이 Disjoint Set 자료구조를 사용해 데이터를 분류/검색하는 알고리즘이 Union-Find이다.
내가 Union-Find를 사용한 케이스는 “익명의 동일한 사용자 식별(Identity Resolution)“이었다.
예를 들어 한 익명의 사용자가 리퀘스트를 할 때 마다
- IP
- session ID
- browser fingerprint
를 제출한다고 치자.
그러나
- 모바일 사용자는 종종 IP가 바뀐다.
- incognito를 켜면 session ID가 바뀐다.
- browser fingerprint는 아주 드물게 바뀐다.
이런 상황에서 동일한 사용자를 어떻게 구분할 것인가?
- IP ⇔ session ID ⇔ fingerprint
한 세트로 등장한 세 가지 정보는 서로 연관되어있어서 하나의 그룹으로 볼 수 있다.
수많은 IP, session ID, fingerprint 세트에 대해서 위와 같은 연결 관계를 하나의 그룹을 만드는 그래프를 계속 그려나간다. 여러 그룹이 만들어질 수도 있지만, 새 데이터(edge)가 들어올 때 두 요소의 소속 그룹이 다르면 두 그룹을 하나로 합친다.
결과적으로는 함께 등장한 적 있는 모든 IP, session ID, fingerprint들이 하나의 그룹으로 만들어진다.
Union-Find 알고리즘은 [ 요소 -> 상위 요소 ] 형태의 key-value(dictionary) 데이터를 기반으로 한다. 탐색 중 [요소 -> 최상위 요소(그룹) ] 으로 경로 압축(path compression)을 하게되어 최종 결과물의 탐색 시간복잡도는 O(1)에 가깝게 된다.