哈夫曼编码码长怎么算？ 哈夫曼编码题.等码长到底是什么东西?怎么求?
\u54c8\u592b\u66fc\u7f16\u7801\u7801\u957f\u600e\u4e48\u7b97\u970d\u592b\u66fc\u7f16\u7801\u662f\u53d8\u957f\u7f16\u7801\uff0c\u601d\u8def\uff1a\u5bf9\u6982\u7387\u5927\u7684\u7f16\u7684\u7801\u5b57\u77ed\uff0c\u6982\u7387\u5c0f\u7684\u7f16\u7684\u7801\u5b57\u957f\uff0c\u8fd9\u6837\u4e00\u6765\u6240\u7f16\u7684\u603b\u7801\u957f\u5c31\u5c0f\uff0c\u8fd9\u6837\u7f16\u7801\u6548\u7387\u5c31\u9ad8\u3002
\u4e0a\u9762\u90a3\u6837\u6c42\u662f\u4e0d\u5bf9\u7684\uff0c\u9664\u975e\u4f60\u8fd96\u4e2a\u7801\u5b57\u662f\u7b49\u6982\u7387\u7684\uff0c\u5404\u53601/6\u3002\u5e94\u8be5\u7528\u5bf9\u5e94\u7684\u6982\u7387*\u5176\u5bf9\u5e94\u5f97\u7801\u957f\uff0c\u518d\u6c42\u548c\u3002
\u6269\u5c55\u8d44\u6599\uff1a\u5728\u8ba1\u7b97\u673a\u6570\u636e\u5904\u7406\u4e2d\uff0c\u970d\u592b\u66fc\u7f16\u7801\u4f7f\u7528\u53d8\u957f\u7f16\u7801\u8868\u5bf9\u6e90\u7b26\u53f7\uff08\u5982\u6587\u4ef6\u4e2d\u7684\u4e00\u4e2a\u5b57\u6bcd\uff09\u8fdb\u884c\u7f16\u7801\uff0c\u5176\u4e2d\u53d8\u957f\u7f16\u7801\u8868\u662f\u901a\u8fc7\u4e00\u79cd\u8bc4\u4f30\u6765\u6e90\u7b26\u53f7\u51fa\u73b0\u673a\u7387\u7684\u65b9\u6cd5\u5f97\u5230\u7684\uff0c\u51fa\u73b0\u673a\u7387\u9ad8\u7684\u5b57\u6bcd\u4f7f\u7528\u8f83\u77ed\u7684\u7f16\u7801\uff0c\u53cd\u4e4b\u51fa\u73b0\u673a\u7387\u4f4e\u7684\u5219\u4f7f\u7528\u8f83\u957f\u7684\u7f16\u7801\u3002
\u8fd9\u4fbf\u4f7f\u7f16\u7801\u4e4b\u540e\u7684\u5b57\u7b26\u4e32\u7684\u5e73\u5747\u957f\u5ea6\u3001\u671f\u671b\u503c\u964d\u4f4e\uff0c\u4ece\u800c\u8fbe\u5230\u65e0\u635f\u538b\u7f29\u6570\u636e\u7684\u76ee\u7684\u3002
\u4f8b\u5982\uff0c\u5728\u82f1\u6587\u4e2d\uff0ce\u7684\u51fa\u73b0\u673a\u7387\u6700\u9ad8\uff0c\u800cz\u7684\u51fa\u73b0\u6982\u7387\u5219\u6700\u4f4e\u3002\u5f53\u5229\u7528\u970d\u592b\u66fc\u7f16\u7801\u5bf9\u4e00\u7bc7\u82f1\u6587\u8fdb\u884c\u538b\u7f29\u65f6\uff0ce\u6781\u6709\u53ef\u80fd\u7528\u4e00\u4e2a\u6bd4\u7279\u6765\u8868\u793a\uff0c\u800cz\u5219\u53ef\u80fd\u82b1\u53bb25\u4e2a\u6bd4\u7279\uff08\u4e0d\u662f26\uff09\u3002\u7528\u666e\u901a\u7684\u8868\u793a\u65b9\u6cd5\u65f6\uff0c\u6bcf\u4e2a\u82f1\u6587\u5b57\u6bcd\u5747\u5360\u7528\u4e00\u4e2a\u5b57\u8282\uff0c\u53738\u4e2a\u6bd4\u7279\u3002
\u4e8c\u8005\u76f8\u6bd4\uff0ce\u4f7f\u7528\u4e86\u4e00\u822c\u7f16\u7801\u76841/8\u7684\u957f\u5ea6\uff0cz\u5219\u4f7f\u7528\u4e863\u500d\u591a\u3002\u5018\u82e5\u80fd\u5b9e\u73b0\u5bf9\u4e8e\u82f1\u6587\u4e2d\u5404\u4e2a\u5b57\u6bcd\u51fa\u73b0\u6982\u7387\u7684\u8f83\u51c6\u786e\u7684\u4f30\u7b97\uff0c\u5c31\u53ef\u4ee5\u5927\u5e45\u5ea6\u63d0\u9ad8\u65e0\u635f\u538b\u7f29\u7684\u6bd4\u4f8b\u3002
\u53c2\u8003\u8d44\u6599\u6765\u6e90\uff1a\u767e\u5ea6\u767e\u79d1-\u970d\u592b\u66fc\u7f16\u7801
假设用于通信的电文由字符集{a,b,c,d,e,f,g,h}中的字母构成，这8个字母在电文中出现的概率分别为{0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10}。
哈夫曼编码 根据上面可得编码表： a:1001 b:01 c:10111 d:1010 e:11 f:10110 g:00 h:1000
用三位二进行数进行的等长编码平均长度为3，而根据哈夫曼树编码的平均码长为：4*0.07+2*0.19+5*0.02+4*0.06+2*0.32+5*0.03+2*0.21+4*0.10=2.61 2.61/3=0.87=87%其平均码长是等长码的87%，所以平均压缩率为13%。
因为定长编码已经用相同的位数这个条件保证了任一个字符的编码都不会成为其它编码的前缀,所以这种情况只会出现在变长编码当中，要想避免这种情况，
就必须用一个条件来制约定长编码，这个条件就是要想成为压缩编码，变长编码就必须是前缀编码，所谓的前缀编码就是任何一个字符的编码都不能是另一个字符编码的前缀。
扩展资料：
实际应用中，除采用定时清洗以消除误差扩散和采用缓冲存储以解决速率匹配以外，主要问题是解决小符号集合的统计匹配，
例如黑（1）、白（0）传真信源的统计匹配，采用0和1不同长度游程组成扩大的符号集合信源。游程，指相同码元的长度（如二进码中连续的一串0或一串1的长度或个数）。按照CCITT标准，需要统计2×1728种游程（长度），
这样，实现时的存储量太大。事实上长游程的概率很小，故CCITT还规定：若l表示游程长度，则l=64q+r。其中q称主码，r为基码。编码时，不小于64的游程长度由主码和基码组成。而当l为64的整数倍时，只用主码的代码，已不存在基码的代码。
参考资料来源：百度百科-哈夫曼编码
介绍一个不用构造哈夫曼树的方法来计算哈夫曼编码的长度的算法，本算法的时间复杂度为O(nlogn)，空间复杂度为O(N)。下面是具体代码。
假设用于通信的电文由字符集{a,b,c,d,e,f,g,h}中的字母构成，这8个字母在电文中出现的概率分别为{0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10}.
哈夫曼编码 根据上面可得编码表： a:1001 b:01 c:10111 d:1010 e:11 f:10110 g:00 h:1000
用三位二进行数进行的等长编码平均长度为3，而根据哈夫曼树编码的平均码长为： 4*0.07+2*0.19+5*0.02+4*0.06+2*0.32+5*0.03+2*0.21+4*0.10=2.61 2.61/3=0.87=87%其平均码长是等长码的87%，所以平均压缩率为13%。
通过互联网来计算最好了，通过公爱计算比较多
绛旓細鍝堝か鏇肩紪鐮 鏍规嵁涓婇潰鍙緱缂栫爜琛細 a:1001 b:01 c:10111 d:1010 e:11 f:10110 g:00 h:1000 鐢ㄤ笁浣嶄簩杩涜鏁拌繘琛岀殑绛夐暱缂栫爜骞冲潎闀垮害涓3锛岃屾牴鎹搱澶浖鏍戠紪鐮佺殑骞冲潎鐮侀暱涓猴細 4*0.07+2*0.19+5*0.02+4*0.06+2*0.32+5*0.03+2*0.21+4*0.10=2.61 2.61/3=0.87...
绛旓細鍝堝か鏇肩紪鐮 鏍规嵁涓婇潰鍙緱缂栫爜琛細 a:1001 b:01 c:10111 d:1010 e:11 f:10110 g:00 h:1000 鐢ㄤ笁浣嶄簩杩涜鏁拌繘琛岀殑绛夐暱缂栫爜骞冲潎闀垮害涓3锛岃屾牴鎹搱澶浖鏍戠紪鐮佺殑骞冲潎鐮侀暱涓猴細4*0.07+2*0.19+5*0.02+4*0.06+2*0.32+5*0.03+2*0.21+4*0.10=2.61 2.61/3=0.87=...
绛旓細璁炬煇淇℃簮浜х敓鏈変簲绉嶇鍙穟1銆乽2銆乽3銆乽4鍜寀5锛屽搴旀鐜嘝1=0.4锛P2=0.1锛孭3=P4=0.2锛孭5=0.1銆傞湇澶浖缂栫爜鏄彉闀跨紪鐮侊紝鎬濊矾锛氬姒傜巼澶х殑缂栫殑鐮佸瓧鐭紝姒傜巼灏忕殑缂栫殑鐮佸瓧闀匡紝杩欐牱涓鏉ユ墍缂栫殑鎬荤爜闀垮氨灏忥紝杩欐牱缂栫爜鏁堢巼灏遍珮銆備笂闈㈤偅鏍锋眰鏄笉瀵圭殑锛岄櫎闈炰綘杩6涓爜瀛楁槸绛夋鐜囩殑锛屽悇鍗1/6銆傚簲璇ョ敤...
绛旓細1锛氱爜闀挎槸鍚︽槸骞冲潎鐮侀暱锛熷鏋滄槸锛鐮侀暱=锛堟墍鏈夌绫诲瓧绗︾疮鍔狅紙瀛楃鍑虹幇鐨勬鏁*璇ュ瓧绗﹀搱澶浖缂栫爜鏄殑闀垮害锛夛級/鎵鏈夊瓧绗︾殑涓暟 渚嬶細瀛楃涓瞐abbb a缂栫爜涓10011 ---5浣 b缂栫爜涓010011 ---6浣 鐮侀暱=锛2*5+3*6锛/5 (鍒嗘瘝5浠ｈ〃aabbb鐨勯暱搴︿负5)2锛氫俊鎭喌锛氫俊鎭喌Eta=绱姞锛圥i*log2锛...
绛旓細鍥炵瓟锛氱敱琛ㄥ彲鐭,涓夌缂栫爜鐨勫钩鍧鐮侀暱涓:(鍏紡:L=鈭慞i*Li 鍝堝紬鏇肩紪鐮:2.42浣 3/3/3缂栫爜:2.52浣 2/7缂栫爜:2.70浣
绛旓細鍝堝か鏇肩紪鐮杩涜鍘嬬缉鐨勫帇缂╃巼鏄牴鎹钩鍧鐮侀暱鏉璁＄畻鐨锛屽帇缂╃巼姣旇緝浣庛備緥濡傦細鐢ㄤ笁浣嶄簩杩涜鏁拌繘琛岀殑绛夐暱缂杁ao鐮佸钩鍧囬暱搴︿负3锛岃屾牴鎹搱澶浖鏍戠紪鐮佺殑骞冲潎鐮侀暱涓猴細4*0.07+2*0.19+5*0.02+4*0.06+2*0.32+5*0.03+2*0.21+4*0.10=2.61 2.61/3=0.87=87 鍏跺钩鍧囩爜闀挎槸绛夐暱鐮佺殑87%锛屾墍浠...
绛旓細鍝堝か鏇肩紪鐮锛屽乏瀛愭爲榛樿涓0锛屽彸瀛愭爲榛樿涓1锛屽緱鍒扮殑缂栫爜濡備笅锛欰锛100 B锛01 C锛1011 D锛11 E锛1010 F锛00 缂栫爜鐨鐮侀暱鏄細8*3 + 12 * 2 + 5*4 + 20 * 2 + 4*4 + 11 * 2 = 146 棰戠巼鏄疻=锛屽彲浠ユ牴鎹繖涓畻鍑烘瘡涓鍙风殑浣跨敤姒傜巼銆Huffman缂栫爜鐨勫熀鏈濇兂灏辨槸锛氬浜庝娇鐢ㄩ鐜囨瘮杈冮珮鐨...
绛旓細鍝堝か鏇肩紪鐮锛屽乏瀛愭爲榛樿涓0锛屽彸瀛愭爲榛樿涓1锛屽緱鍒扮殑缂栫爜濡備笅锛欰锛100 B锛01 C锛1011 D锛11 E锛1010 F锛00 缂栫爜鐨鐮侀暱鏄細8*3 + 12 * 2 + 5*4 + 20 * 2 + 4*4 + 11 * 2 = 146 棰戠巼鏄疻=锛屽彲浠ユ牴鎹繖涓畻鍑烘瘡涓鍙风殑浣跨敤姒傜巼銆Huffman缂栫爜鐨勫熀鏈濇兂灏辨槸锛氬浜庝娇鐢ㄩ鐜囨瘮杈冮珮鐨...
绛旓細鍝堝か鏇肩紪鐮鐨勭畻娉曞氨鏄妸涓や釜鏈灏忕殑姒傜巼鐩稿姞銆傚搱澶浖缂栫爜锛屽張绉伴湇澶浖缂栫爜锛屾槸涓绉嶇紪鐮佹柟寮忥紝鍝堝か鏇肩紪鐮佹槸鍙彉瀛楅暱缂栫爜鐨勪竴绉嶃侶uffman浜1952骞存彁鍑轰竴绉嶇紪鐮佹柟娉曪紝璇ユ柟娉曞畬鍏ㄤ緷鎹瓧绗﹀嚭鐜版鐜囨潵鏋勯犲紓瀛楀ご鐨勫钩鍧囬暱搴︽渶鐭殑鐮佸瓧锛屾湁鏃剁О涔嬩负鏈浣崇紪鐮侊紝涓鑸氨鍙仛Huffman缂栫爜銆傜畻娉曪細鍏堟寜鍑虹幇鐨勬鐜囧ぇ灏忔帓闃燂紝...
