Java利用哈夫曼編碼實現字串壓縮

2022-09-20 22:02:56

赫夫曼編碼基本介紹

1) 赫夫曼編碼也翻譯為哈夫曼編碼(Huffman Coding)，又稱霍夫曼編碼，是一種編碼方式, 屬於一種程式演演算法

2) 赫夫曼編碼是赫哈夫曼樹在電訊通訊中的經典的應用之一。

3) 赫夫曼編碼廣泛地用於資料檔案壓縮。其壓縮率通常在 20%～90%之間

4) 赫夫曼碼是可變字長編碼(VLC)的一種。Huffman 於 1952 年提出一種編碼方法，稱之為最佳編碼

在通訊領域中幾種資訊處理方式的區別（以字串" i like like like java do you like a java"舉例）:

第一種-定長編碼:

第二種-變長編碼:

第三種-赫夫曼編碼:

傳輸的字串:

1、 i like like like java do you like a java

2、 d:1 y:1 u:1 j:2 v:2 o:2 l:4 k:4 e:4 i:5 a:5 :9 // 各個字元對應的個數

3、按照上面字元出現的次數構建一顆赫夫曼樹, 次數作為權值

構成赫夫曼樹的步驟：

1) 從小到大進行排序, 將每一個資料，每個資料都是一個節點，每個節點可以看成是一顆最簡單的二元樹

2) 取出根節點權值最小的兩顆二元樹

3) 組成一顆新的二元樹, 該新的二元樹的根節點的權值是前面兩顆二元樹根節點權值的和

4) 再將這顆新的二元樹，以根節點的權值大小再次排序，不斷重複 1-2-3-4 的步驟，直到數列中，所有的資料都被處理，就得到一顆赫夫曼樹

4、根據赫夫曼樹，給各個字元,規定編碼 (字首編碼)，向左的路徑為 0 向右的路徑為 1 ，編碼

如下:

o: 1000 u: 10010 d: 100110 y: 100111 i: 101

a : 110 k: 1110 e: 1111 j: 0000 v: 0001 l: 001 : 01

5、按照上面的赫夫曼編碼，我們的"i like like like java do you like a java" 字串對應的編碼為 (注意這裡我們使用的無失真壓縮)1010100110111101111010011011110111101001101111011110100001100001110011001111000011001111000100100100110111101111011100100001100001110 通過赫夫曼編碼處理長度為：133

通過以上三種資訊處理方式可以對比看出赫夫曼編碼的優越性。

以下給出實現哈夫曼編碼需要的各個方法:

1、先建立節點物件:

// 為了排序，必須實現Comprable<>介面
 
public class Node implements Comparable<Node>{
    Byte data;
    int weight;
    Node left;
    Node right;
 
    public Node(Byte data, int weight) {
        this.data = data;
        this.weight = weight;
    }
 
    @Override
    public String toString() {
        return "Node{" +
                "data=" + data +
                ", weight=" + weight +
                '}';
    }
 
    @Override
    public int compareTo(Node o) {
        return this.weight - o.weight;
    }
 
    //前序遍歷
    public void prefixOrder(){
        System.out.println(this);
        if (this.left != null){
            this.left.prefixOrder();
        }
        if (this.right != null){
            this.right.prefixOrder();
        }
    }
}

2、需要先實現統計輸入的字串中各個字元的個數:

/**
     * //統計字串中每個字元出現的次數和空格出現次數
     *
     * @param str 字串
     * @return 返回一個排好序的Node集合
     */
    public static List<Node> totalCharCounts(String str) {
 
        for (int i = 0; i < str.length(); i++) {
            char ch = str.charAt(i);
            Integer count = map.get(ch);
            if (count == null) {
                count = 0;
            }
            map.put(ch, count + 1);
        }
        //遍歷map，將map中的資料存入Node節點中
        //先將map轉為set集合
        Set<Map.Entry<Character, Integer>> mapSet = map.entrySet();
        //觀察測試輸出
        //System.out.println(mapSet);
        List<Node> nodeList = new ArrayList<>();
        //遍歷set
        for (Map.Entry<Character, Integer> set : mapSet) {
            // 將map中的資料存入Node節點中
            Node node = new Node((byte) set.getKey().charValue(), set.getValue());
            // 將node存入集合中
            nodeList.add(node);
            //System.out.println(set.getKey() + " = " + set.getValue());
        }
        //排序
        Collections.sort(nodeList);
        //測試
        //System.out.println(nodeList);
        return nodeList;
    }

3、建立赫夫曼樹:

/**
     * 建立huffman樹
     *
     * @param nodeList 排好序的集合
     * @return 返回huffman樹的根節點
     */
    public static Node createHuffmanTree(List<Node> nodeList) {
        //迴圈建立huffman樹
        while (nodeList.size() > 1) {
            //1、每次取出集合中的前兩個節點
            Node left = nodeList.get(0);
            Node right = nodeList.get(1);
            //2、將他們的權值相加構成一個新的節點並作為他們的父節點
            Node parent = new Node(null, left.weight + right.weight);
            parent.left = left;
            parent.right = right;
            //3、刪除已經處理過的節點
            nodeList.remove(left);
            nodeList.remove(right);
            //4、將新的節點存入集合中
            nodeList.add(parent);
            //5、重新給集合排序,迴圈這5步即可，直到集合中只有一個節點，這就是huffman樹的根節點
            Collections.sort(nodeList);
            //觀察測試輸出
            //System.out.println(nodeList);
        }
        //返回huffman樹的根節點
        return nodeList.get(0);
    }

4、根據建立的赫夫曼樹進行字串編碼壓縮:

/**
     * 根據huffman樹來進行資料編碼壓縮
     * 思路:
     * 1、只要向左子樹走就代表0，向右子樹走就代表1
     * 2、從頭節點走到對於字元在的節點位置的路徑對於的0和1組成的二進位制編碼就是壓縮後該字元對於的編碼
     * 3、需要定義一個StringBuffer來儲存某個節點的路徑對於的編碼
     * 4、將赫夫曼編碼表存放在Map<Byte,String>中
     *
     * @param node         huffman樹的根節點
     * @param stringBuffer 用於拼接路徑
     * @param code         路徑：左子節點是0，右子節點是1
     * @return
     */
    private static void getHuffmanCompressionCode(Node node, String code, StringBuffer stringBuffer) {
        StringBuffer stringBuffer1 = new StringBuffer(stringBuffer);
        stringBuffer1.append(code);
        //如果為空，不進行處理
        if (node != null) {
            //判斷node是葉子節點還是非葉子節點
            if (node.data == null) {
                //非葉子節點
                //向左遞迴
                getHuffmanCompressionCode(node.left, "0", stringBuffer1);
                //向右遞迴
                getHuffmanCompressionCode(node.right, "1", stringBuffer1);
            } else {
                //葉子節點
                //說明這條路走到尾了，將路徑編碼存入map中
                huffmanCodes.put(node.data, stringBuffer1.toString());
            }
        }
    }

5、得到壓縮後的赫夫曼編碼長度(二進位制位數):

/**
     * @return 得到壓縮後的赫夫曼編碼大小
     */
    public static int getStrCodeSize() {
        int size = 0;
        //將兩個map集合都轉為set集合
        Set<Map.Entry<Character, Integer>> mapSet = map.entrySet();
        Set<Map.Entry<Byte, String>> huffmanMapSet = huffmanCodes.entrySet();
        //迴圈兩個set集合
        for (Map.Entry<Character, Integer> set1 : mapSet) {
            for (Map.Entry<Byte, String> set2 : huffmanMapSet) {
                //如果兩個set的key相同就將他們的value相乘,只是需要注意儲存huffman編碼中的是字串，需要乘字串的長度
                if ((byte) set1.getKey().charValue() == set2.getKey()) {
                    size = size + set1.getValue() * (set2.getValue().length());
                    //節約時間，之間退出內迴圈。因為不可能有一對多的關係。
                    break;
                }
            }
        }
        return size;
    }

6、編寫一個方法，將字串對應的byte[]陣列，通過生成的赫夫曼編碼表，返回一個赫夫曼編碼壓縮後的byte[]

/**
     * 編寫一個方法，將字串對應的 byte[] 陣列，通過生成的赫夫曼編碼表，返回一個赫夫曼編碼 壓縮後的byte[]
     *
     * @param bytes        這時原始的字串對應的 byte[]
     * @param huffmanCodes 生成的赫夫曼編碼 map
     * @return 返回赫夫曼編碼處理後的 byte[]
     * 舉例： String content = "i like like like java do you like a java"; =》 byte[] contentBytes = content.getBytes();
     * 返 回 的 是 字 符 串:
     * "1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000
     * 101111111100110001001010011011100"
     * => 對應的 byte[] huffmanCodeBytes ，即 8 位對應一個 byte,放入到 huffmanCodeBytes
     * huffmanCodeBytes[0] = 10101000(二補數) => byte [推導 10101000=> 10101000 - 1 => 10100111(反
     * 碼)=> 11011000(原始碼) = -88 ]
     */
    public static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) {
        //1、先利用赫夫曼編碼表將傳進來的bytes陣列轉為壓縮後的編碼
        StringBuffer stringBuffer1 = new StringBuffer();
        for (byte b : bytes) {
            stringBuffer1.append(huffmanCodes.get(b));
        }
        //輸出字串壓縮成赫夫曼編碼後對應的二進位制編碼
        //System.out.println("輸出字串壓縮成赫夫曼編碼後對應的二進位制編碼:" + stringBuffer1 + "長度為:" + stringBuffer1.length());
 
        //獲取byte陣列的長度，Math.ceil()表示向上取整
        int len = (int) Math.ceil(stringBuffer1.length()*1.0 / 8);
        //也可以用下面的方法獲取長度
        /*if(stringBuffer1.length() % 8 == 0) {
            len = stringBuffer1.length() / 8;
        } else {
            len = stringBuffer1.length() / 8 + 1;
        }*/
        //測試
        //System.out.println(stringBuffer1.length());
        //System.out.println(len);
        byte[] huffmanBytes = new byte[len];
        int index = 0;
        for (int i = 0; i < stringBuffer1.length(); i = i + 8) {
            String strByte;
            if (i + 8 > stringBuffer1.length()) {
                //從i取到字串最後一個字元
                strByte = stringBuffer1.substring(i);
            } else {
                //一次擷取8個
                strByte = stringBuffer1.substring(i, i + 8);
            }
            //將 strByte 轉成一個 byte,放入到 huffmanBytes中
            //該方法是將strByte對應的01字串傳換為十進位制
            //第二個參數列示基數（radix）,表示轉換為radix進位制
            huffmanBytes[index] = (byte) Integer.parseInt(strByte, 2);
            index++;
        }
        return huffmanBytes;
    }

其實也可以不用寫5中的方法，可以直接在6中輸出stringBuffer1.length()就可以得到壓縮後的二進位制位數。不過也可以把5當作一種解決的演演算法。

以下給出完整的程式碼:

import java.util.*;
 
/**
 * 實現huffman編碼
 */
 
public class HuffmanCode {
 
    //將赫夫曼編碼表存放在Map<Byte,String>中
    public static Map<Byte, String> huffmanCodes = new HashMap<>();
 
    //需要定義一個StringBuffer來儲存某個節點的路徑對於的編碼
    public static StringBuffer stringBuffer = new StringBuffer();
 
    //建立一個map，來儲存每個字元以及他對應出現的次數
    public static Map<Character, Integer> map = new HashMap<>();
 
    public static void main(String[] args) {
 
        Scanner scanner = new Scanner(System.in);
        System.out.println("輸入字串:");
        //scanner.next()方法不能輸入空格，例如輸入: aaa bbb實際上只能接收到aaa,空格後面的字串都接收不到
        //所以需要用scanner,nextLine()方法來接收字串
 
        String str = scanner.nextLine();
 
        // 把輸入的字串轉為byte陣列，在byte陣列中儲存的是字元對應的ASCII碼值
        byte[] strBytes = str.getBytes();
        System.out.println(str + ",壓縮成赫夫曼編碼前對應的byte陣列:" + Arrays.toString(strBytes));
 
        //計算壓縮前的字串有多少位二進位制數
        int compressionBeforeCodeSize = str.length() * 8 + str.length() - 1;
        System.out.println(str + ",壓縮前的字串大小:" + compressionBeforeCodeSize);
 
        //統計字串中每個字元出現的次數和空格出現次數並存入Node節點中
        List<Node> nodeList = totalCharCounts(str);
 
        //建立huffman樹
        Node root = createHuffmanTree(nodeList);
 
        //得到壓縮後的編碼
        getHuffmanCompressionCode(root, "", stringBuffer);
 
        //輸出赫夫曼編碼表
        System.out.println(str + ",對應的赫夫曼編碼表:");
        System.out.println(huffmanCodes);
 
        //得到壓縮後的字串大小
        int compressionAfterCodeSize = getStrCodeSize();
        System.out.println(str + ",壓縮後的字串大小:" + compressionAfterCodeSize);
 
        //可以算出壓縮率是多少
        double compressionRadio = (compressionBeforeCodeSize - compressionAfterCodeSize) * 1.0 / compressionBeforeCodeSize;
        System.out.println(str + ",壓縮成赫夫曼編碼的壓縮率為:" + compressionRadio);
 
        byte[] bytes = zip(strBytes, huffmanCodes);
        System.out.println(str + ",壓縮成赫夫曼編碼後對應的byte陣列:" + Arrays.toString(bytes));
 
    }
 
    /**
     * @return 得到壓縮後的赫夫曼編碼大小
     */
    public static int getStrCodeSize() {
        int size = 0;
        //將兩個map集合都轉為set集合
        Set<Map.Entry<Character, Integer>> mapSet = map.entrySet();
        Set<Map.Entry<Byte, String>> huffmanMapSet = huffmanCodes.entrySet();
        //迴圈兩個set集合
        for (Map.Entry<Character, Integer> set1 : mapSet) {
            for (Map.Entry<Byte, String> set2 : huffmanMapSet) {
                //如果兩個set的key相同就將他們的value相乘,只是需要注意儲存huffman編碼中的是字串，需要乘字串的長度
                if ((byte) set1.getKey().charValue() == set2.getKey()) {
                    size = size + set1.getValue() * (set2.getValue().length());
                    //節約時間，之間退出內迴圈。因為不可能有一對多的關係。
                    break;
                }
            }
        }
        return size;
    }
 
    /**
     * 根據huffman樹來進行資料編碼壓縮
     * 思路:
     * 1、只要向左子樹走就代表0，向右子樹走就代表1
     * 2、從頭節點走到對於字元在的節點位置的路徑對於的0和1組成的二進位制編碼就是壓縮後該字元對於的編碼
     * 3、需要定義一個StringBuffer來儲存某個節點的路徑對於的編碼
     * 4、將赫夫曼編碼表存放在Map<Byte,String>中
     *
     * @param node         huffman樹的根節點
     * @param stringBuffer 用於拼接路徑
     * @param code         路徑：左子節點是0，右子節點是1
     * @return
     */
    private static void getHuffmanCompressionCode(Node node, String code, StringBuffer stringBuffer) {
        StringBuffer stringBuffer1 = new StringBuffer(stringBuffer);
        stringBuffer1.append(code);
        //如果為空，不進行處理
        if (node != null) {
            //判斷node是葉子節點還是非葉子節點
            if (node.data == null) {
                //非葉子節點
                //向左遞迴
                getHuffmanCompressionCode(node.left, "0", stringBuffer1);
                //向右遞迴
                getHuffmanCompressionCode(node.right, "1", stringBuffer1);
            } else {
                //葉子節點
                //說明這條路走到尾了，將路徑編碼存入map中
                huffmanCodes.put(node.data, stringBuffer1.toString());
            }
        }
    }
 
    /**
     * //統計字串中每個字元出現的次數和空格出現次數
     *
     * @param str 字串
     * @return 返回一個排好序的Node集合
     */
    public static List<Node> totalCharCounts(String str) {
 
        for (int i = 0; i < str.length(); i++) {
            char ch = str.charAt(i);
            Integer count = map.get(ch);
            if (count == null) {
                count = 0;
            }
            map.put(ch, count + 1);
        }
        //遍歷map，將map中的資料存入Node節點中
        //先將map轉為set集合
        Set<Map.Entry<Character, Integer>> mapSet = map.entrySet();
        //觀察測試輸出
        //System.out.println(mapSet);
        List<Node> nodeList = new ArrayList<>();
        //遍歷set
        for (Map.Entry<Character, Integer> set : mapSet) {
            // 將map中的資料存入Node節點中
            Node node = new Node((byte) set.getKey().charValue(), set.getValue());
            // 將node存入集合中
            nodeList.add(node);
            //System.out.println(set.getKey() + " = " + set.getValue());
        }
        //排序
        Collections.sort(nodeList);
        //測試
        //System.out.println(nodeList);
        return nodeList;
    }
 
    /**
     * 建立huffman樹
     *
     * @param nodeList 排好序的集合
     * @return 返回huffman樹的根節點
     */
    public static Node createHuffmanTree(List<Node> nodeList) {
        //迴圈建立huffman樹
        while (nodeList.size() > 1) {
            //1、每次取出集合中的前兩個節點
            Node left = nodeList.get(0);
            Node right = nodeList.get(1);
            //2、將他們的權值相加構成一個新的節點並作為他們的父節點
            Node parent = new Node(null, left.weight + right.weight);
            parent.left = left;
            parent.right = right;
            //3、刪除已經處理過的節點
            nodeList.remove(left);
            nodeList.remove(right);
            //4、將新的節點存入集合中
            nodeList.add(parent);
            //5、重新給集合排序,迴圈這5步即可，直到集合中只有一個節點，這就是huffman樹的根節點
            Collections.sort(nodeList);
            //觀察測試輸出
            //System.out.println(nodeList);
        }
        //返回huffman樹的根節點
        return nodeList.get(0);
    }
 
    /**
     * 編寫一個方法，將字串對應的byte[]陣列，通過生成的赫夫曼編碼表，返回一個赫夫曼編碼壓縮後的byte[]
     *
     * @param bytes        這時原始的字串對應的 byte[]
     * @param huffmanCodes 生成的赫夫曼編碼 map
     * @return 返回赫夫曼編碼處理後的 byte[]
     * 舉例： String content = "i like like like java do you like a java"; =》 byte[] contentBytes = content.getBytes();
     * 返 回 的 是 字 符 串:
     * "1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000
     * 101111111100110001001010011011100"
     * => 對應的 byte[] huffmanCodeBytes ，即 8 位對應一個 byte,放入到 huffmanCodeBytes
     * huffmanCodeBytes[0] = 10101000(二補數) => byte [推導 10101000=> 10101000 - 1 => 10100111(反
     * 碼)=> 11011000(原始碼) = -88 ]
     */
    public static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) {
        //1、先利用赫夫曼編碼表將傳進來的bytes陣列轉為壓縮後的編碼
        StringBuffer stringBuffer1 = new StringBuffer();
        for (byte b : bytes) {
            stringBuffer1.append(huffmanCodes.get(b));
        }
        //輸出字串壓縮成赫夫曼編碼後對應的二進位制編碼
        //System.out.println("輸出字串壓縮成赫夫曼編碼後對應的二進位制編碼:" + stringBuffer1 + "長度為:" + stringBuffer1.length());
 
        //獲取byte陣列的長度，Math.ceil()表示向上取整
        int len = (int) Math.ceil(stringBuffer1.length()*1.0 / 8);
        //也可以用下面的方法獲取長度
        /*if(stringBuffer1.length() % 8 == 0) {
            len = stringBuffer1.length() / 8;
        } else {
            len = stringBuffer1.length() / 8 + 1;
        }*/
        //測試
        //System.out.println(stringBuffer1.length());
        //System.out.println(len);
        byte[] huffmanBytes = new byte[len];
        int index = 0;
        for (int i = 0; i < stringBuffer1.length(); i = i + 8) {
            String strByte;
            if (i + 8 > stringBuffer1.length()) {
                //從i取到字串最後一個字元
                strByte = stringBuffer1.substring(i);
            } else {
                //一次擷取8個
                strByte = stringBuffer1.substring(i, i + 8);
            }
            //將 strByte 轉成一個 byte,放入到 huffmanBytes中
            //該方法是將strByte對應的01字串傳換為十進位制
            //第二個參數列示基數（radix）,表示轉換為radix進位制
            huffmanBytes[index] = (byte) Integer.parseInt(strByte, 2);
            index++;
        }
        return huffmanBytes;
    }
 
}

以下是我的測試結果輸出:

輸入的字串: i like like like java do you like a java

輸入的字串: asdjkj ;lkjsadlkj kj ()dasd

到此這篇關於Java利用哈夫曼編碼實現字串壓縮的文章就介紹到這了,更多相關Java字串壓縮內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！

Java利用哈夫曼編碼實現字串壓縮

熱門文章