问题标签 [information-theory]

有没有标准的方法来做到这一点？

谷歌搜索—— “近似熵”位——发现了多篇学术论文，但我只想找到一段伪代码，为给定的任意长度的位串定义近似熵。

（如果说起来容易做起来难，并且取决于应用程序，我的应用程序涉及 16,320 位加密数据（密文）。但加密是一个谜题，并不是不可能破解的。我想我先检查一下熵，但不容易找到一个好的定义。所以这似乎是一个应该在 StackOverflow 上的问题！也欢迎从哪里开始解密 16k 随机看似位的想法......）

另请参阅此相关问题：
熵的计算机科学定义是什么？

从我的算法教科书：

一年一度的县赛马将带来三匹从未相互竞争过的纯种马。兴奋地，你研究了他们过去的 200 场比赛，并将这些总结为四个结果的概率分布：第一（“第一名”）、第二、第三和其他。

哪匹马最容易预测？解决这个问题的一种定量方法是查看可压缩性。将每匹马的历史记录为一串 200 个值（第一、第二、第三、其他）。然后可以使用霍夫曼算法计算对这些跟踪记录字符串进行编码所需的总比特数。这适用于 Aurora 290 位，Whirlwind 380 位，Phantasm 420 位（检查一下！）。Aurora 具有最短的编码，因此在强烈的意义上是最可预测的。

他们是如何获得 420 的 Phantasm 的？我不断收到 400 个字节，如下所示：

结合第一，其他 = 0.4，结合第二，第三 = 0.6。最终以 2 位编码每个位置。

我对霍夫曼编码算法有什么误解吗？

此处提供教科书：http ://www.cs.berkeley.edu/~vazirani/algorithms.html （第 156 页）。

有没有机会让信息增益的价值为负？

想象一下，在接下来的 10 年里，你拥有世界上所有的超级计算机。你的任务是尽可能无损地压缩 10 部完整的电影。另一个标准是普通计算机应该能够即时解压缩，并且不需要花费太多的 HD 来安装解压缩软件。

我的问题是，与当今最好的替代方案相比，您可以实现多少压缩？1%、5%、50%？更具体地说：给定一个固定的字典大小（如果它也被称为视频压缩），压缩是否存在理论上的限制？

是否有任何机器学习算法、预测模型可以帮助我压缩指数分布的数据？我已经使用 golomb 代码对文件进行了编码，这无疑节省了大量空间，但这还不够——我需要压缩。PAQ8L 压缩得不够。

如果需要，请索取文件。

指数分布——

{a,b,b,a,a,b,c,c,a,a,b,a,a,b,a,c,b,a,b,d}

假设 M 是一组对象 m，每个对象具有属性 X 和 Y。现在如果 X 和 Y 对于给定的 m 只能有一个值（即 X，Y 是随机变量，P(X=x_i|M=m_i)，P( Y=y_i|M=m_i))，可以计算X和Y的互信息。但是如果X可以同时有多个结果呢？即 m_3 X={x1,x2} - 通常 X 的结果是所有可能结果的子集。在这种情况下，是否可以测量互信息或其他某种依赖度量？

是否可以将 X 拆分为二进制随机变量 X_1、X_2 等，其中 X_1=1 iff X 包含 x1，否则 X_1=0，然后为所有组合 i,j 计算 I(X_i,Y_j) 并按顺序汇总信息得到 I(X,Y)？

谢谢。

例子：

我有一些英文书面文本并计算了它的熵。但是我意识到基于 LZ 方法的压缩算法在熵给出的限制下压缩得很多。

这是因为模拟英文文本的信息源具有记忆。因此，压缩的边界由熵率给出，而不是由该源的熵给出。

我看到了具有内存的源的熵率的定义，但想知道如何使用算法或用英文编写的文本的伪代码来计算熵率。

有任何想法吗？

感谢帮助。

Jeff Atwood 最近在推特上发布了一个指向 CodeReview 帖子的链接，他想知道社区是否可以改进他的“计算字符串的熵”代码片段。他解释说：“我们在 Stack Overflow 的几个地方计算字符串的熵，作为低质量的标志。”

他的方法的要点似乎是，如果您计算字符串中唯一字符的数量，则表示熵（代码取自PieterG 的答案）：

我不明白唯一字符数如何表示字符串的熵，以及字符串的熵如何表示低质量。我想知道在这方面有更多知识的人是否可以解释阿特伍德先生正在努力实现的目标。

谢谢！

我希望是个简单的问题。

如果我有一组这样的数据：

那么attribute-2相对于attribute-1的信息增益是多少呢？

我计算了整个数据集的熵：-(3/6)log2(3/6)-(3/6)log2(3/6)=1

那我就卡住了！我认为您也需要计算属性 1 和属性 2 的熵吗？那么在一次信息增益计算中使用这三个计算呢？

任何帮助都会很棒，

谢谢 ：）。

我正在寻找在一长串通话记录中对 user_ids 进行编码。这些记录中占用空间最多的部分是调用者和接收者的符号。我将创建一个映射，为最活跃的调用者分配较短的符号——这将有助于降低文件的整体大小（以及 I/O 时间）。

我事先知道每个符号将被使用多少次——换句话说，我知道相对概率分布。此外，生成的代码是否“无前缀”（例如霍夫曼代码）并不重要。那么最好的编码方案是什么，即能够提供最多压缩并且存在快速实现的方案？

答案不仅应指向压缩方案，还应指向该编码方案的实现。