最近在学习数据结构,但一直没做笔记,只知道敲代码。现在开始记录自己所敲类容。
一、准备知识
1、优先队列:是带有优先权的元素序列。普通队列实现是采用先进先出的方式,优先队列是优先权最小的元素先出队列。优优先队列的长度是所包含元素的个数。空优先队列长度为0;
2、完全二叉树:有严格的形状要求,从根结点到每一层的结点从左到右连续填充,除了最后一层外,其余各层都是满的,并且最下一层的结点都集中在该层的最左边。
3、最小堆:如果一棵二叉树每一个结点存储的值都小于或等于其子节点的值,则称该二叉树具有堆序性质。堆是具有堆序性质的完全二叉树。
二、堆的操作(数组实现)
1、堆的插入:1)扩展堆到下一个空闲位置,作为一个待填充的槽;
2)比较槽所对应的父结点与新插入元素的大小,如果小于或等于新插入的元素,则将新结点复制到槽结点。否则将槽所对应的父结点值复制到槽结点处,同时将槽上移到父节点处。
3)反复执行2)将父节点下移动,槽结点上移操作。直到父节点值小于或等于要插入的元素的值,或者槽到达根结点,这时将插入元素值复制到槽结点。
2、堆的删除:1)复制堆最后一个元素到变量last中,同时将最后一个元素置为null;
2)删除根结点(优先权最小结点),同时将根结点处作为一个槽;
3)获取槽结点子节点中最小元素值与last元素值做比较,如果大于last结点值,则将last结点值复制到槽结点,同时结束。否则将子节点中最小值复制到槽结点,同时将槽结点下移动到最小子结点位置。
4)反复执行3)将槽结点下移动,直到last大于任何一个子节点或者槽结点到达一个叶结点位置,这时将last值复制到槽结点并结束。
3、堆排序:每次从堆中获取最小权值,获取的序列就是一个有序序列。
三、Huffman编码:一种变长的编码。Huffman编码为字符分配代码,其长度取决于对应字母使用的频率或权。每个字符的Huffman编码是从Huffman树(一种满二叉树)中获得。Huffman树中的每个叶结点对应一个字符,叶结点对应的权重就为该字符使用的频率,其目的按照最小外部路径权重建立一棵二叉树。一个叶结点的加权路径长度定义为权乘以深度。具有最小外部路径权重的二叉树就是(对于给定的叶节点集合)具有加权路径长度之和最小的二叉树。权大的叶结点深度小,因而它相对于总路径长度的花费最小。因此其他叶结点的权值小,则在树的较深处。
1、建立n个结点的Huffman树过程
1)创建n个初始的Huffman树,每棵树只包含一个结点,叶结点的记录对应字符及其频率。将n棵树按照权的大小进行排序,接着获取两颗权最小的树,把他们作为两颗子树链接到一个分支结点下面,且分支结点的权为该两个结点的权值和,再把所得到的新树放回到序列中适当位置,使得权顺序保持为升序。重复上述步骤,知道序列中只剩下一个元素,则Huffman树建立完毕。
四、代码实现
1、优先队列ADT
package com.structure.huffman;
/**
* 优先队列ADT
* @author hudp
* 2011-11-28
*/
public interface PriorityQueue {
//添加新节点
void insert(Comparable val);
//移除节点
Comparable remove();
//返回节点数
int size();
//获取优先级最小的节点
Comparable get();
//清除数据
void clear();
}
2、堆实现优先队列
package com.structure.huffman;
/**
* 采用最小堆实现优先队列
* @author hudp
* 2011-11-28
*/
public class HeapPriorityQueue implements PriorityQueue {
private final int DEFAULT_SIZE = 10;//默认大小10
private Comparable[] array;
private int count ;
public HeapPriorityQueue(){
array = new Comparable[DEFAULT_SIZE];
count = 0;
}
@Override
public void insert(Comparable val) {
if(array.length >= count){
expand();
}
int holePoint = count ++;
while(holePoint > 0){
int parentPoint = (holePoint -1)/2;
if(array[parentPoint].compareTo(val) < 0){
break;
}
array[holePoint] = array[parentPoint];
holePoint = parentPoint;
}
array[holePoint] = val;
}
//扩展数组长度为先前的2倍
private void expand() {
Comparable[] newArr = new Comparable[array.length * 2];
for(int i = 0 ; i < array.length ; i ++){
newArr[i] = array[i];
}
array = newArr;
}
@Override
public Comparable remove() {
if(count <= 0){
throw new IllegalStateException("error count !");
}
Comparable min = array[0];
Comparable last = array[--count];
array[count] = null;
int holePoint = 0;
int child = holePoint * 2 + 1;//left节点
while(child < count){
if(child + 1 < count && array[child].compareTo(array[child+1]) > 0){
child ++;
}
if(array[child].compareTo(last) > 0){
break;
}
array[holePoint] = array[child];
holePoint = child;
child = holePoint * 2 + 1;
}
array[holePoint] = last;
return min;
}
@Override
public int size() {
return count;
}
@Override
public Comparable get() {
if(count <= 0 ){
throw new IllegalStateException("no data !");
}
return array[0];
}
@Override
public void clear() {
for(int i = 0 ; i < count ; i ++){
array[i] = null;
}
count = 0;
}
}
3、Huffman树实现
package com.structure.huffman;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
/**
* Huffman tree实现
* @author hudp
* 2011-11-28
*/
public class HuffmanTree {
private CodeMember[] codeTable;
private final int SYS_LEN = 256;//可以接受256个8位字符
private HuffNode root;//Huffman树根
public HuffmanTree() {
codeTable = new CodeMember[SYS_LEN];
root = null;
}
//Huffman树节点
private class HuffNode implements Comparable {
char letter ;//ASCII字符
int frequency;//出现频率
HuffNode left, right;
public HuffNode() {
letter = '\0';
frequency = 0;
left = right = null;
}
@Override
public int compareTo(Object other) {
HuffNode otherNode = (HuffNode) other;
return this.frequency = otherNode.frequency;
}
}
//编码表
private class CodeMember {
String code;
int frequency;
public CodeMember() {
frequency = 0;
code = "";
}
}
//创建树
public void buildHuffTree(String text) {
for (int i = 0; i < text.length(); i++) {
int k = text.charAt(i);
if (null == codeTable[k]) {
codeTable[k] = new CodeMember();
}
codeTable[k].frequency++;
}
PriorityQueue pq = new HeapPriorityQueue();
root = buildHuffTree(pq);
createCode();
}
//创建树
private HuffNode buildHuffTree(PriorityQueue pq) {
for (int i = 0; i < codeTable.length; i++) {
if (null != codeTable[i]) {
HuffNode node = new HuffNode();
node.letter = (char) i;
node.frequency = codeTable[i].frequency;
pq.insert(node);
}
}
while (pq.size() > 1) {
HuffNode childLeft = (HuffNode) pq.remove();
HuffNode childRight = (HuffNode) pq.remove();
HuffNode parent = new HuffNode();
parent.frequency = childLeft.frequency + childRight.frequency;
parent.left = childLeft;
parent.right = childRight;
pq.insert(parent);
}
return (HuffNode) pq.remove();
}
//创建编码
private void createCode() {
String code = "";
createCode(root, code);
}
private void createCode(HuffNode ref, String code) {
if (ref == null) {
return;
} else if (null == ref.left && null == ref.right) {
int i = ref.letter;
codeTable[i].code = code;
} else {
createCode(ref.left, code + "0");
createCode(ref.right, code + "1");
}
}
//编码
public String encode(String text) {
StringBuilder sbf = new StringBuilder();
int len = text.length();
for (int i = 0; i < len; i++) {
int k = text.charAt(i);
if (null == codeTable[k]) {
return null;
}
sbf.append(codeTable[k].code);
}
return sbf.toString();
}
//解码
public String decode(String code) {
StringBuilder sbf = new StringBuilder();
int k = 0;
while (k < code.length()) {
HuffNode ref = root;
while (null != ref.left && null != ref.right) {
int l = code.charAt(k);
if ('0' == l) {
ref = ref.left;
} else if ('1' == l) {
ref = ref.right;
} else {
throw new IllegalArgumentException("error input!");
}
k++;
}
sbf.append(ref.letter);
}
return sbf.toString();
}
public static void main(String[] args) throws IOException {
System.err.println("input data :");
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
HuffmanTree ht = new HuffmanTree();
String text = br.readLine();
ht.buildHuffTree(text);
String encode = ht.encode(text);
System.err.println("edcode:" + encode);
System.err.println("decode:" + ht.decode(encode));
}
}
说明:
1、编码:字符用编码标记:从根结点开始,分别把'0'(对应左子节点那条边)或'1'(对应右子结点的那条边),其编码就是从根结点到对应字符叶结点路径的二进制编码。在遍历的过程中,每当遇到一个叶结点,就把该结点包含的字符所对应的编码串填入编码表中。
2、反编码:从左到右逐位扫描编码串,直到确定一个字符位置。(从根结点开始进行反编码,根据每一位的值'0‘或'1‘选择左分支还是右分支,直到到达一个叶结点,取得其对应的字符)
3、前缀特性:如果一组编码中任何一个编码都不是另外一个编码的前缀,则称这组代码符合前缀特性。这种前缀特性保证了代码串被反编码时不会有多种可能。由于任何一个编码的前缀都对应一个分支结点,而每个编码都对应一个字符,所以Huffman编码符合前缀特性。
分享到:
相关推荐
本项目将深入探讨如何使用C语言实现Huffman树和Huffman编码。 首先,我们要理解Huffman树(也称为最优二叉树或最小带权路径长度树)。这种特殊的二叉树是由赫尔曼·霍夫曼在1952年提出,其构建过程基于字符出现的...
本篇文章将详细介绍如何在C语言中实现Huffman编码,包括Huffman树的构建、编码过程以及解码过程,并提供完整的代码示例。 #### 二、Huffman编码原理 1. **统计字符频率**:首先统计待压缩文本中每个字符出现的频率...
huffman的简单压缩,简单实现,总之非常简单23333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333
总结来说,Huffman编码是一种基于字符频率的无损压缩方法,通过构建特定的Huffman树来为每个字符分配唯一的二进制编码,以实现高效的压缩效果。理解并实现这一编码机制,对于学习数据结构和算法,尤其是数据压缩技术...
以下是一段简单的C代码片段,展示了如何构建Huffman树: ```c typedef struct Node { char data; int freq; struct Node* left; struct Node* right; } Node; // 创建新节点 Node* newNode(char data, int ...
Huffman编码的实现主要依赖于Huffman树。Huffman树是一种特殊的二叉树,它由一系列步骤构建而成: 1. **初始化**:根据给定的字符及其出现频率(权重),构建一系列只有根节点的二叉树(即每个根节点代表一个字符)...
哈弗曼编码(Huffman Coding)是一种用于数据压缩的高效算法,由大卫·艾尔文·哈弗曼在1952年提出。它利用了字符出现频率的不均匀性,构建了一棵特殊的二叉树——哈弗曼树,使得出现频率高的字符具有较短的编码,而...
VC6.0 下实现的哈夫曼算法源代码,读完能对哈夫曼算法有深刻的了解。
然后,构建Huffman树,Matlab虽然没有内置的Huffman编码函数,但可以通过自定义算法实现。这通常涉及构造最小堆和合并节点的过程,直到只剩下一个根节点,此时得到的树结构就是Huffman树。 编码过程是从根节点开始...
它的基本思想是通过构建一棵特殊的二叉树——Huffman树(也称为最优二叉树或最小带权路径长度树),来为源符号(如文件中的字符)分配具有变长的编码,使得出现频率高的符号拥有较短的编码,而出现频率低的符号则有...
使用文件保存初始的文本数据及最终的结果。 文件名为inputfile1.txt的文件保存的...统计inputfile1.txt中各字符的出现频率,并据此构造Huffman树,编制Huffman编码;根据已经得到的编码,对01形式的编码段进行译码。
哈夫曼编码的解码过程相对简单:只需按照二进制编码从根节点开始遍历哈夫曼树,遇到0向左走,遇到1向右走,直到到达叶子节点,即可得到对应的原始字符。 在实际应用中,哈夫曼编码通常会配合其他技术,如字典编码...
5. **编写C语言代码**:使用C语言实现上述过程,包括读取文件、构建Huffman树、生成编码表、进行文件压缩等功能。 #### 四、示例代码分析 在给出的代码片段中,可以看到一个主函数`main`的框架,它接受待压缩文件...
1. **Huffman树的生成方法**:理解Huffman树的生成过程及其重要性。 2. **位操作**:掌握如何将编码一位一位地保存至文件中,以及如何从文件中读取。 3. **编码文件中需要保存的数据**:除了字符编码之外,还需要...
- `compress()`函数负责执行文件的压缩操作,包括构建Huffman树、生成Huffman编码表以及对文件进行编码。 - `uncompress()`函数负责解码Huffman编码的文件,恢复原始数据。 - `help()`函数提供了简单的使用说明,...
1. 数据结构的选择:选择合适的数据结构(如堆、队列)来有效地实现Huffman树的构建和编码查找。 2. 编码表示:如何有效地表示和存储Huffman编码,例如使用字典或列表,以及处理编码长度不一致的问题。 3. 文件I/O:...
哈夫曼编码(Huffman Coding)是一种数据压缩算法,由美国计算机科学家大卫·艾尔文·哈夫曼在1952年提出。这个算法基于字符出现频率进行编码,经常出现的字符会得到较短的编码,而较少出现的字符则获得较长的编码,...
Huffman编码的关键在于构建最优的Huffman树,它满足以下特性: 1. **二叉树结构**:Huffman树是特殊的二叉树,每个节点代表一个字符,叶子节点代表实际的字符,非叶子节点则不存储任何信息。 2. **最小带权路径...
C语言实现哈夫曼编码的关键在于理解哈夫曼树的构造过程以及如何通过这个树进行编码和解码。代码中添加详细的注释可以帮助理解每个步骤的作用,同时也有助于其他开发者阅读和维护代码。 在实际应用中,哈夫曼编码常...