利用Matlab实现霍夫曼编码，要求不使用Matlab自带的生成霍夫曼编码的函数，要求对于任意输入概率均可使用，同时若出现概率之和等于原始概率中的某一个话，使用概率之和相等向上排和向下排两种方法来实现，并对比编码效率以及码长和信源熵

好的，我可以为您讲解一下霍夫曼编码的实现思路和步骤，并提供一份Matlab代码。

## 霍夫曼编码的实现

### 1. 构建霍夫曼树

对于给定的概率分布，首先需要根据概率构建霍夫曼树。具体步骤如下：

- 将每个概率看作一个节点，构成一个节点集合。
- 从节点集合中选出两个概率最小的节点，将它们合并为一个新的节点，其概率为两个节点概率之和。
- 将新的节点加入节点集合中，并删除原来的两个节点。
- 重复上述过程，直到节点集合中只剩下一个节点，即为霍夫曼树的根节点。

### 2. 构建霍夫曼编码表

构建霍夫曼编码表的过程可以通过遍历霍夫曼树实现。从根节点开始遍历，走左子树就标记为0，走右子树就标记为1，直到遍历到叶子节点，得到该叶子节点对应的符号的霍夫曼编码。具体步骤如下：

- 从根节点开始，设当前节点为根节点，编码为空。
- 若当前节点是叶子节点，则将该叶子节点对应的符号和编码加入霍夫曼编码表中。
- 若当前节点不是叶子节点，则遍历其左子树和右子树，分别在编码后加上0和1，并递归地处理左右子树。

### 3. 对输入进行编码

利用构建好的霍夫曼编码表，可以对输入进行编码。具体步骤如下：

- 对于每个输入符号，查找其在霍夫曼编码表中的编码，并将编码拼接到输出编码序列中。

### 4. 对输入进行解码

对于给定的霍夫曼编码和编码表，可以对输入进行解码。具体步骤如下：

- 从输入编码序列中取出一个字符，加入当前编码中。
- 在霍夫曼编码表中查找当前编码对应的符号，若找到了符号，则输出该符号并清空当前编码。
- 若没有找到符号，则继续从输入编码序列中取出字符，重复上述过程。

## Matlab代码实现

下面是一个简单的Matlab代码实现霍夫曼编码的例子。首先是构建霍夫曼树和编码表的代码：

function [huffCodes, avgLen] = huffmanCoding(prob)
% HUFFMANCODING - Huffman coding algorithm implementation.
%
%   [huffCodes, avgLen] = huffmanCoding(prob) returns the Huffman codes of
%   given symbols with probabilities in vector `prob`. The output `huffCodes`
%   is a cell array containing the Huffman codes for each symbol. The output
%   `avgLen` is the average length of the Huffman code.
%
%   Example:
%
%       >> prob = [0.15, 0.2, 0.35, 0.3];
%       >> [huffCodes, avgLen] = huffmanCoding(prob)
%
%   Reference:
%
%       https://en.wikipedia.org/wiki/Huffman_coding

% make sure input is valid
assert(isvector(prob) && isnumeric(prob) && all(prob >= 0) && all(prob <= 1));
n = length(prob);

% initialize nodes
nodes = cell(1, n);
for i = 1:n
    nodes{i} = struct('symbol', i, 'prob', prob(i), 'parent', [], 'code', []);
end

% build Huffman tree
for i = 1:n-1
    % find two smallest nodes
    [min1, min2] = findMinNodes(nodes);
    % combine two smallest nodes
    parent = struct('symbol', [], 'prob', min1.prob + min2.prob, 'parent', [], 'code', []);
    parent.left = min1;
    parent.right = min2;
    min1.parent = parent;
    min2.parent = parent;
    nodes{end+1} = parent;
end

% build Huffman codes
huffCodes = cell(1, n);
for i = 1:n
    % traverse from leaf node to root node
    node = nodes{i};
    code = '';
    while ~isempty(node.parent)
        if node == node.parent.left
            code = ['0', code];
        else
            code = ['1', code];
        end
        node = node.parent;
    end
    huffCodes{i} = code;
end

% calculate average code length
avgLen = 0;
for i = 1:n
    avgLen = avgLen + prob(i) * length(huffCodes{i});
end
end

function [min1, min2] = findMinNodes(nodes)
% FINDMINNODES - Find two smallest nodes from a list of nodes.
min1 = struct('prob', Inf);
min2 = struct('prob', Inf);
for i = 1:length(nodes)
    node = nodes{i};
    if node.prob < min1.prob
        min2 = min1;
        min1 = node;
    elseif node.prob < min2.prob
        min2 = node;
    end
end
end

然后是编码和解码的代码：

function encoded = huffmanEncode(data, huffCodes)
% HUFFMANENCODE - Encode input data using given Huffman codes.
%
%   encoded = huffmanEncode(data, huffCodes) encodes the input data using the
%   given Huffman codes. The input `data` should be a vector of symbols to be
%   encoded. The input `huffCodes` is a cell array containing the Huffman
%   codes for each symbol.
%
%   Example:
%
%       >> data = [1 3 4 2 3];
%       >> prob = [0.15, 0.2, 0.35, 0.3];
%       >> [huffCodes, ~] = huffmanCoding(prob);
%       >> encoded = huffmanEncode(data, huffCodes)

% make sure input is valid
assert(isvector(data) && isnumeric(data));
assert(iscell(huffCodes) && isvector(huffCodes) && length(huffCodes) >= max(data));

% encode data using Huffman codes
encoded = '';
for i = 1:length(data)
    code = huffCodes{data(i)};
    encoded = [encoded, code];
end
end

function decoded = huffmanDecode(encoded, huffCodes)
% HUFFMANDECODE - Decode input data using given Huffman codes.
%
%   decoded = huffmanDecode(encoded, huffCodes) decodes the input data using
%   the given Huffman codes. The input `encoded` should be a string of binary
%   code to be decoded. The input `huffCodes` is a cell array containing the
%   Huffman codes for each symbol.
%
%   Example:
%
%       >> data = [1 3 4 2 3];
%       >> prob = [0.15, 0.2, 0.35, 0.3];
%       >> [huffCodes, ~] = huffmanCoding(prob);
%       >> encoded = huffmanEncode(data, huffCodes);
%       >> decoded = huffmanDecode(encoded, huffCodes)

% make sure input is valid
assert(ischar(encoded) && isvector(encoded));
assert(iscell(huffCodes) && isvector(huffCodes) && length(huffCodes) >= 1);

% decode data using Huffman codes
decoded = [];
code = '';
for i = 1:length(encoded)
    code = [code, encoded(i)];
    for j = 1:length(huffCodes)
        if strcmp(code, huffCodes{j})
            decoded = [decoded, j];
            code = '';
            break;
        end
    end
end
end

最后，是一个例子，演示如何使用上述代码来进行霍夫曼编码和解码：

% example usage of huffmanCoding, huffmanEncode, and huffmanDecode
prob = [0.15, 0.2, 0.35, 0.3];
symbols = 1:length(prob);
[data, prob] = generateData(prob, 1000);
[huffCodes, avgLen] = huffmanCoding(prob);
encoded = huffmanEncode(data, huffCodes);
decoded = huffmanDecode(encoded, huffCodes);
assert(all(data == decoded));
fprintf('Average code length: %.4f\n', avgLen);

% helper function to generate random data with given probability distribution
function [data, prob] = generateData(prob, numData)
assert(isvector(prob) && isnumeric(prob) && all(prob >= 0) && all(prob <= 1));
n = length(prob);
assert(numData > 0);
data = randsample(1:n, numData, true, prob);
prob = histcounts(data, 1:n+1);
prob = prob / sum(prob);
end

注意，这份代码只是一个简单的实现，可能存在一些性能问题。如果需要处理大规模数据或者需要更高效的实现，可以考虑使用其他的编程语言或者更加优化的实现方式。