Java利用哈夫曼編碼實現(xiàn)字符串壓縮
赫夫曼編碼基本介紹
1) 赫夫曼編碼也翻譯為 哈夫曼編碼(Huffman Coding),又稱霍夫曼編碼,是一種編碼方式, 屬于一種程序算法
2) 赫夫曼編碼是赫哈夫曼樹在電訊通信中的經(jīng)典的應(yīng)用之一。
3) 赫夫曼編碼廣泛地用于數(shù)據(jù)文件壓縮。其壓縮率通常在 20%~90%之間
4) 赫夫曼碼是可變字長編碼(VLC)的一種。Huffman 于 1952 年提出一種編碼方法,稱之為最佳編碼
在通信領(lǐng)域中幾種信息處理方式的區(qū)別(以字符串" i like like like java do you like a java"舉例):
第一種-定長編碼:
第二種-變長編碼:
第三種-赫夫曼編碼:
傳輸?shù)淖址?
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 // 各個字符對應(yīng)的個數(shù)
3、 按照上面字符出現(xiàn)的次數(shù)構(gòu)建一顆赫夫曼樹, 次數(shù)作為權(quán)值
構(gòu)成赫夫曼樹的步驟:
1) 從小到大進(jìn)行排序, 將每一個數(shù)據(jù),每個數(shù)據(jù)都是一個節(jié)點(diǎn) , 每個節(jié)點(diǎn)可以看成是一顆最簡單的二叉樹
2) 取出根節(jié)點(diǎn)權(quán)值最小的兩顆二叉樹
3) 組成一顆新的二叉樹, 該新的二叉樹的根節(jié)點(diǎn)的權(quán)值是前面兩顆二叉樹根節(jié)點(diǎn)權(quán)值的和
4) 再將這顆新的二叉樹,以根節(jié)點(diǎn)的權(quán)值大小 再次排序, 不斷重復(fù) 1-2-3-4 的步驟,直到數(shù)列中,所有的數(shù)據(jù)都被處理,就得到一顆赫夫曼樹
4、 根據(jù)赫夫曼樹,給各個字符,規(guī)定編碼 (前綴編碼), 向左的路徑為 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" 字符串對應(yīng)的編碼為 (注意這里我們使用的無損壓縮)1010100110111101111010011011110111101001101111011110100001100001110011001111000011001111000100100100110111101111011100100001100001110 通過赫夫曼編碼處理 長度為:133
通過以上三種信息處理方式可以對比看出赫夫曼編碼的優(yōu)越性。
以下給出實現(xiàn)哈夫曼編碼需要的各個方法:
1、先創(chuàng)建節(jié)點(diǎn)對象:
// 為了排序,必須實現(xiàn)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、需要先實現(xiàn)統(tǒng)計輸入的字符串中各個字符的個數(shù):
/** * //統(tǒng)計字符串中每個字符出現(xiàn)的次數(shù)和空格出現(xiàn)次數(shù) * * @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中的數(shù)據(jù)存入Node節(jié)點(diǎn)中 //先將map轉(zhuǎn)為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中的數(shù)據(jù)存入Node節(jié)點(diǎn)中 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、創(chuàng)建赫夫曼樹:
/** * 創(chuàng)建huffman樹 * * @param nodeList 排好序的集合 * @return 返回huffman樹的根節(jié)點(diǎn) */ public static Node createHuffmanTree(List<Node> nodeList) { //循環(huán)創(chuàng)建huffman樹 while (nodeList.size() > 1) { //1、每次取出集合中的前兩個節(jié)點(diǎn) Node left = nodeList.get(0); Node right = nodeList.get(1); //2、將他們的權(quán)值相加構(gòu)成一個新的節(jié)點(diǎn)并作為他們的父節(jié)點(diǎn) Node parent = new Node(null, left.weight + right.weight); parent.left = left; parent.right = right; //3、刪除已經(jīng)處理過的節(jié)點(diǎn) nodeList.remove(left); nodeList.remove(right); //4、將新的節(jié)點(diǎn)存入集合中 nodeList.add(parent); //5、重新給集合排序,循環(huán)這5步即可,直到集合中只有一個節(jié)點(diǎn),這就是huffman樹的根節(jié)點(diǎn) Collections.sort(nodeList); //觀察測試輸出 //System.out.println(nodeList); } //返回huffman樹的根節(jié)點(diǎn) return nodeList.get(0); }
4、根據(jù)創(chuàng)建的赫夫曼樹進(jìn)行字符串編碼壓縮:
/** * 根據(jù)huffman樹來進(jìn)行數(shù)據(jù)編碼壓縮 * 思路: * 1、只要向左子樹走就代表0,向右子樹走就代表1 * 2、從頭節(jié)點(diǎn)走到對于字符在的節(jié)點(diǎn)位置的路徑對于的0和1組成的二進(jìn)制編碼就是壓縮后該字符對于的編碼 * 3、需要定義一個StringBuffer來存儲某個節(jié)點(diǎn)的路徑對于的編碼 * 4、將赫夫曼編碼表存放在Map<Byte,String>中 * * @param node huffman樹的根節(jié)點(diǎn) * @param stringBuffer 用于拼接路徑 * @param code 路徑:左子節(jié)點(diǎn)是0,右子節(jié)點(diǎn)是1 * @return */ private static void getHuffmanCompressionCode(Node node, String code, StringBuffer stringBuffer) { StringBuffer stringBuffer1 = new StringBuffer(stringBuffer); stringBuffer1.append(code); //如果為空,不進(jìn)行處理 if (node != null) { //判斷node是葉子節(jié)點(diǎn)還是非葉子節(jié)點(diǎn) if (node.data == null) { //非葉子節(jié)點(diǎn) //向左遞歸 getHuffmanCompressionCode(node.left, "0", stringBuffer1); //向右遞歸 getHuffmanCompressionCode(node.right, "1", stringBuffer1); } else { //葉子節(jié)點(diǎn) //說明這條路走到尾了,將路徑編碼存入map中 huffmanCodes.put(node.data, stringBuffer1.toString()); } } }
5、得到壓縮后的赫夫曼編碼長度(二進(jìn)制位數(shù)):
/** * @return 得到壓縮后的赫夫曼編碼大小 */ public static int getStrCodeSize() { int size = 0; //將兩個map集合都轉(zhuǎn)為set集合 Set<Map.Entry<Character, Integer>> mapSet = map.entrySet(); Set<Map.Entry<Byte, String>> huffmanMapSet = huffmanCodes.entrySet(); //循環(huán)兩個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()); //節(jié)約時間,之間退出內(nèi)循環(huán)。因為不可能有一對多的關(guān)系。 break; } } } return size; }
6、編寫一個方法,將字符串對應(yīng)的byte[]數(shù)組,通過生成的赫夫曼編碼表,返回一個赫夫曼編碼壓縮后的byte[]
/** * 編寫一個方法,將字符串對應(yīng)的 byte[] 數(shù)組,通過生成的赫夫曼編碼表,返回一個赫夫曼編碼 壓縮后的byte[] * * @param bytes 這時原始的字符串對應(yīng)的 byte[] * @param huffmanCodes 生成的赫夫曼編碼 map * @return 返回赫夫曼編碼處理后的 byte[] * 舉例: String content = "i like like like java do you like a java"; =》 byte[] contentBytes = content.getBytes(); * 返 回 的 是 字 符 串: * "1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000 * 101111111100110001001010011011100" * => 對應(yīng)的 byte[] huffmanCodeBytes ,即 8 位對應(yīng)一個 byte,放入到 huffmanCodeBytes * huffmanCodeBytes[0] = 10101000(補(bǔ)碼) => byte [推導(dǎo) 10101000=> 10101000 - 1 => 10100111(反 * 碼)=> 11011000(源碼) = -88 ] */ public static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) { //1、先利用赫夫曼編碼表將傳進(jìn)來的bytes數(shù)組轉(zhuǎn)為壓縮后的編碼 StringBuffer stringBuffer1 = new StringBuffer(); for (byte b : bytes) { stringBuffer1.append(huffmanCodes.get(b)); } //輸出字符串壓縮成赫夫曼編碼后對應(yīng)的二進(jìn)制編碼 //System.out.println("輸出字符串壓縮成赫夫曼編碼后對應(yīng)的二進(jìn)制編碼:" + stringBuffer1 + "長度為:" + stringBuffer1.length()); //獲取byte數(shù)組的長度,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 轉(zhuǎn)成一個 byte,放入到 huffmanBytes中 //該方法是將strByte對應(yīng)的01字符串傳換為十進(jìn)制 //第二個參數(shù)表示基數(shù)(radix),表示轉(zhuǎn)換為radix進(jìn)制 huffmanBytes[index] = (byte) Integer.parseInt(strByte, 2); index++; } return huffmanBytes; }
其實也可以不用寫5中的方法,可以直接在6中輸出stringBuffer1.length()就可以得到壓縮后的二進(jìn)制位數(shù)。不過也可以把5當(dāng)作一種解決的算法。
以下給出完整的代碼:
import java.util.*; /** * 實現(xiàn)huffman編碼 */ public class HuffmanCode { //將赫夫曼編碼表存放在Map<Byte,String>中 public static Map<Byte, String> huffmanCodes = new HashMap<>(); //需要定義一個StringBuffer來存儲某個節(jié)點(diǎn)的路徑對于的編碼 public static StringBuffer stringBuffer = new StringBuffer(); //創(chuàng)建一個map,來保存每個字符以及他對應(yīng)出現(xiàn)的次數(shù) 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(); // 把輸入的字符串轉(zhuǎn)為byte數(shù)組,在byte數(shù)組中存儲的是字符對應(yīng)的ASCII碼值 byte[] strBytes = str.getBytes(); System.out.println(str + ",壓縮成赫夫曼編碼前對應(yīng)的byte數(shù)組:" + Arrays.toString(strBytes)); //計算壓縮前的字符串有多少位二進(jìn)制數(shù) int compressionBeforeCodeSize = str.length() * 8 + str.length() - 1; System.out.println(str + ",壓縮前的字符串大小:" + compressionBeforeCodeSize); //統(tǒng)計字符串中每個字符出現(xiàn)的次數(shù)和空格出現(xiàn)次數(shù)并存入Node節(jié)點(diǎn)中 List<Node> nodeList = totalCharCounts(str); //創(chuàng)建huffman樹 Node root = createHuffmanTree(nodeList); //得到壓縮后的編碼 getHuffmanCompressionCode(root, "", stringBuffer); //輸出赫夫曼編碼表 System.out.println(str + ",對應(yīng)的赫夫曼編碼表:"); 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 + ",壓縮成赫夫曼編碼后對應(yīng)的byte數(shù)組:" + Arrays.toString(bytes)); } /** * @return 得到壓縮后的赫夫曼編碼大小 */ public static int getStrCodeSize() { int size = 0; //將兩個map集合都轉(zhuǎn)為set集合 Set<Map.Entry<Character, Integer>> mapSet = map.entrySet(); Set<Map.Entry<Byte, String>> huffmanMapSet = huffmanCodes.entrySet(); //循環(huán)兩個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()); //節(jié)約時間,之間退出內(nèi)循環(huán)。因為不可能有一對多的關(guān)系。 break; } } } return size; } /** * 根據(jù)huffman樹來進(jìn)行數(shù)據(jù)編碼壓縮 * 思路: * 1、只要向左子樹走就代表0,向右子樹走就代表1 * 2、從頭節(jié)點(diǎn)走到對于字符在的節(jié)點(diǎn)位置的路徑對于的0和1組成的二進(jìn)制編碼就是壓縮后該字符對于的編碼 * 3、需要定義一個StringBuffer來存儲某個節(jié)點(diǎn)的路徑對于的編碼 * 4、將赫夫曼編碼表存放在Map<Byte,String>中 * * @param node huffman樹的根節(jié)點(diǎn) * @param stringBuffer 用于拼接路徑 * @param code 路徑:左子節(jié)點(diǎn)是0,右子節(jié)點(diǎn)是1 * @return */ private static void getHuffmanCompressionCode(Node node, String code, StringBuffer stringBuffer) { StringBuffer stringBuffer1 = new StringBuffer(stringBuffer); stringBuffer1.append(code); //如果為空,不進(jìn)行處理 if (node != null) { //判斷node是葉子節(jié)點(diǎn)還是非葉子節(jié)點(diǎn) if (node.data == null) { //非葉子節(jié)點(diǎn) //向左遞歸 getHuffmanCompressionCode(node.left, "0", stringBuffer1); //向右遞歸 getHuffmanCompressionCode(node.right, "1", stringBuffer1); } else { //葉子節(jié)點(diǎn) //說明這條路走到尾了,將路徑編碼存入map中 huffmanCodes.put(node.data, stringBuffer1.toString()); } } } /** * //統(tǒng)計字符串中每個字符出現(xiàn)的次數(shù)和空格出現(xiàn)次數(shù) * * @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中的數(shù)據(jù)存入Node節(jié)點(diǎn)中 //先將map轉(zhuǎn)為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中的數(shù)據(jù)存入Node節(jié)點(diǎn)中 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; } /** * 創(chuàng)建huffman樹 * * @param nodeList 排好序的集合 * @return 返回huffman樹的根節(jié)點(diǎn) */ public static Node createHuffmanTree(List<Node> nodeList) { //循環(huán)創(chuàng)建huffman樹 while (nodeList.size() > 1) { //1、每次取出集合中的前兩個節(jié)點(diǎn) Node left = nodeList.get(0); Node right = nodeList.get(1); //2、將他們的權(quán)值相加構(gòu)成一個新的節(jié)點(diǎn)并作為他們的父節(jié)點(diǎn) Node parent = new Node(null, left.weight + right.weight); parent.left = left; parent.right = right; //3、刪除已經(jīng)處理過的節(jié)點(diǎn) nodeList.remove(left); nodeList.remove(right); //4、將新的節(jié)點(diǎn)存入集合中 nodeList.add(parent); //5、重新給集合排序,循環(huán)這5步即可,直到集合中只有一個節(jié)點(diǎn),這就是huffman樹的根節(jié)點(diǎn) Collections.sort(nodeList); //觀察測試輸出 //System.out.println(nodeList); } //返回huffman樹的根節(jié)點(diǎn) return nodeList.get(0); } /** * 編寫一個方法,將字符串對應(yīng)的byte[]數(shù)組,通過生成的赫夫曼編碼表,返回一個赫夫曼編碼壓縮后的byte[] * * @param bytes 這時原始的字符串對應(yīng)的 byte[] * @param huffmanCodes 生成的赫夫曼編碼 map * @return 返回赫夫曼編碼處理后的 byte[] * 舉例: String content = "i like like like java do you like a java"; =》 byte[] contentBytes = content.getBytes(); * 返 回 的 是 字 符 串: * "1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000 * 101111111100110001001010011011100" * => 對應(yīng)的 byte[] huffmanCodeBytes ,即 8 位對應(yīng)一個 byte,放入到 huffmanCodeBytes * huffmanCodeBytes[0] = 10101000(補(bǔ)碼) => byte [推導(dǎo) 10101000=> 10101000 - 1 => 10100111(反 * 碼)=> 11011000(源碼) = -88 ] */ public static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) { //1、先利用赫夫曼編碼表將傳進(jìn)來的bytes數(shù)組轉(zhuǎn)為壓縮后的編碼 StringBuffer stringBuffer1 = new StringBuffer(); for (byte b : bytes) { stringBuffer1.append(huffmanCodes.get(b)); } //輸出字符串壓縮成赫夫曼編碼后對應(yīng)的二進(jìn)制編碼 //System.out.println("輸出字符串壓縮成赫夫曼編碼后對應(yīng)的二進(jìn)制編碼:" + stringBuffer1 + "長度為:" + stringBuffer1.length()); //獲取byte數(shù)組的長度,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 轉(zhuǎn)成一個 byte,放入到 huffmanBytes中 //該方法是將strByte對應(yīng)的01字符串傳換為十進(jìn)制 //第二個參數(shù)表示基數(shù)(radix),表示轉(zhuǎn)換為radix進(jìn)制 huffmanBytes[index] = (byte) Integer.parseInt(strByte, 2); index++; } return huffmanBytes; } }
以下是我的測試結(jié)果輸出:
輸入的字符串: i like like like java do you like a java
輸入的字符串: asdjkj ;lkjsadlkj kj ()dasd
到此這篇關(guān)于Java利用哈夫曼編碼實現(xiàn)字符串壓縮的文章就介紹到這了,更多相關(guān)Java字符串壓縮內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
Java對象轉(zhuǎn)json JsonFormat注解
這篇文章主要介紹了Java對象轉(zhuǎn)json JsonFormat注解,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2020-05-05springMvc和mybatis-plus中枚舉值和字段的映射
這篇文章主要為大家介紹了springMvc和mybatis-plus中枚舉值和字段的映射示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2023-05-05Java Eclipse進(jìn)行斷點(diǎn)調(diào)試的方法
本篇文章主要介紹了Java Eclipse進(jìn)行斷點(diǎn)調(diào)試的方法,小編覺得挺不錯的,現(xiàn)在分享給大家,也給大家做個參考。一起跟隨小編過來看看吧2017-11-11Java利用DelayQueue實現(xiàn)延遲任務(wù)代碼實例
這篇文章主要介紹了Java利用DelayQueue實現(xiàn)延遲任務(wù)代碼實例,DelayQueue?是一個支持延時獲取元素的阻塞隊列,?內(nèi)部采用優(yōu)先隊列?PriorityQueue?存儲元素,同時元素必須實現(xiàn)?Delayed?接口,需要的朋友可以參考下2023-12-12SpringBoot實現(xiàn)接口數(shù)據(jù)的加解密功能
這篇文章主要介紹了SpringBoot實現(xiàn)接口數(shù)據(jù)的加解密功能,對接口的加密解密操作主要有兩種實現(xiàn)方式,文中給大家詳細(xì)介紹,需要的朋友可以參考下2019-10-10springboot使用Thymeleaf報錯常見的幾種解決方案
這篇文章主要介紹了springboot使用Thymeleaf報錯常見的幾種解決方案,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教2022-11-11