根据文件中的要求与内容用2020b版本matlab编写相关程序

根据《Assignment1.pdf》的要求和内容，以下是使用MATLAB R2020b编写的实现Huffman Coding和Shannon-Fano Coding的代码。这个代码包括了所有必要的步骤，从输入设置到效率分析，并且提供了详细的注释和可视化结果。

### MATLAB Script (`FirstnameLastname.mlx`)

%% Beijing Dublin International College EEEN3017J - Information Theory & Coding
% Assignment 1
% Author: [Your Full Name]
% Date: [Current Date]

%% Input Setup
symbols = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'};
probabilities = [0.25, 0.2, 0.15, 0.12, 0.1, 0.08, 0.06, 0.04];

%% Entropy Calculation
function H = calculate_entropy(probs)
    % Calculate the entropy of the source
    H = -sum(probs .* log2(probs));
end

entropy = calculate_entropy(probabilities);
fprintf('Entropy (H) of the source: %.4f bits\n', entropy);

%% Custom Huffman Coding Implementation
function [codes, huffman_tree] = huffman_coding(symbols, probabilities)
    % Create a priority queue (min-heap)
    nodes = arrayfun(@(i) struct('symbol', symbols{i}, 'probability', probabilities(i), 'left', [], 'right', []), 1:length(symbols), 'UniformOutput', false);
    nodes = sort(nodes, 'Probability');

    while length(nodes) > 1
        % Pop two nodes with the smallest probabilities
        node1 = nodes{1};
        node2 = nodes{2};
        nodes(1:2) = [];

        % Create a new internal node
        newNode = struct('symbol', '', 'probability', node1.probability + node2.probability, 'left', node1, 'right', node2);
        nodes = [nodes, newNode];
        nodes = sort(nodes, 'Probability');
    end

    huffman_tree = nodes{1};

    % Generate Huffman codes
    codes = get_codes(huffman_tree, '');
end

function codes = get_codes(node, code, codes = containers.Map())
    if ~isempty(node.symbol)
        codes(node.symbol) = code;
    else
        get_codes(node.left, [code '0'], codes);
        get_codes(node.right, [code '1'], codes);
    end
end

[huffman_codes, huffman_tree] = huffman_coding(symbols, probabilities);

%% Custom Shannon-Fano Coding Implementation
function codes = shannon_fano_coding(symbols, probabilities)
    % Sort symbols by decreasing probability
    [sorted_probs, idx] = sort(probabilities, 'descend');
    sorted_symbols = symbols(idx);

    % Recursive function to split the list
    function codes = sf_split(symbols, probs, code, codes)
        n = length(symbols);
        if n == 1
            codes(symbols{1}) = code;
        else
            best_diff = inf;
            best_idx = 1;
            left_sum = 0;
            right_sum = sum(probs);
            for i = 1:n-1
                left_sum = left_sum + probs(i);
                right_sum = right_sum - probs(i);
                diff = abs(left_sum - right_sum);
                if diff < best_diff
                    best_diff = diff;
                    best_idx = i;
                end
            end
            codes = sf_split(symbols(1:best_idx), probs(1:best_idx), [code '0'], codes);
            codes = sf_split(symbols(best_idx+1:end), probs(best_idx+1:end), [code '1'], codes);
        end
    end

    codes = containers.Map();
    codes = sf_split(sorted_symbols, sorted_probs, '', codes);
end

shannon_fano_codes = shannon_fano_coding(symbols, probabilities);

%% String Encoding
sample_string = 'AABCCDEFGH';

function encoded_str = encode_string(str, codes)
    encoded_str = '';
    for i = 1:length(str)
        encoded_str = [encoded_str, codes(char(str(i)))];
    end
end

huffman_encoded = encode_string(sample_string, huffman_codes);
shannon_fano_encoded = encode_string(sample_string, shannon_fano_codes);

fprintf('Huffman Encoded String: %s\n', huffman_encoded);
fprintf('Shannon-Fano Encoded String: %s\n', shannon_fano_encoded);

%% Efficiency Analysis
function avg_code_length(codes, probabilities)
    total_length = 0;
    for i = 1:length(symbols)
        total_length = total_length + probabilities(i) * length(codes(symbols{i}));
    end
    avg_code_length = total_length;
end

huffman_avg_len = avg_code_length(huffman_codes, probabilities);
shannon_fano_avg_len = avg_code_length(shannon_fano_codes, probabilities);

compression_ratio_huffman = length(sample_string) / length(huffman_encoded);
compression_ratio_shannon_fano = length(sample_string) / length(shannon_fano_encoded);

redundancy_huffman = huffman_avg_len - entropy;
redundancy_shannon_fano = shannon_fano_avg_len - entropy;

coding_efficiency_huffman = (entropy / huffman_avg_len) * 100;
coding_efficiency_shannon_fano = (entropy / shannon_fano_avg_len) * 100;

results = table({'Huffman'; 'Shannon-Fano'}, ...
                [huffman_avg_len; shannon_fano_avg_len], ...
                [compression_ratio_huffman; compression_ratio_shannon_fano], ...
                [redundancy_huffman; redundancy_shannon_fano], ...
                [coding_efficiency_huffman; coding_efficiency_shannon_fano], ...
                'VariableNames', {'Method', 'AverageCodeLength', 'CompressionRatio', 'Redundancy', 'CodingEfficiency'});

disp(results);

%% Visualization
figure;
bar([huffman_avg_len, shannon_fano_avg_len]);
set(gca, 'XTickLabel', {'Huffman', 'Shannon-Fano'});
ylabel('Average Code Length');
title('Comparison of Average Code Length');

figure;
bar([coding_efficiency_huffman, coding_efficiency_shannon_fano]);
set(gca, 'XTickLabel', {'Huffman', 'Shannon-Fano'});
ylabel('Coding Efficiency (%)');
title('Comparison of Coding Efficiency');

### 报告（PDF）
在提交时，需要附带一个详细的报告（PDF），其中包括以下内容：

1. **熵计算**：解释熵的计算方法及其在数据压缩中的意义。
2. **编码实现**：详细说明Huffman Coding和Shannon-Fano Coding的实现过程。
3. **字符串编码**：展示样本字符串的编码结果。
4. **效率分析**：比较两种编码方法的平均码长、压缩比、冗余度和编码效率。
5. **数学证明**：提供数学证明，解释为什么Huffman Coding通常能实现更短的平均码长和更高的编码效率。
6. **可视化结果**：使用条形图等图表展示和比较结果。

### 提交指南
1. 将上述MATLAB脚本保存为 `FirstnameLastname.mlx`。
2. 编写并提交一个详细的PDF报告，总结你的发现、数学证明和结果。
3. 确保所有图表和表格都清晰标注轴标签和标题。
4. 在Brightspace上按时提交。

希望这些代码和指导对你完成作业有所帮助！如果有任何问题，请随时联系我。