文章

Shannon-fano编码和译码(C++)

#include <iostream>
#include <vector>
#include <map>
#include <iomanip>
#include <algorithm>

using namespace std;

// 信源结构体
struct Source {
    char symbol;      // 信源符号
    double probability;  // 信源概率
};

// 节点结构体
struct Node {
    double probability;  // 节点概率
    string code;         // 节点对应的编码
    Node* left;          // 左子节点
    Node* right;         // 右子节点
    
    Node(double p) : probability(p), left(nullptr), right(nullptr) {}
};

// 比较器
bool compareSources(const Source& a, const Source& b) {
    return a.probability < b.probability;
}

// 构建香农-费诺树
Node* buildShannonFanoTree(vector<Source>& sources, int start, int end) {
    if (start == end)
        return new Node(sources[start].probability);

    double sum = 0.0;
    for (int i = start; i <= end; i++) {
        sum += sources[i].probability;
    }

    double lhsSum = 0.0;
    int split = start;
    for (; split <= end; split++) {
        lhsSum += sources[split].probability;
        if (lhsSum >= sum / 2)
            break;
    }

    Node* node = new Node(sum);

    node->left = buildShannonFanoTree(sources, start, split);
    node->right = buildShannonFanoTree(sources, split + 1, end);

    return node;
}

// 递归地遍历香农-费诺树,构建编码
void buildCodes(Node* root, string code, map<char, string>& codes) {
    if (root == nullptr)
        return;

    if (root->left == nullptr && root->right == nullptr) {
        codes[root->code[0]] = code;
        return;
    }

    buildCodes(root->left, code + "0", codes);
    buildCodes(root->right, code + "1", codes);
}

// 输出信源的码长、码字和熵
void printEncodingDetails(const vector<Source>& sources, const map<char, string>& codes) {
    double entropy = 0.0;
    double avgCodeLength = 0.0;
	
	cout << "-----------------------------" << endl;
    cout << "消息\t概率\t码长\t码字" << endl;
    cout << "-----------------------------" << endl;

    for (const auto& source : sources) {
        string code = codes.at(source.symbol);
        int codeLength = code.length();
        double sourceEntropy = -log2(source.probability);

        entropy += source.probability * sourceEntropy;
        avgCodeLength += source.probability * codeLength;

        cout << setw(4) << source.symbol << "\t";
        cout << setw(6) << fixed << setprecision(2) << source.probability << "\t";
        cout << setw(4) << codeLength << "\t";
        cout << code << endl;
    }

    cout << "-----------------------------" << endl;
    cout << "信源熵: H(X) = -∑(p(x)log2(p(x))) = " << fixed << setprecision(2) << entropy << " bits" << endl;
    cout << "平均码长: L(X) = ∑(p(x)l(x)) = " << fixed << setprecision(2) << avgCodeLength << " bits" << endl;
    cout << "编码效率: E(X) = (H(X) / L(X)) * 100.0 = " << fixed << setprecision(2) << (entropy / avgCodeLength * 100.0) << "%" << endl;
}

// 译码函数
string decode(string encodedText, Node* root) {
    string decodedText;

    Node* current = root;
    for (char bit : encodedText) {
        if (bit == '0') {
            current = current->left;
        } else {
            current = current->right;
        }

        if (current->left == nullptr && current->right == nullptr) {
            decodedText += current->code;
            current = root;
        }
    }

    return decodedText;
}

int main() {
    int numSources;

    cout << "请输入消息个数:";
    cin >> numSources;

    vector<Source> sources(numSources);
    for (int i = 0; i < numSources; i++) {
        cout << "请输入第 " << (i + 1) << " 个消息符号:";
        cin >> sources[i].symbol;
        cout << "请输入第 " << (i + 1) << " 个消息概率:";
        cin >> sources[i].probability;
    }
    
    // 按概率从大到小排序
    sort(sources.begin(), sources.end(), compareSources);

    // 构建香农-费诺树和编码表
    Node* root = buildShannonFanoTree(sources, 0, numSources - 1);
    map<char, string> codes;
    buildCodes(root, "", codes);

    // 输出编码信息
    printEncodingDetails(sources, codes);

    // 进行译码
	while(1){
		char judge;
		cout << "\n是否进行译码(y/n):";
		cin >> judge;
		if(judge == 'y'){
		    cout << "\n请输入要译码的二进制序列:";
		    string encodedText;
		    cin >> encodedText;
		    string decodedText = decode(encodedText, root);
		    cout << "译码结果:" << decodedText << endl;
		}
		else{
			break;
		}
	}
    // 释放动态分配的内存
    delete root;

    return 0;
}

License:  CC BY 4.0