计算机科学中熵的定义是什么？

Question

计算机科学中熵的定义是什么？

computer-scienceinformation-theoryentropycompression

70

我最近在大学开始了一门数据压缩课程。然而，我发现在计算机科学中使用的“熵”一词有些模糊不清。据我所知，它大致相当于系统或结构的“随机性”。

计算机科学中“熵”的恰当定义是什么？

- fluffels

6

熵是打开衣服烘干机，却发现里面没有已经给你叠好的衣服。 - Bradley Thomas

16个回答

22

我最喜欢的定义是来自 Andrew Hunt 和 David Thomas 的优秀书籍 The Pragmatic Programmer: From Journeyman to Master 第一章：

软件熵

虽然软件开发几乎免疫于所有物理定律，但熵会给我们带来很大的压力。熵是物理学中指系统“混乱程度”的术语。遗憾的是，热力学定律保证了宇宙中的熵趋向于最大值。当软件的混乱程度增加时，程序员把它称为“软件腐败”。

有许多因素可以导致软件腐败。最重要的一个似乎是项目上工作的心理学或文化。即使你只是一个人的团队，你的项目心态也可能是非常微妙的。尽管有最好的计划和最好的人员，一个项目仍然可能在其生命周期内经历毁灭和衰退。但是还有其他项目，尽管面临巨大困难和不断的挫折，成功地与本质上趋向于混乱的自然斗争，并且管理做得很好。

...

...

破窗效应

一个未被修复的破窗，无论它保持多长时间，都会在建筑物居民中灌输一种被遗弃的感觉——一种权力机构不关心建筑物的感觉。于是另一个窗户被打破了。人们开始乱扔垃圾，涂鸦出现，严重的结构损坏开始出现。在相对较短的时间内，建筑物变得损坏到业主不愿意修理它的程度，而被遗弃的感觉成为现实。

“破窗效应理论”启发了纽约和其他大城市的警察部门，采取行动打击小事情，以防止大事情发生。它奏效了：解决破窗、涂鸦和其他小违规行为降低了重罪水平。

提示4

不要容忍破窗

不要让“破窗”（糟糕的设计、错误的决策或糟糕的代码）未被修复。一旦发现问题，立即解决它。如果没有足够时间正确修复它，那么就把它封起来。也许您可以注释掉有问题的代码，或显示“未实现”消息，或替换虚拟数据。采取一些行动以防止进一步损坏并表明您掌握局势。

文本来自：http://pragprog.com/the-pragmatic-programmer/extracts/software-entropy

- Ash

2

我非常确定这与所提出的问题只有些许关联。代码熵仅比将“熵”用作隐喻略微严谨一些。 - Charlie Martin

@Charlie，不同意，这与问题有绝对的关联。"我发现在计算机科学中使用"熵"这个术语有些模糊。"在计算机科学中，熵有专业定义和更一般的定义，这个答案提供了更一般的定义。因此，fluffels有疑问/困惑。 - Ash

开始阅读时，我不知道自己最终会点赞。这一点在涉及新贡献者的项目中尤其明显。通常，缺乏经验的贡献者会遵循之前的设计，导致糟糕的设计被重复。 - akostadinov

12

我经常遇到熵的概念，它是指香农熵。

根据http://en.wikipedia.org/wiki/Information_entropy：

在信息论中，熵是与随机变量相关的不确定性度量。在此上下文中，这个术语通常指香农熵，它以期望值的方式量化消息中所包含的信息，通常以比特等单位表示。同样，香农熵是衡量当我们不知道随机变量的值时平均缺少的信息内容。

- Adrian Grigore

10

_{(来源：mit.edu)}

来自墨西哥大学

信息论熵的概念是物理概念的一种推广。描述熵的方法有很多种。它是随机变量随机程度的度量，也是随机变量或随机过程所包含的信息量的度量。此外，它是消息压缩量的下界。最后，它是需要询问关于随机实体的是/否问题的平均数量，以确定其值。

在概率计算的示例应用中，熵的方程式为：

它是一个随机变量所有值的概率乘以该概率（即p(x)logp(x)）的对数之和。该方程式可以从信息的属性的第一原理推导出来。

- Ric Tokyo

你应该明确指出你的第二段是引用。 - fluffels

1

吹毛求疵。在最终的引用中，它不应该说“乘以该概率的对数（以2为底）的次数（即-p(x)log(p(x))）”换句话说，每个值的信息，平均分布在这些值上。 - Mike Dunlavey

9

这里是关于信息论中的熵的一个很好的替代解释。

熵是预测中涉及的不确定性的度量。我们也可以将熵描述为，如果我们在做出初始预测后得到一个结果会有多么惊讶。

假设我们有一枚弯曲的硬币，99%的时间会得到正面，1%的时间会得到反面。由于只有1%的机会得到反面，我们实际上得到反面时会非常惊讶。另一方面，如果我们得到正面，这并不令人惊讶，因为我们已经有了99%的获得正面的机会。

假设我们有一个名为Surprise(x)的函数，它会给我们每个结果的惊喜程度;那么我们可以对概率分布的惊喜程度进行平均。这个平均惊喜程度也可以用作我们不确定性的度量。这种不确定性被称为熵。

我制作了这个可视化图表，描述了动物图像分类器模型（机器学习）中熵和预测类别的置信度之间的关系。在这里熵被用作衡量分类器模型对其预测的置信度的指标。

这些图表展示了两个分类器模型预测的熵值的比较。右侧的图表预测马的图像，并且置信度相对较高（熵较低），而左侧的分类器无法真正区分（熵较高）它是一匹马、一头牛还是长颈鹿。

- Zahra

6

从压缩和信息理论的角度来看，源的熵是源中符号可以传递的平均信息量（以位为单位）。简单地说，一个符号出现的可能性越小，其出现就越令人惊讶。

如果您的源有两个符号，比如 A 和 B，并且它们的可能性相等，则每个符号传递相同数量的信息（一个比特）。一个有四个等可能符号的源每个符号传递两个比特。

对于一个更有趣的例子，如果您的源有三个符号 A、B 和 C，其中前两个符号的可能性是第三个符号的两倍，则第三个符号更令人惊讶但也更不可能出现。这个源的净熵为1.52，如下所示计算。

您可以将熵计算为“平均惊喜”，其中每个符号的“惊喜”是其概率乘以概率的负二进制对数：

                            binary
symbol  weight  probability   log    surprise
  A        2        0.4      -1.32    0.53
  B        2        0.4      -1.32    0.53
  C        1        0.2      -2.32    0.46
total      5        1.0               1.52

二进制日志的负数被使用（当然）是因为值在0和1之间（不包括1）的日志是负数。

- joel.neely

为什么需要将值取绝对值？ - NelsonGon

4

超级简单的定义

熵这个词可以用一句话来定义：

"描述一个系统所需要的信息量。"

例如，想象一下宇宙的扩张：从开始时，所有物质都集中在一个小点之内，因此我们可以用“所有物质都在一个点之内”来描述该系统。而今天，为了描述整个宇宙系统，需要更多的信息，例如行星的位置、它们的运动以及上面的内容等等。根据信息理论，这个定义也适用：例如，如果向密码（即该系统）添加更多字母，则需要更多的信息来描述密码。然后，您可以使用不同的单位进行度量，比如位或字符，例如 "hello" = 5个字符的熵 = 40位熵（如果字符大小为8位）。

由此还可以得出，拥有更多信息意味着你可以用更多方法来安排这些信息。如果你有40位，则有2^40种不同的安排方式。如果我们谈论密码，那么信息（位数）的可能组合越多，其破解所需的时间就越长（通过暴力破解或字典攻击）。

- Axel K

2

简单来说，熵定义了随机性。它更像是衡量某物的不可预测性。更加技术化地说，“在计算机中，熵是操作系统或应用程序收集用于加密或其他需要随机数据的数据。这些随机数据通常从硬件源（如鼠标移动或专门提供的随机性生成器）中收集。” 如维基百科所定义。

现在，我们可以轻松地将熵的含义与文件联系起来，作为衡量文件中字节的无序程度的度量。有各种用于定义熵的单位，例如nat、shannon或hartley。最常用的单位是Shannon。根据Shannon的算法，文件熵的值范围必须在0到8之间。因此，当熵值为零时，可以说结果是确定的。相反，当熵值为8时，结果是最不可预测的。 Shannon提供了一个公式来衡量事件结果的随机性：

          Entropy = ∑ pi log(1/pi)

其中i是概率为pi的事件。

这个方程的结果总是在0到8之间。

欲了解更多信息，请访问链接：https://www.talentcookie.com/2016/02/file-entropy-in-malware-analysis/

- Tarang Arora

你假设8位字节而没有任何解释。0到8的任意范围毫无意义，除非你意识到它是每个位1。但我几乎认为这并没有澄清问题。 - tripleee

0

在计算机科学中，熵通常指一串比特的随机程度。

下面的问题是关于如何精确计算它：

如何计算比特串的近似熵？

- dreeves

0

熵对于病毒研究人员来说就像哈希码一样。如果你得到的熵较低，那么很可能是加密或压缩代码，可能会成为病毒。

标准二进制文件的熵比压缩或加密文件高。

- Can

有趣。我不知道那个。 - fluffels

我认为应该是相反的情况。加密压缩代码的熵比手写代码高。例如，一个全是1的信号没有任何信息，而加密版本往往会有相等概率的1或0，以隐藏信号。在压缩（无损）的情况下，信息将被保留（因为...你应该能够恢复原始信号），但由于熵是平均信息量，我们有更少的位数，熵会更高。希望我没有漏掉什么。 - mehmet.ali.anil

关于压缩，一个像FF00FF00FF00这样的代码可以被压缩为101010或2A，它具有更高的熵。 - mehmet.ali.anil

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Niyaz · Accepted Answer

熵可以有不同的含义：

计算机

在计算中，熵是操作系统或应用程序收集用于加密或其他需要随机数据的随机性。该随机性通常来自硬件源，包括现有的鼠标移动等，或专门提供的随机数生成器。

信息论

在信息论中，熵是与随机变量相关的不确定性度量。在这种情况下，该术语通常指香农熵，它以期望值的意义量化了消息中包含的信息量，通常以比特为单位。同样，香农熵是一个平均信息内容的度量，当我们不知道随机变量的值时，我们所缺失的信息内容。

数据压缩中的熵

数据压缩中的熵可能表示您输入到压缩算法的数据的随机性。熵越大，压缩比就越小。这意味着文本越随机，您就越无法将其压缩。

香农熵代表任何通信最佳可能无损压缩的绝对极限：将要编码的消息视为独立同分布随机变量序列，香农源编码定理显示，在极限情况下，用于将目标字母表中的消息编码成最短可能表示形式的平均长度是它们的熵除以目标字母表中符号数量的对数。