matlab哈夫曼编码 c语言

以下是C语言和Matlab语言实现哈夫曼编码的示例：

C语言实现：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_TREE_HT 100

struct MinHeapNode {
    char data;
    unsigned freq;
    struct MinHeapNode *left, *right;
};

struct MinHeap {
    unsigned size;
    unsigned capacity;
    struct MinHeapNode **array;
};

struct MinHeapNode *newNode(char data, unsigned freq) {
    struct MinHeapNode *temp = (struct MinHeapNode *)malloc(sizeof(struct MinHeapNode));
    temp->left = temp->right = NULL;
    temp->data = data;
    temp->freq = freq;
    return temp;
}

struct MinHeap *createMinHeap(unsigned capacity) {
    struct MinHeap *minHeap = (struct MinHeap *)malloc(sizeof(struct MinHeap));
    minHeap->size = 0;
    minHeap->capacity = capacity;
    minHeap->array = (struct MinHeapNode **)malloc(minHeap->capacity * sizeof(struct MinHeapNode *));
    return minHeap;
}

void swapMinHeapNode(struct MinHeapNode **a, struct MinHeapNode **b) {
    struct MinHeapNode *t = *a;
    *a = *b;
    *b = t;
}

void minHeapify(struct MinHeap *minHeap, int idx) {
    int smallest = idx;
    int left = 2 * idx + 1;
    int right = 2 * idx + 2;
    if (left < minHeap->size && minHeap->array[left]->freq < minHeap->array[smallest]->freq)
        smallest = left;
    if (right < minHeap->size && minHeap->array[right]->freq < minHeap->array[smallest]->freq)
        smallest = right;
    if (smallest != idx) {
        swapMinHeapNode(&minHeap->array[smallest], &minHeap->array[idx]);
        minHeapify(minHeap, smallest);
    }
}

int isSizeOne(struct MinHeap *minHeap) {
    return (minHeap->size == 1);
}

struct MinHeapNode *extractMin(struct MinHeap *minHeap) {
    struct MinHeapNode *temp = minHeap->array[0];
    minHeap->array[0] = minHeap->array[minHeap->size - 1];
    --minHeap->size;
    minHeapify(minHeap, 0);
    return temp;
}

void insertMinHeap(struct MinHeap *minHeap, struct MinHeapNode *minHeapNode) {
    ++minHeap->size;
    int i = minHeap->size - 1;
    while (i && minHeapNode->freq < minHeap->array[(i - 1) / 2]->freq) {
        minHeap->array[i] = minHeap->array[(i - 1) / 2];
        i = (i - 1) / 2;
    }
    minHeap->array[i] = minHeapNode;
}

void buildMinHeap(struct MinHeap *minHeap) {
    int n = minHeap->size - 1;
    int i;
    for (i = (n - 1) / 2; i >= 0; --i)
        minHeapify(minHeap, i);
}

void printArr(int arr[], int n) {
    int i;
    for (i = 0; i < n; ++i)
        printf("%d", arr[i]);
    printf("\n");
}

int isLeaf(struct MinHeapNode *root) {
    return !(root->left) && !(root->right);
}

struct MinHeap *createAndBuildMinHeap(char data[], int freq[], int size) {
    struct MinHeap *minHeap = createMinHeap(size);
    for (int i = 0; i < size; ++i)
        minHeap->array[i] = newNode(data[i], freq[i]);
    minHeap->size = size;
    buildMinHeap(minHeap);
    return minHeap;
}

struct MinHeapNode *buildHuffmanTree(char data[], int freq[], int size) {
    struct MinHeapNode *left, *right, *top;
    struct MinHeap *minHeap = createAndBuildMinHeap(data, freq, size);
    while (!isSizeOne(minHeap)) {
        left = extractMin(minHeap);
        right = extractMin(minHeap);
        top = newNode('$', left->freq + right->freq);
        top->left = left;
        top->right = right;
        insertMinHeap(minHeap, top);
    }
    return extractMin(minHeap);
}

void printCodes(struct MinHeapNode *root, int arr[], int top) {
    if (root->left) {
        arr[top] = 0;
        printCodes(root->left, arr, top + 1);
    }
    if (root->right) {
        arr[top] = 1;
        printCodes(root->right, arr, top + 1);
    }
    if (isLeaf(root)) {
        printf("%c: ", root->data);
        printArr(arr, top);
    }
}

void HuffmanCodes(char data[], int freq[], int size) {
    struct MinHeapNode *root = buildHuffmanTree(data, freq, size);
    int arr[MAX_TREE_HT], top = 0;
    printCodes(root, arr, top);
}

int main() {
    char arr[] = {'a', 'b', 'c', 'd', 'e', 'f'};
    int freq[] = {5, 9, 12, 13, 16, 45};
    int size = sizeof(arr) / sizeof(arr[0]);
    HuffmanCodes(arr, freq, size);
    return 0;
}

Matlab实现：

function [code, dict] = huffman(p)
    % HUFFMAN Create a variable-length code using the Huffman algorithm.
    %   [CODE,DICT] = HUFFMAN(P) returns a Huffman code as a cell array of
    %   strings and its corresponding dictionary as a containers.Map object.
    %
    %   P is a vector of probabilities that correspond to the alphabet of
    %   symbols to be encoded. The probabilities must sum to 1.
    %
    %   CODE is a cell array of strings that represents the variable-length
    %   code for each symbol in the alphabet. The order of the symbols in
    %   CODE corresponds to the order of the probabilities in P.
    %
    %   DICT is a containers.Map object that maps each symbol in the alphabet
    %   to its corresponding variable-length code.
    %
    %   Example:
    %       p = [0.25 0.125 0.125 0.0625 0.0625 0.0625 0.0625 0.03125 0.03125 0.03125 0.03125 0.03125 0.03125 0.03125 0.03125];
    %       [code, dict] = huffman(p);
    %
    %   See also HUFFMANDICT, HUFFMANENCODE, HUFFMANDECODE, CONTAINERS.MAP.

    % Check input arguments
    narginchk(1, 1);
    validateattributes(p, {'numeric'}, {'vector', 'nonnegative', '<=', 1, 'nonempty', 'real'}, mfilename, 'P', 1);

    % Create a dictionary that maps each symbol to its probability
    dict = containers.Map(1:numel(p), num2cell(p));

    % Create a priority queue of tree nodes
    q = priorityQueue();
    for i = 1:numel(p)
        q.insert(treeNode(i, p(i)));
    end

    % Build the Huffman tree
    while q.size() > 1
        % Remove the two nodes with the lowest probabilities
        node1 = q.remove();
        node2 = q.remove();

        % Create a new node that is the parent of the two nodes
        parent = treeNode([node1.symbols node2.symbols], node1.probability + node2.probability);
        parent.left = node1;
        parent.right = node2;

        % Add the new node to the priority queue
        q.insert(parent);
    end

    % Traverse the tree to get the variable-length codes
    code = cell(size(p));
    root = q.remove();
    traverse(root, '');

    % Nested functions
    function traverse(node, prefix)
        if ~isempty(node.symbols)
            % Leaf node
            code(node.symbols) = {prefix};
        else
            % Non-leaf node
            traverse(node.left, [prefix '0']);
            traverse(node.right, [prefix '1']);
        end
    end
end

function q = priorityQueue()
    % PRIORITYQUEUE Create a priority queue.
    %   Q = PRIORITYQUEUE() returns an empty priority queue.
    %
    %   Example:
    %       q = priorityQueue();
    %       q.insert(1);
    %       q.insert(2);
    %       q.insert(3);
    %       q.remove() % Returns 1
    %       q.remove() % Returns 2
    %       q.remove() % Returns 3
    %
    %   See also HEAPQ.

    % Properties
    q.heap = {};

    % Methods
    q.insert = @insert;
    q.remove = @remove;
    q.size = @size;

    % Nested functions
    function insert(item)
        % Insert an item into the priority queue
        q.heap{end+1} = item;
        heapq(q.heap, numel(q.heap), 'ascend');
    end

    function item = remove()
        % Remove and return the item with the highest priority
        if isempty(q.heap)
            error('Priority queue is empty');
        end
        item = q.heap{1};
        q.heap(1) = [];
        if ~isempty(q.heap)
            heapq(q.heap, 1, 'descend');
        end
    end

    function n = size()
        % Return the number of items in the priority queue
        n = numel(q.heap);
    end
end

function node = treeNode(symbols, probability)
    % TREENODE Create a tree node.
    %   NODE = TREENODE(SYMBOLS,PROBABILITY) returns a tree node with the
    %   specified symbols and probability.
    %
    %   SYMBOLS is a vector of indices that correspond to the symbols in the
    %   alphabet to be encoded.
    %
    %   PROBABILITY is the probability of the node.
    %
    %   Example:
    %       node = treeNode([1 2], 0.25);
    %
    %   See also HUFFMAN.

    % Properties
    node.symbols = symbols;
    node.probability = probability;
    node.left = [];
    node.right = [];
end

function heapq(heap, i, order)
    % HEAPQ Heapify a binary tree.
    %   HEAPQ(HEAP,I,ORDER) heapifies the binary tree rooted at index I in
    %   the specified order. ORDER can be 'ascend' or 'descend'.
    %
    %   Example:
    %       heap = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
    %       heapq(heap, 1, 'ascend');
    %       heap % Returns {1, 1, 2, 3, 3, 9, 4, 6, 5, 5, 5}
    %
    %   See also HEAPPUSH, HEAPPUSHPOP, HEAPREPLACE.

    % Get the indices of the left and right children
    left = 2 * i;
    right = 2 * i + 1;

    % Find the index of the smallest or largest element
    if left <= numel(heap) && compare(heap{left}, heap{i}, order)
        smallest_or_largest = left;
    else
        smallest_or_largest = i;
    end
    if right <= numel(heap) && compare(heap{right}, heap{smallest_or_largest}, order)
        smallest_or_largest = right;
    end

    % Swap the current element with the smallest or largest element
    if smallest_or_largest ~= i
        temp = heap{i};
        heap{i} = heap{smallest_or_largest};
        heap{smallest_or_largest} = temp;
        heapq(heap, smallest_or_largest, order);
    end
end

function result = compare(a, b, order)
    % COMPARE Compare two elements.
    %   RESULT = COMPARE(A,B,ORDER) compares the elements A and B in the
    %   specified order. ORDER can be 'ascend' or 'descend'.
    %
    %   Example:
    %       compare(1, 2, 'ascend') % Returns true
    %       compare(1, 2, 'descend') % Returns false
    %
    %   See also HEAPQ.

    if strcmp(order, 'ascend')
        result = a < b;
    else
        result = a > b;
    end
end