建站
咨詢
售后
建站咨詢
新聞中心
1.什么是哈夫曼樹?
專注于為中小企業(yè)提供成都網(wǎng)站設(shè)計(jì)、成都網(wǎng)站建設(shè)、外貿(mào)網(wǎng)站建設(shè)服務(wù),電腦端+手機(jī)端+微信端的三站合一,更高效的管理,為中小企業(yè)珠山免費(fèi)做網(wǎng)站提供優(yōu)質(zhì)的服務(wù)。我們立足成都，凝聚了一批互聯(lián)網(wǎng)行業(yè)人才，有力地推動(dòng)了上千家企業(yè)的穩(wěn)健成長(zhǎng)，幫助中小企業(yè)通過網(wǎng)站建設(shè)實(shí)現(xiàn)規(guī)模擴(kuò)充和轉(zhuǎn)變。
哈夫曼樹是一種最優(yōu)二叉樹，它的最優(yōu)點(diǎn)體現(xiàn)在它的的帶權(quán)路徑長(zhǎng)度最小。(結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度為：結(jié)點(diǎn)的路徑長(zhǎng)度乘以結(jié)點(diǎn)的權(quán)值，樹的帶權(quán)路徑長(zhǎng)度為所有葉子結(jié)點(diǎn)帶權(quán)路徑長(zhǎng)度之和)
2.什么是哈弗曼編碼?
從哈弗曼樹的根結(jié)點(diǎn)開始，按照左子樹分配代碼“0”，右子樹分配代碼“1”的規(guī)則，直到葉子結(jié)點(diǎn)為止，每個(gè)葉子結(jié)點(diǎn)的哈弗曼編碼就是從根結(jié)點(diǎn)開始，一直到該葉子結(jié)點(diǎn)為止，把途中經(jīng)過的代碼按順序串起來就OK了。
3.什么是哈弗曼壓縮?
Huffman( 哈夫曼 ) 算法在上世紀(jì)五十年代初提出來了，它是一種無損壓縮方法，在壓縮過程中不會(huì)丟失信息熵，而且可以證明 Huffman 算法在無損壓縮算法中是最優(yōu)的。 Huffman 原理簡(jiǎn)單，實(shí)現(xiàn)起來也不困難，在現(xiàn)在的主流壓縮軟件得到了廣泛的應(yīng)用。對(duì)應(yīng)用程序、重要資料等絕對(duì)不允許信息丟失的壓縮場(chǎng)合， Huffman 算法是非常好的選擇。
哈夫曼壓縮，一般用來壓縮文本和程序文件。哈夫曼壓縮屬于可變代碼長(zhǎng)度算法一族。意思是個(gè)體符號(hào)(例如，文本文件中的字符)用一個(gè)特定長(zhǎng)度的位序列替代。因此，在文件中出現(xiàn)頻率高的符號(hào)，使用短的位序列，而那些很少出現(xiàn)的符號(hào)，則用較長(zhǎng)的位序列。
有了以上的基本概念，我們就可以動(dòng)手實(shí)現(xiàn)哈弗曼壓縮軟件了!
4.哈弗曼壓縮軟件的實(shí)現(xiàn)：
在文件中，所有的數(shù)據(jù)都是以字節(jié)的形式存在的，一個(gè)字節(jié)是8位，所以所有可能出現(xiàn)的字節(jié)在0——256之間(不包括256)，所以，第一步要做的事情就是，把文件所有的字節(jié)的出現(xiàn)頻率統(tǒng)計(jì)出來，并用頻率做為權(quán)值生成一棵哈弗曼樹：
Java代碼
- int[] ByteCount = new int[256];//字節(jié)頻率統(tǒng)計(jì)
- InputStream fis = new FileInputStream(pathName_former);
- InputStream bis = new BufferedInputStream(fis);//創(chuàng)建文件輸入流
- while(bis.available()>0){
- int tmp = bis.read();
- ByteCount[tmp]++;
- }//統(tǒng)計(jì)頻率
- //構(gòu)造哈弗曼樹
- hfmTree hfm = new hfmTree(ByteCount);
Java代碼
- public hfmTree(int[] rank){//根據(jù)頻率構(gòu)造哈弗曼樹
- //把頻率不為零的字節(jié)加入節(jié)點(diǎn)優(yōu)先級(jí)隊(duì)列
- PriorityQueue nodes = new java.util.PriorityQueue ();
- for(int i=0;i
- if(rank[i]!=0){
- nodes.add(new hfmNode(rank[i],i));
- }
- }
- //構(gòu)造哈弗曼樹
- while(nodes.size()!=1){
- hfmNode node_1 = nodes.poll();//1
- hfmNode node_2 = nodes.poll();//2
- hfmNode addNode = new hfmNode(node_1.getRank()+node_2.getRank(),0);
- addNode.setLeft(node_1);
- addNode.setRight(node_2);
- nodes.add(addNode);
- }
- root = nodes.poll();
- }//構(gòu)造函數(shù)(correct)
接下來，要做的就是獲得0——256之間每個(gè)字節(jié)所對(duì)應(yīng)的哈弗曼編碼，用一個(gè)String[] Code = new Code[256]保存 下來
Java代碼
- //獲得編碼
- private void getStrByte(hfmNode node,String s){
- if(node.getLeft()==null&&node.getRight()==null){
- Code[node.getData()] = s;//獲得編碼字符串
- }
- if(node.getLeft()!=null){
- getStrByte(node.getLeft(),s+"0");
- }//左零
- if(node.getRight()!=null){
- getStrByte(node.getRight(),s+"1");
- }//右1
- }
然后就是把每個(gè)字節(jié)的編碼長(zhǎng)度打入文件：
Java代碼
- //先將0-255的編碼長(zhǎng)度打到文件里
- for(int i=0;i
- if(Code[i]==null||Code[i]==""){
- Code[i] = "";
- bos.write(0);
- }else{
- bos.write(Code[i].length());
- }
- }
接下來就是，將每個(gè)字節(jié)的編碼打入文件(這里需要吧8個(gè)長(zhǎng)度的01串轉(zhuǎn)換成一個(gè)byte打入文件)：
Java代碼
- //把每個(gè)字節(jié)的編碼表打到文件里
- int i = 0;//第i個(gè)字節(jié)
- int count = 0;//滿8打一，計(jì)數(shù)器
- String writeCode = "";//寫入的8位編碼
- String allCode = "";//所有待寫入的編碼
- String inCode = "";
- while(i<256||count>=8){
- if(count>=8){//滿8
- writeCode = allCode.substring(0,8);//前8位
- count-=8;
- allCode = allCode.substring(8);
- bos.write(changeString(writeCode));//寫入一個(gè)字節(jié)
- }else{
- count+=Code[i].length();
- allCode+=Code[i];
- inCode+=Code[i];
- i++;//嚴(yán)重錯(cuò)誤發(fā)生地
- }
- }
- //如果不滿8位的
- if(allCode.length()>0){
- int len = 8-allCode.length();//補(bǔ)零
- for(int j=0;j
- allCode+="0";
- }
- inCode+=allCode;
- bos.write(changeString(allCode));
- }
最后就是把文件中的所有字節(jié)按照這種哈弗曼的編碼方式保存到文件中，過程類似于上一步(在最后打入末尾補(bǔ)入的0的個(gè)數(shù)，主要是為了方便解壓縮)：
Java代碼
- //編碼表輸出完畢，將文件中的字節(jié)按照這種編碼方式壓縮
- InputStream ins = new FileInputStream(pathName_former);
- InputStream buf = new BufferedInputStream(ins);//創(chuàng)建輸入流
- count = 0;
- writeCode = "";
- allCode = "";
- while(buf.available()>0||count>=8){
- if(count>=8){//滿8
- writeCode = allCode.substring(0,8);//前8位
- count-=8;
- allCode = allCode.substring(8);
- bos.write(changeString(writeCode));//寫入一個(gè)字節(jié)
- }else{
- int data = buf.read();
- count+=Code[data].length();
- allCode+=Code[data];
- }
- }
- //如果不滿8位的
- if(allCode.length()>0){
- int len = 8-allCode.length();//補(bǔ)零
- for(int j=0;j
- allCode+="0";
- }
- bos.write(changeString(allCode));
- bos.write(len);//補(bǔ)入了幾個(gè)0
- }else{
- bos.write(0);//補(bǔ)入了0個(gè)0
- }
到這里，整個(gè)壓縮過程基本完成了，解壓縮就是壓縮的逆過程，在此不再贅述，所有的操作都保存在附上源代碼中。
新聞標(biāo)題：哈弗曼編碼以及用其實(shí)現(xiàn)壓縮軟件
標(biāo)題路徑：http://www.dlmjj.cn/article/cooioip.html
