本文主要介紹如何實現哈夫曼壓縮以及提高哈夫曼壓縮過程的讀寫速率，對于哈夫曼樹的概念及其構造則沒有介紹，感興趣的朋友可以先百度一下了解相關知識。

一、哈夫曼壓縮原理

哈夫曼壓縮是一種無損的壓縮算法，在壓縮過程中不會損失信息熵，因此常用哈夫曼算法去壓縮一些重要的文件資料。

哈夫曼壓縮是通過采用特定長度的位序列去替代原來的個體符號（如字節）。對于一些高頻率出現的字節，使用短字節表示，而對于一些低頻率出現的字節，則采用較長的位序列來代替，這從而降低整個文本的位序列長度，達到壓縮目的。

二、哈夫曼壓縮與解壓縮過程

要實現哈夫曼壓縮，我們需要做如下工作：

1、讀取文本；

2、統計文本中各字節出現的次數；

3、根據第二步統計出來結果構造哈夫曼樹；

4、生成哈夫曼編碼；

5、將文件轉換為哈夫曼編碼格式的字節文件；

6、寫入哈夫曼編碼。

哈夫曼解壓縮是壓縮的逆過程，其主要步驟如下：

1、讀取壓縮文件；

2、還原哈夫曼編碼；

3、根據哈夫曼編碼還原文件。

三、哈夫曼壓縮

壓縮思路：

1、int [ ] byteCount和String [ ] charCode

創建兩個數組分別保存各字節出現的次數和哈夫曼編碼，由于本文壓縮的是英文文本，只需要用基礎ASCII碼（0-127），所以數組長度均設為128位，利用數組索引來存儲對應的字節，索引位置的值存儲相應信息；

2、采用優先隊列來構建哈夫曼樹，通過調用poll( )方法可快速構建哈夫曼樹，需要注意的是，這里需要加入一個比較器，重寫compare（）方法，采用按字節出現次數排序（從小到大）；

3、讀寫數據時采用字節緩沖流加字節數組的方法提高讀寫效率，減少對磁盤文件的操作；

4、本文將編碼文件與文件編碼合并后一起生成字節文件后，再一次性寫入壓縮文件；

5、生成字節文件時，最后一個字節不足8位時，加0補齊8位生成字節寫入；

6、壓縮文件格式:

? ? ? ? 本文壓縮文件分為三段,分別為:?

? ? ? ? a.各字節編碼長度( 0-127);

? ? ? ? b.末位補0數(128);

? ? ? ? c.字節編碼文件(含編碼字節)；

7、整型數據轉換為字節方法：new Integer( int value).byteValue。

package com.liao.Huffman0830v1;import java.io.BufferedInputStream; import java.io.BufferedOutputStream; import java.io.File; import java.io.FileInputStream; import java.io.FileNotFoundException; import java.io.FileOutputStream; import java.io.IOException; import java.util.Comparator; import java.util.PriorityQueue;public class HufTree {private static final int LEN = 128;private int[] byteCount = new int[LEN];// 統計各字節出現次數private String[] charCode = new String[LEN];// 記錄各字節哈夫曼編碼private PriorityQueue<hufNode> nodeQueue = new PriorityQueue<>(LEN, new Comparator<hufNode>() {@Overridepublic int compare(hufNode o1, hufNode o2) {return o1.count - o2.count;// 按次數排序}});// 成員內部類private static class hufNode {private hufNode lchild;// 左分支private hufNode rchild;// 右分支private String str;// 記錄字符private int count;// 統計次數// 構造方法public hufNode(String str, int count) {super();this.str = str;this.count = count;}}// 主函數public static void main(String[] args) {File file = new File("file\\01.txt");File file2 = new File("file\\壓縮文件.txt");new HufTree().compress(file, file2);// 壓縮文件System.out.println("原文件大小：" + file.length() + "b");System.out.println("壓縮文件大小：" + file2.length() + "b");}// 壓縮文件private void compress(File file, File file2) {byte[] bs = readFile(file);// 讀取文件countChar(bs);// 統計詞頻hufNode root = createTree();// 創建哈夫曼樹generateCode(root, "");// 生成哈夫曼編碼printCode();// 打印哈夫曼編碼writeFile(bs, file2);// 寫入壓縮文件}// 將文件轉換為字節數組保存private byte[] readFile(File file) {byte[] bs = new byte[(int) file.length()];// 創建字節數組BufferedInputStream bis = null;// 聲明字節緩沖流try {bis = new BufferedInputStream(new FileInputStream(file));bis.read(bs);// 將文件讀取到字節數組中} catch (FileNotFoundException e) {e.printStackTrace();} catch (IOException e) {e.printStackTrace();} finally {try {if (bis != null)bis.close();// 關閉輸入流} catch (IOException e) {e.printStackTrace();}}return bs;}// 統計詞頻private void countChar(byte[] bs) {for (int i = 0, length = bs.length; i < length; i++) {byteCount[bs[i]]++;}}// 創建哈夫曼樹private hufNode createTree() {for (int i = 0; i < LEN; i++) {if (byteCount[i] != 0) {// 使用優先隊列保存nodeQueue.add(new hufNode((char) i + "", byteCount[i]));}}// 構建哈夫曼樹while (nodeQueue.size() > 1) {hufNode min1 = nodeQueue.poll();// 獲取并移除隊列頭元素hufNode min2 = nodeQueue.poll();hufNode result = new hufNode(min1.str + min2.str, min1.count + min2.count);result.lchild = min1;result.rchild = min2;nodeQueue.add(result);// 加入左節點}return nodeQueue.peek();// 返回根節點}// 生成哈夫曼編碼private void generateCode(hufNode root, String s) {// 葉子節點if (root.lchild == null && root.rchild == null) {// 保存至編碼數組對應位置charCode[(int) root.str.charAt(0)] = s;}if (root.lchild != null) {// 左邊加0generateCode(root.lchild, s + "0");}if (root.rchild != null) {// 右邊加1generateCode(root.rchild, s + "1");}}// 寫入壓縮文件 ：1、各字節編碼長度 2、各字節編碼 3、編碼后的文件private void writeFile(byte[] bs, File file2) {BufferedOutputStream bos = null;// 聲明字符緩沖流try {// 創建字符緩沖流bos = new BufferedOutputStream(new FileOutputStream(file2));// 寫入各字節編碼長度String binaryCode = writeCodeLength(file2, bos);// 字節數組文件轉碼成二進制文件String binaryFile = transFile(bs);// 合并二進制編碼及文件String codeAndFile = binaryCode + binaryFile;// 生成字節并寫入合并后二進制文件generateFile(bos, codeAndFile);} catch (IOException e) {e.printStackTrace();} finally {try {if (bos != null)bos.close();// 關閉輸入流} catch (IOException e) {e.printStackTrace();}}}// 寫入各字節編碼長度private String writeCodeLength(File file2, BufferedOutputStream bos) throws IOException {StringBuilder sb = new StringBuilder();// 創建字符緩沖流for (int i = 0; i < LEN; i++) {if (charCode[i] == null) {bos.write(0);} else {sb.append(charCode[i]);// 存儲哈夫曼編碼bos.write(charCode[i].length());}}return sb.toString();// 返回各字節哈夫曼編碼}// 文件轉碼private String transFile(byte[] bs) {StringBuilder sb = new StringBuilder();for (int i = 0, length = bs.length; i < length; i++) {sb.append(charCode[bs[i]]);}return sb.toString();}// 生成字節文件private void generateFile(BufferedOutputStream bos, String codeAndFile) throws IOException {int lastZero = 8 - codeAndFile.length() % 8;// 補0數int len = codeAndFile.length() / 8 + 1;// 取商+1if (lastZero != 8) {// 余數不為0,則補加1位len = len + 1;for (int i = 0; i < lastZero; i++) {codeAndFile += "0";// 加0補齊8位}}// 創建字符數組，保存字節byte[] bv = new byte[len];bv[0] = new Integer(lastZero).byteValue();for (int i = 1; i < len; i++) {// 先將8位01字符串二進制數據轉換為十進制整型數據，再轉為一個bytebyte bytes = new Integer(changeString(codeAndFile.substring(0, 8))).byteValue();bv[i] = bytes;// 加入到數組中codeAndFile = codeAndFile.substring(8);// 去除前8個字節}// 寫入文件bos.write(bv);}// 8位01字符串轉換為十進制整型數據private int changeString(String str) {return (int) (str.charAt(0) - 48) * 128 + (str.charAt(1) - 48) * 64 + (str.charAt(2) - 48) * 32+ (str.charAt(3) - 48) * 16 + (str.charAt(4) - 48) * 8 + (str.charAt(5) - 48) * 4+ (str.charAt(6) - 48) * 2 + (str.charAt(7) - 48);}// 打印編碼private void printCode() {for (int i = 0; i < LEN; i++) {if (charCode[i] != null) {System.out.println("(" + i + "," + (char) i + "," + byteCount[i] + "," + charCode[i] + ","+ charCode[i].length() + ")");}}} }

四、哈夫曼解壓縮

解壓縮思路：

1、利用String類的substring(）方法和Arrays類的copyOfRange方法對字符串進行復制及截取；

2、利用BigInteger類的 new BigInteger(1, byte [ ]).toString(2)方法將字節數組轉換為二進制字符串形式；

package com.liao.Huffman0830v1;import java.io.BufferedInputStream; import java.io.BufferedOutputStream; import java.io.File; import java.io.FileInputStream; import java.io.FileNotFoundException; import java.io.FileOutputStream; import java.io.IOException; import java.math.BigInteger; import java.util.ArrayList; import java.util.Arrays;public class Decompress {private final static int LEN = 128;// 編碼字節個數private String[] charCode = new String[LEN];// 主函數public static void main(String[] args) {File file = new File("file\\壓縮文件.txt");File file3 = new File("file\\解壓文件.txt");new Decompress().decompress(file, file3);System.out.println("解壓前文件大小：" + file.length() + "b");System.out.println("解壓后文件大小：" + file3.length() + "b");}// 解壓文件private void decompress(File file, File file3) {// 讀取文件byte[] bs = readFile(file);// 獲取各字節編碼長度并返回哈夫曼編碼總長度int codeLengths = getCodeLength(bs);// 截取記錄哈夫曼編碼長度部分byte[] CodeLength = Arrays.copyOfRange(bs, 0, LEN);// 末位補0數int lastZero = bs[LEN]; // 截取二進制數據部分bs = Arrays.copyOfRange(bs, LEN+1, bs.length);// 將字節數組轉換為二進制字符串String codeAndFile =processData(bs);// 截取編碼表部分String binaryCode = codeAndFile.substring(0, codeLengths);// 截取文件部分(增補0)String binaryFile = codeAndFile.substring(codeLengths, codeAndFile.length() - lastZero);// 還原編碼表restoreCode(binaryCode, CodeLength);// 將二進制文件轉換為字節數組byte[] byteArray = restoreFile(binaryFile);// 寫入文件writeFile(file3, byteArray);}// 將文件轉換為字節數組保存private byte[] readFile(File file) {byte[] bs = new byte[(int) file.length()];// 創建字節數組BufferedInputStream bis = null;// 聲明字節緩沖流try {bis = new BufferedInputStream(new FileInputStream(file));bis.read(bs);// 將文件讀取到字節數組中} catch (FileNotFoundException e) {e.printStackTrace();} catch (IOException e) {e.printStackTrace();} finally {try {if (bis != null)bis.close();// 關閉輸入流} catch (IOException e) {e.printStackTrace();}}return bs;}//數據處理（轉為二進制）private String processData(byte [] bs) {//將數據轉換為二進制String codeAndFile =new BigInteger(1, bs).toString(2);//判斷首位是否需要補0if(bs[0]>0) {//轉為二進制，根據位數得到補0數int firstZero=8-Integer.toBinaryString(bs[0]).length();for(int i=0;i<firstZero;i++) {codeAndFile="0" + codeAndFile;}}return codeAndFile;}// 獲取各字節編碼長度并返回哈夫曼編碼總長度private int getCodeLength(byte[] bs) {int codeLengths = 0;for (int i = 0; i < LEN; i++) {if (bs[i] != 0) {codeLengths += bs[i];// 統計哈夫曼編碼總長度}}return codeLengths;}// 還原編碼private void restoreCode(String binaryCode, byte[] CodeLength) {for (int i = 0; i < LEN; i++) {charCode[i] = binaryCode.substring(0, CodeLength[i]);// 存儲該編碼binaryCode = binaryCode.substring(CodeLength[i]);// 更新編碼文件if (CodeLength[i] != 0) {System.out.println("(" + i + "," + (char) i + "," + charCode[i] + "," + CodeLength[i] + ")");}}}// 將二進制文件轉換為字符串private byte[] restoreFile(String binaryFile) {ArrayList<Byte> byteList = new ArrayList<>();// 創建字節隊列保存讀取字節for (int i = 0; i < binaryFile.length(); i++) {String charcode = binaryFile.substring(0, i + 1);for (int j = 0; j < LEN; j++) {if (charcode.equals(charCode[j])) {byteList.add(new Integer(j).byteValue());// 更新參數binaryFile = binaryFile.substring(i + 1);i = 0;break;}}}// 將字節隊列數據轉移至數組中byte[] byteArray = new byte[byteList.size()];for (int i = 0, len = byteList.size(); i < len; i++) {byteArray[i] = byteList.get(i);}return byteArray;}// 寫入文件private void writeFile(File file3, byte[] byteArray) {BufferedOutputStream bos = null;try {bos = new BufferedOutputStream(new FileOutputStream(file3));bos.write(byteArray);bos.flush();} catch (FileNotFoundException e) {e.printStackTrace();} catch (IOException e) {e.printStackTrace();} finally {if (bos != null) {try {bos.close();} catch (IOException e) {e.printStackTrace();}}}} }

五、測試類

通過壓縮文件與解壓縮文件內容對比測試壓縮是否成功：

package com.liao.Huffman0830v1;import java.io.BufferedInputStream; import java.io.File; import java.io.FileInputStream; import java.io.IOException; import java.util.Arrays;public class Test {public static void main(String[] args) throws IOException {File file1 = new File("file\\001.txt");File file2 = new File("file\\解壓文件.txt");File file3 = new File("file\\壓縮文件.txt");BufferedInputStream bis1 = new BufferedInputStream(new FileInputStream(file1));BufferedInputStream bis2 = new BufferedInputStream(new FileInputStream(file2));byte[] bs1 = new byte[(int) file1.length()];byte[] bs2 = new byte[(int) file2.length()];bis1.read(bs1);bis2.read(bs2);bis1.close();bis2.close();System.out.println(Arrays.equals(bs1, bs2) );System.out.println("原文件大小：" + file1.length() / 1000 + "kb" + "----" + "壓縮文件大小："+ file3.length() / 1000 + "kb");} }

測試結果：

根據測試結果，可以看出文件壓縮成功，壓縮率約為57% 。

六、注意事項

1、本文只適用于英文文本壓縮，對于中文文本壓縮，下篇會介紹；

2、本文基本上都是用一個字符串或字節數組保存整篇文檔，然后再進行讀寫操作（獲得更高效的讀寫速率），對于較大的文件（超過100Mb）可考慮將文件分成若干段再進行相關操作；

3、為進一步提高壓縮與解壓縮效率，可考慮使用多線程，但須注意數據同步的問題。

總結

以上是生活随笔為你收集整理的哈夫曼压缩（一）——英文文本的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。