霍夫曼編碼中一個字符的單位代碼的條件是什麼？

這是我在學校設置中遇到的一個問題，但它讓我煩惱，所以我決定在這裏問一下。霍夫曼編碼中一個字符的單位代碼的條件是什麼？

在霍夫曼壓縮中，固定長度序列（字符）是用可變長度序列編碼的。代碼序列長度取決於源字符的頻率（或概率）。

我的問題是：什麼是最低的最高字符頻率，與哪個字符將被一個位編碼？

來源

2010-06-21 daphshez

事實證明，答案是0.4，即，如果最高頻率p是P> = 0.4，爲對應的字符的1位代碼被保證。換句話說，這是一個充分的條件。

p> = 1/3是必要條件也是如此。也就是說，可能存在這樣的示例，其中最短代碼是1位，但是不存在像這樣的情況，如果p < 1/3。

推理的方法是查看代碼樹的構造方式，特別是在最後3個存活子樹的頻率上。在約翰森，"On the redundancy of binary Huffman codes", 1980（不幸的是，這是一個付費鏈接）出現證明。

來源

2010-06-24 07:22:58 daphshez

除了平凡的二進制情況 - 如果只有2個符號，霍夫曼總是爲每個符號分配1位，不管頻率是多少。 – 2011-07-26 14:25:58

[此arxiv預印本]中有一個附錄證明作爲附錄（https://arxiv.org/pdf/cs/0508039.pdf）。不幸的是，我無法遵循推理......我不明白爲什麼標記爲「u」的節點在標爲「v1」和「v2」的節點之前合併。 – 2016-11-21 22:30:28

通常，輸入符號流的大約50％必須包含一個給定的符號，以便霍夫曼將其編碼爲單個位。原因在於，由於霍夫曼編碼的工作原理（一個符號的編碼不能作爲另一個編碼的前綴），通過用一位編碼符號，您要求的每個其他符號的第一位是相反的值（即如果一個符號編碼爲0，則其他所有內容必須以1加上至少一個位開始）。由於您要消除任何給定位長度的一半可能的編碼空間，因此您需要獲得對至少一半輸入符號進行編碼以實現均衡的方法。

請注意，特殊情況下符號空間只包含3個符號。在這種情況下，無論哪個符號具有最大頻率，都將用1位進行編碼（因爲其他兩個符號將是未選擇第一位值的第二位變體） - 如果2個或更多個具有相同的更大概率，任何一個都可以編碼。因此，在3符號的情況下，可能理論上將具有34％可能性的符號編碼爲單個位（例如，0），而其他兩個可能具有33％或更低的概率並且編碼爲10並且11。因此，如果你正在考慮全部的可能性，那麼從技術上講，任何1/3或以上的東西都可能被編碼爲一個位（在3符號的情況下）。

來源

2010-06-21 08:17:42 Amber

一個例外是3個相同概率的符號：它們可以編碼爲0,10,11 – Artelius 2010-06-21 08:23:46

是的，我已經將它添加爲一個註釋。 :)這是一個邊緣案例，但潛在的相關性。 – Amber 2010-06-21 08:24:38

還有其他的相關案例（1/3，1/6，1/6，1/6，1/6），但對於一個符號有1/3概率的情況並非如此。我很樂意看到一個答案，顯示了區別。 – Artelius 2010-06-21 08:41:09

霍夫曼編碼中一個字符的單位代碼的條件是什麼？

回答

相關問題