2

私は下に書かれている課題を持っています：

完全圧縮を使用した場合、イギリス英語の 1 文字を格納するのに必要な平均ビット数は?

実験のエントロピーは、その結果を格納するために必要な最小ビット数として解釈できるためです。すべての文字のエントロピーを計算し、それらをすべて加算してすべての文字のエントロピーを見つけるプログラムを作成してみました。

これにより4.17ビットが得られますが、このリンクによると

完全な圧縮アルゴリズムがあれば、1 文字あたり 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

「完全な圧縮」が適用される場合、ビット数を計算することはおそらく不可能であるため、完全な圧縮などはありません。コルモゴロフの複雑さを参照してください。

数行のコードで、コンピューター プログラムによる英語テキストの圧縮率の限界と思われる値 (1 文字あたり約 1 ビット) に近づくコンプレッサーを実装することはできません。人間はもう少し上手にできるかもしれません。

于 2013-06-21T15:14:15.970 に答える
1

リンク先のページは、次のページにリンクしています。

シャノン ゲーム シミュレーションによる英語の推定エントロピーの精緻化

注意深く読むと、そこで計算されるエントロピーは、各文字の出現確率を使用して単純に計算されるのではなく、次のように計算されます。

被験者は前の 100 文字のテキストを見せられ、成功するまで次の文字を推測するよう求められました

使い方が違うだけで間違ってはいないと思いますが、ナイーブな発生確率データだけではそこまで圧縮できませんが、文脈を考えれば冗長な情報の方がはるかに多いのです。たとえば、eの確率は 0.127 ですが、 の場合th_、eおそらく 0.3 に近いものになります。

于 2013-06-21T14:57:34.263 に答える