霍夫曼编码的python和c++实现

本文来源吾爱破解论坛

本帖最后由 笙若 于 2019-1-15 08:17 编辑

最近在学算法,用python和c++各自写了一遍代码,虽然实现的并不是很好,还是贴出来记录一下吧.

class Node:
    def __init__(self, name=None, value=None):
        self._name = name
        self._value = value
        self._left = None
        self._right = None

class HuffmanTree:

    # 根据Huffman树的思想：以叶子节点为基础，根据value排序，反向创建Huffman树
    def __init__(self, char_weights):
        self.a = [Node(key, value) for key, value in dict.items()]
        # 将字典中的key和值逐个添加到节点列表a中
        while len(self.a) != 1:
            self.a.sort(key=lambda node: node._value, reverse=True)  # 按叶子的值排序
            c = Node(value=(self.a[-1]._value + self.a[-2]._value))  
            # 将最小的两个节点的值相加赋给新节点c
            c._left = self.a.pop(-1)
            c._right = self.a.pop(-1)  # 删掉最小的两个节点
            self.a.append(c)  # 将新节点添加到列表中
        self.root = self.a[0]  # 根节点=a中第一个节点
        self.b = list(range(20))  # b用来存储字符的二进制序列
        self.d = {}

    # 递归的思想生成编码
    def pre(self, tree, length):
        node = tree
        if (not node):
            return  # 树为空则直接返回

        elif node._name:  # 当节点是一个字符时进行编码
            str_num = ""
            for i in range(length):
                str_num += str(self.b[i])
            # print(node._name + '编码为：', str_num)
            self.d[node._name] = str_num
            return
        # 在找到字符节点前进行递归
        self.b[length] = 0
        self.pre(node._left, length+1)

        self.b[length] = 1
        self.pre(node._right, length+1)

    # 生成霍夫曼编码
    def get_code(self):
        self.pre(self.root, 0)
        print(self.d)

def fRead(filename):
    symbolDict = {}
    fl = 0
    f = open(filename, 'r')
    str = f.read()
    f.close()
    for i in str:
        for j, k in symbolDict.items():
            if i == j:
                fl = 1
                k = k + 1
                break
        if fl == 0:
            symbolDict[i] = 1
        else:
            symbolDict[i] = k
    return symbolDict

if __name__ == '__main__':

    dict = fRead('test.py')
    tree = HuffmanTree(dict)
    tree.get_code()

顺便吐槽一下vscode真的很严格,写python时连有几个空行都要管.

~~~c++

#include<iostream>
#include<algorithm>
using namespace std;
#define MAXBIT 100
#define MAXVALUE 1000
#define MAXLEAF 30
#define MAXNODE MAXLEAF*2-1
typedef struct //定义节点
{
        double weight;
        int parent;
        int lchild;
        int rchild;
        char value;
}HNodeType;
typedef struct //定义编码类型
{
        int bit[MAXBIT]; //存储01编码的数组
        int start; //编码在数组中开始的位置,从最后往前减小
}HCodeType;
HNodeType HuffNode[MAXNODE]; //定义一个足够大的节点数组
HCodeType HuffCode[MAXLEAF]; 
void HuffmanTree (HNodeType HuffNode[MAXNODE],int n) //构造霍夫曼树
{
        int i,j,x1,x2;
        double m1,m2;
        for(i=0;i<2*n-1;i++) //初始化节点数据
        {
                HuffNode[i].weight = 0;
                HuffNode[i].parent = -1;
                HuffNode[i].lchild = -1;
                HuffNode[i].rchild = -1;
        }
        for(i=0;i<n;i++) //输入节点数据
        {
                cout<<"please input the value and weight of leaf node "<<i+1<<endl;
                cin>>HuffNode[i].value>>HuffNode[i].weight;
        }
        for(i=0;i<n-1;i++) //循环合并n-1次
        {
                m1=m2=MAXVALUE; 
                x1=x2=0;
                for(j=0;j<n+i;j++) //在已有的节点里找权重最小的且没有parent的节点
                {
                        if(HuffNode[j].weight<m1&&HuffNode[j].parent==-1)
                        {
                                m2=m1;
                                x2=x1;
                                m1=HuffNode[j].weight;
                                x1=j;
                        }
                        else if (HuffNode[j].weight<m2&&HuffNode[j].parent==-1)
                        {
                                m2=HuffNode[j].weight;
                                x2=j;
                        }
                } //最后m1,m2为最新权重节点的权重,x1,x2为其位置
                HuffNode[x1].parent=n+i;
                HuffNode[x2].parent=n+i;
                HuffNode[n+i].weight=m1+m2;
                HuffNode[n+i].lchild=x1;
                HuffNode[n+i].rchild=x2;
                cout<<"x1.weight and x2.weight in round "<<i+1<<"\t"<<HuffNode[x1].weight<<"\t"<<HuffNode[x2].weight<<endl;
        }
}
void HuffmanCode(HCodeType HuffCode[MAXLEAF],int n) //对生成的树进行编码
{
        HCodeType cd; //临时结构体
        int i,j,c,p;
        for(i=0;i<n;i++)
        {
                cd.start=n-1;
                c=i;
                p=HuffNode[c].parent; //p为遍历过程中每个节点的parent值
                while(p!=-1) //如果未到根节点
                {
                        if(HuffNode[p].lchild==c) //为parent的左节点则在该处编码为0
                                cd.bit[cd.start]=0;
                        else
                                cd.bit[cd.start]=1;
                        cd.start--; //编码长度加1,start位置减1
                        c=p;
                        p=HuffNode[c].parent;
                }
                for(j=cd.start+1;j<n;j++)
                        HuffCode[i].bit[j]=cd.bit[j]; 
                HuffCode[i].start=cd.start; //将临时变量复制到编码结构体
        }
}
int main()
{
        int i,j,n;
        cout<<""<<endl;
        cin>>n;
        HuffmanTree(HuffNode,n);
        HuffmanCode(HuffCode,n);
        for(i=0;i<n;i++)
        {
                cout<<HuffNode[i].value<<" :Huffman code is: ";
                for(j=HuffCode[i].start+1;j<n;j++)
                        cout<<HuffCode[i].bit[j];
                cout<<endl;
        }
        return 0;
}

然后python写起来简单多了.