介紹
上一篇文章我們講到了哈夫曼樹寂诱，相信看官們對其也有一定的了解了
http://www.reibang.com/p/bad3472aae5a（需先理解何為哈夫曼樹）
哈夫曼編碼(Huffman Coding)，又稱霍夫曼編碼激蹲，是一種編碼方式腔呜，哈夫曼編碼是可變字長編碼(VLC)的一種叁温。Huffman于1952年提出一種編碼方法，該方法完全依據(jù)字符出現(xiàn)概率來構(gòu)造異字頭的平均長度最短的碼字核畴，有時稱之為最佳編碼膝但，一般就叫做Huffman編碼。
舉個例子
我們有 A, B, C, D 四個字符谤草，他們的出現(xiàn)頻率分別是1跟束，2莺奸，3，4（這也是他們的權(quán)值）
這個時候冀宴，我們根據(jù)哈夫曼樹的生成方式灭贷，將其構(gòu)建成一個哈夫曼樹
huffman1.png
之后，我們再給它的路徑添加上代碼（左分支0略贮，右分支1）
最后得出 A甚疟，B，C刨肃，D的哈夫曼編碼分別是100古拴，101，11真友，0
huffman2.png
java代碼實現(xiàn)
package tree;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
/**
* Created by Sheldon on 2019/4/11.
* Project Name: alstudy.
* Package Name: tree.
*/
// 數(shù)據(jù)類
class Data{
public char key;
public int value;
public Data(char key, int value){
this.key = key;
this.value = value;
}
}
// 結(jié)點結(jié)構(gòu)
class CodeNode{
// 權(quán)值
Data data;
// 左結(jié)點
CodeNode leftChild;
// 右結(jié)點
CodeNode rightChild;
public CodeNode(Data data){
this.data = data;
}
public CodeNode(Data data, CodeNode leftChild, CodeNode rightChild){
this.leftChild = leftChild;
this.rightChild = rightChild;
this.data = data;
}
}
public class HuffmanCode {
/**
* 創(chuàng)建哈弗曼樹
* @param datas
* @return
*/
public static CodeNode createHuffmanTree(Data[] datas){
// 將傳進(jìn)來的數(shù)組元素創(chuàng)建成結(jié)點
List<CodeNode> nodes = new ArrayList<>();
for (Data d: datas){
nodes.add(new CodeNode(d));
}
// 循環(huán)處理以下操作
while (nodes.size()>1){
// 依據(jù)權(quán)值排序（選擇排序算法）
CodeNode temp;
for (int i=0; i<nodes.size(); i++){
int k = i;
for (int j=nodes.size()-1; j>i; j--){
if (nodes.get(j).data.value < nodes.get(k).data.value){
k = j;
}
}
temp = nodes.get(i);
nodes.set(i, nodes.get(k));
nodes.set(k, temp);
}
// 取出權(quán)值最小的兩個二叉樹
CodeNode leftNode = nodes.get(0);
CodeNode rightNode = nodes.get(1);
// 創(chuàng)建新的二叉樹
Data d = new Data('#', leftNode.data.value+rightNode.data.value);
CodeNode parent = new CodeNode(d, leftNode, rightNode);
// 移除取出的二叉樹
nodes.remove(leftNode);
nodes.remove(rightNode);
// 放入原來的二叉樹集合中
nodes.add(parent);
}
return nodes.get(0);
}
static StringBuilder sb = new StringBuilder(); // 存儲編碼字符
static Map<String, String> huffcodes = new HashMap<>(); // 存儲編碼表
/**
* 創(chuàng)建哈夫曼編碼編碼表
* @param codeNode
* @return
*/
public static Map<String, Integer> createCode(CodeNode codeNode){
if (codeNode==null){
return null;
}
getCode(codeNode.leftChild, "0", sb);
getCode(codeNode.rightChild, "1", sb);
return null;
}
public static void getCode(CodeNode codeNode, String code, StringBuilder sb){
StringBuilder sb2 = new StringBuilder(sb);
sb2.append(code);
if (codeNode.data==null||codeNode.data.key=='#'){
getCode(codeNode.leftChild,"0",sb2);
getCode(codeNode.rightChild,"1",sb2);
}else {
huffcodes.put(String.valueOf(codeNode.data.key),sb2.toString());
}
}
public static void main(String[] args) {
String plaintext = "ABCBCDCDDD";
char[] ch = plaintext.toCharArray();
Map<String,Integer> textMap = new HashMap<>();
// 統(tǒng)計字符出現(xiàn)次數(shù)
for (char c : ch) {
String cTo = String.valueOf(c);
if (!textMap.containsKey(cTo)) {
textMap.put(cTo, 1);
} else {
textMap.put(cTo, textMap.get(cTo) + 1);
}
}
System.out.println(textMap.entrySet());
// 創(chuàng)建結(jié)點數(shù)組
Data[] datas = new Data[textMap.size()];
int i = 0;
// 結(jié)點數(shù)組的元素對象創(chuàng)建
for (Map.Entry<String, Integer> entry: textMap.entrySet()) {
datas[i] = new Data(entry.getKey().charAt(0),entry.getValue());
i++;
}
// 創(chuàng)建哈夫曼樹
CodeNode root = HuffmanCode.createHuffmanTree(datas);
// 創(chuàng)建哈夫曼編碼表
HuffmanCode.createCode(root);
// 輸出哈夫曼樹
System.out.println(HuffmanCode.huffcodes);
StringBuilder textSb = new StringBuilder();
// 加密文本信息
for (char c: ch) {
textSb.append(HuffmanCode.huffcodes.get(String.valueOf(c)));
}
// 輸出加密前的信息
System.out.println("加密前："+plaintext);
// 輸出加密后的信息
System.out.println("加密后："+textSb);
}
}
結(jié)果
結(jié)果.png
