package dataStruct.树;
import java.util.*;
public class 哈夫曼编码 {
public static void main(String[] args) {
//创建字符数zu
String str = "i like like like java do you like a java";
System.out.println(Arrays.toString(huffmanZip(str)));//压缩后变成17个数,从40 压缩到 17 个
}
//解压需要二进制知识,博主知识浅薄
//将以下全部压缩方法进行封装
private static byte[] huffmanZip(String str){
//将字符串转换成字符数组
char[] chars = str.toCharArray();
//将字符数组转换成list
List<CodeNode> nodeList = getCodeNodes(chars);
Collections.sort(nodeList);
//将list转换成huffman树
CodeNode root = creatTree(nodeList);
//将huffman树转成成huffman编码
toCode(root,"",stringBuilder);
//压缩huffman编码,并将byte数组返回
return zip(chars,map);
}
//统计字符数组中字符出现的个数,存入哈市表中,并转换链表返回
public static List<CodeNode> getCodeNodes(char[] chars){
//1.创建一个Arrayslist
ArrayList<CodeNode> list = new ArrayList<>();
//2.存储每个字符出现的次数,遍历字符数组,并将其存放到hash表中
Hashtable<Character, Integer> hashtable = new Hashtable<>();
for (char ch:chars) {
Integer conuts = hashtable.get(ch);//统计ch在hashTable中出现的次数
if(conuts == null){//如果ch在hashTable中出现的次数为空,则将ch存入hashTable中,并将次数置为1
hashtable.put(ch,1);
}else {
hashtable.put(ch,conuts+1);//如果已经存在就将其的value值加一
}
}
//循环结束,对hash表进行遍历,创建节点,存到ArraysList链表中,开始构造树节点
for (Map.Entry<Character, Integer> node: hashtable.entrySet()) {
list.add(new CodeNode(node.getKey(),node.getValue()));
}
return list;
}
//创建哈夫曼树
public static CodeNode creatTree(List<CodeNode> list){
while (list.size() > 1){
Collections.sort(list);
CodeNode leftNode = list.get(0);
CodeNode rightNode = list.get(1);
int leftCount = leftNode.count;
int righrCount = rightNode.count;
CodeNode parent = new CodeNode((leftCount+righrCount));
parent.left = leftNode;
parent.right = rightNode;
list.remove(leftNode);
list.remove(rightNode);
list.add(parent);
}
return list.get(0);
}
//前序遍历
public static void preOrder(CodeNode root){
if (root != null){
root.preOrder();
}else{
System.out.println("此树为空");
}
}
//创建一个map将哈夫曼编码存放在Map<char,String>
static Map<Character,String> map = new HashMap();
//在生成哈夫曼编码时,需要拼接路径,定义一个StringBUilder存储有叶子节点的路径
static StringBuilder stringBuilder = new StringBuilder();
//将哈夫曼树转换成哈夫曼编码
public static void toCode(CodeNode node,String code,StringBuilder stringBuilder){
StringBuilder stringBuilder1 = new StringBuilder(stringBuilder);
//将code添加到stringBuilder1中。
stringBuilder1.append(code);
if(node.left == null || node.right == null){
map.put(node.c,stringBuilder1.toString());
}else {//说明已经到达叶子节点,返回结果
//向左递归
toCode(node.left,"0",stringBuilder1);
//向右递归
toCode(node.right,"1",stringBuilder1);
}
}
//编写一个方法,将对应的字符数组的,通过生成的哈夫曼编码表,返回一个压缩后的byte[]数组
public static byte[] zip(char[] chars,Map<Character,String> map){
StringBuilder stringBuilder = new StringBuilder();//创建一个Stringbuilder,用来拼接字符
//通过遍历字符数组,得到字符数组中的关键字,通过关键字ch将map中的value值拼接到stringBuilder中
for (char ch:chars) {
stringBuilder.append(map.get(ch));
}
//然后将计算stringbuilder的长度,创建一个byte[]数组,将stringbulider转换成byte类型,存放到byte[]数组中
int len;//定义一个len用来记录数组的长度
if (stringBuilder.length() % 8 == 0){
len = stringBuilder.length()/8;
}else {
len = stringBuilder.length() / 8 + 1;
}
byte[] bt = new byte[len];
int index = 0;
for (int i = 0; i < stringBuilder.length(); i+=8) {
//将String 转成二进制的数存放到二进制数组中
String str;
if(i+8 > stringBuilder.length()){
str = stringBuilder.substring(i);
}else {
str = stringBuilder.substring(i,i+8);
}
bt[index] = (byte) Integer.parseInt(str,2);
index++;
}
return bt;
}
}
/**
* c : 存放字符本身
* count : 字符本身出现的次数,及权值
*/
class CodeNode implements Comparable<CodeNode>{
char c;
int count;
CodeNode left;
CodeNode right;
public CodeNode(char c, int count) {
this.c = c;
this.count = count;
}
public CodeNode(int count) {
this.count = count;
}
@Override
public String toString() {
return "CodeNode{" +
"c=" + c +
", count=" + count +
'}';
}
//前序遍历
public void preOrder(){
System.out.println(this);
if (this.left != null){
this.left.preOrder();
}
if (this.right != null){
this.right.preOrder();
}
}
@Override
public int compareTo(CodeNode o) {
//从小到大排序
return this.count - o.count;
}
}
无解压代码