Java字符串压缩
终有弱水替沧海i 人气:0赫夫曼编码基本介绍
1) 赫夫曼编码也翻译为 哈夫曼编码(Huffman Coding)，又称霍夫曼编码，是一种编码方式, 属于一种程序算法
2) 赫夫曼编码是赫哈夫曼树在电讯通信中的经典的应用之一。
3) 赫夫曼编码广泛地用于数据文件压缩。其压缩率通常在 20%～90%之间
4) 赫夫曼码是可变字长编码(VLC)的一种。Huffman 于 1952 年提出一种编码方法，称之为最佳编码
在通信领域中几种信息处理方式的区别（以字符串" i like like like java do you like a java"举例）:
第一种-定长编码:
第二种-变长编码:
第三种-赫夫曼编码:
传输的字符串:
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 // 各个字符对应的个数
3、 按照上面字符出现的次数构建一颗赫夫曼树, 次数作为权值
构成赫夫曼树的步骤：
1) 从小到大进行排序, 将每一个数据，每个数据都是一个节点 ， 每个节点可以看成是一颗最简单的二叉树
2) 取出根节点权值最小的两颗二叉树
3) 组成一颗新的二叉树, 该新的二叉树的根节点的权值是前面两颗二叉树根节点权值的和
4) 再将这颗新的二叉树，以根节点的权值大小 再次排序， 不断重复 1-2-3-4 的步骤，直到数列中，所有的数据都被处理，就得到一颗赫夫曼树
4、 根据赫夫曼树，给各个字符,规定编码 (前缀编码)， 向左的路径为 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" 字符串对应的编码为 (注意这里我们使用的无损压缩)1010100110111101111010011011110111101001101111011110100001100001110011001111000011001111000100100100110111101111011100100001100001110 通过赫夫曼编码处理 长度为：133
通过以上三种信息处理方式可以对比看出赫夫曼编码的优越性。
以下给出实现哈夫曼编码需要的各个方法:
1、先创建节点对象:
// 为了排序，必须实现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、需要先实现统计输入的字符串中各个字符的个数:
/**
* //统计字符串中每个字符出现的次数和空格出现次数
*
* @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中的数据存入Node节点中
//先将map转为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中的数据存入Node节点中
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、创建赫夫曼树:
/**
* 创建huffman树
*
* @param nodeList 排好序的集合
* @return 返回huffman树的根节点
*/
public static Node createHuffmanTree(List<Node> nodeList) {
//循环创建huffman树
while (nodeList.size() > 1) {
//1、每次取出集合中的前两个节点
Node left = nodeList.get(0);
Node right = nodeList.get(1);
//2、将他们的权值相加构成一个新的节点并作为他们的父节点
Node parent = new Node(null, left.weight + right.weight);
parent.left = left;
parent.right = right;
//3、删除已经处理过的节点
nodeList.remove(left);
nodeList.remove(right);
//4、将新的节点存入集合中
nodeList.add(parent);
//5、重新给集合排序,循环这5步即可，直到集合中只有一个节点，这就是huffman树的根节点
Collections.sort(nodeList);
//观察测试输出
//System.out.println(nodeList);
}
//返回huffman树的根节点
return nodeList.get(0);
}4、根据创建的赫夫曼树进行字符串编码压缩:
/**
* 根据huffman树来进行数据编码压缩
* 思路:
* 1、只要向左子树走就代表0，向右子树走就代表1
* 2、从头节点走到对于字符在的节点位置的路径对于的0和1组成的二进制编码就是压缩后该字符对于的编码
* 3、需要定义一个StringBuffer来存储某个节点的路径对于的编码
* 4、将赫夫曼编码表存放在Map<Byte,String>中
*
* @param node huffman树的根节点
* @param stringBuffer 用于拼接路径
* @param code 路径：左子节点是0，右子节点是1
* @return
*/
private static void getHuffmanCompressionCode(Node node, String code, StringBuffer stringBuffer) {
StringBuffer stringBuffer1 = new StringBuffer(stringBuffer);
stringBuffer1.append(code);
//如果为空，不进行处理
if (node != null) {
//判断node是叶子节点还是非叶子节点
if (node.data == null) {
//非叶子节点
//向左递归
getHuffmanCompressionCode(node.left, "0", stringBuffer1);
//向右递归
getHuffmanCompressionCode(node.right, "1", stringBuffer1);
} else {
//叶子节点
//说明这条路走到尾了，将路径编码存入map中
huffmanCodes.put(node.data, stringBuffer1.toString());
}
}
}5、得到压缩后的赫夫曼编码长度(二进制位数):
/**
* @return 得到压缩后的赫夫曼编码大小
*/
public static int getStrCodeSize() {
int size = 0;
//将两个map集合都转为set集合
Set<Map.Entry<Character, Integer>> mapSet = map.entrySet();
Set<Map.Entry<Byte, String>> huffmanMapSet = huffmanCodes.entrySet();
//循环两个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());
//节约时间，之间退出内循环。因为不可能有一对多的关系。
break;
}
}
}
return size;
}6、编写一个方法，将字符串对应的byte[]数组，通过生成的赫夫曼编码表，返回一个赫夫曼编码压缩后的byte[]
/**
* 编写一个方法，将字符串对应的 byte[] 数组，通过生成的赫夫曼编码表，返回一个赫夫曼编码 压缩后的byte[]
*
* @param bytes 这时原始的字符串对应的 byte[]
* @param huffmanCodes 生成的赫夫曼编码 map
* @return 返回赫夫曼编码处理后的 byte[]
* 举例： String content = "i like like like java do you like a java"; =》 byte[] contentBytes = content.getBytes();
* 返 回 的 是 字 符 串:
* "1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000
* 101111111100110001001010011011100"
* => 对应的 byte[] huffmanCodeBytes ，即 8 位对应一个 byte,放入到 huffmanCodeBytes
* huffmanCodeBytes[0] = 10101000(补码) => byte [推导 10101000=> 10101000 - 1 => 10100111(反
* 码)=> 11011000(源码) = -88 ]
*/
public static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) {
//1、先利用赫夫曼编码表将传进来的bytes数组转为压缩后的编码
StringBuffer stringBuffer1 = new StringBuffer();
for (byte b : bytes) {
stringBuffer1.append(huffmanCodes.get(b));
}
//输出字符串压缩成赫夫曼编码后对应的二进制编码
//System.out.println("输出字符串压缩成赫夫曼编码后对应的二进制编码:" + stringBuffer1 + "长度为:" + stringBuffer1.length());
//获取byte数组的长度，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 转成一个 byte,放入到 huffmanBytes中
//该方法是将strByte对应的01字符串传换为十进制
//第二个参数表示基数（radix）,表示转换为radix进制
huffmanBytes[index] = (byte) Integer.parseInt(strByte, 2);
index++;
}
return huffmanBytes;
}其实也可以不用写5中的方法，可以直接在6中输出stringBuffer1.length()就可以得到压缩后的二进制位数。不过也可以把5当作一种解决的算法。
以下给出完整的代码:
import java.util.*;
/**
* 实现huffman编码
*/
public class HuffmanCode {
//将赫夫曼编码表存放在Map<Byte,String>中
public static Map<Byte, String> huffmanCodes = new HashMap<>();
//需要定义一个StringBuffer来存储某个节点的路径对于的编码
public static StringBuffer stringBuffer = new StringBuffer();
//创建一个map，来保存每个字符以及他对应出现的次数
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();
// 把输入的字符串转为byte数组，在byte数组中存储的是字符对应的ASCII码值
byte[] strBytes = str.getBytes();
System.out.println(str + ",压缩成赫夫曼编码前对应的byte数组:" + Arrays.toString(strBytes));
//计算压缩前的字符串有多少位二进制数
int compressionBeforeCodeSize = str.length() * 8 + str.length() - 1;
System.out.println(str + ",压缩前的字符串大小:" + compressionBeforeCodeSize);
//统计字符串中每个字符出现的次数和空格出现次数并存入Node节点中
List<Node> nodeList = totalCharCounts(str);
//创建huffman树
Node root = createHuffmanTree(nodeList);
//得到压缩后的编码
getHuffmanCompressionCode(root, "", stringBuffer);
//输出赫夫曼编码表
System.out.println(str + ",对应的赫夫曼编码表:");
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 + ",压缩成赫夫曼编码后对应的byte数组:" + Arrays.toString(bytes));
}
/**
* @return 得到压缩后的赫夫曼编码大小
*/
public static int getStrCodeSize() {
int size = 0;
//将两个map集合都转为set集合
Set<Map.Entry<Character, Integer>> mapSet = map.entrySet();
Set<Map.Entry<Byte, String>> huffmanMapSet = huffmanCodes.entrySet();
//循环两个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());
//节约时间，之间退出内循环。因为不可能有一对多的关系。
break;
}
}
}
return size;
}
/**
* 根据huffman树来进行数据编码压缩
* 思路:
* 1、只要向左子树走就代表0，向右子树走就代表1
* 2、从头节点走到对于字符在的节点位置的路径对于的0和1组成的二进制编码就是压缩后该字符对于的编码
* 3、需要定义一个StringBuffer来存储某个节点的路径对于的编码
* 4、将赫夫曼编码表存放在Map<Byte,String>中
*
* @param node huffman树的根节点
* @param stringBuffer 用于拼接路径
* @param code 路径：左子节点是0，右子节点是1
* @return
*/
private static void getHuffmanCompressionCode(Node node, String code, StringBuffer stringBuffer) {
StringBuffer stringBuffer1 = new StringBuffer(stringBuffer);
stringBuffer1.append(code);
//如果为空，不进行处理
if (node != null) {
//判断node是叶子节点还是非叶子节点
if (node.data == null) {
//非叶子节点
//向左递归
getHuffmanCompressionCode(node.left, "0", stringBuffer1);
//向右递归
getHuffmanCompressionCode(node.right, "1", stringBuffer1);
} else {
//叶子节点
//说明这条路走到尾了，将路径编码存入map中
huffmanCodes.put(node.data, stringBuffer1.toString());
}
}
}
/**
* //统计字符串中每个字符出现的次数和空格出现次数
*
* @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中的数据存入Node节点中
//先将map转为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中的数据存入Node节点中
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;
}
/**
* 创建huffman树
*
* @param nodeList 排好序的集合
* @return 返回huffman树的根节点
*/
public static Node createHuffmanTree(List<Node> nodeList) {
//循环创建huffman树
while (nodeList.size() > 1) {
//1、每次取出集合中的前两个节点
Node left = nodeList.get(0);
Node right = nodeList.get(1);
//2、将他们的权值相加构成一个新的节点并作为他们的父节点
Node parent = new Node(null, left.weight + right.weight);
parent.left = left;
parent.right = right;
//3、删除已经处理过的节点
nodeList.remove(left);
nodeList.remove(right);
//4、将新的节点存入集合中
nodeList.add(parent);
//5、重新给集合排序,循环这5步即可，直到集合中只有一个节点，这就是huffman树的根节点
Collections.sort(nodeList);
//观察测试输出
//System.out.println(nodeList);
}
//返回huffman树的根节点
return nodeList.get(0);
}
/**
* 编写一个方法，将字符串对应的byte[]数组，通过生成的赫夫曼编码表，返回一个赫夫曼编码压缩后的byte[]
*
* @param bytes 这时原始的字符串对应的 byte[]
* @param huffmanCodes 生成的赫夫曼编码 map
* @return 返回赫夫曼编码处理后的 byte[]
* 举例： String content = "i like like like java do you like a java"; =》 byte[] contentBytes = content.getBytes();
* 返 回 的 是 字 符 串:
* "1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000
* 101111111100110001001010011011100"
* => 对应的 byte[] huffmanCodeBytes ，即 8 位对应一个 byte,放入到 huffmanCodeBytes
* huffmanCodeBytes[0] = 10101000(补码) => byte [推导 10101000=> 10101000 - 1 => 10100111(反
* 码)=> 11011000(源码) = -88 ]
*/
public static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) {
//1、先利用赫夫曼编码表将传进来的bytes数组转为压缩后的编码
StringBuffer stringBuffer1 = new StringBuffer();
for (byte b : bytes) {
stringBuffer1.append(huffmanCodes.get(b));
}
//输出字符串压缩成赫夫曼编码后对应的二进制编码
//System.out.println("输出字符串压缩成赫夫曼编码后对应的二进制编码:" + stringBuffer1 + "长度为:" + stringBuffer1.length());
//获取byte数组的长度，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 转成一个 byte,放入到 huffmanBytes中
//该方法是将strByte对应的01字符串传换为十进制
//第二个参数表示基数（radix）,表示转换为radix进制
huffmanBytes[index] = (byte) Integer.parseInt(strByte, 2);
index++;
}
return huffmanBytes;
}
}以下是我的测试结果输出:
输入的字符串: i like like like java do you like a java
输入的字符串: asdjkj ;lkjsadlkj kj ()dasd
加载全部内容