huffman编码matlab

Huffman编码是一种用于压缩数据的算法，它利用字符出现的频率来决定每个字符的编码方式，使得出现频率较高的字符具有较短的编码，从而实现数据压缩的效果。

以下是一个简单的Huffman编码的Matlab实现：

function [codes, dict] = huffman_encoding(symbols, prob)
% symbols: a cell array of symbols to be encoded
% prob: a vector of probabilities for each symbol

% Step 1: Create a min-heap of probability nodes
n = length(symbols);
heap = cell(n, 1);
for i = 1:n
    heap{i} = struct('symbol', symbols{i}, 'prob', prob(i));
end
heap = min_heap_build(heap);

% Step 2: Build the Huffman tree
while heap.count > 1
    node1 = min_heap_pop(heap);
    node2 = min_heap_pop(heap);
    new_node = struct('symbol', [], 'prob', node1.prob + node2.prob, ...
                      'left', node1, 'right', node2);
    min_heap_push(heap, new_node);
end
root = min_heap_pop(heap);

% Step 3: Traverse the tree to generate codes
codes = cell(n, 1);
dict = struct();
traverse(root, '', codes, dict);

function traverse(node, code, codes, dict)
    if isempty(node.symbol)
        traverse(node.left, [code '0'], codes, dict);
        traverse(node.right, [code '1'], codes, dict);
    else
        codes{node.symbol} = code;
        dict.(node.symbol) = code;
    end
end

end

% Helper functions for min-heap operations
function heap = min_heap_build(nodes)
    n = length(nodes);
    heap = struct('nodes', nodes, 'count', n);
    for i = floor(n/2):-1:1
        min_heapify(heap, i);
    end
end

function min_heap_push(heap, node)
    heap.count = heap.count + 1;
    heap.nodes{heap.count} = node;
    i = heap.count;
    while i > 1 && heap.nodes{i}.prob < heap.nodes{parent(i)}.prob
        swap(heap, i, parent(i));
        i = parent(i);
    end
end

function node = min_heap_pop(heap)
    node = heap.nodes{1};
    heap.nodes{1} = heap.nodes{heap.count};
    heap.count = heap.count - 1;
    min_heapify(heap, 1);
end

function min_heapify(heap, i)
    l = left(i);
    r = right(i);
    smallest = i;
    if l <= heap.count && heap.nodes{l}.prob < heap.nodes{smallest}.prob
        smallest = l;
    end
    if r <= heap.count && heap.nodes{r}.prob < heap.nodes{smallest}.prob
        smallest = r;
    end
    if smallest ~= i
        swap(heap, i, smallest);
        min_heapify(heap, smallest);
    end
end

function swap(heap, i, j)
    temp = heap.nodes{i};
    heap.nodes{i} = heap.nodes{j};
    heap.nodes{j} = temp;
end

function p = parent(i)
    p = floor(i/2);
end

function l = left(i)
    l = 2*i;
end

function r = right(i)
    r = 2*i+1;
end

使用方法：

symbols = {'A', 'B', 'C', 'D', 'E'};
prob = [0.2, 0.25, 0.15, 0.1, 0.3];
[codes, dict] = huffman_encoding(symbols, prob);

其中`symbols`是要编码的字符数组，`prob`是每个字符出现的概率。函数返回值`codes`是每个字符的Huffman编码，`dict`是一个结构体，可以通过`dict.(symbol)`的方式获取某个字符的编码。