费诺编码matlab代码

以下是一个简单的 MATLAB 实现费诺编码的代码：

function [codebook, avglen] = huffman(p)
% HUFFMAN  Huffman codebook for a given probability mass function.
%   Given a probability mass function p, return a Huffman codebook.
%   The codebook is represented as a cell array of strings, where
%   codebook{i} is the binary codeword for the symbol with probability
%   p(i). Also return the average codeword length.

n = length(p);
codebook = cell(n, 1);
avglen = 0;

% Initialize the heap with the symbols and their probabilities.
heap = cell(n, 1);
for i = 1:n
    heap{i} = {p(i), i};
end

% Build the Huffman tree.
for k = 1:n-1
    % Extract the two symbols with smallest probabilities.
    [p1, i1] = extractMin(heap);
    [p2, i2] = extractMin(heap);
    
    % Combine the symbols and their probabilities.
    pnew = p1 + p2;
    inew = {pnew, i1, i2};
    
    % Insert the new symbol back into the heap.
    heap{k+n} = inew;
    
    % Update the tree by adding new edges.
    if k == 1
        % The first iteration.
        tree = inew;
    else
        % Find the leaf nodes that correspond to the two symbols.
        [u, v] = findNodes(tree, i1, i2);
        % Add new edges to the tree.
        tree = addEdge(tree, u, k+n);
        tree = addEdge(tree, v, k+n);
    end
end

% Generate the codebook by traversing the tree.
for i = 1:n
    % Traverse the tree from the root to the leaf node.
    code = '';
    node = i;
    while node ~= n+k
        [u, v] = findNodes(tree, node, 0);
        if u == 0
            code = ['0' code];
            node = v;
        else
            code = ['1' code];
            node = u;
        end
    end
    codebook{i} = code;
    avglen = avglen + p(i) * length(code);
end
end

function [p, i] = extractMin(heap)
% Extract the symbol with smallest probability from the heap.

n = length(heap);
p = heap{1}{1};
i = heap{1}{2};

% Replace the root with the last leaf node and sift down.
heap{1} = heap{n};
heap = heap(1:n-1);
n = n - 1;
k = 1;
while 2*k <= n
    j = 2*k;
    if j < n && heap{j}{1} > heap{j+1}{1}
        j = j + 1;
    end
    if heap{k}{1} > heap{j}{1}
        tmp = heap{k};
        heap{k} = heap{j};
        heap{j} = tmp;
        k = j;
    else
        break;
    end
end
end

function [u, v] = findNodes(tree, i, j)
% Find the leaf nodes in the subtree rooted at i and j.

u = 0;
v = 0;
n = length(tree);
for k = 1:n
    node = tree{k};
    if node{2} == i
        u = k;
    end
    if node{2} == j
        v = k;
    end
    if u > 0 && v > 0
        break;
    end
end
end

function tree = addEdge(tree, u, v)
% Add a new edge to the Huffman tree.

n = length(tree);
node = {0, 0, 0};
node{1} = tree{u}{1} + tree{v}{1};
node{2} = u;
node{3} = v;
tree{end+1} = node;
end

在这个实现中，我们使用一个小根堆来维护符号的概率。我们首先将每个符号及其概率插入堆中，然后不断从堆中取出概率最小的两个符号，将它们合并成一个新符号，然后将新符号插入堆中。在这个过程中，我们还维护了一个 Huffman 树，用于生成编码。最后，我们从根节点开始遍历 Huffman 树，生成每个符号的编码。