`

霍夫曼树(Huffman tree)

阅读更多

 

1.基本概念

  • 霍夫曼树又称最优二叉树,是一种带权路径长度最短的二叉树。所谓树的带权路径长度,就是树中所有的叶结点的权值乘上其到根结点的路径长度(若根结点为0层,叶结点到根结点的路径长度为叶结点的层数)。
  • 树的带权路径长度:设一棵二叉树有 n 个叶子结点,每个叶子结点拥有一个权值W 1 ,W 2 ...... n ,从根结点到每个叶子结点的路径长度分别为 L1 L2......Ln ,那么树的带权路径长度为从树根到每一结点的路径长度之和,记为WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln)。可以证明霍夫曼树的WPL是最小的。

 Huffman

2.构造霍夫曼树的方法

对于已知的一组叶子的权值 1 ,W 2...... ,W n

①首先把 n 个叶子结点看做 n 棵树(仅有一个结点的二叉树),把它们看做一个森林。

②在森林中把权值最小和次小的两棵树合并成一棵树,该树根结点的权值是两棵子树权值之和。这时森林中还有 n-1 棵树。

③重复第②步直到森林中只有一棵为止。此树就是哈夫曼树。

 

n叶子结点的哈夫曼树共有2n-1个结点

 

3.霍夫曼编码

霍夫曼编码(Huffman Coding)是一种编码方式,是一种用于无损数据压缩的熵编码(权编码)算法。1952年,David A. Huffman在麻省理工攻读博士时所发明的,并发表于《一种构建极小多余编码的方法》(A Method for the Construction of Minimum-Redundancy Codes)一文。

 

在通信及数据传输中多采用二进制编码。为了使电文尽可能的缩短,可以对电文中每个字符出现的次数进行统计。设法让出现次数多的字符的二进制码短些,而让那些很少出现的字符的二进制码长一些。假设有一段电文,其中ABCD出现的频率为0.4, 0.3, 0.2, 0.1则得到的哈夫曼树和二进制前缀编码如图所示。在树中令所有左分支取编码为 0 ,令所有右分支取编码为1。将从根结点起到某个叶子结点路径上的各左、右分支的编码顺序排列,就得这个叶子结点所代表的字符的二进制编码。

 

这些编码拼成的电文不会混淆,因为每个字符的编码均不是其他编码的前缀,这种编码称做前缀编码

4.霍夫曼编码实现

 下面是java实现的霍弗曼编码,包括霍夫曼树的构造,编码和解码。

package com.iteye.cake513.code;

import java.util.*;
/** 
 * @ClassName: Huffman 
 * @Description: TODO(Huffman编码) 
 * @author liujie
 * @date 2011-10-4 下午09:49:29 
 *  
 */

class HuffmanNode implements Comparable<HuffmanNode> {
	
	private char letter;
	private int count;//字符letter出现的频率,即权重
	private HuffmanNode left;
	private HuffmanNode right;
	
	public HuffmanNode(char letter, int count) {
		this.letter = letter;
		this.left = null;
		this.right = null;
		this.count = count;
	}
	
	public HuffmanNode(HuffmanNode left, HuffmanNode right) {
		this.letter = '?';
		this.left = left;
		this.right = right;
		this.count = left.count + right.count;
	}
	
	//为了进行排序
	public int compareTo(HuffmanNode o) {
		return count - o.count;
	}
	
	public boolean isLeaf() {
		return(this.left == null && this.right == null);
	}

	public HuffmanNode getLeft() {
		return left;
	}

	public HuffmanNode getRight() {
		return right;
	}

	public char getLetter() {
		return letter;
	}

}

public class Huffman {
	
	private HuffmanNode root;
	private HashMap<Character, String> map;//用于存放字符到编码的映射
	
	@SuppressWarnings("unchecked")
	public Huffman() {
		char[] letters = "bekprs_&".toCharArray();
		int[] counts = {2,7,1,1,1,2,2,1};
		map = new HashMap<Character, String>();
		root = generateTree(letters, counts);
		
		generateCodes(root, "");
		for (int i = 0; i < letters.length; i++) {
			System.out.print(letters[i] + "(" + counts[i] +") ");
		}
		System.out.println("生成二进制编码如下:");
		Iterator itr = map.entrySet().iterator();
		while (itr.hasNext()) {
			Map.Entry entry = (Map.Entry)itr.next();
			System.out.print(entry.getKey() + ":" + entry.getValue() +" ");
		}
		System.out.println();
	}
	
	//构造霍夫曼树
	private HuffmanNode generateTree(char[] letters, int[] counts) {
		List<HuffmanNode> list = new LinkedList<HuffmanNode>();
		
		for(int i = 0; i < letters.length; i++) {
			list.add(new HuffmanNode(letters[i], counts[i]));
		}
		while (true) {
			Collections.sort(list);
			HuffmanNode a = list.remove(0);
			if (list.isEmpty()) {
				return a;
			}
			HuffmanNode b = list.remove(0);
			list.add(new HuffmanNode(a, b));
		}
	}
	
	//生成编码,存放在HashMap中,key对应letter,value对应letter的二进制编码
	private void generateCodes(HuffmanNode root, String code) {
		if (root.isLeaf()) {
			map.put(root.getLetter(), code);
		} else {
			generateCodes(root.getLeft(), code + "0");
			generateCodes(root.getRight(), code + "1");
		}
	}
	
	//对给定电文进行编码,messag中的字符必须属于生成编码用到的字符集合letters
	private String encode(String message) {
		StringBuilder result = new StringBuilder();
		
		for (char c : message.toCharArray()) {
			result.append(map.get(c) + " ");
		}
		return result.toString();
	}
	
	//对编码进行解码
	public String decode(String encodeMessage) {
		StringBuilder result = new StringBuilder();
		HuffmanNode node = root;
		
		for (char c : encodeMessage.toCharArray()) {
			if (c == '0') {
				node = node.getLeft();
			} else if (c == '1') {
				node = node.getRight();
			}
			if (node.isLeaf()) {
				result.append(node.getLetter());
				node = root;
			}
		}
		return result.toString();
	}
	
	public static void main(String[] args) {
		Huffman hfm = new Huffman();
		
		String encode = hfm.encode("beekeepers_&_bees");
		System.out.println("对beekeepers_&_bees编码:" + encode);
		String decode = hfm.decode(encode);
		System.out.println("对上面进行解码:" + decode);
	}
}

 

0
2
分享到:
评论

相关推荐

    基于HuffmanTree实现的对数据进行编码

    基于HuffmanTree实现的对数据进行编码是一种高效的数据压缩方法,源于1952年David Huffman提出的一种熵编码算法——霍夫曼编码(Huffman Coding)。本项目设计主要探讨了如何构建Huffman树,并利用它对数据进行编码...

    霍夫曼树和堆排序

    `HuffmanTree.cpp`文件可能包含了霍夫曼树的构建、遍历以及编码生成的相关函数。 霍夫曼编码是通过霍夫曼树生成的一种前缀码,即没有公共前缀的编码,这使得编码具有自解释性,无需额外的结束标识就能正确解码。在...

    霍夫曼树编码解码

    在提供的代码文件`HuffmanTree.cpp`中,可能包含了构建霍夫曼树、生成霍夫曼编码以及解码的实现。`HuffmanCode.txt`文件则是霍夫曼编码表,其中列出了每个字符及其对应的霍夫曼编码。通过运行`HuffmanTree.cpp`,...

    霍夫曼树和二叉搜索树代码实现

    从给定的文件信息来看,该段代码主要涉及到了数据结构中的两个重要概念:霍夫曼树(Huffman Tree)和二叉搜索树(Binary Search Tree),并使用C++语言进行实现。以下是对这两个知识点的详细解析: ### 霍夫曼树...

    [实例]利用霍夫曼树获得霍夫曼编码并进行加密和解密

    总结起来,本实例的`HuffmanTree.cpp`和`HuffmanTree.h`文件将展示如何使用C++实现霍夫曼树的创建、霍夫曼编码的生成与使用,以及可能涉及的数据加密和解密方法。通过阅读和理解这些代码,开发者可以深入理解霍夫曼...

    C 语言项目源码大全 链表Huffman Tree

    本项目聚焦于C语言实现的链表和霍夫曼树(Huffman Tree),这对于理解数据结构与算法有着深远的意义。以下是关于这两个主题的详细讲解。 链表是一种数据结构,它不同于数组,不连续存储数据。每个链表节点包含数据...

    HuffmanTree:用C ++编写的霍夫曼树

    源代码可能包括了以上所述的各个部分,如`Node`类表示霍夫曼树的节点,`HuffmanTree`类负责树的构建和编码/解码,以及可能的`main`函数用于测试和运行程序。阅读这些代码可以帮助你更好地理解和实现霍夫曼树。 ...

    huffman_编码_霍夫曼树_源码

    它基于一种称为霍夫曼树(Huffman Tree)的数据结构,也被称为最优二叉树或最小带权路径长度树。这个压缩过程是通过为每个字符分配一个唯一的二进制码字,使得频繁出现的字符拥有较短的编码,从而减少总的编码长度。...

    霍夫曼树实现编码解码C语言实现

    霍夫曼树(Huffman Tree),也称为最优二叉树,是数据压缩技术中的关键工具,主要用于构建霍夫曼编码。这种编码方法基于字符出现频率,频繁出现的字符赋予较短的编码,不常出现的字符则赋予较长的编码,以此达到数据...

    C语言实现Huffman树,Huffman编码

    在提供的压缩包文件`HuffmanTree`中,可能包含了实现以上过程的源代码文件,比如`huffman.c`和`huffman.h`,它们分别包含了函数声明和实现。通过阅读和理解这些代码,可以加深对Huffman编码和数据结构的理解,并能够...

    霍夫曼树——创建霍夫曼数及其部分应用

    void createHTree(HuffmanTree HT, char *c, int *w, int n); /* 选择权重最小的两个节点 */ void select(HuffmanTree HT, int n, int *p1, int *p2); /* 生成霍夫曼编码 */ void HuffmanCoding(HuffmanTree HT, ...

    链表HuffmanTree.zip

    链表HuffmanTree.zip文件很可能包含了关于链表和Huffman树的详细教程或代码示例。为了理解这个主题,我们需要分别讨论链表和Huffman树。 链表是一种线性数据结构,与数组不同,它不连续存储元素。每个节点包含数据...

    用C++实现霍夫曼树编码

    - `HuffmanTree` 是指向`HTNode`的指针类型,表示霍夫曼树。 - `HuffmanCode` 是指向字符数组的指针类型,用于存储霍夫曼编码。 2. **函数定义**: - `LookFor` 函数用于查找字符串中的特定字符并返回其出现次数...

    霍夫曼树代码

    霍夫曼树(Huffman Tree),也称为最优二叉树,是一种带权路径长度最短的二叉树,在数据压缩领域有着广泛的应用。在霍夫曼树中,权值较小的叶子节点通常距离根节点较远,而权值较大的叶子节点距离根节点较近。这样...

    Huffman树编码解码

    - Huffmantree:一个指向HTnode结构体的指针类型,用于方便地操作霍夫曼树。 - Huffmancode:一个指向字符指针的指针,用于存储每个字符的霍夫曼编码。 - 主函数中,通过输入字符串构建字符频率数组,进而构建霍夫曼...

    huffmanTree_temp01-master.zip

    在这个项目“huffmanTree_temp01-master”中,我们将深入探讨如何用C语言来实现Huffman树,并了解其背后的理论和应用。 一、Huffman树的基本概念 Huffman树是由美国计算机科学家David A. Huffman在1952年提出的一...

    霍夫曼树——数据结构

    - `HuffmanTree` 类型定义:指向 `HTNode` 的指针类型,表示霍夫曼树。 - `HuffmanCode` 类型定义:指向字符数组的指针类型,表示霍夫曼编码。 2. **选择权值最小的节点函数 `Select`**: - 该函数的作用是在...

    【数据结构与算法】-哈夫曼树(Huffman Tree)与哈夫曼编码

    哈夫曼树(Huffman Tree)与哈夫曼编码(Huffman Coding)是数据结构与算法领域中的一个重要概念,主要用于数据的无损压缩。在计算机科学中,它们扮演着优化存储空间、提高传输效率的关键角色。哈夫曼编码是一种可变...

    根据节点权值构建霍夫曼树

    在实际编程实现中,`HuffmanTree.c`文件很可能是包含了构建和操作霍夫曼树的C语言源代码。可能包含的数据结构有: - 结构体定义,用于表示霍夫曼树的节点,包括权值、左子节点和右子节点等属性。 - 队列(优先队列...

    基于matlab实现的霍夫曼Huffman编码译码GUI界面设计 源程序代码.rar

    这些函数可能包括`count_frequencies`用于计算字符频率,`build_huffman_tree`用于构造霍夫曼树,以及`generate_codes`用于生成编码。接着,利用MATLAB的GUI工具箱创建一个用户界面,可以包括输入文本框、编码按钮、...

Global site tag (gtag.js) - Google Analytics