비용이 다른 문자에 대한 최적 접두어 코드 문제란?
문자별 비용(cost)이 서로 다른 경우의 최적 접두어 자유 코드(prefix-free code)를 찾는 문제는, 인코딩 알파벳이 길이(비용)가 각각 α와 β인 두 종류의 문자(α ≤ β)로 구성된 조건에서 최소 비용의 접두어 자유 코드를 계산하는 것이다. 본 글에서는 이 문제를 이진 트리(binary tree)로 한정하여 살펴본다.
편향 트리(Lopsided Tree)와 허프만 트리의 차이
이러한 코드는 편향 트리(lopsided tree) 형태로 표현되는데, 이는 허프만 코딩 문제의 해답이 허프만 트리로 표현되는 방식과 매우 유사하다.
그러나 겉보기의 유사성에도 불구하고, 문자 비용이 서로 다른 경우는 고전적인 허프만 문제보다 훨씬 어렵다. 이 주제에 관해 방대한 연구 문헌이 축적되어 있음에도 불구하고, 일반적인 문자 비용에 대해 알려진 다항 시간(polynomial time) 알고리즘은 아직 존재하지 않는다.
다만 예외적으로, α와 β가 정수 상수인 경우에는 다항 시간 알고리즘이 알려져 있다.
연구의 역사: Karp의 초기 연구부터 현재까지
최소 비용 트리를 계산하는 이 문제는 1961년 Karp가 처음 연구했다. 그는 문제를 정수 선형 계획법(integer linear programming)으로 환원하여 해결했으나, 그 결과로 나온 알고리즘은 n과 β 양쪽 모두에 대해 지수 시간(exponential time)이 소요되었다.
이후로는 다음과 같은 다양한 측면에서 활발한 연구가 이어졌다.
- 최적 트리 비용의 상한(bound) 도출
- 모든 가중치가 동일한 특수 사례로의 제한
흥미롭게도, 이러한 수많은 노력에도 불구하고 이 기본 문제가 다항 시간에 풀리는 문제인지, 아니면 NP-완전(NP-complete) 문제인지조차 아직 밝혀지지 않았다는 점은 놀라운 사실이다.
동적 계획법 기반 알고리즘의 발전
Golin과 Rote는 트리를 하향식(top-down) 방식으로 구축하는 O(nβ+2) 시간의 동적 계획법(dynamic programming) 알고리즘을 제시했다.
이후 이 알고리즘은 몽주 성질(Monge property)과 SMAWK 알고리즘 같은 단조 행렬(monotone matrix) 개념을 활용하는 새로운 접근법을 통해 더욱 개선되었다.
정리 1 (Theorem 1)
최적 편향 트리는 O(nβ) 시간 안에 구성할 수 있다.
이 알고리즘은 β 값이 작은 경우에 알려진 가장 효율적인 방법이다. 실제 응용에서는 문자 비용이 대체로 작기 때문에(예: 모스 부호(Morse code)) 이 알고리즘은 매우 실용적이다.
근사 알고리즘으로의 확장
최근에는 효율적인 근사(approximation) 알고리즘 체계가 새롭게 제시되었다.
정리 2 (Theorem 2)
최적 편향 트리에 대한 다항 시간 근사 스킴(polynomial time approximation scheme, PTAS)이 존재한다.