Java实现Greedy Algorithm进行Huffman Encoding and Decoding
发布时间
阅读量：
阅读量
写在前面：
我也是一位热衷于Java语言开发的专业人士。特此记录下我的学习历程，并对文章中涉及的代码规范、排版方式以及算法性能提出疑问。恳请您们的宝贵意见和建议。也希望能够与 fellow learners 进行交流与分享。
——Steven_zhaosh@163.com
一.问题描述
假设一个文件仅包含七个字符a,e,i,s,t,space,newline这七种类型，在特定场景下它们的出现频率分别为：a出现10次,e出现15次,i出现12次,s出现3次,t出现4次,space出现13次以及newline出现一次。根据信息编码理论，在使用等长编码时所需的基本单位数量即为对数值向上取整的结果（即log7向上取整为3比特）。因此，在这种情况下整个文件的信息量计算方式为：(各字符频率之和)乘以每位编码所需的比特数即（10+15+12+3+4+13+1）×3=
在现实场景中, 大量较大的文件通常是某个程序产生的输出。
这些大量较大的文件中, 高频与低频字符之间的使用比例通常有显著差异。
如果对所有不同频率等级（高低频）采用统一码长, 这会极大浪费存储空间。
更合理的解决方案是, 对出现次数少（低频）则应采用较长码长,
而高频字符则可配以较短码长。
该过程采用二叉树结构对各字符对应的二进制编码进行分配。需要注意的是其必须是一棵满二叉树其任意一个节点要么没有子节点要么有两个子节点。
可以看到此时总大小为146
这里给出我的实现
import java.util.Collection;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Scanner;
//哈夫曼编码
public class Main {
/** * @param args
*/
private static LinkedList<HufNode> hufList = new LinkedList<HufNode>();//容器存放节点值
class HufNode implements Comparable<HufNode>{
int value;
String name;
HufNode Lchild = null;
HufNode Rchild = null;
public HufNode(){
}
public HufNode(int v,String s){
value = v;
name = s;
}
public HufNode(HufNode l,HufNode r){
Lchild =l;
Rchild =r;
value = Lchild.value + Rchild.value;
}
@Override
public int compareTo(HufNode node1) {
// TODO Auto-generated method stub
if (value<node1.value) {
return -1;
}else if (value == node1.value) {
return 0;
}else {
return 1;
}
}
}
//哈夫曼编码
public static void HufmanCode(){
if (hufList.size()==1) {
return;
}
while(hufList.size()>1){
Collections.sort(hufList);
HufNode node = new Main().new HufNode(hufList.get(0),hufList.get(1));
hufList.remove();
hufList.remove();
hufList.add(node);
}//此时hufList中只有一个元素，这就是编码后的哈夫曼树的根节点
}
//解码，后序遍历
public static void decode(HufNode n,String code){
if ((n.Lchild==null)&&(n.Rchild==null)) {
System.out.print("元素值为 "+n.name+" 编码为："+code);
System.out.println();
return;
}
decode(n.Lchild, code+"0");
decode(n.Rchild, code+"1");
return;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt();//待编码元素个数
for(int i=0;i<N;i++){
hufList.add(new Main().new HufNode(scanner.nextInt(),scanner.next()));
}
HufmanCode();
decode(hufList.get(0), "");
}
}
全部评论 (0)
还没有任何评论哟~