Huffman Coding
- 簡介
-
- 3種編碼原理
- 代碼實作
簡介
- 赫夫曼編碼是可變字長編碼(VLC)的一種, 常用于資料檔案壓縮. 其壓縮通常在20%~90%之間
3種編碼原理
- 在通信領域中資訊的處理方式
- 定長編碼:
- 變長編碼:
* 變長編碼的缺點是編碼格式重疊無法避免, 即不能比對重複的編碼
3) 赫夫曼編碼:
代碼實作
- 字元串解壓縮
public class HuffmanCodeApp {
public static void main(String[] args) {
String content = "i like like like java do you like a java";
System.out.println("原資料長度 " + content.length() + ", 内容 " + content);
/** 原資料内容轉 bytes*/
byte[] contentBytes = content.getBytes();
System.out.println("原資料轉 bytes後的數組長度 " + contentBytes.length + ", 内容 " + Arrays.toString(contentBytes));
/** 把原資料的 bytes數組進行壓縮*/
byte[] huffmanCodesBytes= zip(contentBytes);
System.out.println("壓縮後的内容長度 " + huffmanCodesBytes.length + ", 内容 " + Arrays.toString(huffmanCodesBytes));
/** 解壓(解碼)*/
byte[] sourceBytes = unzip(huffmanCodes, huffmanCodesBytes);
System.out.println("解壓還原原資料内容 " + new String(sourceBytes));
}
/** Map形式, 生成哈夫曼編碼表 {32=01, 97=100, 100=11000, 117=11001, 101=1110, 118=11011, 105=101, 121=11010, 106=0010, 107=1111, 108=000, 111=0011}*/
static Map<Byte, String> huffmanCodes = new HashMap<>();
/** 采用赫夫曼編碼壓縮資料的方法
* @param bytes 原資料對應的位元組數組(将此位元組數組進行壓縮)
* @return 采用赫夫曼編碼方式處理過的(壓縮後的)位元組數組*/
private static byte[] zip(byte[] bytes) {
/** 生成節點清單*/
List<Node> nodes = getNodes(bytes);
/** 建立的赫夫曼樹*/
Node huffmanTreeRoot = createHuffmanTree(nodes);
/** 開始處理赫夫曼樹 root的左子樹*/
createHuffmanCode(huffmanTreeRoot.left, "0", null);
/** 開始處理赫夫曼樹 root的右子樹*/
createHuffmanCode(huffmanTreeRoot.right, "1", null);
/** 将原資料字元對應位元組, 按序周遊, 從 huffmanCodes擷取每個位元組的路徑, 拼接成赫夫曼編碼*/
StringBuilder _path = new StringBuilder();
for(byte b: bytes) {
_path.append(huffmanCodes.get(b));
}
// _path輸出 => 1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000101111111100110001001010011011100
// [105(i), 32( ), 108(l), 105(i)... => 101 01 000 101 ... => 也就是拼接後 10101000101...
// 将赫夫曼編碼當成位元組, 計算長度(每個位元組占8位)
// int len = (_path.length() + 7) / 8;
int len;
if(_path.length() % 8 == 0) {
len = _path.length() / 8;
} else {
len = _path.length() / 8 + 1;
}
byte[] huffmanCodeBytes = new byte[len];
int index = 0;
for (int i = 0; i < _path.length(); i += 8) {
String strByte;
if(i + 8 > _path.length()) { /** 最後輪不夠8位時*/
strByte = _path.substring(i);
}else{
strByte = _path.substring(i, i + 8);
}
/** 将 strByte轉成一個 byte; 轉成二進制*/
huffmanCodeBytes[index] = (byte) Integer.parseInt(strByte, 2);
index++;
}
return huffmanCodeBytes;
}
/** @param bytes 接收原資料的位元組數組*/
private static List<Node> getNodes(byte[] bytes) {
ArrayList<Node> nodes = new ArrayList<>();
/** 将原資料的位元組數組周遊
* - 統計每一個位元組出現的次數, map(key位元組碼, value出現次數)*/
Map<Byte, Integer> counts = new HashMap<>();
for (byte b : bytes) {
Integer count = counts.get(b);
if (count == null) {
counts.put(b, 1);
} else {
counts.put(b, count + 1);
}
}
/** 在上面統計過相同位元組的 map, 将 map.key(位元組碼)當作節點資料本身, map.value(指定位元組的重複次數)當作節點權值, 循環制作節點清單
* 其中位元組碼會用于赫夫曼*/
for(Map.Entry<Byte, Integer> entry: counts.entrySet()) {
nodes.add(new Node(entry.getKey(), entry.getValue()));
}
/** 此清單用于生成赫夫曼樹*/
return nodes;
}
/** 建立的赫夫曼樹方法*/
private static Node createHuffmanTree(List<Node> nodes) {
while(nodes.size() > 1) {
/** 從小到大排序*/
Collections.sort(nodes);
/** 取出根節點權值最小的兩顆二叉樹*/
//(1) 取出權值最小的結點(二叉樹)
Node leftNode = nodes.get(0);
//(2) 取出權值第二小的結點(二叉樹)
Node rightNode = nodes.get(1);
//(3) 建立一顆新的二叉樹, 此樹的根節點, 沒有 data, 隻有權值
Node parent = new Node(null, leftNode.weight + rightNode.weight);
parent.left = leftNode;
parent.right = rightNode;
//(4) 将 parent加到 List中
nodes.add(parent);
//(5) 從 List中删除處理過的二叉樹
nodes.remove(leftNode);
nodes.remove(rightNode);
}
/** 最後傳回制作完成的赫夫曼樹的 root結點*/
return nodes.get(0);
}
/** 功能: 将傳入的 node節點的所有葉子節點的赫夫曼編碼得到，并放入到 huffmanCodes集合
* @param node 傳入節點
* @param code 路徑: 左子節點是0, 右子節點1
*/
private static void createHuffmanCode(Node node, String code, StringBuilder path) {
if(node != null) {
StringBuilder _path = new StringBuilder(path == null ? "": path.toString());
_path.append(code);
/** 判斷目前 node是否為非葉子節點*/
if(node.data == null) {
/** 目前 node為非葉子結點時
* - 繼續遞歸向左右處理*/
createHuffmanCode(node.left, "0", _path);
createHuffmanCode(node.right, "1", _path);
} else {
/** 抵達到葉子節點, 将節點值(原資料的指定位元組碼)和到達此節點的路徑加到 huffmanCodes集合中*/
huffmanCodes.put(node.data, _path.toString());
}
}
}
/* 解碼方法
* @param huffmanCodeBytes 赫夫曼編碼得到的位元組數組
* @return 傳回原資料對應的位元組數組*/
private static byte[] unzip(Map<Byte, String> huffmanCodes, byte[] huffmanCodeBytes) {
/** 将采用赫夫曼編碼生成的赫夫曼編碼位元組數組(huffmanCodeBytes), 重新解析轉成赫夫曼編碼字元串*/
StringBuilder _path = new StringBuilder();
for(int i = 0; i < huffmanCodeBytes.length; i++) {
byte b = huffmanCodeBytes[i];
/** 判斷是否為最後的位元組*/
boolean flag = (i == huffmanCodeBytes.length - 1);
String strByte = byteToBitString(!flag, b);
_path.append(strByte);
}
// _path => 1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000101111111100110001001010011011100
/** 将赫夫曼編碼表 map, key/vlaue調過來, 為反向查詢 {32=01, 97=100... => {01=32, 100=97...*/
Map<String, Byte> map = new HashMap<>();
for(Map.Entry<Byte, String> entry: huffmanCodes.entrySet()) {
map.put(entry.getValue(), entry.getKey());
}
/** List中存放, 解析後的原始字元的位元組碼*/
List<Byte> list = new ArrayList<>();
/** 将赫夫曼編碼 _path路徑字元串, 一個路徑字元->一個路徑字元...做字元串掃描, 判斷 huffmanCodes中是否存在*/
for(int i = 0; i < _path.length();) {
int count = 1; // 小的計數器
boolean flag = true;
Byte b = null;
while(flag) {
/** 赫夫曼編碼中每個路徑的起始下标 i保持不變, 移動到 count位置, 一一比對, 判斷 huffmanCodes中是否存在*/
String key = _path.substring(i, i+count);
b = map.get(key);
if(b == null) { /** 說明沒有比對到*/
count++;
}else {
/** 比對到了, 結束此 while, 将比對到的位元組碼加到 List, 繼續往後掃描*/
flag = false;
}
}
list.add(b);
/** 下次掃描的開始下标是這次結束的下标*/
i += count;
}
/** 将解析後得到的原資料位元組 List, 轉存到 byte數組中後傳回*/
byte b[] = new byte[list.size()];
for(int i = 0;i < b.length; i++) {
b[i] = list.get(i);
}
return b;
}
/** 将傳入的 b轉成一個二進制的字元串
* @param flag 标志是否需要補高位 如是 true就補高位, 否則不補. 最後一個位元組不做補高位操作
* @param b 傳入的 byte
* @return 傳回 b對應二進制的字元串(按補碼傳回)*/
private static String byteToBitString(boolean flag, byte b) {
/** 将 b轉成 int*/
int temp = b;
if(flag) {
/** 如果是正數, 需要補高位*/
temp |= 256; // 按位與 256 1 0000 0000 | 0000 0001 => 1 0000 0001
/** 例 byte 77 => (temp |= 256) => temp=333*/
}
String str = Integer.toBinaryString(temp); /** 例 int 333 => 101001101*/
if(flag) {
return str.substring(str.length() - 8); /** 例 101001101 => 01001101*/
} else {
return str;
}
}
}
/** 定義結點*/
class Node implements Comparable<Node> {
/** 存放資料本身, 比如 'a' => 97,' ' => 32*/
Byte data;
/** 權值, 表示字元出現的次數*/
int weight;
Node left;
Node right;
public Node(Byte data, int weight) {
this.data = data;
this.weight = weight;
}
@Override
public int compareTo(Node o) {
/** 表示從小到大排序*/
return this.weight - o.weight;
}
public String toString() {
return "Node [data = " + data + " weight=" + weight + "]";
}
}
輸出:
> 原資料長度 40, 内容 i like like like java do you like a java
> 原資料轉 bytes後的數組長度 40, 内容 [105, 32, 108, 105, 107, 101, 32, 108, 105, 107, 101, 32, 108, 105, 107, 101, 32, 106, 97, 118, 97, 32, 100, 111, 32, 121, 111, 117, 32, 108, 105, 107, 101, 32, 97, 32, 106, 97, 118, 97]
> 壓縮後的内容長度 17, 内容 [-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, 28]
> 解壓還原原資料内容 i like like like java do you like a java
- 檔案解壓縮
public static void main(String[] args) {
String srcFile = "/Users/quanchunlin/Desktop/test.txt";
String dstFile = "/Users/quanchunlin/Desktop/test.zip";
zipFile(srcFile, dstFile);
System.out.println("壓縮檔案成功!");
// String zipFile = "/Users/quanchunlin/Desktop/test.zip";
// String dstFile = "/Users/quanchunlin/Desktop/test.txt";
// unZipFile(zipFile, dstFile);
// System.out.println("解壓檔案成功!");
}
/** 壓縮檔案方法
* @param srcFile 傳入原檔案包括路徑
* @param dstFile 壓縮後, 将要放置的新目錄及檔案名稱*/
public static void zipFile(String srcFile, String dstFile) {
OutputStream os = null;
ObjectOutputStream oos = null;
FileInputStream is = null;
try {
/** 建立檔案的輸入流*/
is = new FileInputStream(srcFile);
/** 建立與原檔案大小一樣的 byte[]*/
byte[] b = new byte[is.available()];
/** 讀取檔案到 byte[] b中*/
is.read(b);
/** 将原檔案位元組内容進行壓縮*/
byte[] huffmanBytes = zip(b);
/** 建立輸出流, 存放壓縮檔案*/
os = new FileOutputStream(dstFile);
/** 建立對象的輸出流*/
oos = new ObjectOutputStream(os);
/** 将赫夫曼編碼後的位元組數組寫入壓縮檔案*/
oos.writeObject(huffmanBytes);
/** 将赫夫曼編碼一并寫入到壓縮檔案中*/
oos.writeObject(huffmanCodes);
} catch (Exception e) {
System.out.println(e.getMessage());
} finally {
try {
is.close();
oos.close();
os.close();
} catch (Exception e) {
System.out.println(e.getMessage());
}
}
}
/** 解壓檔案方法
* @param zipFile 準備解壓的檔案
* @param dstFile 将檔案解壓到哪個路徑
*/
public static void unZipFile(String zipFile, String dstFile) {
InputStream is = null;
ObjectInputStream ois = null;
//定義檔案的輸出流
OutputStream os = null;
try {
/** 建立檔案的輸入流*/
is = new FileInputStream(zipFile);
/** 建立對象的輸入流*/
ois = new ObjectInputStream(is);
/** 讀取 huffmanCodeBytes*/
byte[] huffmanBytes = (byte[]) ois.readObject();
/** 讀取赫夫曼編碼表*/
Map<Byte, String> huffmanCodes = (Map<Byte,String>) ois.readObject();
/** 将赫夫曼編碼進行解壓*/
byte[] bytes = unzip(huffmanCodes, huffmanBytes);
/** 建立輸出流, 存放解壓後的檔案*/
os = new FileOutputStream(dstFile);
/** 将解碼後的原資料位元組數組寫入到 dstFile件中*/
os.write(bytes);
} catch (Exception e) {
System.out.println(e.getMessage());
} finally {
try {
os.close();
ois.close();
is.close();
} catch (Exception e) {
System.out.println(e.getMessage());
}
}
}
如果您覺得有幫助，歡迎點贊哦 ~ 謝謝!!