package cn.zhf.test;
import java.util.Comparator;
import java.util.NoSuchElementException;
public class HuffmanTree {
final int SIZE = 256;
public static void main(String[] args) {
new HuffmanTree().encode();
}
// 编码
public void encode() {
String str = "hello";
char[] ch = str.toCharArray();
int[] freq = new int[SIZE];
// 字符频率统计
for (int i = 0; i < ch.length; i++)
freq[ch[i]]++;
Node1 root = buildTrie(freq);
Node1.printTree(root);
printBinaryTree(root, 0);
}
// 打印树形二叉树
public static void printBinaryTree(Node1 root, int level) {
if (root == null)
return;
printBinaryTree(root.right, level + 1);
if (level != 0) {
for (int i = 0; i < level - 1; i++)
System.out.print("|\t");
System.out.println("|-------" + root.ch + ":" + root.freq);
} else
System.out.println(root.ch + ":" + root.freq);
printBinaryTree(root.left, level + 1);
}
/**
* 创建哈夫曼树 1.根据频率表,将所有字符按照频率从小到大的顺序插入优先级队列中
* 2.从优先级队列的第一个节点开始,把优先级最低的2个节点左右接到一个新的节点下,两者频率之和作为新节点的频率, 然后把这个新节点插入到优先级队列中
* 3.循环上述过程直到优先级队列只剩下一个根节点,此时哈夫曼树构造完成。
*/
public Node1 buildTrie(int[] freq) {
PQueue pq = new PQueue(freq.length);
for (int i = 0; i < freq.length; i++)
if (freq[i] > 0)
pq.insert(new Node1((char) i, freq[i], null, null));
while (pq.size() > 1) {
Node1 left = pq.delMin();
Node1 right = pq.delMin();
Node1 parent = new Node1('\0', left.freq + right.freq, left, right);
pq.insert(parent);
}
return pq.delMin();
}
}
// 节点类
class Node1 {
char ch;
int freq;
Node1 left, right;
public Node1(char ch, int freq, Node1 left, Node1 right) {
this.ch = ch;
this.freq = freq;
this.left = left;
this.right = right;
}
// 判断是否是叶节点
public boolean isLeaf() {
return left == null && right == null;
}
// 节点频率比较
public int compareTo(Node1 that) {
return this.freq - that.freq;
}
public String toString() {
return "ch:" + this.ch + "; freq:" + this.freq;
}
/**
* 编码: 从根节点开始,向左的方向上标记为0,向右的方向上标记为1
*/
private void printNode(String path) {
if ((left == null) && (right == null))
System.out.println(ch + " " + path);
if (left != null)
left.printNode(path + '0');
if (right != null)
right.printNode(path + '1');
}
public static void printTree(Node1 tree) {
tree.printNode("");
}
}
// 优先级队列
class PQueue {
Node1[] node1;
int N;
Comparator comparator;
public PQueue(int size) {
node1 = new Node1[size];
N = 0;
}
public PQueue() {
}
public boolean isEmpty() {
return N == 0;
}
public int size() {
return N;
}
// 插入队列中,新插入的节点先放在队尾
public boolean insert(Node1 node) {
if (node1.length == size())
return false;
node1[++N] = node;
swim(N);
return true;
}
// 新插入的数与其他数比较
private void swim(int k) {
while (k > 1 && greater(k / 2, k)) {
swap(k, k / 2);
k = k / 2;
}
}
// 比较大小
private boolean greater(int i, int j) {
if (comparator == null) {
return ((Comparable) node1[i].freq).compareTo(node1[j].freq) < 0;
} else {
return comparator.compare(node1[i].freq, node1[j].freq) < 0;
}
}
// 交换位置
private void swap(int i, int j) {
Node1 temp = node1[i];
node1[i] = node1[j];
node1[j] = temp;
}
// 返回并移除最小值
public Node1 delMin() {
if (isEmpty())
throw new NoSuchElementException("underflow!");
else
return node1[N--];
}
}
分享到:
相关推荐
利用哈夫曼编码进行通信可以大大提高信道利用率,缩短信息传输时间,降低传输成本。但是,这要求在发送端通过一个编码系统对待传输数据预先编码,在接收端将传来的数据进行译码(复原)。对于双工信道(即可以双向...
详细描述了哈夫曼树的构造方法,同时推广到三元哈夫曼编码,并用C语言于VC++上实现
这个代码是用C/C++实现哈夫曼编码并将编码输出。 文本为操作者输入,,对各字符进行频率统计,然后进行哈夫曼编码,并将编码结果输出,同时可求得平均码长。
哈夫曼树与哈夫曼编码 建立哈夫曼树并计算哈夫曼编码
哈夫曼编码实现文本文件的压缩,可作为数据压缩作业的参考
压缩文件即读文件,统计文件中的字符个数,对文件进行哈夫曼编码和译码,并将编码译码后的字符存储在文件中。 完成功能的详细说明: 1.统计文本文件中各字符的频率(涉及读文件,统计字符个数); 2.对文件中的...
哈夫曼编码(Huffman Coding),是一种熵编码方式,哈夫曼编码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法,该方法完全依据字符出现概率来构造异字头的平均长度最短的码字,有时称之为最佳编码,一般...
摘 要:哈夫曼编码是一种数据编码方式,以哈夫曼树——即最优二叉树,用带权路径长度最小的二叉树,对数据进行重编码,经常应 用于数据压缩。在计算机信息处理中,“哈夫曼编码”是一种一致性编码法(又称“熵编码法...
利用哈夫曼编码思想,设计对一个文本文件(.txt)中的字符进行哈夫曼编码,生成编码压缩文件(.txt),并且还可将压缩后的文件进行解码还原为原始文本文件(.txt)。 实现的功能: (1)压缩:实现对文件的压缩,生成...
哈夫曼编码课程设计,我要让所以人都知道写一个哈夫曼编码树便不是难事。
哈夫曼编码是广泛用于数据文件压缩的十分有效的编码方式,其压缩率通常在20%—90%之间。哈夫曼编码算法是通过使用字符在文件中出现的频率表来构造最优前缀码的贪心算法。所谓前缀码,即是任一字符的编码都不是其他...
这是那个用c语言来实现的哈夫曼编码程序,可以对输入的数据进行相应的编码……
c语言实现哈夫曼编码,并求平均码长 c语言实现哈夫曼编码,并求平均码长
本人的小工具仅针对英文大小字母及 ' '\n' ' ' 字符针对性的进行了哈夫曼编码,若想实现中文及各种支持语言的编码,可在此代码基础上,进行优化。 详细介绍参考:...
一、【问题描述】 利用哈夫曼编码进行通信可以大大提高信道利用率,缩短信息传输时间,降低传输成本 。但是,这要求在发送端通过一个编码系统对待传数据预先编码,在接收端将传来的数 据进行译码,此实验即设计这样...
c++ 源代码 哈夫曼树 哈夫曼编码 部分代码如下: #include"Huffman.h" #include"hfmTree.h" #include using namespace std; int main() { cout~~~~~~~~~~~~~welcome to Huffman encodrding&decoding system ~~~~~~...
要求对一段数据序列进行哈夫曼编码,使得平均码长最短,输出各元素编码和编码后的数据序列。 ①组成序列的元素是[0-9]这10个数字,每个数字其对应的4位二进制数表示。比如5对应0101,9对应1001。 ②输入数据序列的...
数据结构课程设计,实现哈夫曼编码,译码,打印哈夫曼树