标签: information-theory

是否有任何论文描述了从编译程序推断子程序的任何算法/技术？换句话说:是否有一种算法可以找到在程序中出现多次的代码块？这些块可以重新排序指令(当然没有程序行为改变),因此它更有可能找到匹配.

这个过程可以看作是子程序内联的反面,它由编译器完成,以避免调用,但增加了二进制大小.

在我看来,这是一个非常困难的理论问题.

我遇到了这个问题;

"无损压缩算法声称保证使一些文件更小,文件更大.
这是;

a)不可能

b)可能但可能运行不确定的时间,

c)压缩系数2或更低可能,

d)可能出现任何压缩因素？"

我倾向于(a),但无法对其原因给出可靠的解释.(我会列出朋友和我想出的想法作为可能的答案)

我道歉,因为我不知道这是否更像是一个属于mathoverflow的数学问题,或者它是否属于这里的计算机科学问题.

也就是说,我相信我理解数据,信息和知识之间的根本区别.我的理解是信息包含数据和意义.我不清楚的一件事是信息是否是数据.信息被认为是一种特殊的数据,还是完全不同的东西？

我接受了一些课程来实现我选择的压缩算法。它可以是任何语言，但是我最了解的语言是 Java，其次是 C。它将基于 -

1. 解压后的输出必须与原始输入匹配，所以我只能看损失较小的算法。

2. 运行时间必须与消息的长度成正比。

3. 内存要求必须与消息的长度无关。

我们的实施将进行如下测试 -

1. 标准文本文件

2. 字节值范围为 0-255 的二进制文件

3. 一个大约 10mb 的大文件，其中包含未指定的内容。

我最初的想法是使用动态算术编码，但我想知道是否有更适合上述约束的算法？其次，用 C 语言比用 Java 语言更好吗？我问这个问题是因为我认为 C 的内存占用较小，但我不确定是否确实如此。

我花了一些时间谷歌搜索这个问题，一些网站提到了 LZW 编码与动态霍夫曼编码相结合。这是一个明智的追求途径吗？我们的讲师确实警告我们，多年来尝试动态霍夫曼编码的提交内容中有 90% 没有得到正确实现。

也就是说，我并不害怕尝试一下，但在开始之前我会重视一些意见。

任何反馈将不胜感激。

我知道决策树试图在决策树上放置具有高熵的分类器.但是,信息如何发挥作用呢？

信息增益定义为:

InformationGain = EntropyBefore - EntropyAfter

决策树是否尝试在树的顶部放置信息增益较低的分类器？因此,熵总是最大化,信息增益总是最小化？

对不起,我有点困惑.谢谢!

离散变量的Tsallis 熵定义为：

H[p,q] = 1/(q-1) * (1 - sum(p^q))

连续变量的 Tsallis 熵定义为：

H[p,q] = 1/(q-1) * (1 - int((p(x)^q dx)

其中p(x)是数据的概率密度函数，并且int是积分。

我正在尝试在 R 中实现 Tsallis 熵。

假设我有以下数据（由 beta 函数生成，但考虑分布未知）

set.seed(567)
mystring <- round(rbeta(500, 2,4), 2)

离散变量的 Tsallis 熵为：

freqs <- table(mystring) / 500
q = 3
H1 <- 1/(q-1) * (1 - sum(freqs^q))
[1] 0.4998426

我现在想要计算连续变量的 Tsallis 熵：

PDF <- density(mystring)
library(sfsmisc)
xPDF <- PDF$x
yPDF <- PDF$y
H1 <- 1/(q-1) * (1 …

旧的英国信息学奥林匹克问题(3c)询问字母表中最小的明确编码方案(仅使用两个符号 - 因此是二进制).据我所知,答案是130 - 5位需要存储每个字母,如2 ^ 4 <26.字母表有26个字符,因此编码方案长5*26位.但是,标记方案表明可以使用124位.那么长的编码方案是什么？

给定 15 个随机十六进制数（60 位），其中每 20 位运行（5 个十六进制）中总是至少有 1 个重复。

压缩字节的最佳方法是什么？

这里有些例子：

01230 45647 789AA
D8D9F 8AAAF 21052
20D22 8CC56 AA53A
AECAB 3BB95 E1E6D
9993F C9F29 B3130

最初，我一直尝试仅在 20 位上使用霍夫曼编码，因为霍夫曼编码可以从 20 位降低到约 10 位，但存储表需要超过 9 位。

这是显示 20 位 -> 10 位的细分 01230

Character   Frequency   Assignment  Space Savings
0           2           0           2×4 - 2×1 = 6 bits
2           1           10          1×4 - 1×2 = 2 bits
1           1           110         1×4 - 1×3 = 1 bits
3           1           111         1×4 - 1×3 …

这是一个计算机科学/信息理论问题,而不是一个简单的编程问题,所以如果有人知道一个更好的网站发布这个,请告诉我.

假设我有一个N位数据,将在M个消息中冗余发送,其中至少M-1个消息将被成功接收.我对以每个消息更少的比特编码N比特数据的不同方式感兴趣.(这类似于RAID但是在更小的级别,其中N = 8或16或32)

示例:假设N = 16且M = 4.那么我可以使用以下算法:

1st and 3rd message: send "0" + bits 0-7
2nd and 4th message: send "1" + bits 8-15

如果我能保证4个消息中的3个消息将通过,则每个组中至少有一条消息将通过.因此,我可以用9位或更少的位来完成这项工作,可能有一种方法可以用更少的总位来做到这一点,但我不知道如何.

是否有一些简单的编码/解码算法来做这种事情？这个问题有名字吗？(如果我知道它叫什么,我可以谷歌吧!)

注意:在我的特定情况下,消息要么正确到达,要么根本没有到达(没有消息到达有错误).

(编辑:将第二部分移到另一个问题)

我有一个概率分布,定义了n可能状态的发生概率.

我想计算给定概率分布的香农熵值(以位为单位).

我可以wentropy(x,'shannon')用来获取值吗？如果可以,我可以在哪里定义系统可能的状态数？