霍夫曼码和数据结构中的熵
霍夫曼密码
霍夫曼码被定义为通常用于无损数据压缩的最优前缀码的特定类型。
查找或实现这种代码的过程是通过霍夫曼编码进行的，霍夫曼编码是戴维·霍夫曼（DavidA.Huffman）担任法学博士学位时开发的一种算法。麻省理工学院的学生，并发表于1952年的论文“一种构建最小冗余码的方法”。
霍夫曼算法的输出可以显示为可变长度代码表，用于对源符号（例如文件中的字符）进行编码。该算法根据源符号每个可能值的估计概率或出现频率（权重）创建此表。如同在其他熵编码方法中一样，与较少公共的符号相比，通常表示更多公共的符号实现更少的比特。霍夫曼方法可以有效地实现，如果对这些权重进行排序，则可以找到与输入权重数量呈线性关系的时间码。
熵
在信息论中，香农的源编码定理（或无噪声编码定理）能够确定可能的数据压缩以及香农熵的运算含义的极限。
源编码定理显示（在极限情况下，由于独立且均匀分布的随机变量(iid)数据流的长度趋于无穷大），无法压缩数据以使编码率（每个符号的比特数）小于源的香农熵，但实际上并不能确定会丢失信息。然而，有可能获得任意接近香农熵的码率，而丢失的可能性很小。
信息熵定义为由随机数据源产生信息的平均速率。
计算随机变量的熵
我们还可以计算随机变量中包含多少信息。
例如，如果我们要计算概率分布为p的随机变量X的信息，则可以将其写为函数H()；例如：H(X)
实际上，为随机变量计算信息与为随机变量事件的概率分布计算信息相似。
计算随机变量的信息表示为“信息熵”，“香农熵”或简称为“熵”。
通过类推，它与物理学中的熵概念有关，因为两者都与术语不确定性有关。
熵的直觉是将其定义为表示或传输从随机变量的概率分布得出的事件所需的平均位数。
分布的香农熵定义为从该分布中提取的事件中的预期信息量。
它为编码从分布P提取的符号平均所需的位数提供了下限。
可以为K个离散状态下的k个随机变量X计算熵，如下所示
H(X) = -sum(each k in K p(k) * log(p(k)))
这意味着每个事件的概率之和乘以每个事件的概率的对数的负数。
像信息一样，该log()函数实现base-2，单位为位。可以使用自然对数代替。
对于具有单个事件的随机变量（确定性为1.0），计算最低熵。如果所有事件的执行概率均等，则随机变量的最大熵将是可能的。