TA貢獻1802條經驗 獲得超4個贊
我也知道了,根據熵來算的.256個字符出現的頻數都不一樣的情況下,霍夫曼編碼為最佳且能得到最長編碼位數.也就是說頻數為1-255,總和就是(1+255)*256/2=32768.其中頻數為1的符號需要的編碼位數最多,熵為-lg(1/32768)=15,因為實際位數會有(+-)1的出入,所以最多為15+1=16位
TA貢獻1824條經驗 獲得超6個贊
以下是沒有100%把握的分析。首先基于以下兩個前提進行討論：零頻度的字符不存在編碼，不出現在Huffman樹中，實際使用的頻度最低為1。Huffman樹生成算法在遇到森林中多個樹的權重相同時，合并深度最低的兩個樹，保證最終生成的Huffman樹總高度最小。從Huffman樹的生成反推。顯然合并次數是固定的255次。則如果想制造較長的Huffman樹，目標就是很明顯的：盡可能讓每次合并時，森林中最深樹的深度仍能+1。觀感上是盡量每次都讓單節點并入最長的樹。從[1,1,1]開始，這三個節點肯定能形成樹(((1)2(1))3(1))。則如果想掛入一個葉節點，和根節點3合并形成新的根，這個葉節點的值必須比已存在樹中最大的枝葉節點還要大。在這里就是大于1,2,1,1取3，形成以下的樹：1-2-3-6|||11[3]不能小于枝葉節點是當然的。等于也不行，因為如果相等，新加入的節點就會由于深度為0的原因，比已存在的節點在合并中占有優勢，從而破壞預計的合并過程。例如在上邊的例子中如果敢取2就會……5/|1-23//|11[2]所以按照這個規律生成：a=[1,2,3,6];b=[1,1,3];whileb[-1]<256:b.append(max(a[:-1]+b)+1)a.append(a[-1]+b[-1])print(a)#[1,2,3,6,10,17,28,46,75,122,198,321,520,842]print(b)#[1,1,3,4,7,11,18,29,47,76,123,199,322]這表示了這樣一棵樹，高度為12，使用了13個葉子節點：1-2-3-6-10-17-28-46-75-122-198-321-520||||||||||||113471118294776123199在葉子權重255的限制下，不能繼續生成下去了。此時還剩下243個字符沒有使用過，而這243個字符的權重都不能低于199（不破壞已有樹的存在性）。則這243個字符應該會生成一個深度為8的完全二叉樹（不是也差不多），然后這個長鏈掛在其中的某個節點上，很有可能掛在倒數第二層（而不是最底層）。沒有進一步更深入的研究。定性的來看，已經可以估計最后的這個值應該在12+8-1=19左右。
舉報