Klein's Algorithm for Computing Edit Distance on Tree

https://www.acmicpc.net/problem/19021

트리를 DFS하면서, 노드의 방문을 시작한 시점에 (, 끝내는 시점에 ) 를 붙이는 식으로 올바른 괄호 문자열을 만들어 줄 수 있습니다. 주어진 입력을 트리가 아니라 괄호 문자열이라고 생각하면

• 1, 2번 연산은 짝이 맞는 괄호 쌍을 추가하는 것이고
• 3번 연산은 짝이 맞는 괄호 쌍을 제거하는 것

으로 볼 수 있습니다.

Edit Distance와 LCS의 관계처럼, 두 괄호 문자열의 최대 공통 부분 괄호 문자열을 찾아 줍시다. $T_1$ 의 모든 괄호를 제거 / $T_2$ 의 모든 괄호를 추가하는 비용을 미리 지불했다고 하면, 두 괄호 $A, B$ 를 매치했을 때의 비용은 $C_3 \times \text{(A, B를 매칭하는 데 드는 비용)} - C_2 \times \text{(A를 제거하는 비용)} - C_1 \times \text{(B를 추가하는 비용)}$ 입니다. 이 비용 합을 최소화하는 공통 괄호 부분 문자열을 찾으면 됩니다. 여기서 공통 괄호 부분문자열은 일반적인 LCS가 당연히 아고, 두 매치하는 괄호가 LCS에 항상 같이 들어가거나 같이 빠져야 합니다.

$dp_{l_1, r_1, l_2, r_2}$ 를, $S[l_1,r_1)$ 과 $T[l_2, r_2)$ 간의 최소 매칭 합이라고 정의합시다. (이 부분문자열 안에 매칭하지 않는 괄호 쌍이 있을 수 있는데, 이들은 없는 문자 취급합시다). 상태 전이는

• $S$ 의 앞 문자 제거
• $T$ 의 앞 문자 제거
• $S$ 의 앞 문자와 $T$ 의 앞 문자를 매칭: $S = (S_1)S_2, T = (T_1)T_2$ 라고 하면, $(S_1, T_1)$ 의 subproblem과 $(S_2, T_2)$ 의 subproblem이 독립적으로 형성됩니다. 각각에 대해서 문제를 해결한 후 합쳐주면 됩니다.

이렇게 하면 전체 문제가 $O(n^2m^2)$ 에 해결됩니다. 여기까지는 그렇게 어렵지 않고 백준에도 있었던 문제입니다.

아주 기상천외한 아이디어를 사용하여 이를 최적화합니다. 지금 모든 상태 전이는 "맨 앞의 문자 제거", "맨 앞의 매칭하는 괄호 쌍 제거" 와 같이 앞을 기준으로 합니다. 하지만 똑같은 원리를 뒷쪽으로도 적용하면, $S = S_1(S_2), T = T_1(T_2)$ 와 같은 분할을 찾을 수도 있습니다. 만약 $|T_2| < |T_1|$ 이면, 오른쪽을 기준으로 상태 전이를 하고, $|T_1| < |T_2|$ 이면 왼쪽을 기준으로 상태 전이를 합시다. 이 때 다음 정리가 성립합니다.

Theorem. 위와 같이 상태 전이를 했을 때, 유효한 DP 상태에서 등장하는 $(l_2, r_2)$ 쌍은 $O(m \log m)$ 이다.

Proof. (Klein, 1998) 문제의 초기 상태는 1번 정점의 자식으로 이루어진 서브트리이다. 여기에서 할 수 있는 것은, 만약 왼쪽 서브트리가 작다면 왼쪽을 제거하고, 오른쪽 서브트리가 작다면 오른쪽을 제거하는 것이다. 원소를 하나씩 제거하든, 매칭으로 한 서브트리를 한꺼번에 날리든, 서브트리가 제거되는 순서는 똑같다. 고로 어떠한 경우에도 마지막 서브트리는 최후에 제거된다.

즉, ($v$ 번 정점의 자식으로 이루어진 서브트리에서 만드는 서로 다른 쌍) = ($v$의 서브트리 크기) - ($v$ 의 가장 큰 서브트리 크기) + (모든 $v$ 의 자식 $w$ 에 대해, $w$번 정점의 자식으로 이루어진 서브트리에서 만드는 서로 다른 쌍) 과 같이 된다. Heavy-light decomposition의 argument를 사용하여, 1번 정점의 자식으로 이루어진 서브트리에서의 서로 다른 쌍이 $O(m \log m)$ 임을 보일 수 있다. $\blacksquare$

유효한 DP 상태들을 전처리하고 위와 같이 DP를 돌리면 전체 문제가 $O(n^2 m \log m)$ 에 해결됩니다.

여담으로 이 문제의 State-of-the-art 알고리즘은 2007년 Demaine과 Mozes가 발견한 $O(N^3)$ 알고리즘 으로 소개된 알고리즘보다 약간 빠릅니다. Tree Edit Distance는 2017년 APSP로의 Hardness reduction이 발견되었기 때문에, 이보다 빠른 알고리즘은 존재하지 않을 가능성이 높습니다. 하지만 특이 케이스에 대해서는 조금 빠르게 풀 수가 있는데

• 모든 연산에 1의 비용이 든다고 가정하면 2021년 Mao가 $O(N^{2.956})$ 정도에 풀었습니다.
• 모든 연산에 1의 비용이 들고, 답이 $K$ 이하라고 가정하면 2021년 Akmal, Jin이 $O(NK^2 \log N)$ 에 풀었습니다.