信息來源與記憶的熵率

Question

我有一些英文書寫文本並計算它的熵。然而我意識到基於LZ方法的壓縮算法在熵給定的限制下壓縮得非常少。

這是由於模擬英文文本的信息來源具有記憶。 所以壓縮的邊界由熵率給出，而不是由該熵的熵給出。

我看到了帶有記憶的信息源熵率的定義，但想知道如何用英文寫的文本的算法或僞代碼計算熵率。

任何想法？

感謝您的幫助。

Answer 1

一般來說，用記憶來估計一個信息源的熵率是一個難題，而且當有很多長距離依賴性時（就像自然語言一樣），這是特別困難的。本質上你需要做的是根據樣本構建語言的語法，然後計算語法的熵率。您在提取語法時所做的特定假設將會對最終的熵率產生很大的影響，所以您能夠做的最好的做法是估計實際熵率的一些相當薄弱的界限資源。

一個常見的做法是簡單地通過使用像gzip這樣的標準壓縮程序壓縮大樣本來估計熵率，儘管Cosma Shalizi指出這是一個可怕的想法。如果您打算使用通用數據壓縮算法，LZ76是更好的選擇; FermínMoscoso del Prado有一個paper出來尋找一些替代品。

儘管壓縮算法確實給了你一種語法，但它甚至會更好地使用能準確捕獲語言中長距離依賴關係的語法。不幸的是，從原始文本樣本中學習現實的自然語言語法是一個開放的研究問題。但是，在學習有限狀態逼近自然語言方面有一些有前途的工作可用於產生良好的熵率估計。檢查出CSSR是一種解決這些問題的方法。