0
C에서 허프만 코딩. 대략적인 순서 보존 허프만 코딩 - 각각의 단계는 가중치가 가장 작은 두 개의 인접한 서브 트리를 병합한다. 입력은 1) 양의 정수 n 및 2) 주파수에 숫자가 지정된 문자 집합의 기호에 대한 개수 (가중치)를 제공하는 n 개의 양의 정수 시퀀스입니다.허프만 코딩 (ordering preserving)을위한 알고리즘을 구현하기 위해
잎 순서가 문자 집합의 순서와 일치하는 인 경우에만 순서 보존이 보장됩니다.
나는 위의 수를 확인하기 위해 아래의 코드를 수정해야합니다 :
// Huffman code using a minHeap with handles (index-heap-based priority queue).
// Heap routines are adapted from "Algorithms in C, Third Edition", and
// "Algorithms in Java, Third Edition", Robert Sedgewick
// This is a prototype for demonstration purposes only.
// Minimally, the heap/priority queue implementation should
// be in a different source file.
#include <stdio.h>
#include <stdlib.h>
int N, // Number of items in queue
*pq, // Priority queue
*qp, // Table of handles (for tracking)
maxQueued; // Capacity of priority queue
double *a; // Pointer to user's table
void exch(int i, int j) {
// Swaps parent with child
int t;
t = pq[i];
pq[i] = pq[j];
pq[j] = t;
qp[pq[i]] = i;
qp[pq[j]] = j;
}
void PQinit(double *items, int n, int m) {
int i;
a = items; // Save reference to index table
maxQueued = m;
N = 0;
pq = (int*) malloc((maxQueued + 1) * sizeof(int)); // Contains subscripts to a[]
qp = (int*) malloc(n * sizeof(int)); // Inverse of pq, allows changing priorities
if (!pq || !qp) {
printf("malloc failed %d\n", __LINE__);
exit(0);
}
// Set all handles to unused
for (i = 0; i < n; i++)
qp[i] = (-1);
}
int PQempty() {
return !N;
}
int PQfull() {
return N == maxQueued;
}
int less(int i, int j) {
// Notice how heap entries reference a[]
return a[pq[i]] < a[pq[j]];
}
void fixUp(int *pq, int k) // AKA swim
{
while (k > 1 && less(k, k/2)) {
exch(k, k/2);
k = k/2;
}
}
void fixDown(int *pq, int k, int N) // AKA sink
{
int j;
while (2 * k <= N) {
j = 2 * k;
if (j < N && less(j + 1, j))
j++;
if (!less(j, k))
break;
exch(k, j);
k = j;
}
}
void PQinsert(int k) {
qp[k] = ++N;
pq[N] = k;
fixUp(pq, N);
}
int PQdelmin() {
exch(1, N);
fixDown(pq, 1, --N);
qp[pq[N + 1]] = (-1); // Set to unused
return pq[N + 1];
}
void PQchange(int k) {
fixUp(pq, qp[k]);
fixDown(pq, qp[k], N);
}
// main implements Huffman code.
// Index is just a table of priorities whose
// subscripts are used in the PQ.
main() {
int n, m, op, i, j, val;
double *priority, probSum, expected = 0.0;
int *left, *right; // Links for Huffman code tree, root is subscript m-1
int *parent; // For printing the codes
int *length;
char *outString;
printf("Enter alphabet size\n");
scanf("%d", &n);
m = 2 * n - 1; // Number of nodes in tree
priority = (double*) malloc(m * sizeof(double));
left = (int*) malloc(m * sizeof(int));
right = (int*) malloc(m * sizeof(int));
parent = (int*) malloc(m * sizeof(int));
outString = (char*) malloc((n + 1) * sizeof(char));
length = (int*) malloc(m * sizeof(int));
if (!priority || !left || !right || !parent || !outString || !length) {
printf("malloc problem %d\n", __LINE__);
exit(0);
}
PQinit(priority, m, n);
for (i = 0; i < n; i++)
priority[i] = (-1);
// Read and load alphabet symbols' probabilities into priority queue.
probSum = 0.0;
for (i = 0; i < n; i++) {
scanf("%lf", priority + i);
probSum += priority[i];
PQinsert(i);
left[i] = right[i] = (-1);
}
printf("Probabilities sum to %f\n", probSum);
// Huffman code tree construction
for (i = n; i < m; i++) {
left[i] = PQdelmin();
right[i] = PQdelmin();
parent[left[i]] = parent[right[i]] = i;
priority[i] = priority[left[i]] + priority[right[i]];
PQinsert(i);
}
i = PQdelmin();
if (i != m - 1) {
printf("The root isn't the root\n");
exit(0);
}
parent[m - 1] = (-1);
// Goes breadth-first from root to compute length of prefix bit codes.
length[m - 1] = 0;
for (i = m - 1; i >= n; i--)
length[left[i]] = length[right[i]] = length[i] + 1;
// Print the leaves, i.e. for the alphabet symbols
printf(" i prob parent bits product code\n");
for (i = 0; i < n; i++) {
// Crawl up the tree to get prefix code
outString[length[i]] = '\0';
for (j = i; j != m - 1; j = parent[j])
outString[length[j] - 1] = (left[parent[j]] == j) ? '0' : '1';
printf("%5d %5.3f %5d %5d %5.3f %s\n", i, priority[i], parent[i],
length[i], priority[i] * length[i], outString);
expected += priority[i] * length[i];
}
printf("Expected bits per symbol: %f\n", expected);
// Print the internal nodes
printf(" i prob left right parent\n");
for (i = n; i < m; i++)
printf("%5d %5.3f %5d %5d %5d\n", i, priority[i], left[i], right[i],
parent[i]);
free(priority);
free(left);
free(right);
free(parent);
free(outString);
free(length);
free(pq);
free(qp);
}
(A). 각 힙 항목은 병합 될 수있는 인접한 두 개의 서브 트리 에 대응해야합니다. PQdelmin()이 병합을 결정한 후 병합을 적용하면 불필요한 후보자 (병합으로 인해) 및 PQinsert()가 새 후보를 포함하도록 폐기해야합니다 (또한 병합). 핸들이 이것을 용이하게합니다.
그러나 배열 배열 및 관리에 막혔습니다. 친절히 도와주세요!
무엇이 당신의 질문입니다. – ouah