Infomation Theory - The Implementation of Huffman Coder

1、INFOMATION THEORYThe Implementation of Huffman Coder2016-1-7莫幫杰2013301200227信息論與編碼Huffman編碼器的實(shí)現(xiàn)一、 實(shí)驗(yàn)?zāi)康?、理解和掌握Huffman編碼的基本原理和方法；2、給出信源符號(hào)的概率統(tǒng)計(jì)分布，并計(jì)算信源熵；3、給出兩種以上單信源符號(hào)Huffman碼表；4、計(jì)算每信源的平均字長(zhǎng)，并與信源熵比較；5、計(jì)算編碼效率，分析碼長(zhǎng)方差對(duì)實(shí)驗(yàn)系統(tǒng)的影響。二、 實(shí)驗(yàn)原理1、 二元霍夫曼編碼的基本原理（1）將q個(gè)信源符號(hào)按照概率分布P(si)的大小順序遞增（或遞減）排列：P1=P2=P3=Pq；（2）用碼符號(hào)0和1分別

2、給概率最小的兩個(gè)信源符號(hào)編碼，并將這兩個(gè)符號(hào)合并成一個(gè)新符號(hào)，新符號(hào)的概率即為這兩個(gè)符號(hào)的概率之和，從而得到只包含q-1個(gè)符號(hào)的新信源Si；（3）重復(fù)步驟（1）（2）,直至信源不能再縮減；（4）從編碼路徑向前返回，所得到的路徑序列即為對(duì)應(yīng)符號(hào)的碼字。由于碼符號(hào)分配的任意性和符號(hào)合并后概率與其他符號(hào)相同時(shí)排序方法的不同，同一信源的霍夫曼編碼往往并不唯一。但是，針對(duì)第二種情況，編碼時(shí)如盡量把新生成的碼符號(hào)概率排在最前面將有利于減小碼長(zhǎng)方差，編出來的碼也就跟接近于等長(zhǎng)碼，這在后面的實(shí)驗(yàn)結(jié)果當(dāng)中會(huì)有所體現(xiàn)。2、r元霍夫曼編碼的基本原理（1）將q個(gè)信源符號(hào)按照概率分布P(si)的大小順序遞增（或遞減）排

3、列：P1=P2=P3=2）是否滿足q=(r-1)*n+r，如果不滿足，則填充最少的0使?jié)M足。特殊的，在r=2，即二元編碼的條件下，q=(r-1)*n+r總是成立的。3. 平均碼長(zhǎng)：L=Psi*li （單位為：碼符號(hào)/信源符號(hào)）其中，Psi為信源S在q個(gè)信源符號(hào)中出現(xiàn)的概率，li為編碼后信源S的第i個(gè)碼字的碼長(zhǎng)。4. 信息熵：HS=-Psi*log Psi （單位為：比特/信源符號(hào)）其中，Psi為信源S在q個(gè)信源符號(hào)中出現(xiàn)的概率。5. 編碼效率：=H(S)/L其中，H(S)為信息熵，L為平均碼長(zhǎng)。三、 算法設(shè)計(jì) 四、 JAVA關(guān)鍵代碼/* * 迭代編碼，由下至上構(gòu)建碼樹 * param prob

4、abilities 信源的概率分布 * param codeTreeMap 碼樹圖 * return 碼樹 */private CodeTree code(double probabilities, CodeTreeMap codeTreeMap) /每一次迭代都生成新的碼樹CodeTree codeTree = new CodeTree();/符號(hào)挑選器SymbolPicker symbolPicker = new SymbolPicker(arbitrary ,symbolSet);/新信源符號(hào)的概率double probability = 0;for (int i = probabili

5、ties.length-1; i probabilities.length-base-1; i-) /累加生成新信源符號(hào)的概率probability += probabilitiesi;/下一個(gè)符號(hào)T symbol = symbolPicker.next();/從碼樹圖中取得游離的歷史碼樹，放入新的碼樹中構(gòu)建，同時(shí)將其移除（忘記）codeTree.put(symbol,codeTreeMap.remove(i);/迭代直到信源大小不能再縮減為止if (probabilities.length = base) return codeTree;/縮減信源probabilities = reduce

6、(probabilities);/找到新信源符號(hào)待插入位置int index = indexToInsert(probability, probabilities);/插入新信源符號(hào)insert(probabilities, probability, index);/調(diào)整碼樹圖adjustCodeTreeMap(codeTreeMap, index);/記住新生成的碼樹codeTreeMap.put(index, codeTree);/繼續(xù)下一輪編碼return code(probabilities, codeTreeMap);說明：以上只是代碼中比較核心的部分，完整的可運(yùn)行程序請(qǐng)查看附件中的

7、JAVA代碼包。五、 實(shí)驗(yàn)過程1、 二元huffman編碼驗(yàn)證性實(shí)驗(yàn)用Eclipse打開源碼，在測(cè)試類中將BASE設(shè)置為2，輸入信源分布p=0.4,0.2,0.2,0.1,0.1，構(gòu)造具有隨機(jī)編碼、提供優(yōu)化特性的huffman編碼器，設(shè)置循環(huán)5次編碼，如圖：配置好后點(diǎn)擊運(yùn)行JAVA程序，在控制臺(tái)輸出以下測(cè)試內(nèi)容： 可見有優(yōu)化的隨機(jī)huffman編碼的編碼結(jié)果可能不盡相同，但他們的平均碼長(zhǎng)、碼長(zhǎng)方差和編碼效率是一致的，所以可以把他們看作等價(jià)碼。下面再來看一下無優(yōu)化的隨機(jī)二元huffman編碼。將編碼器構(gòu)造函數(shù)的第三個(gè)參數(shù)改為false，其他不變，再次運(yùn)行編碼程序，在控制臺(tái)有新的輸出：從輸出結(jié)果可

8、以看到，無優(yōu)化的隨機(jī)huffman編碼的編碼結(jié)果也不盡相同，但他們的平均碼長(zhǎng)、碼長(zhǎng)方差和編碼效率也是一致的，所以也可以把他們看作等價(jià)碼。對(duì)比有優(yōu)化和無優(yōu)化兩種碼型可見，有優(yōu)化時(shí)編出來的huffman碼方差更小、更接近于等長(zhǎng)碼，原因是有優(yōu)化時(shí)程序會(huì)盡量將合并后的碼符號(hào)放在最前面，從而減少重復(fù)編碼的次數(shù)，使短碼得到充分利用。故實(shí)際應(yīng)用時(shí)應(yīng)采用有優(yōu)化的編碼方式。2、四元huffman編碼驗(yàn)證性實(shí)驗(yàn)在測(cè)試類中將BASE設(shè)置為4，輸入信源分布p=0.22,0.20,0.18,0.15,0.10,0.08,0.05,0.02，構(gòu)造具有隨機(jī)編碼、提供優(yōu)化特性的huffman編碼器，設(shè)置循環(huán)5次編碼，如圖：運(yùn)

9、行程序，在JAVA控制臺(tái)輸出：將huffman編碼器構(gòu)造函數(shù)的第三個(gè)參數(shù)改為false，重新運(yùn)行程序，輸出結(jié)果如下：3、 找一篇1000個(gè)單詞以上的英文文章，只考慮26個(gè)字母和空格(標(biāo)點(diǎn)符號(hào)當(dāng)空格處理)，進(jìn)行Huffman統(tǒng)計(jì)編解碼實(shí)驗(yàn)。以下為實(shí)驗(yàn)結(jié)果：original source:My father was a self-taught mandolin player. He was one of the best string instrument players in our town. He could not read music, but if he heard a tune a

10、few times, he could play it. When he was younger, he was a member of a small country music band. They would play at local dances and on a few occasions would play for the local radio station. He often told us how he had auditioned and earned a position in a band that featured Patsy Cline as their le

11、ad singer. He told the family that after he was hired he never went back. Dad was a very religious man. He stated that there was a lot of drinking and cursing the day of his audition and he did not want to be around that type of environment.Occasionally, Dad would get out his mandolin and play for t

12、he family. We three children: Trisha, Monte and I, George Jr., would often sing along. Songs such as the Tennessee Waltz, Harbor Lights and around Christmas time, the well-known rendition of Silver Bells. Silver Bells, Silver Bells, its Christmas time in the city would ring throughout the house. One

13、 of Dads favorite hymns was The Old Rugged Cross. We learned the words to the hymn when we were very young, and would sing it with Dad when he would play and sing. Another song that was often shared in our house was a song that accompanied the Walt Disney series: Davey Crockett. Dad only had to hear

14、 the song twice before he learned it well enough to play it. Davey, Davey Crockett, King of the Wild Frontier was a favorite song for the family. He knew we enjoyed the song and the program and would often get out the mandolin after the program was over. I could never get over how he could play the

15、songs so well after only hearing them a few times. I loved to sing, but I never learned how to play the mandolin. This is something I regret to this day.Dad loved to play the mandolin for his family he knew we enjoyed singing, and hearing him play. He was like that. If he could give pleasure to othe

16、rs, he would, especially his family. He was always there, sacrificing his time and efforts to see that his family had enough in their life. I had to mature into a man and have children of my own before I realized how much he had sacrificed.I joined the United States Air Force in January of 1962. Whe

17、never I would come home on leave, I would ask Dad to play the mandolin. Nobody played the mandolin like my father. He could touch your soul with the tones that came out of that old mandolin. He seemed to shine when he was playing. You could see his pride in his ability to play so well for his family

18、.When Dad was younger, he worked for his father on the farm. His father was a farmer and sharecropped a farm for the man who owned the property. In 1950, our family moved from the farm. Dad had gained employment at the local limestone quarry. When the quarry closed in August of 1957, he had to seek

19、other employment. He worked for Owens Yacht Company in Dundalk, Maryland and for Todd Steel in Point of Rocks, Maryland. While working at Todd Steel, he was involved in an accident. His job was to roll angle iron onto a conveyor so that the welders farther up the production line would have it to com

20、plete their job. On this particular day Dad got the third index finger of his left hand mashed between two pieces of steel. The doctor who operated on the finger could not save it, and Dad ended up having the tip of the finger amputated. He didnt lose enough of the finger where it would stop him pic

21、king up anything, but it did impact his ability to play the mandolin.After the accident, Dad was reluctant to play the mandolin. He felt that he could not play as well as he had before the accident. When I came home on leave and asked him to play he would make excuses for why he couldnt play. Eventu

22、ally, we would wear him down and he would say Okay, but remember, I cant hold down on the strings the way I used to or Since the accident to this finger I cant play as good. For the family it didnt make any difference that Dad couldnt play as well. We were just glad that he would play. When he playe

23、d the old mandolin it would carry us back to a cheerful, happier time in our lives. Davey, Davey Crockett, King of the Wild Frontier, would again be heard in the little town of Bakerton, West Virginia.In August of 1993 my father was diagnosed with inoperable lung cancer. He chose not to receive chem

24、otherapy treatments so that he could live out the rest of his life in dignity. About a week before his death, we asked Dad if he would play the mandolin for us. He made excuses but said okay. He knew it would probably be the last time he would play for us. He tuned up the old mandolin and played a f

25、ew notes. When I looked around, there was not a dry eye in the family. We saw before us a quiet humble man with an inner strength that comes from knowing God, and living with him in ones life. Dad would never play the mandolin for us again. We felt at the time that he wouldnt have enough strength to

26、 play, and that makes the memory of that day even stronger. Dad was doing something he had done all his life, giving. As sick as he was, he was still pleasing others. Dad sure could play that Mandolin! statistic: =1149.0, A=7.0, B=4.0, C=8.0, D=24.0, E=1.0, F=4.0, G=2.0, H=20.0, I=18.0, J=2.0, K=2.0

27、, L=1.0, M=5.0, N=1.0, O=6.0, P=2.0, R=2.0, S=8.0, T=8.0, U=1.0, V=1.0, W=18.0, Y=2.0, a=344.0, b=32.0, c=84.0, d=214.0, e=478.0, f=100.0, g=80.0, h=241.0, i=242.0, j=6.0, k=32.0, l=210.0, m=98.0, n=279.0, o=306.0, p=66.0, q=3.0, r=194.0, s=187.0, t=327.0, u=118.0, v=41.0, w=109.0, x=3.0, y=103.0, z

28、=2.0p-distribution:0.22117420596727622,0.09201154956689124,0.06621751684311838,0.0629451395572666,0.05890279114533205,0.05370548604427334,0.0465832531280077,0.04639076034648701,0.0411934552454283,0.04042348411934552,0.03734359961501444,0.03599615014436958,0.02271414821944177,0.020981713185755535,0.0

29、19826756496631376,0.019249278152069296,0.01886429258902791,0.01616939364773821,0.015399422521655439,0.012704523580365737,0.007892204042348411,0.006159769008662175,0.006159769008662175,0.0046198267564966315,0.0038498556304138597,0.0034648700673724736,0.0034648700673724736,0.0015399422521655437,0.0015

30、399422521655437,0.0015399422521655437,0.001347449470644851,0.0011549566891241579,0.0011549566891241579,9.624639076034649E-4,7.699711260827719E-4,7.699711260827719E-4,5.774783445620789E-4,5.774783445620789E-4,3.8498556304138594E-4,3.8498556304138594E-4,3.8498556304138594E-4,3.8498556304138594E-4,3.84

31、98556304138594E-4,3.8498556304138594E-4,3.8498556304138594E-4,1.9249278152069297E-4,1.9249278152069297E-4,1.9249278152069297E-4,1.9249278152069297E-4,1.9249278152069297E-4entrophy:4.181669518192732code-table(0) -|probability|code-word|code-word length -|0.22117420596727622|11|2 -|0.09201154956689124

32、|0000|4 -|0.06621751684311838|0001|4 -|0.0629451395572666|0011|4 -|0.05890279114533205|0101|4 -|0.05370548604427334|1000|4 -|0.0465832531280077|1010|4 -|0.04639076034648701|1011|4 -|0.0411934552454283|01000|5 -|0.04042348411934552|01100|5 -|0.03734359961501444|01110|5 -|0.03599615014436958|01111|5 -

33、|0.02271414821944177|10010|5 -|0.020981713185755535|001000|6 -|0.019826756496631376|001001|6 -|0.019249278152069296|001011|6 -|0.01886429258902791|010011|6 -|0.01616939364773821|011010|6 -|0.015399422521655439|011011|6 -|0.012704523580365737|100111|6 -|0.007892204042348411|0010101|7 -|0.006159769008662175|00101000|8 -|0.006159769008662175|01001000|8 -|0.0046198267564966315|01001001|8 -|0.0038498556304138597|01001011|8 -|0.0034648700673724736|10011010|8 -|0.0034648700673724736|10011011|8 -|0.0015399422521655437|100110000|9 -|0.001539942252165