分类: Java
2021-04-21 17:21:00
赫夫曼算法类 Huffman.java
/**
* @Author: ltx
* @Description: 赫夫曼编码
*/
public class Huffman {
Map
/**
* 中序遍历(前序或后序也行)
* 得到huffman编码
*
* @param node 节点
* @param sb StringBuilder
*/
public void getCodeByMidOrder(Node node, StringBuilder sb) {
if (node.left != null) {
//往左走+'0'
sb.append("0");
getCodeByMidOrder(node.left, sb);
}
//叶子节点
if (node.left == null && node.right == null) {
// System.out.print(node + ":" + sb + ", ");
codeMap.put(node.value, sb.toString());
}
if (node.right != null) {
//往右走+'1'
sb.append("1");
getCodeByMidOrder(node.right, sb);
}
//回溯向上走减少一个字符
if (sb.length() > 0) {
sb.deleteCharAt(sb.length() - 1);
}
}
public Node getHuffmanTree(List
Collections.sort(nodes);
// System.out.println(nodes);
while (nodes.size() > 1) {
//左叶子-数组最小值
Node leafLeft = nodes.remove(0);
//右叶子-数组次小值
Node leafRight = nodes.remove(0);
//父节点=数组最小值+数组次小值
Node parentNode = new Node(null, leafLeft.weight + leafRight.weight);
parentNode.left = leafLeft;
parentNode.right = leafRight;
//新的节点添加到list里面
nodes.add(parentNode);
Collections.sort(nodes);
}
return nodes.get(0);
}
/**
* 获取各个字符权重(字符个数)
*
* @param str
* @return
*/
public List
Map
char[] chs = str.toCharArray();
for (char c : chs) {
//数量
Integer count = charNumMap.get(c);
if (count == null) {
charNumMap.put(c, 1);
} else {
charNumMap.put(c, count + 1);
}
}
// System.out.println(charNumMap);
List
//创建节点List
for (char c : charNumMap.keySet()) {
nodes.add(new Node(c, charNumMap.get(c)));
}
return nodes;
}
/**
* 编码
* 根据赫夫曼编码表,对原始数据做转换
*
* @param str 原始字符串
* @return
*/
public String encoding(String str) {
StringBuilder sb = new StringBuilder();
char[] chs = str.toCharArray();
for (char c : chs) {
sb.append(codeMap.get(c));
}
return sb.toString();
}
/**
* 解码
*
* @return
*/
public String decode(String encodStr) {
//翻转codeMap
Map
for (char c : codeMap.keySet()) {
encodeMap.put(codeMap.get(c), c);
}
char[] chs = encodStr.toCharArray();
int j = 0;
StringBuilder res = new StringBuilder();
while (j < encodStr.length() - 1) {
StringBuilder sb = new StringBuilder();
Character cr;
//匹配出字符串
while ((cr = encodeMap.get(sb.toString())) == null) {
sb.append(chs[j]);
j++;
}
res.append(cr);
}
return res.toString();
}
public static void main(String[] args) {
Huffman huffman = new Huffman();
System.out.println("原始数据:");
//需要压缩的串
String str = "i like like like java do you like a java";
System.out.println(str);
//1.获得字符权重List
List
//[ :9, a:5, d:1, e:4, u:1, v:2, i:5, y:1, j:2, k:4, l:4, o:2]
System.out.println("节点权重列表:");
System.out.println(nodes);
//2.构造赫夫曼树
Node root = huffman.getHuffmanTree(nodes);
//3.获得赫夫曼编码表
huffman.getCodeByMidOrder(root, new StringBuilder(""));
System.out.println("赫夫曼编码表:");
//得到赫夫曼编码表
//{ =01, a=100, d=11000, u=11001, e=1110, v=11011, i=101, y=11010, j=0010, k=1111, l=000, o=0011}
System.out.println(huffman.codeMap);
//4.压缩编码
String encodStr = huffman.encoding(str);
System.out.println("压缩后数据:");
//1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000101111111100110001001010011011100
System.out.println(encodStr);
//5.解压
String res = huffman.decode(encodStr);
System.out.println("解压后数据:");
//打印最终结果
//i like like like java do you like a java
System.out.println(res);
}
}