「霍夫曼算法java」哈夫曼算法的应用
今天给各位分享霍夫曼算法java的知识，其中也会对哈夫曼算法的应用进行解释，如果能碰巧解决你现在面临的问题，别忘了关注本站，现在开始吧！
本文目录一览：
- 1、用java写。已知四个带权的结点：(A,1),(B,2),(C,2),(D,3)，构造Huffman数，并给出每个结点的编码。
- 2、霍夫曼算法
- 3、Java中Huffman问题
- 4、哈夫曼编码与译码 java
- 5、java用huffman树压缩文件时，文件夹应该如何处理
用java写。已知四个带权的结点：(A,1),(B,2),(C,2),(D,3)，构造Huffman数，并给出每个结点的编码。
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
public class Huffman {
public static void main(String[] args) {
Huffman huff = new Huffman();
//准备数据
Node node_a = new Node("A", 1);
Node node_b = new Node("B", 2);
Node node_c = new Node("C", 2);
Node node_d = new Node("D", 3);
ArrayListNode list = new ArrayListNode();
list.add(node_a);
list.add(node_b);
list.add(node_c);
list.add(node_d);
//建树
huff.build(list);
//根
Node root = list.get(0);
//编码
huff.setHuffmanCode(root);
//
System.out.println(node_a.getName()+":"+node_a.huffmanCodeString);
System.out.println(node_b.getName()+":"+node_b.huffmanCodeString);
System.out.println(node_c.getName()+":"+node_c.huffmanCodeString);
System.out.println(node_d.getName()+":"+node_d.huffmanCodeString);
}
private void setHuffmanCode(Node huff) {
Node left = huff.getNodeLeft();
// 左节点追加"0"
if (left != null) {
left.huffmanCodeString = huff.huffmanCodeString + "0";
setHuffmanCode(left);
}
Node right = huff.getNodeRight();
// 右节点追加"1"
if (right != null) {
right.huffmanCodeString = huff.huffmanCodeString + "1";
setHuffmanCode(right);
}
}
public void build(ListNode list) {
// 按权值从小到大排序
if (list.size() 2)
Collections.sort(list, new ComparatorNode() {
@Override
public int compare(Node o1, Node o2) {
return o1.getWeight() - o2.getWeight();
}
});
//移除最小的2个
Node l = list.get(0);
Node r = list.get(1);
list.remove(l);
list.remove(r);
//生成一个新的，并设置左右子节点
Node newNode = new Node(l.getName() + r.getName(), l.getWeight() + r.getWeight());
newNode.setNodeLeft(l);
newNode.setNodeRight(r);
if (list.isEmpty()) {// 根节点
list.add(newNode);
return;
} else {
list.add(newNode);
build(list);
}
}
}
class Node {
//存储编码
public String huffmanCodeString = "";
private String name; // 名称
private int weight; // 权值
private Node nodeLeft; // 左节点
private Node nodeRight;// 右节点
public Node(String name, int weight) {
this.name = name;
this.weight = weight;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getWeight() {
return weight;
}
public void setWeight(int weight) {
this.weight = weight;
}
public Node getNodeLeft() {
return nodeLeft;
}
public void setNodeLeft(Node nodeLeft) {
this.nodeLeft = nodeLeft;
}
public Node getNodeRight() {
return nodeRight;
}
public void setNodeRight(Node nodeRight) {
this.nodeRight = nodeRight;
}
}
霍夫曼算法
霍夫曼算法的步骤是这样的：
·从各个节点中找出最小的两个节点，给它们建一个父节点，值为这两个节点之和。
·然后从节点序列中去除这两个节点，加入它们的父节点到序列中。
重复上面两个步骤，直到节点序列中只剩下唯一一个节点。这时一棵最优二叉树就已经建成了，它的根就是剩下的这个节点。
仍以上面的例子来看霍夫曼树的建立过程。
最初的节点序列是这样的：
a(6) b(15) c(2) d(9) e(1)
把最小的c和e结合起来
| (3)
a(6) b(15) d(9) +------+------+
| |
c e
不断重复，最终得到的树是这样的：
根
|
+-----33-----+
| |
15 +----18----+
| |
9 +------9-----+
| |
6 +--3--+
| |
2 1
这时各个字符的编码长度和前面我们说过的方法得到的编码长度是相同的，因而文件的总长度也是相同的： 3*6 + 1*15 + 4*2 + 2*9 + 4*1 = 63
考察霍夫曼树的建立过程中的每一步的节点序列的变化：
6 15 2 9 1
6 15 9 3
15 9 9
15 18
33
下面我们用逆推法来证明对于各种不同的节点序列，用霍夫曼算法建立起来的树总是一棵最优二叉树：
对霍夫曼树的建立过程运用逆推法：
当这个过程中的节点序列只有两个节点时（比如前例中的15和18），肯定是一棵最优二叉树，一个编码为0，另一个编码为1，无法再进一步优化。
然后往前步进，节点序列中不断地减少一个节点，增加两个节点，在步进过程中将始终保持是一棵最优二叉树，这是因为：
1.按照霍夫曼树的建立过程，新增的两个节点是当前节点序列中最小的两个，其他的任何两个节点的父节点都大于（或等于）这两个节点的父节点，只要前一步是最优二叉树，其他的任何两个节点的父节点就一定都处在它们的父节点的上层或同层，所以这两个节点一定处在当前二叉树的最低一层。
2.这两个新增的节点是最小的，所以无法和其他上层节点对换。符合我们前面说的最优二叉树的第一个条件。
3.只要前一步是最优二叉树，由于这两个新增的节点是最小的，即使同层有其他节点，也无法和同层其他节点重新结合，产生比它们的父节点更小的上层节点来和同层的其他节点对换。它们的父节点小于其他节点的父节点，它们又小于其他所有节点，只要前一步符合最优二叉树的第二个条件，到这一步仍将符合。
这样一步步逆推下去，在这个过程中霍夫曼树每一步都始终保持着是一棵最优二叉树。
由于每一步都从节点序列中删除两个节点，新增一个节点，霍夫曼树的建立过程共需 (原始节点数 - 1) 步，所以霍夫曼算法不失为一种精巧的编码式压缩算法。
附：对于 huffman 树，《计算机程序设计艺术》中有完全不同的证明，大意是这样的：
1．二叉编码树的内部节点（非叶子节点）数等于外部节点（叶子节点）数减1。
2．二叉编码树的外部节点的加权路径长度（值乘以路径长度）之和，等于所有内部节点值之和。（这两条都可以通过对节点数运用数学归纳法来证明，留给大家做练习。）
3．对 huffman 树的建立过程运用逆推，当只有一个内部节点时，肯定是一棵最优二叉树。
4．往前步进，新增两个最小的外部节点，它们结合在一起产生一个新的内部节点，当且仅当原先的内部节点集合是极小化的，加入这个新的内部节点后仍是极小化的。（因为最小的两个节点结合在一起，并处于最低层，相对于它们分别和其他同层或上层节点结合在一起，至少不会增加加权路径长度。）
5．随着内部节点数逐个增加，内部节点集合总维持极小化。
2．实现部分
如果世界上从没有一个压缩程序，我们看了前面的压缩原理，将有信心一定能作出一个可以压缩大多数格式、内容的数据的程序，当我们着手要做这样一个程序的时候，会发现有很多的难题需要我们去一个个解决，下面将逐个描述这些难题，并详细分析 zip 算法是如何解决这些难题的，其中很多问题带有普遍意义，比如查找匹配，比如数组排序等等，这些都是说不尽的话题，让我们深入其中，做一番思考。
Java中Huffman问题
这题在实现层面变得和Huffman树没啥关系...
反复取取最小值，使值成为优先级..用优先队列最合适。。可自己把输入方式补上
import java.util.Arrays;
import java.util.PriorityQueue;
public class Test {
public static void main(String[] args){
Integer[] a= {5, 3, 8, 2, 9};
PriorityQueueInteger q=new PriorityQueueInteger(Arrays.asList(a));
int cost=0;
while(q.size()1){
System.out.println(q); //可删
int c=q.poll()+q.poll();
q.offer(c); cost+=c;
}
System.out.println(q); //可删
System.out.println(cost);
}
}
[2, 3, 8, 5, 9]
[5, 5, 8, 9]
[8, 9, 10]
[10, 17]
[27]
59
哈夫曼编码与译码 java
class HaffmanNode //哈夫曼树的结点类
{
int weight; //权值
int parent,left,right; //父母结点和左右孩子下标
public HaffmanNode(int weight)
{
this.weight = weight;
this.parent=-1;
this.left=-1;
this.right=-1;
}
public HaffmanNode()
{
this(0);
}
public String toString()
{
return this.weight+", "+this.parent+", "+this.left+", "+this.right;
}
return code;
}
public static void main(String[] args)
{
int[] weight={5,29,7,8,14,23,3,11}; //指定权值集合
HaffmanTree htree = new HaffmanTree(weight);
System.out.println("哈夫曼树的结点数组:\n"+htree.toString());
String[] code = htree.haffmanCode();
System.out.println("哈夫曼编码:");
for (int i=0; icode.length; i++)
System.out.println(code[i]);
}
}
java用huffman树压缩文件时，文件夹应该如何处理
我讲一下我的思路：
用java的字节流读取一个文件，假设这个文件是100字节的。
int b;
FileInputStream in = new FileInputStream("文件路径");
while((b = in.read()) != -1){...}这样便得到100个整形（0~255）的数。
然后按照huffman的思想是统计每个数在这100个出现的概率，然后将最小的两个概率合起来作为两个叶子结点......一直做下去，直至生成一棵数。
关于霍夫曼算法java和哈夫曼算法的应用的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。