Huffman Coding Back

Huffman Coding

• Huffman編碼: 為了解決字符因不同權值編碼時, 不能出現前綴碼問題

  A: 00; B: 001; //B出現前綴碼A

• 字符權值表

• Huffman樹不唯一

• 需要事先知道字符權值, (Adaptive Huffman Coding解決這個問題)
• 廣泛應用於壓縮技術
• 採用自底向上的編碼方式

數據結構

class coded_char
{
    private:
    char value;
    double weight;
    string code;
    bool iscoded = false;

    public:
    coded_char(char value, double weight) :value(value), weight(weight){}

    coded_char* left, *right;

    void setcode(string s){code = s;}
    string getcode(){return code;}
    double getweight(){return weight;}
    bool getiscoded(){return iscoded;}
    void setiscoded(){iscoded = true;}
    char getvalue(){return value;}
};

算法實現

/* Create a Hufman Tree */
void HUFFMAN_CODE_CREATE(coded_char* data[])
{
    for (int i = num; i < 2 * num - 1; i++)
    {
        coded_char* last = get_last(data, i);
        coded_char* second_last = get_second_last(data, last, i);
        data[i] = new coded_char(' ', (*last).getweight() + (*second_last).getweight());
        (*data[i]).left = last;
        (*data[i]).right = second_last;
        (*last).setiscoded();
        (*second_last).setiscoded();
    }

    (*data[2 * num - 2]).setcode("");    //root
}

/* Code */
void CODE(coded_char* root)
{
    if ((*root).getvalue() != ' ')
    {
        return;
    }
    else
    {
        (*((*root).left)).setcode((*root).getcode() + "0");
        (*((*root).right)).setcode((*root).getcode() + "1");
        trace((*root).left);
        trace((*root).right);
    }
}

Comments Copyright © aleen42 all right reserved, powered by aleen42

Empty Comments

Sign in GitHub

As the plugin is integrated with a code management system like GitLab or GitHub, you may have to auth with your account before leaving comments around this article.

Notice: This plugin has used Cookie to store your token with an expiration.

authorize