哈夫曼编码

哈夫曼编码(Huffman Coding)，又称霍夫曼编码，是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫做Huffman编码（有时也称为霍夫曼编码）。—-百度百科

哈夫曼编码性质

  1. 哈夫曼编码是前缀编码，因为没有一片叶子是另一片叶子的祖先，所以就不可能是其他编码的前缀
  2. 哈夫曼编码是最优前缀编码，因为哈夫曼树的带权路径长度最短，古字符编码总长最短

创建哈夫曼编码算法实现

--创建哈夫曼编码算法
--array - 哈夫曼树数组，n - 叶子结点数量
--[[
	哈夫曼树数组结构：
    array.weight = 0--权重值
    array.lch = 0--左孩子(数组中的下标)
    array.rch = 0--右孩子(数组中的下标)
    array.parent = 0--双亲(数组中的下标)
    ]]
function HuffmanTree:CreatHuffmanCode(array, n)
	--哈夫曼编码
	local huffmanCodeCode = ""

	--从叶子到跟逆向求每个字符的哈夫曼编码，存储在huffmanCodeCode中
	for i = 1, n do
		local chart = ""--临时存储单个编码字符
		local c = i--开始叶子下标
		local parent= array[i].parent

		--从叶子结点开始向上回溯，直到根结点
		while f ~= 0 do
			if array[parent].lch == c then chart = "0" .. chart--左孩子
			else chart = "1" .. chart end				       --右孩子

			--继续向上回溯
			c = parent
			f = array[parent].parent
		end
		huffmanCodeCode = huffmanCodeCode .. chart
	end
	return huffmanCodeCode
end

构造哈夫曼树数组算法请查看：
【Lua】哈夫曼树构造算法分析