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

我最近在我的大学开始了一个关于数据压缩的课程。 然而,我发现“熵”这个术语在计算机科学中应用的含义很模糊。 据我所知,它大致转化为系统或结构的“随机性”。

计算机科学“熵”的正确定义是什么?

熵可能意味着不同的东西:

计算

在计算中,熵是操作系统或应用程序收集的用于密码学或其他需要随机数据的用途的随机性。 这种随机性通常是从硬件来源收集的,既可以是已有的,如鼠标移动,也可以是专门提供的随机生成器。

信息论

在信息论中,熵是与随机variables相关的不确定性的量度。 在这种情况下,术语本身通常是指香农熵,它以预期值的意义量化消息中包含的信息,通常以位为单位。 等效地,香农熵是衡量当人们不知道随机variables的值时人们所缺less的平均信息量

熵数据压缩

数据压缩中的熵可以表示input到压缩algorithm中的数据的随机性。 熵越大,压缩比越小。 这意味着文本越随机,你可以压缩它越小。

香农熵表示对任何通信的最佳可能无损压缩的绝对限制:将待编码的消息视为一系列独立同分布的随机variables,Shannon的源编码定理表明,在极限情况下,最短的平均长度对给定字母表中的消息进行编码的可能表示方式是将它们的熵除以目标字母表中的符号数量的对数。

我最喜欢的定义,更实际的重点,在安德鲁·亨特(Andrew Hunt)和大卫·托马斯(David Thomas)的优秀着作“实用程序员:从熟人到大师”

软件熵

尽pipe软件开发几乎可以免除所有的物理规律,但是熵对我们却很难。 熵是一个来自物理学的术语,指的是系统中“无序”的数量。 不幸的是,热力学定律保证了宇宙中的熵趋于最大。 当软件不断增加时,程序员称之为“软件腐烂”。

有很多因素可以导致软件腐败。 最重要的一个似乎是在项目工作中的心理学或文化。 即使你是一个团队,你的项目的心理可能是一个非常微妙的事情。 尽pipe最好的计划和最好的人,一个项目仍然可以在其一生中经历毁灭和衰败。 然而,还有其他一些项目,虽然面临巨大的困难和不断的挫折,却成功地对抗了自然界的混乱倾向,并且出现得相当不错。

一个破窗户。

一扇破窗,任何一段时间都没有修好,给build筑的居民灌输了一种放弃的感觉 – 这种感觉是,那些不关心build筑物的力量。 所以另一个窗口被打破了。 人们开始乱丢垃圾 出现涂鸦。 严重的结构破坏开始。 在相对较短的时间内,build筑物被破坏的可能性超出了所有者的意愿,放弃的感觉成为现实。

“破窗理论”激发了纽约等大城市的警察部门打击小事,以排除大事。 它的工作原理:保持在破窗户,涂鸦和其他小的违规行为之上,降低了严重的犯罪水平。

提示4

不要与残破的Windows一起生活

不要留下“破窗户”(不好的devise,错误的决定,或糟糕的代码)不成功。 发现后立即修复每一个。 如果没有足够的时间来正确解决问题,那就把它安置好。 也许你可以注释掉有问题的代码,或者显示一个“未实现”的消息,或者替代伪数据。 采取一些行动,以防止进一步的损害,并表明你是在情况之上。

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

我总是在香农熵的意义上遇到熵。

来自http://en.wikipedia.org/wiki/Information_entropy

在信息论中,熵是与随机variables相关的不确定性的量度。 在这种情况下,术语本身通常是指香农熵,它以预期值的意义量化消息中包含的信息,通常以位为单位。 等价地,香农熵是当人们不知道随机variables的值时人们所缺less的平均信息量的度量。

alt text http://ocw.mit.edu/NR/rdonlyres/Electrical-Engineering-and-Computer-Science/6-050JSpring-2008/9CD33A23-A58F-4CCD-8C34-DF5A83D56435/0/chp_telegraph_1.jpg

来自墨西哥大学

熵的信息理论概念是物理概念的一种推广。 有很多方法来描述熵。 它是一个随机variables的随机性的度量。 它也是一个随机variables或随机过程所包含的信息量的度量。 这也是一个消息可以压缩的数量的下限。 最后,对于一个随机实体来说,需要询问是/否问题的平均数量来确定它的价值。

用于概率计算的样本应用中的熵的等式:

它是该值的概率rv的所有值乘以该概率的对数(即p(x)logp(x))的总和。 这个等式可以从信息属性的第一原理推导出来。

就压缩和信息理论而言,信源的熵是来自信源的符号可以传达的平均信息量(以比特为单位)。 非正式地说,符号越不可能,其外观带来的惊喜就越多。

如果你的信源有两个符号,比如AB ,它们的可能性是相同的,那么每个符号传达的信息量相同(一位)。 具有四个相同可能符号的源传送每个符号两位。

对于一个更有趣的例子,如果你的源代码有三个符号ABC ,前两个符号的可能性是第三个符号的两倍,那么第三个符号更令人惊讶,但也不太可能。 这个数据源的净熵值为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之间(独占)的值是负值。

超级简单的定义

熵这个词可以用一个句子来定义:

“描述系统所需的信息量”

想象一下宇宙膨胀的一个例子:从一开始,所有的事物都是在大爆炸之前的一个小点上收集的,所以我们可以用“一切物质在一个点之内”来描述这个系统。 虽然今天需要更多的信息来描述系统(即宇宙),但是需要描述所有的行星位置,它们的运动,它们是什么等等。就信息论而言,这个定义也是有效的:例如:您添加到密码(系统)的字母越多,描述密码所需的信息就越多。 然后你可以用不同的单位进行测量,例如比特或者字符,比如“hello”= 5个字符熵= 40比特的熵(如果charsize是8比特)。

从这也可以看出,你有更多的信息可以安排信息。如果你有40位,有2 ^ 40种不同的方式可以安排。 如果我们在这里说密码,那么信息(比特)的更多可能的安排就要花更长的时间(用暴力或字典攻击)。

这里是理论的一个很好的替代解释。

熵是进行预测所涉及不确定性的量度。

我们也可以把熵描述成在我们做出最初的预测之后得到一个结果是多么的惊讶

可以说,我们有一个弯曲的硬币,99%的时间给我们一个头,1%的时间给我们一个尾巴。 由于只有一个百分之一的机会得到一个尾巴,我们会很惊讶,如果我们真的得到一个尾巴。 另一方面,如果我们有一个头,我们已经有99%的机会得到一个头,这不会是太惊人。

让我们假设我们有一个叫Surprise(x)的函数,它会给我们每个结果带来惊喜的数量。 那么我们可以在概率分布上平均惊喜的数量。 这种平均数量的惊喜也可以用来衡量我们的不确定性。 这种不确定性被称为

熵就像病毒研究人员的散列码一样。 你得到的熵较小,这意味着它可能是encryption或压缩的代码,可能是病毒。

标准二进制的熵比压缩或encryption的要高。

熵在计算机科学中通常具有许多含义。 这取决于上下文。 在安全熵中意味着你放置了多less随机数,例如当你生成一个私钥时,许多应用程序要求你移动鼠标来产生熵。 这通过采用随机性的“人”元素来生成熵,并将其添加到生成密钥的哈希处理中。

现在还有一个熵的软件工程的定义。 这个定义代表了过时的代码,或许多开发者编写代码。 通常用于参考重构软件项目的时间。 “这个项目的代码有很多熵,因为许多维护它的人目前不在这个项目上”。

这是我记得的第三个例子。 在模拟退火(就计算机科学而言)的话题中,熵被描述为在评估algorithm期间发生了多less衰变。

我想尽量回答你的问题,除了你可以在字典中find的东西外,没有关于“熵”这个词的具体定义。 计算机科学如何应用这个术语取决于所使用的术语的内容以及它的应用。

用熵来做一件大事很容易。 在我看来,这是一个非常简单而有用的概念 。

基本上,它会量化平均来说,您将从事件中学习什么,如翻转硬币,执行分支指令或索引数组。

就像一个searchalgorithm中间的比较操作,取一个分支有一定的概率P,取另一个分支的1-P。

假设P是1/2,就像二进制search一样。 那么如果你采取这个分支,你知道1比你以前更多,因为日志(2/1),基地2,是1.另一方面,如果你拿另一个分支,你也学习1位。

为了获得平均数量的信息,你将学习,将你在第一个分支上学到的东西乘以该分支的概率,再加上你在第二个分支上学到的东西乘以该分支的概率。

1/2位1位,1/2位1位,1/2位加1/2位,或总共1位熵。 这就是你可以从这个决定中平均学到的东西。

另一方面,假设您正在1024个条目的表中进行线性search。

在第一个==testing中,YES的概率是1/1024,所以在这个决定中的YES的熵是

 1/1024 times log(1024/1) 

或者1/1024 * 10 =大约1/100比特。

所以如果答案是肯定的,你可以学习10位数,但是这个数字大约是一千分之一。

另一方面,NO更可能。 它的熵是

 1023/1024 * log(1024/1023) 

或大致1倍大致为零=大约为零。

把这两者加在一起,平均来说,你会在这个决定上学到大约1/100的一点点。

这就是线性search速度缓慢的原因。 在每个决定中熵(你可以期望学到多less)太小,因为你将不得不学习10位才能find表中的条目。

计算机科学中的熵通常是指一串比特是多么随机的。 下面的问题是关于如何精确的:

如何计算位串的近似熵?

简单来说,熵定义了随机性。 更像是不可预测的事情。 用更多的技术术语来说,“在计算中,熵是操作系统或应用程序收集的用于密码学或其他需要随机数据的用途的随机性。 这种随机性通常是从硬件来源收集的,既可以是已有的,如鼠标移动,也可以是专门提供的随机生成器。

现在,人们可以很容易地得出关于文件的熵的含义,作为文件中字节有多less无序的度量。 有不同的单位用于定义像自然,香农或哈特利熵。 那么,最常用的单位是香农。 按照Shannonalgorithm,文件熵必须进入的值的范围是0到8.所以,当熵值为零时,可以说结果是确定的。 相反,当熵值是8时,结果是最不可预测的。 香农给出的衡量事件结果随机性的公式是:

  Entropy = ∑ pi log(1/pi) 

其中是概率为pi的事件。

这个方程总是会在0到8之间。

欲了解更多信息,请通过链接: https : //www.talentcookie.com/2016/02/file-entropy-in-malware-analysis/

简单地说,如果您知道语言符号的概率,可以计算语言中符号的平均信息量。

要么

语言的熵是语言中平均符号的信息内容的量度

考虑一个公平的硬币;

有两个符号,每个都有概率1/2,因此熵计算为

h = – (1/2 * log1 / 2 + 1/2 * log1 / 2)= 1

熵是指软件偶尔根据客户需求重新定型的程度,因此重塑它以满足客户需求的成本变得最大。

我听说有人滥用熵关于熵的热力学定义。

例如熵在这个系统中肯定会增加。

当他们的意思是这个代码越来越差!