数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究霍夫曼编码和数据结构中的熵
霍夫曼编码
霍夫曼编码被定义为一种特定类型的最优前缀码，通常用于无损数据压缩。
查找或实现此类代码的过程通过霍夫曼编码进行，该算法由 David A. Huffman 在麻省理工学院攻读 Sc.D. 学位期间开发，并于 1952 年发表在论文“一种构建最小冗余代码的方法”中。
霍夫曼算法的输出可以显示为一个可变长度代码表，用于对源符号（例如文件中的字符）进行编码。该算法根据每个可能的源符号值的估计概率或出现频率（权重）创建此表。与其他熵编码方法一样，更常见的符号通常用比不太常见的符号更少的位表示。霍夫曼方法可以有效地实现，如果这些权重已排序，则可以在线性时间内找到代码。
熵
在信息论中，香农信源编码定理（或无噪声编码定理）能够确定数据压缩的可能性极限，以及香农熵的操作含义。
信源编码定理表明（在极限情况下，当独立同分布随机变量（i.i.d.）数据流的长度趋于无穷大时），不可能压缩数据，使得码率（每个符号的平均比特数）小于信源的香农熵，而不会几乎肯定地丢失信息。但是，可以获得任意接近香农熵的码率，并且信息丢失的概率可以忽略不计。
信息熵被定义为随机数据源产生信息的平均速率。
计算随机变量的熵
我们还可以计算随机变量中包含多少信息。
例如，如果我们想要计算概率分布为 p 的随机变量 X 的信息，这可能被写成一个函数 H()；例如：H(X)
实际上，计算随机变量的信息与计算随机变量事件的概率分布的信息类似。
计算随机变量的信息被称为“信息熵”、“香农熵”或简称“熵”。
它与物理学中的熵概念通过类比相关联，因为两者都涉及不确定性这一概念。
熵的直觉是，它被定义为表示或传输从随机变量的概率分布中抽取的事件所需的平均比特数。
分布的香农熵被定义为从该分布中抽取的事件中的信息的期望量。
它为从分布 P 中抽取的符号所需的平均编码比特数提供了下界。
对于具有 k 个离散状态的随机变量 X，可以计算熵如下
H(X) = -sum(each k in K p(k) * log(p(k)))
这意味着每个事件的概率乘以每个事件概率的对数的总和的负数。
与信息一样，log() 函数使用以 2 为底的对数，单位为比特。可以改用自然对数。
对于概率为 1.0 的单个事件的随机变量（确定性），计算出的熵最低。如果所有事件都等可能发生，则随机变量的熵将达到最大。
2K+ 浏览量
