2023年6月22日发(作者：)

⾃⼰动⼿写word2vec（三）：构建Huffman树系列所有帖⼦

这⼀部分将解释Huffman树的构造⽅法，并说明了如何根据Huffman树来产⽣对应的⼆进制编码。这部分的代码放在中Huffman树的构造Huffman树的构造⽅法与Huffman编码密切相关。

具体的做法可以⽤下列伪码来描述while (单词列表长度>1) { 从单词列表中挑选出出现频率最⼩的两个单词 ; 创建⼀个新的中间节点，其左右节点分别是之前的两个单词节点 ; 从单词列表中删除那两个单词节点并插⼊新的中间节点 ;}当循环执⾏完毕，节点列表中的唯⼀⼀个节点即为树的根节点。具体的执⾏稍微有点复杂，⾸先要构造⼀个Huffman树的节点类，在该类中存储⼀个节点的相关信息，包括这个节点的概率，左右⼦树，节点的value ( value存储的内容根据节点类型有所不同，对于叶节点，存储的是这个单词本⾝，⽽对于⾮叶节点，存储的是这个节点中存储的中间向量 ) 和对应的huffman码，如下所⽰class HuffmanTreeNode(): def __init__(self,value,possibility): # common part of leaf node and tree node ility = possibility = None # 左⼦树 = None # 右⼦树 # value of leaf node will be the word, and be # mid vector in tree node = value # the value of word

n = "" # store the huffman codeHuffman树类中主要的⽅法有：build_tree，merge，generate_huffman_code。

build_tree 顾名思义，⽤来产⽣树形结构

merge⽤来合并两个节点并产⽣它们的⽗节点

generate_huffman_code⽤来根据已经产⽣的树结构来为词典中的每个词产⽣对应的huffman码所以在构造Huffman树的部分，主要看build_tree,merge和构造⽅法这三个⽅法⾸先来看构造⽅法class HuffmanTree(): def __init__(self, word_dict, vec_len=15000): _len = vec_len # the length of word vector = None word_dict_list = list(word_()) node_list = [HuffmanTreeNode(x['word'],x['possibility']) for x in word_dict_list] _tree(node_list) # _CBT(node_list) te_huffman_code(, word_dict)可以看到，构建HuffmanTree需要由WordCount产⽣的词典，并且需要指定词向量的长度。node_list = [HuffmanTreeNode(x['word'],x['possibility']) for x in word_dict_list]这⼀⾏代码，对词典中的每个词都产⽣对应的HuffmanTreeNode对象，以便进⼀步处理接下来来看merge⽅法 def merge(self,node1,node2): top_pos = ility + ility # 将概率相加 top_node = HuffmanTreeNode(([1,_len]), top_pos) if ility >= ility : top_ = node1 top_ = node2 else: top_ = node2 top_ = node1 return top_nodemerge⽅法⾮常简单，新⽣成的节点的概率是两个输⼊节点的概率之和，其左右⼦节点即为输⼊的两个节点。值得注意的是，新⽣成的节点肯定不是叶节点，⽽⾮叶结点的value值是中间向量，初始化为零向量。最后是buid_tree⽅法 def build_tree(self,node_list): while node_list.__len__()>1: i1 = 0 # i1表⽰概率最⼩的节点 i2 = 1 # i2 概率第⼆⼩的节点 if node_list[i2].possibility < node_list[i1].possibility : [i1,i2] = [i2,i1] for i in range(2,node_list.__len__()): # 找到最⼩的两个节点 if node_list[i].possibilityi2: node_(i1) node_(i2) else: raise RuntimeError('i1 should not be equal to i2') node_(0,top_node) # 插⼊新节点 = node_list[0]这个之前已经⽤伪码描述过了，就不多说了Huffman码的⽣成⽣成了Huffman树之后，就需要⽣成对应的Huffman码，以便进⾏下⼀步的训练过程。

⽣成Huffman码的过程⽐较简单，假设⼀个节点的huffman码为“xx”，那么其左节点的huffman码为”xx1”，右节点的huffman码为”xx0”，从上到下直到叶节点，由此⽣成所有节点(包括叶节点和⾮叶结点)的Huffman码 def generate_huffman_code(self, node, word_dict): stack = [] while (stack.__len__()>0): node = () # go along left tree while or : code = n n = code + "1" n = code + "0" () node = word = code = n # print(word,'t',code.__len__(),'t',ility) word_dict[word]['Huffman'] = code这⼀过程理所当然的需要遍历所有节点。遍历可以⽤递归来完成，但是这⾥使⽤栈来完成遍历过程。