Python语言实现哈夫曼编码

class Node:
    def __init__(self,freq):
        self.left = None
        self.right = None
        self.father = None
        self.freq = freq

    def is_left(self):
        return self.father.left == self

def create_nodes(frequencies):
    return [Node(freq) for freq in frequencies]

def create_huffman_tree(nodes):
    queue = nodes[:]
    while len(queue) > 1:
        queue.sort(key=lambda item: item.freq)
        node_left = queue.pop(0)
        node_right = queue.pop(0)
        node_father = Node(node_left.freq + node_right.freq)
        node_father.left = node_left
        node_father.right = node_right
        node_left.father = node_father
        node_right.father = node_father
        queue.append(node_father)
    queue[0].father = None
    return queue[0]

def huffman_encoding(nodes, root):
    codes = [''] * len(nodes)
    for i in range(len(nodes)):
        node_tmp = nodes[i]
        while node_tmp != root:
            if node_tmp.is_left():
                codes[i] = '0' + codes[i]
            else:
                codes[i] = '1' + codes[i]
            node_tmp = node_tmp.father
    return codes

# 获取字符出现的频数
def count_frequency(input_string):
    # 用于存放字符
    char_store = []
    # 用于存放频数
    freq_store = []

    # 解析字符串
    for index in range(len(input_string)):
        if char_store.count(input_string[index]) > 0:
            temp = int(freq_store[char_store.index(input_string[index])])
            temp = temp + 1
            freq_store[char_store.index(input_string[index])] = temp
        else:
            char_store.append(input_string[index])
            freq_store.append(1)
    # 返回字符列表和频数列表
    return char_store, freq_store

# 获取字符、频数的列表
def get_char_frequency(char_store=[], freq_store=[]):
    # 用于存放char_frequency
    char_frequency = []
    for item in zip(char_store, freq_store):
        temp = (item[0], item[1])
        char_frequency.append(temp)
    return char_frequency

# 将字符转换成huffman编码
def get_huffman_file(input_string, char_frequency, codes):
    # 逐个字符替换
    file_content = ''
    for index in range(len(input_string)):
        for item in zip(char_frequency, codes):
            if input_string[index] == item[0][0]:
                file_content = file_content + item[1]
    file_name = 'huffman_' + str(uuid.uuid1())+'.txt'
    with open(file_name, 'w+') as destination:
        destination.write(file_content)
    return file_name

# 解压缩huffman文件
def decode_huffman(input_string,  char_store, freq_store):
    encode = ''
    decode = ''
    for index in range(len(input_string)):
        encode = encode + input_string[index]
        for item in zip(char_store, freq_store):
            if encode == item[1]:
                decode = decode + item[0]
                encode = ''
    return decode

# 计算压缩比
def get_encode_ration(codes):
    # 计算所需要的二进制个数
    h_length = 0
    for item in codes:
        h_length = h_length + len(item)
    t_length = bin_middle(len(codes))*len(codes)
    ratio = t_length/h_length
    return str(ratio)[0:3]

# 计算所在的二进制空间
def bin_middle(number):
    n, i = 1, 0
    while n < number:
        n = n * 2
        i = i + 1
    return i

def upload(request):
    ctx = {}
    if request.method == "POST":
        file_name = str(request.FILES['file'])
        if not file_name.endswith('txt'):
            ctx['fail'] = 'file format exist wrong!'
        else:
            file = request.FILES['file']
            ctx['success'] = 'Successful'
            input_string = tool.read_file(tool.save_file(file))
            char_store, freq_store = tool.count_frequency(input_string)
            char_frequency = tool.get_char_frequency(char_store, freq_store)
            nodes = huf.create_nodes([item[1] for item in char_frequency])
            root = huf.create_huffman_tree(nodes)
            codes = huf.huffman_encoding(nodes, root)
            save_file_name = tool.get_huffman_file(input_string, char_frequency, codes)
            for item in zip(char_frequency, codes):
                print('Character:%s freq:%-2d   encoding: %s', item[0][0], item[0][1], item[1])
            ctx['node'] = char_frequency

            def file_iterator(files, chunk_size=512):
                with open(files) as f:
                    while True:
                        c = f.read(chunk_size)
                        if c:
                            yield c
                        else:
                            break
            the_file_name = tool.get_encode_ration(codes)+'_'+str(uuid.uuid1())+'.txt'
            response = StreamingHttpResponse(file_iterator(save_file_name))
            response['Content-Type'] = 'application/octet-stream'
            response['Content-Disposition'] = 'attachment;filename="{0}"'.format(the_file_name)
            return response