[TIL] 두 트리는 얼마나 다른가 - Zhang-Shasha 트리 편집 거리

트리 편집 거리란?

"트리 A를 트리 B로 바꾸려면 최소 몇 번 고쳐야 하나?" 그 최소 횟수가 트리 편집 거리다. 두 트리가 얼마나 다른지를 숫자 하나로 재는 것

글자에도 똑같은 개념이 있다. "cat" 을 "cut" 으로 바꾸려면 가운데 글자 하나만 고치면 되니까 편집 거리는 1이다. (Levenshtein 거리) 트리 편집 거리는 이걸 트리로 확장한 것 뿐이다.

프론트엔드 개발하다보면 이 개념이 종종 나오는데, 문서 모델·Virtual DOM/JSON/HTML은 전부 트리라서, "이전 트리와 지금 트리가 얼마나 다른가"를 알아야 실행 취소, 협업 병합, 최소 DOM 패치를 조금 더 깊게 이해할 수 있다.

세 가지 편집 연산

트리를 고치는 방법은 세 가지가 있다.

연산	하는 일	비용
치환(relabel)	노드는 그대로, 이름표만 바꾼다	다르면 1, 같으면 0
삭제(delete)	노드를 빼고, 자식들을 부모에게 올려붙인다	1
삽입(insert)	새 노드를 중간에 끼워 넣는다	1

글자와 딱 하나 다른 점은 삭제다. 트리에서 노드를 빼면 그 아래 자식들이 부모 자리로 올라온다.

text

"B"를 삭제하기 전            "B"를 삭제한 후
      A                         A
      │                       ╱   ╲
      B            →        C      D
    ╱   ╲
   C     D

핵심 개념: 노드 짝짓기

세 연산을 따로 외울 필요 없다. 편집 거리는 결국 이 한 문장이다.

A의 노드와 B의 노드를 최대한 "그대로 재활용"하도록 짝짓는다.

짝이 맞으면 → 유지(공짜) 또는 이름표만 치환(+1)
A에만 남는 노드 → 삭제(+1)
B에만 있는 노드 → 삽입(+1)

그래서 편집 거리를 구한다는 건 비용이 가장 적게 드는 짝짓기를 찾는 일 이다. 예를 들어 (a × b) + c 를 (a × d) − c 로 바꾼다면 - ×, a, c 는 그대로 두고 b → d, + → − 두 번만 치환하면 되니까 편집 거리는 2다.

어떻게 계산할까

핵심은 작은 조각의 답부터 쌓아 큰 답을 만드는 것(동적 계획법)이다. 글자 편집 거리가 격자표를 한 칸씩 채워 나가듯, 트리도 작은 서브트리끼리의 거리부터 구해 점점 큰 서브트리로 올라간다.

각 단계에서 하는 선택도 글자와 똑같다 - 지울까(삭제), 넣을까(삽입), 짝지을까(유지·치환) 중 제일 싼 것을 고른다. 트리는 부모-자식 관계 때문에 조금 더 복잡하지만, 발상은 이게 전부다.

Zhang-Shasha가 특별한 이유

트리를 순진하게 비교하면 "이 서브트리를 통째로 지울까, 루트만 지울까?" 같은 갈림길이 노드마다 생겨 중복 계산이 폭발한다.

Zhang-Shasha(1989)의 아이디어는 "똑같은 계산을 두 번 하지 말자" 는 것이다. 노드를 후위 순회로 번호 매긴 뒤, 무거운 계산을 실제로 돌릴 지점만 골라낸다(이 지점들을 keyroot 라고 부른다). keyroot 개수는 트리의 잎 개수와 같아서, 트리가 커도 계산량이 억제된다. 시간 복잡도는 최악 $O(n^4)$ , 메모리 $O(n^2)$ 수준으로, 실무의 문서 트리 크기에선 충분히 빠르다.

사실 우리가 매일 쓰는 도구들은 이 정확한 계산을 실시간으로 하지는 않는다. React의 key나 ProseMirror는 "형제는 key로만 짝짓는다" 같은 규칙을 걸어, 트리 편집 거리를 훨씬 빠른 근사로 대체한다. Zhang-Shasha를 알아두면 그 근사들이 무엇을 포기하고 무엇을 얻었는지가 보인다.

실습 1 - 손으로 세보기

두 트리 A = f(a, b) 와 B = f(a, c) 의 편집 거리는 얼마일까? (루트 f 아래에 자식이 둘씩 있는 트리)

정답

f 와 a 는 그대로 두고, 오른쪽 자식 b → c 만 이름표를 바꾸면 된다 → 편집 거리 1. 이렇게 "그대로 둘 수 있는 노드는 최대한 두고, 다른 것만 고친다"가 핵심 감각이다.

실습 2 - 비용을 바꾸면 결과가 달라진다

지금은 모든 연산 비용이 1이다. 그런데 실제 에디터에선 글자 내용 바꾸기는 흔해도 h1 을 p 로 바꾸는 구조 변경은 더 큰 사건으로 치고 싶을 수 있다. 이럴 땐 치환 비용만 손보면 된다.

typescript

const 구조태그 = new Set(["doc", "h1", "p", "ul", "li"]);
 
function 치환비용(a: string, b: string): number {
  if (a === b) return 0;                   // 그대로면 공짜
  const 구조변경 = 구조태그.has(a) || 구조태그.has(b);
  return 구조변경 ? 2 : 1;                  // 구조 바꾸는 건 2배 비싸게
}

생각해볼 점: p → blockquote 치환 비용이 2로 오르면, 알고리즘은 치환 대신 "삭제(1) + 삽입(1)" 을 택할 수도 있다. 편집 거리 숫자는 같아도 어떤 노드를 살리고 어떤 노드를 새로 만드는지 가 달라지고, 이 선택이 실제 DOM 패치의 품질을 좌우한다.

레퍼런스

Zhang, K. & Shasha, D. Simple fast algorithms for the editing distance between trees and related problems, SIAM J. Comput. 18(6), 1989 - 원 논문
Revisiting the tree edit distance and its backtracing: A tutorial (2018) - 점화식을 단계별로 설명하는 친절한 튜토리얼
Wikipedia - Levenshtein distance - 글자 편집 거리