3
우리는 동적 프로그래밍을 사용하여 허프만 코딩의 문제를 해결할 수있는 욕심 접근 또는 동적 프로그래밍을 기반으로 코딩, 어떤 알고리즘 알고리즘에 대한 내 지식으로 당허프만이
Q
허프만이
A
답변
1
가 있는가, 나는 욕심 접근 방식을 기반으로 허프만 코딩을 믿습니다 . 활동 선택 문제와 마찬가지로. 작업 스케줄링 및 배낭 문제도 그 예입니다.
2
허프만 코딩은 노드의 이진 트리를 만들어 작동합니다. 이것들은 심볼의 수 n에 의존하는 크기의 일반 배열로 저장 될 수 있습니다. 허프만 코딩은 Greedy Algorithm 접근 방식을 사용하여 O(n logn) 시간에 구현할 수 있습니다. 허프만 코딩은 문제가 중첩되는 하위 문제를 포함하지 않으므로 동적 프로그래밍 솔루션에 적합하지 않습니다.
1
[업데이트] : 아래에서 언급 한 솔루션이 최적의 프리픽스 코드를 생성하지만, 반드시 허프만 코드와 같지는 않을 것이라고 생각합니다. 정의에 의한 허프만 코드는 욕심 많은 접근법을 취함으로써 생성된다. 그것이 최적이지만, 유일한 해결책은 아닙니다. 그것을 원하지만, 나는이 동적 프로그래밍을 사용하여 해결 될 수 있다고 생각
을 (하프 맨 트리가 생성되면 여전히 최적하면서 예를 들어, 당신은 그들에게 서로 다른 코드를 제공하는 동일한 수준에서 잎을 교환 할 수있다) 그렇게 효율적이지는 않습니다. 이 방법은 Optimal Binary Search Tree를 찾는 것과 매우 유사합니다. 한 레벨 아래로 가면 잎에 비트를 하나 더 추가하기 때문입니다.
Here 총 최소 비트 수를 계산하는 코드에 대한 링크이다. 물론 이것은 기하 급수적이지만 DP를 사용하면 O (n^2) 시간으로 풀 수 있습니다. 나는 인코딩을 생성하려고 시도하지 않았지만 믿을 수 있어야합니다.
IIRC 표준 접근법은 우선 순위 큐 (예 : 바이너리 힙)를 사용하는 것입니다. 낮은 확률은 높은 우선 순위를 의미합니다. 큐를 알파벳의 초기 리프 노드로 채 웁니다. 가장 중요한 두 가지 우선 순위를 취합니다 (즉, 가장 낮은 확률). 그 노드를 자식으로 추가하고 그 확률을 합계로 한 다음 새 하위 트리를 우선 순위 큐에 다시 추가합니다. 대기열에 항목이 하나만 남을 때까지 반복하십시오. – Steve314
각 단계에서 가장 작은 새로운 하위 트리를 형성하기 위해 최소한 두 개의 기존 하위 트리를 선택하는 것이 각 단계에서 [엔트로피] (https://en.wikipedia.org/wiki/Entropy_%)를 극대화하기 때문에 욕심 많은 것으로 간주됩니다. 28 정보 _ % 29)를 검색합니다. – Steve314