동일하지 않은 문자 비용에 대한 최적의 프리픽스 없는 코드를 찾는 문제는 인코딩 알파벳이 길이가 α 및 β인 동일하지 않은 비용(길이) 문자로 구성된 최소 비용 프리픽스 없는 코드를 계산하는 것으로 구성되며, 여기서 α ≤ β입니다. 우리는 바이너리 트리로 제한됩니다.
코드는 허프만 트리가 허프만 코딩 문제의 솔루션을 나타내는 것과 유사한 방식으로 편향된 트리로 표시됩니다. 유사성에도 불구하고 편지 비용이 같지 않은 경우는 고전적인 허프만 문제보다 훨씬 어렵습니다. 문제에 대한 풍부한 문헌에도 불구하고 일반적인 편지 비용에 대해 다항식 시간 알고리즘이 알려져 있거나 사용할 수 없습니다.
그러나 알려진 다항식 시간 알고리즘을 사용할 수 있습니다. α와 β는 정수 상수입니다.
이 경우 최소 비용 트리를 계산하는 문제는 1961년 Karp가 처음 연구하여 정수 선형 계획법으로 환원하여 문제를 해결하여 n과 β 모두에서 지수 알고리즘을 생성했습니다. 그 이후로 다음과 같은 문제의 다양한 측면에 대한 많은 작업이 있었습니다. 최적의 트리 비용 경계 모든 가중치가 동일한 특별한 경우에 대한 제한입니다.
이러한 모든 노력에도 불구하고 놀랍게도 기본 문제가 다항식 시간 풀이인지 NP 완전인지 여부는 아직 알려지지 않았습니다.
Golin과 Rote는 하향식 방식으로 트리를 구축하는 O(nβ+2) 시간 동적 프로그래밍 알고리즘을 설명합니다.
이것은 다른 접근 방식(모노톤 매트릭스 개념, 예:Monge 속성 및 SMAWK 알고리즘)을 구현하여 개선되었습니다.
정리 1:O(nβ) 시간에 최적의 편향 나무를 구성할 수 있습니다.
이것은 β 값이 작은 경우에 대해 알려진 가장 효율적인 알고리즘입니다. 실제로 문자 비용은 일반적으로 작습니다(예:모스 부호).
최근에 효율적인 근사 알고리즘의 체계가 제공되었습니다.
정리 2
최적의 편향 트리를 위한 다항식 시간 근사 방식이 있습니다.