在开发手机程序时,总是希望压缩网络传输的信息,以减少流量。本文仅以哈夫曼编码为引导,抛砖引玉,实现压缩功能。
大家可能会想,程序和第三方提供了很多压缩方式,何必自己写压缩代码呢?不错,如GZIP这样的压缩工具很多,可是在某些情况下(如文本内容小且字符不重复),GZIP压缩后会比原始文本还要大。所以在某些特殊情况下用自己的压缩方式可以更优。
大家可能早已忘记了在学校学习的哈夫曼知识,可以先在百度百科了解一下哈夫曼知识
http://baike.baidu.com/view/127820.htm
哈夫曼思想:统计文本字符重复率,求出各字符权值,再构造出一颗最优二叉树(又称哈夫曼树),然后给每个叶子结点生成一个以位(bit)为单位的码值,每个码值不能做为其他码值的前缀,再将码值合并以每8个生成一个字节。
package com.huffman;
/**
* 结点
* @author Davee
*/
public class Node implements Comparable<Node> {
int weight;//权值
Node leftChild;//左孩子结点
Node rightChild;//右孩子结点
String huffCode;
private boolean isLeaf;//是否是叶子
Character value;
public Node(Character value, int weight) {
this.value = value;
this.weight = weight;
this.isLeaf = true;
}
public Node(int weight, Node leftChild, Node rightChild) {
this.weight = weight;
this.leftChild = leftChild;
this.rightChild = rightChild;
}
public void increaseWeight(int i) {
weight += i;
}
public boolean isLeaf() {
return isLeaf;
}
@Override
public int compareTo(Node o) {
return this.weight - o.weight;
}
}
package com.huffman;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;
public class HuffmanTree {
private boolean debug = false;
private HashMap<Character, Node> nodeMap;
private ArrayList<Node> nodeList;
public HuffmanTree() {
nodeMap = new HashMap<Character, Node>();
nodeList = new ArrayList<Node>();
}
public void setDebug(boolean debug) {
this.debug = debug;
}
public String decode(Map<String, Character> codeTable, String binary) {
int begin = 0, end = 1, count = binary.length();
StringBuffer sb = new StringBuffer();
while (end <= count) {
String key = binary.substring(begin, end);
if (codeTable.containsKey(key)) {
sb.append(codeTable.get(key));
begin = end;
} else {
}
end++;
}
return sb.toString();
}
public String encode(String originText) {
if (originText == null) return null;
calculateWeight(originText);
// if (debug) printNodes(nodeList);
Node root = generateHuffmanTree(nodeList);
generateHuffmanCode(root, "");
if (debug) printNodes(root);
StringBuffer sb = new StringBuffer();
for (Character key : originText.toCharArray()) {
sb.append(nodeMap.get(key).huffCode);
}
if (debug) System.out.println("二进制:"+sb.toString());
return sb.toString();
}
/**
* 计算叶子权值
* @param text
*/
private void calculateWeight(String text) {
for (Character c : text.toCharArray()) {
if (nodeMap.containsKey(c)) {
nodeMap.get(c).increaseWeight(1);//权值加1
} else {
Node leafNode = new Node(c, 1);
nodeList.add(leafNode);
nodeMap.put(c, leafNode);
}
}
}
/**
* 生成哈夫曼树
* @param nodes
*/
private Node generateHuffmanTree(ArrayList<Node> nodes) {
Collections.sort(nodes);
while(nodes.size() > 1) {
Node ln = nodes.remove(0);
Node rn = nodes.remove(0);
insertSort(nodes, new Node(ln.weight + rn.weight, ln, rn));
}
Node root = nodes.remove(0);
nodes = null;
return root;
}
/**
* 插入排序
* @param sortedNodes
* @param node
*/
private void insertSort(ArrayList<Node> sortedNodes, Node node) {
if (sortedNodes == null) return;
int weight = node.weight;
int min = 0, max = sortedNodes.size();
int index;
if (sortedNodes.size() == 0) {
index = 0;
} else if (weight < sortedNodes.get(min).weight) {
index = min;//插入到第一个
} else if (weight >= sortedNodes.get(max-1).weight) {
index = max;//插入到最后
} else {
index = max/2;
for (int i=0, count=max/2; i<=count; i++) {
if (weight >= sortedNodes.get(index-1).weight && weight < sortedNodes.get(index).weight) {
break;
} else if (weight < sortedNodes.get(index).weight) {
max = index;
} else {
min = index;
}
index = (max + min)/2;
}
}
sortedNodes.add(index, node);
}
private void generateHuffmanCode(Node node, String code) {
if (node.isLeaf()) node.huffCode = code;
else {
generateHuffmanCode(node.leftChild, code + "0");
generateHuffmanCode(node.rightChild, code + "1");
}
}
/**
* 生成码表
* @return
*/
public Map<String, Character> getCodeTable() {
Map<String, Character> map = new HashMap<String, Character>();
for (Node node : nodeMap.values()) {
map.put(node.huffCode, node.value);
}
return map;
}
/**
* 打印节点信息
* @param root
*/
private void printNodes(Node root) {
System.out.println("字符 权值 哈夫码");
printTree(root);
}
private void printTree(Node root) {
if (root.isLeaf()) System.out.println((root.value == null ? " " : root.value)+" "+root.weight+" "+(root.huffCode == null ? "" : root.huffCode));
if (root.leftChild != null) printTree(root.leftChild);
if (root.rightChild != null) printTree(root.rightChild);
}
/**
* 打印节点信息
* @param nodes
*/
private void printNodes(ArrayList<Node> nodes) {
System.out.println("字符 权值 哈夫码");
for (Node node : nodes) {
System.out.println(node.value+" "+node.weight+" "+node.huffCode);
}
}
}
package com.test;
import java.util.Map;
import com.huffman.HuffUtils;
import com.huffman.HuffmanTree;
public class Test {
public static void main(String[] args) {
String originText = "abcdacaha";
HuffmanTree huffmanTree = new HuffmanTree();
huffmanTree.setDebug(true);//测试
String binary = huffmanTree.encode(originText);
byte[] bytes = HuffUtils.binary2Bytes(binary);
Map<String, Character> codeTable = huffmanTree.getCodeTable();
int lastByteNum = binary.length() % 8;
System.out.println(bytes.length);
//将bytes、codeTable、 lastByteNum传递到服务器端
//省略。。。。。。
/*
服务器端解析
接收到参数,并转换成bytes、relationMap、 lastByteNum
*/
String fullBinary = HuffUtils.bytes2Binary(bytes, lastByteNum);
System.out.println("服务器二进制:"+fullBinary);
String retrieveText = huffmanTree.decode(codeTable, fullBinary);
System.out.println("恢复文本:"+retrieveText);
}
}
分享到:
相关推荐
在开发手机程序时,总是希望压缩网络传输的信息,以减少流量。本文仅以哈夫曼编码为引导,抛砖引玉,实现压缩功能
用java swing 实现标准的曼彻斯特图像输出
包含huffman编码java实现源程序、该java程序的javadoc文档、huffman编码简单原理ppt
JAVA实现曼彻斯特编码与差分曼彻斯特编码 计算机网络课程设计中,可以参考此编码!
实现BASE64编码和解码程序, 在类中实现如下函数并运行测试正确。 BASE64编码算法请在网上查询。 public String encode(byte[] data) { } public byte[] decode(String b) { }
自己实现的Huffman编码,压缩率接近50%,使用字节流写入文件。解码时读取字节流,将字节流转化为二进制串,匹配字符解压。使用I have a dream作为测试文件。
1.哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。给出文件中各个字符出现的频率,求各个字符的哈夫曼编码方案。
基于java实现的霍夫曼编码 随意输入数字 实现编码 并可以计算码长
JAVA代码实现MD5编码,不调用任何第三方API-MD5 hash algorithm implemented by JAVA.
NULL 博文链接:https://hunnuxiaobo.iteye.com/blog/397792
本程序实现了用java语言控制串口,采用pdu编码对数据进行编解码。最终分别实现了收发短信的功能。
Java实现的JPEG算法,只有一个文件,但是支持调整压缩质量,方便学习图像编码
主要介绍了java使用Hex编码解码实现Aes加密解密功能,结合完整实例形式分析了Aes加密解密功能的定义与使用方法,需要的朋友可以参考下
Java实现二维码QRCode的编码和解码
用Java编写的Base64编码技术,可以把密文编码成为Base64编码,Base64编码技术广泛用于编码密文和电子邮件。
我和朋友写的Huffman编码译码器,可显示数据压缩比,暂时只支持英文txt文件处理。用NetBeans载入调整一下布局就可以用了
Java实现二维码QRCode的编码和解码所需类库
java实现信息论与编码,包含香农码、费诺码、霍夫曼码,有算法有界面
本程序利用Java实现以下功能: 1、读取一行或多行数据,统计出现的所有字母的出现次数 2、构造huffman树 3、生成出现字母的编码表 4、对输入的数据进行编码输出 5、输入编码结果,对编码结果进行解码,得到原来的...