2

我有一个作业写在：

如果使用完美压缩，存储一个英式英语字母所需的平均位数是多少？

由于实验的熵可以解释为存储其结果所需的最小位数。我尝试制作一个程序来计算所有字母的熵，然后将它们加在一起以找到所有字母的熵。

这给了我 4.17 位，但根据这个链接

使用完美的压缩算法，我们应该每个字符只需要 2 位！

那么我该如何实现这个完美的压缩算法呢？

import math
letters=['A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z']
sum =0

def find_perc(s):

perc=[0.082,0.015,0.028,0.043,0.127,0.022,0.02,0.061,0.07,0.002,0.008,0.04,0.024,0.067,0.075,0.019,0.001,0.060,0.063,0.091,0.028,0.01,0.023,0.001,0.02,0.001]

letter=['A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z']
pos = 0
temp = s.upper()
if temp in letter:
    for x in xrange(1,len(letter)):
        if temp==letter[x]:
            pos = x
return perc[pos]

def calc_ent(s):
P=find_perc(s)
sum=0
    #Calculates the Entropy of the current letter
temp = P *(math.log(1/P)/math.log(2)) 

    #Does the same thing just for binary entropy (i think)
#temp = (-P*(math.log(P)/math.log(2)))-((1-P)*(math.log(1-P)/math.log(2)))
sum=temp
return sum


for x in xrange(0,25):
    sum=sum+calc_ent(letters[x])

print "The min bit is : %f"%sum
4

2 回答 2

2

没有完美压缩这样的东西，因为如果应用“完美压缩”，就不可能计算比特数。请参阅Kolmogorov 复杂性。

您将无法在几行代码中实现压缩器，该压缩器似乎接近计算机程序对英文文本的压缩限制，每个字符大约一位。人类或许能做得更好一点。

于 2013-06-21T15:14:15.970 回答
1

您链接到的页面再次链接到此页面：

用香农博弈模拟细化英语的估计熵

如果您仔细阅读，那里计算的熵不是使用每个字母的出现概率简单计算的 - 相反，它是由

向受试者显示前 100 个字符的文本，并要求其猜测下一个字符，直到成功

所以我认为你没有错，只是你使用的方法不同 - 只使用幼稚的发生概率数据，你不能很好地压缩信息，但是如果你考虑到上下文，那么冗余信息​​就更多了。例如，e概率为 0.127，但对于th_，e可能更接近于 0.3。

于 2013-06-21T14:57:34.263 回答