역 허프만 알고리즘?

Question

허프만의 인코딩과 비슷한 문제가 있습니다. 정확히 어떻게 해결할 수 있는지 또는 역방향 허프만 인코딩 인 경우 확실하지 않습니다. 그러나 탐욕스러운 접근 방식을 사용하여 확실히 해결할 수 있습니다.

---

각각의 확률과 관련된 길이의 세트를 생각해 보자. 즉

X={a1=(100,1/4),a2=(500,1/4),a3=(200,1/2)} 

는 물론, 모든 확률의 합 = 1

시작점에서 다른 후의 라인의 길이를 함께 정렬.

예 : {a2,a1,a3} 처음부터 끝까지.

요소의 비용을 시작 행에서이 요소의 끝까지 확률로 곱한 값으로 정의하십시오. a_i 이전 배치에서

그래서 :

cost(a2) = (500)*(1/4) 
cost(a1) = (500+100)*(1/4) 
cost(a3) = (500+100+200)*(1/2) 

은 모든 비용의 합으로 총 비용을 정의합니다. 예 : cost(X) = cost(a2) + cost(a1) + cost(a3). 나는 약간 다른 허프만 트리를 형성하는 시도했지만 작동하지 않습니다 cost(X)

---

최소화하는 배열을 발견하는 알고리즘을 지정합니다.

확률로 정렬하면 실패합니다 (X = {(100,0.4), (300,0.6)} 고려).

길이로 정렬해도 실패합니다 (X = {(100,0.1), (300,0.9)}).

누군가가 최적의 솔루션 알고리즘을 도울 수 있거나 도움이된다면 좋을 것입니다.

Answer 1

인접한 두 요소를 바꿔 넣으면 어떻게 될지 생각해보십시오. 두 요소 전후의 계산은 동일하므로 두 요소에 따라 달라집니다.

두 요소를 분리하면 비용은 P1L1 + P2 (L1 + L2) 및 P2L2 + P1 (L1 + L2)입니다. 만약 당신이 이것을 빼고 단순 대수를 얻었 으면 L1/P1 < L2/P2 일 때 1을 먼저 바꾸고 싶습니다. 확인 - 이것은 L1 = 0 일 때 올바른 대답을 얻습니다.

그래서 Li/Pi의 증가 순서로 요소를 정렬하려고합니다. 그렇지 않은 경우 인접 요소를 스와핑하여 응답을 향상시킬 수 있기 때문에 집단.