想吃项记的烩面了……这小地方的可难吃。
看完了《裸婚时代》，我觉得冬瓜说得对，刘易阳不敢面对自己的真实感受。
女生都是感性的，工作永远不如生活重要。
不是坐在一起就叫团队，不是不吵架就叫态度。
昨晚一哥们说求k小直接可以进行k次冒泡，我都想不起来，我想到的是区间快拍，说明基础很重要。
对原版本的算法有很大修改，个人认为原版代码的命名不太规范，读起来比较累，本程序主要是界面参考了参考资料，读写文件完全是自己搞的(原文字节流，我的字符流)，不过原文不可压缩汉字(原版压缩效率高一些)，我的可以，压缩比40%左右(文件大小做除)。
一.概念引入
优先级队列（Priority Queue）又叫最小堆。Huffman( 哈夫曼 ) 算法在上世纪五十年代初提出来了，它是一种无损压缩方法，在压缩过程中不会丢失信息熵，而且可以证明Huffman 算法在无损压缩算法中是最优的。Hufmann coding 是最古老，以及最优雅的数据压缩方法之一。它是以最小冗余编码为基础的，即如果我们知道数据中的不同符号在数据中的出现频率，我们就可以对它用一种占用空间最少的编码方式进行编码，这种方法是，对于最频繁出现的符号制定最短长度的编码，而对于较少出现的符号给较长长度的编码。哈夫曼编码可以对各种类型的数据进行压缩，但在本文中我们仅仅针对字符进行编码。
哈夫曼编码是一种前缀码，即任一个字符的编码都不是其他字符编码的前缀。从我们的编码过程中可以很容易看到这一点，因为所有字符都是哈夫曼树中的叶子节点，这个特征能够保证解码的唯一性，不会产生歧义。笔者认为这样说或许更好理解：任意字符的编码的所有前缀都不是其它字符的编码，而且字符和编码是满单射，为后面value反查key打基础。可以看出，出现频率最高的字符，使用最短的编码，字符出现频率越低，编码逐渐增长。这样不同字符在文档中出现的频率差异越大，则压缩效果将会越好。因此字符出现频率越大，我们希望给它的编码越短（在哈夫曼树中的深度越浅），即我们希望更晚的将它所在的树进行合并。反之，字符频率越低，我们希望给他的编码最长（在哈夫曼树中的深度越深），因此我们希望越早的将它所在的树进行合并。因此，哈夫曼编码的贪心策略就体现在合并树的过程中，我们每一次总是选择根节点频率最小的两个树先合并，这样就能达到我们所希望的编码结果。
例：假设一个文本文件中只包含7个字符{A，B，C，D，E，F，G}，这7个字符在文本中出现的次数为{5，24，7，17，34，5，13}，求这些字符的哈夫曼编码。
仔细看上图，发现树的深度不一定是n(节点数)，内节点个数是(n-1)。右子树的频率为17的内节点并没有和字符节点的D(频率17)合并，先和G(频率13)合并了(用的是内节点频率为17的，不是字符节点，数据结构课本上也是这么搞的)，然后左子树的D、B合并。
为什么能压缩？压缩的时候当我们遇到了文本中的1 、 2 、 3 、 4 几个字符的时候，我们不用原来的存储，而是转化为用它们的 01 串来存储不久是能减小了空间占用了吗。（什么 01 串不是比原来的字符还多了吗？怎么减少？）大家应该知道的，计算机中我们存储一个 int 型数据的时候一般式占用了32 个 01 位，因为计算机中所有的数据都是最后转化为二进制位去存储的。所以，想想我们的编码不就是只含有 0 和 1 嘛，因此我们就直接将编码按照计算机的存储规则用位的方法写入进去就能实现压缩了。比如：1这个数字，用整数写进计算机硬盘去存储，占用了32个二进制位， 而如果用它的哈弗曼编码去存储，只有几个二进制位，效果显而易见。不过笔者认为这是采用字节流，那为什么我用字符流也能实现压缩呢？因为写入的时候都是一个字节，原来可能1、2、4字节。
二.Java实现
import java.awt.Container;
import javax.swing.JMenu;
import javax.swing.JMenuBar;
import javax.swing.JMenuItem;
import javax.swing.JPanel;
public class HuffmanMain extends javax.swing.JFrame{
static javax.swing.JTextArea textarea=null;
public static void main(String[] args) {
new HuffmanMain().display();
}
public void display(){
this.setSize(400,400);
this.setTitle("火星十一郎解压压缩软件");
this.setLayout(new java.awt.FlowLayout());
//添加菜单栏
this.setJMenuBar(getMenu());
this.setVisible(true);
}
public JMenuBar getMenu(){
//菜单栏、菜单项、菜单条目
JMenuBar mb = new JMenuBar();
//菜单项
JMenu file = new JMenu("File");
JMenu contact = new JMenu("Contact");
//菜单条目
JMenuItem Code = new JMenuItem("Code");
JMenuItem Decode = new JMenuItem("Decode");
JMenuItem exit = new JMenuItem ("Exit");
JMenuItem qq = new JMenuItem ("About");
//加入文件菜单项中
file.add(Code);
file.addSeparator();
file.add(Decode);
//在这加了个分割线
file.addSeparator();
file.add(exit);
contact.add(qq);
//添加菜单事件
Action action = new Action();
Code.addActionListener(action);
Decode.addActionListener(action);
exit.addActionListener(action);
qq.addActionListener(action);
//放上去
mb.add(file);
mb.add(contact);
return mb;
}
}
class Node implements Comparable<Node>{
public char data;
public int times;
public Node lchild;
public Node rchild;
public Node(char data,int times){
this.data=data;
this.times=times;
}
public int getData() {
return data;
}
public void setData(char data) {
this.data = data;
}
public int getTimes() {
return times;
}
public void setTimes(int times) {
this.times = times;
}
public Node getLchild() {
return lchild;
}
public void setLchild(Node lchild) {
this.lchild = lchild;
}
public Node getRchild() {
return rchild;
}
public void setRchild(Node rchild) {
this.rchild = rchild;
}
public int compareTo(Node o) {
Node other = o;
int temp = times-other.times;
if(temp>0){
return 1;
}else {
return 0;
}
}
}
---------------------------------------------------------------------------------------------------------
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import javax.swing.JFileChooser;
import javax.swing.JOptionPane;
import javax.swing.filechooser.FileNameExtensionFilter;
public class Action implements ActionListener {
public void actionPerformed(ActionEvent e) {
String command = e.getActionCommand();
//3个if是并列的，因为可能多次压缩、解压
if ("Code".equals(command)) {
System.out.println("进行压缩");
// 文件选择
JFileChooser Chooser = new JFileChooser();
int t = Chooser.showOpenDialog(null);// 弹出文件选择框
if (t == Chooser.APPROVE_OPTION) {// 如果点击的是确定
// 得到文件的绝对路径
String path = Chooser.getSelectedFile().getAbsolutePath();
HuffmanCode code = new HuffmanCode(path);
code.readFile();// 读取文件
code.writeFile();// 写出压缩文件
}
}
if ("Decode".equals(command)) {
System.out.println("解压缩");
// 显示打开的窗口
JFileChooser chooser = new JFileChooser();
//参数：文件描述(显示的)和文件类型
FileNameExtensionFilter filter = new FileNameExtensionFilter(
"hxsyl压缩文件", "hxsyl");
chooser.setFileFilter(filter);
int returnVal = chooser.showOpenDialog(null);
if (returnVal == chooser.APPROVE_OPTION) {
String path = chooser.getSelectedFile().getAbsolutePath();// 得到压缩文件的路径
HuffmanDecode decode = new HuffmanDecode(path);
decode.decode();// 解压缩文件
}
}
if ("Exit".equals(command)) {
System.exit(0);
}
if ("About".equals(command)) {
JOptionPane.showConfirmDialog(null, "By 791909235@qq.com", "作者",
JOptionPane.YES_OPTION, JOptionPane.QUESTION_MESSAGE);
}
}
}
---------------------------------------------------------------------------------------
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.util.HashMap;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Scanner;
public class HuffmanCode {
private String path;// 文件的输入绝对路径
Node root = null;// 定义的根节点
private Map<Character,Integer> mm = new Hashtable<Character, Integer>();
//大小：大小写字母、数字、汉字，就开100吧
private Map<Character,String> mapCode = new Hashtable<Character, String>();
public HuffmanCode() {
}
public HuffmanCode(String path) {
//频率清零 初始化
this.path = path;
mapCode.clear();
}
//我想起了单例模式，才想起这种方法来在另一个java文件里因为一个java文件里的成员变量
//注意不是方法，否则直接new 类调用就好
public Map<Character,String> returnMap() {
return this.mapCode;
}
public void readFile() {
try {
System.out.println("---------------读入文件--------------");
//把“\”换成“/”，实际上没必要
path.replaceAll("\\\\", "/");
FileReader fr = new FileReader(path);
BufferedReader br = new BufferedReader(fr);//有readline
String str = "";
mm.clear();
while ((str=br.readLine())!=null) {
System.out.println("读入了："+str);
char[] ch = str.toCharArray();
for(int i=0; i<ch.length; i++) {
//加上if判断就可以防止NullPointer异常了
if(mm.get(ch[i])!=null) {
mm.put(ch[i], mm.get(ch[i])+1);
}else {
mm.put(ch[i], 1);
}
}
}
System.out.println("---------文件读入结束-------------");
// 构建哈弗曼树
createHfmTree();
// 递归生成编码，root是成员函数
genenateHFMCode(root, "");
br.close();
fr.close();
} catch (Exception e) {
e.printStackTrace();
}
}
public void writeFile() {
try {
System.out.println("------------写入文件---------------");
path.replaceAll("\\\\", "/");
FileReader fr = new FileReader(path);
BufferedReader br = new BufferedReader(fr);//有readline
//第二个参数true表示追加
BufferedWriter bw = new BufferedWriter(new FileWriter(path + ".hxsyl",true));
String str = "";
while ((str=br.readLine())!=null) {
char[] ch = str.toCharArray();
for(int i=0; i<ch.length; i++) {
bw.write(mapCode.get(ch[i]));
}
}
//刷新该流的缓冲，br没有该方法
bw.flush();
System.out.println("------------文件写入完毕---------------");
} catch (Exception ef) {
ef.printStackTrace();
}
}
//广搜建树
public void createHfmTree() {
//里面是Node
PriorityQueue<Node> nodeQueue = new PriorityQueue<Node>();
// 把所有的节点都加入到 队列里面去
Iterator<Character> iter = mm.keySet().iterator();
while(iter.hasNext()) {
char key = iter.next();
if (mm.get(key)!= 0) {//实际上这个判断没必要，因为Map里没的都是null
Node node = new Node(key, mm.get(key));
nodeQueue.add(node);// 加入节点
}
}
//不是不为空，最后是一个节点
while (nodeQueue.size() > 1) {
Node min1 = nodeQueue.poll();
Node min2 = nodeQueue.poll();
/*
* data搞为‘$’，说明是内节点
* 权值和就是data值为$的节点的times值之和
* 使用优先队列算权值就是基于此
*/
Node result = new Node('$', min1.times + min2.times);
result.lchild = min1;
result.rchild = min2;
nodeQueue.add(result);
}
root = nodeQueue.peek(); // 得到根节点
}
//递归生成Hfm编码
public void genenateHFMCode(Node root, String s) {
if (null == root) {
return ;
}
//hfm节点全部是叶子节点
if ((root.lchild == null) && (root.rchild == null)) {
//root是Node
System.out.println("节点" + root.data + "编码" + s);
mapCode.put(root.data,s);
}
if (root.lchild != null) {// 左0 右 1
genenateHFMCode(root.lchild, s + '0');
}
if (root.rchild != null) {
genenateHFMCode(root.rchild, s + '1');
}
}
}
----------------------------------------------------------------------------------------------
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.util.ArrayList;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
/*
* 为什么输出汉子提示呢？
* 因为实际上需要保存在日志里的.
*
* 解码需要全部读入文件，不能一行一行，因为
*/
public class HuffmanDecode {
private String path;
Map<Character,String> mapCode = new Hashtable<Character, String>();
public HuffmanDecode(String path) {
this.path = path;
//想了好久想到的方法，哈哈
this.mapCode = new HuffmanCode().returnMap();
}
//通过
private static char valueGetKey(Map<Character,String> map,StringBuffer value) {
Set set = map.entrySet();
Iterator it = set.iterator();
char ch='$';//表示没有找到，实际没必要，因为是哈夫曼编码是单射
while(it.hasNext()) {
Map.Entry entry = (Map.Entry)it.next();
if(entry.getValue().equals(value)) {
//转换为char报错
ch = (Character)entry.getKey();
return ch;
}
}
//加这个是为了不让编译器报错，原因如上
return ch;
}
//解压缩
public void decode() {
try {
path.replaceAll("\\\\", "/");
FileReader fr = new FileReader(path);
BufferedReader br = new BufferedReader(fr);//有readline
//第二个参数true表示追加
int index = path.lastIndexOf(".hxsyl");
path = path.substring(0,index);
BufferedWriter bw = new BufferedWriter(new FileWriter(path,true));
StringBuffer sb = new StringBuffer("");
String str = "";
while ((str=br.readLine())!=null) {
sb.append(str);
}
//刷新该流的缓冲，br没有该方法
bw.flush();
System.out.println(sb);
System.out.println("------------解码文件---------------");
StringBuffer waitSB = new StringBuffer("");
for(int i=0; i<sb.length(); i++) {
if(mapCode.containsValue(waitSB)) {
char ch = valueGetKey(mapCode, waitSB);
bw.write(ch);
waitSB.delete(0, waitSB.length());
if(null==waitSB) {
break;
}
}else {
waitSB.append(sb.charAt(i));
}
}
System.out.println("------------解码完毕---------------");
} catch (Exception e) {
e.printStackTrace();
}
}
}
运行界面如下：
三.结束语
处理IO过程中我发现以Reader结尾的都是read单个字符，以stream结尾的都是read字节。如何从现有字符读入呢？可以用StringReader或者System.in(str)。
压缩也能实现信息隐藏，把压缩文件命名为常见格式比如txt，只有有该解压软件的才能打开。自己写的，你懂得，bug在所难免，若您发现，还请告知，咱们共同进步。
参考文献：http://www.cppblog.com/biao/archive/2010/12/04/135457.html
