一千萬個為什麽

搜索
當前位置: 首頁 > 矛盾編碼

矛盾編碼

考慮以下情況,我想向接收器發送兩個位串A或B中的一個。很明顯,我可以通過發送最短的信息來做到這一點,但有更好的方法嗎?似乎任何一個應該到達的要求應該允許我們節省比特。

給出一個特定的應用程序:說接收器和我有一個DFA,我想用自動機描述的語言發送一些單詞。我可以通過將自動機上的路徑編碼為n元字符串來實現此目的。但是如果在自動機上有幾條路徑,我不關心接收器解碼的內容,只要它解碼為正確的字。

對這個問題有研究嗎?是否有我不知道的google-capable短語?

此外,如果我們使用概率DFA,它會定義其語言中單詞的概率分布。通過Kraft不等式,存在對該概率的編碼,其中字W的代碼長度等於P(W)的對數。然而,如果我們在自動機上使用特定路徑A來編碼W,則該路徑可能僅貢獻P(W)的概率質量的一部分。假設有兩條路徑A和B產生W,因此P(A)+ P(B)= P(W)。是否有一個方案允許我們發送一個長度為log(P(W))的消息,該消息被解碼為A或B?

最佳答案

我可以在這裏回答我自己的問題。超過$ S = \ {A,B,\ ldots \} $的原始代碼(通過卡夫不等式)對應於$ S $的概率分布。我可以通過我厭惡的子集來劃分S,所以在$ S'$中,有一個元素$ a = \ {A,B \} $來表示我不關心$ A $和$ A $之間的區別$ B $。

這給了我一個簡單的概率分布在$ S'$:$ p(a)= p(A)+ p(B)$。

通過Kraft不等式,還有一個與此分布相對應的編碼,因此我可以使用像這樣的算法。算術編碼實現長度$的順序 - \ log p(a)= - \ log p(A)+ p(B)$。

轉載註明原文: 矛盾編碼