如何用Java实现啥夫曼编码

大家可能会想,程序和第三方提供了很多压缩方式,何必自己写压缩代码呢?不错,如GZIP这样的压缩工具很多,可是在某些情况下(如文本内容小且字符不重复),GZIP压缩后会比原始文本还要大。所以在某些特殊情况下用自己的压缩方式可以更优。

大家可能早已忘记了在学校学习的哈夫曼知识,可以先在百度百科了解一下哈夫曼知识:http://baike.baidu.com/view/127820.htm

哈夫曼思想:统计文本字符重复率,求出各字符权值,再构造出一颗最优二叉树(又称哈夫曼树),然后给每个叶子结点生成一个以位(bit)为单位的码值,每个码值不能做为其 他码值的前缀,再将码值合并以每8个生成一个字节。


代码如下:

package com.huffman;

/**
 * 结点
 * @author Davee
 */
public class Node implements Comparable<Node> {
    int weight;//权值
    Node leftChild;//左孩子结点
    Node rightChild;//右孩子结点
    String huffCode;
    private boolean isLeaf;//是否是叶子
    Character value;

public Node(Character value, int weight) {
        this.value = value;
        this.weight = weight;
        this.isLeaf = true;
    }

public Node(int weight, Node leftChild, Node rightChild) {
        this.weight = weight;
        this.leftChild = leftChild;
        this.rightChild = rightChild;
    }

public void increaseWeight(int i) {
        weight += i;
    }

public boolean isLeaf() {
        return isLeaf;
    }

@Override
    public int compareTo(Node o) {
        return this.weight - o.weight;
    }
}

代码如下:

package com.huffman;

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;

public class HuffmanTree {
    private boolean debug = false;

private HashMap<Character, Node> nodeMap;
    private ArrayList<Node> nodeList;

public HuffmanTree() {
        nodeMap = new HashMap<Character, Node>();
        nodeList = new ArrayList<Node>();
    }

public void setDebug(boolean debug) {
        this.debug = debug;
    }

public String decode(Map<String, Character> codeTable, String binary) {
        int begin = 0, end = 1, count = binary.length();
        StringBuffer sb = new StringBuffer();
        while (end <= count) {
            String key = binary.substring(begin, end);
            if (codeTable.containsKey(key)) {
                sb.append(codeTable.get(key));
                begin = end;
            } else {
            }
            end++;
        }
        return sb.toString();
    }

public String encode(String originText) {
        if (originText == null) return null;

calculateWeight(originText);

//        if (debug) printNodes(nodeList);

Node root = generateHuffmanTree(nodeList);

generateHuffmanCode(root, "");

if (debug) printNodes(root);

StringBuffer sb = new StringBuffer();
        for (Character key : originText.toCharArray()) {
            sb.append(nodeMap.get(key).huffCode);
        }
        if (debug) System.out.println("二进制:"+sb.toString());

return sb.toString();
    }

/**
     * 计算叶子权值
     * @param text
     */
    private void calculateWeight(String text) {
        for (Character c : text.toCharArray()) {
            if (nodeMap.containsKey(c)) {
                nodeMap.get(c).increaseWeight(1);//权值加1
            } else {
                Node leafNode = new Node(c, 1);
                nodeList.add(leafNode);
                nodeMap.put(c, leafNode);
            }
        }
    }

/**
     * 生成哈夫曼树
     * @param nodes
     */
    private Node generateHuffmanTree(ArrayList<Node> nodes) {
        Collections.sort(nodes);
        while(nodes.size() > 1) {
            Node ln = nodes.remove(0);
            Node rn = nodes.remove(0);
            insertSort(nodes, new Node(ln.weight + rn.weight, ln, rn));
        }
        Node root = nodes.remove(0);
        nodes = null;
        return root;
    }

/**
     * 插入排序
     * @param sortedNodes
     * @param node
     */
    private void insertSort(ArrayList<Node> sortedNodes, Node node) {
        if (sortedNodes == null) return;

int weight = node.weight;
        int min = 0, max = sortedNodes.size();
        int index;
        if (sortedNodes.size() == 0) {
            index = 0;
        } else if (weight < sortedNodes.get(min).weight) {
            index = min;//插入到第一个
        } else if (weight >= sortedNodes.get(max-1).weight) {
            index = max;//插入到最后
        } else {
            index = max/2;
            for (int i=0, count=max/2; i<=count; i++) {
                if (weight >= sortedNodes.get(index-1).weight && weight < sortedNodes.get(index).weight) {
                    break;
                } else if (weight < sortedNodes.get(index).weight) {
                    max = index;
                } else {
                    min = index;
                }
                index = (max + min)/2;
            }
        }
        sortedNodes.add(index, node);
    }

private void generateHuffmanCode(Node node, String code) {
        if (node.isLeaf()) node.huffCode = code;
        else {
            generateHuffmanCode(node.leftChild, code + "0");
            generateHuffmanCode(node.rightChild, code + "1");
        }
    }

/**
     * 生成码表
     * @return
     */
    public Map<String, Character> getCodeTable() {
        Map<String, Character> map = new HashMap<String, Character>();
        for (Node node : nodeMap.values()) {
            map.put(node.huffCode, node.value);
        }
        return map;
    }

/**
     * 打印节点信息
     * @param root
     */
    private void printNodes(Node root) {
        System.out.println("字符  权值  哈夫码");
        printTree(root);
    }

private void printTree(Node root) {
        if (root.isLeaf()) System.out.println((root.value == null ? "   " : root.value)+"    "+root.weight+"    "+(root.huffCode == null ? "" : root.huffCode));
        if (root.leftChild != null) printTree(root.leftChild);
        if (root.rightChild != null) printTree(root.rightChild);
    }

/**
     * 打印节点信息
     * @param nodes
     */
    private void printNodes(ArrayList<Node> nodes) {
        System.out.println("字符  权值  哈夫码");
        for (Node node : nodes) {
            System.out.println(node.value+"    "+node.weight+"    "+node.huffCode);
        }
    }
}

代码如下:

package com.test;

import java.util.Map;

import com.huffman.HuffUtils;
import com.huffman.HuffmanTree;

public class Test {
    public static void main(String[] args) {
        String originText = "abcdacaha";
        HuffmanTree huffmanTree = new HuffmanTree();
        huffmanTree.setDebug(true);//测试
        String binary = huffmanTree.encode(originText);
        byte[] bytes = HuffUtils.binary2Bytes(binary);
        Map<String, Character> codeTable = huffmanTree.getCodeTable();
        int lastByteNum = binary.length() % 8;
        System.out.println(bytes.length);
        //将bytes、codeTable、 lastByteNum传递到服务器端
        //省略。。。。。。

/*
                         服务器端解析
                         接收到参数,并转换成bytes、relationMap、 lastByteNum
        */
        String fullBinary = HuffUtils.bytes2Binary(bytes, lastByteNum);
        System.out.println("服务器二进制:"+fullBinary);
        String retrieveText = huffmanTree.decode(codeTable, fullBinary);
        System.out.println("恢复文本:"+retrieveText);
    }
}

(0)

相关推荐

  • 如何用Java实现啥夫曼编码

    大家可能会想,程序和第三方提供了很多压缩方式,何必自己写压缩代码呢?不错,如GZIP这样的压缩工具很多,可是在某些情况下(如文本内容小且字符不重复),GZIP压缩后会比原始文本还要大.所以在某些特殊情况下用自己的压缩方式可以更优. 大家可能早已忘记了在学校学习的哈夫曼知识,可以先在百度百科了解一下哈夫曼知识:http://baike.baidu.com/view/127820.htm 哈夫曼思想:统计文本字符重复率,求出各字符权值,再构造出一颗最优二叉树(又称哈夫曼树),然后给每个叶子结点生成一

  • Java利用哈夫曼编码实现字符串压缩

    赫夫曼编码基本介绍 1) 赫夫曼编码也翻译为 哈夫曼编码(Huffman Coding),又称霍夫曼编码,是一种编码方式, 属于一种程序算法 2) 赫夫曼编码是赫哈夫曼树在电讯通信中的经典的应用之一. 3) 赫夫曼编码广泛地用于数据文件压缩.其压缩率通常在 20%-90%之间 4) 赫夫曼码是可变字长编码(VLC)的一种.Huffman 于 1952 年提出一种编码方法,称之为最佳编码 在通信领域中几种信息处理方式的区别(以字符串" i like like like java do you li

  • java实现哈夫曼压缩的实例

    哈夫曼压缩的原理: 通过统计文件中每个字节出现的频率,将8位的01串转换为位数较短的哈夫曼编码. 其中哈夫曼编码是根据文件中字节出现的频率构建的,其中出现频率越高的字节,其路径长度越短; 出现频率越低的字节其路径长度越长.从而达到压缩的目的. 如何构造哈夫曼树? 一.  定义字节类  我的字节类定义了一下属性 public int data;//节点数据 public int weight;//该节点的权值 public int point;//该节点所在的左右位置 0-左 1-右 privat

  • 图文详解JAVA实现哈夫曼树

    前言  我想学过数据结构的小伙伴一定都认识哈夫曼,这位大神发明了大名鼎鼎的"最优二叉树",为了纪念他呢,我们称之为"哈夫曼树".哈夫曼树可以用于哈夫曼编码,编码的话学问可就大了,比如用于压缩,用于密码学等.今天一起来看看哈夫曼树到底是什么东东. 概念 当然,套路之一,首先我们要了解一些基本概念. 1.路径长度:从树中的一个结点到另一个结点之间的分支构成这两个结点的路径,路径上的分支数目称为路径长度. 2.树的路径长度:从树根到每一个结点的路径长度之和,我们所说的完全

  • java实现哈夫曼压缩与解压缩的方法

    一哈夫曼树以及文件压缩原理: 1.哈夫曼树 : 给定N个权值作为N个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树.哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近(频率越高的结点离根越进). 以 下数组为例,构建哈夫曼树 int a[] = {0,1,2,3,4,5,6,7,8} 我们可以发现以下规律 1:9个数构成的哈夫曼树一共有17个结点,也就是可以n个数可以生产2*n-1个结点 2:数字越大的数离根节点越近,越小的数离根节点越近.

  • java实现哈夫曼文件解压缩

    本文实例为大家分享了java实现哈夫曼文件解压缩的具体代码,供大家参考,具体内容如下 1.哈夫曼压缩对已经经过压缩处理的文件压缩率比较低,比如ppt和视频. 2.这个程序主要涉及到集合.树.IO相关知识. 字符的统计可以用map集合进行统计. 哈夫曼树的构建过程也并不复杂: ①先对树的集合按照根节点大小进行排序 ②拿出根节点数值最小的两棵树,用它两构建成一颗新的树: ③从集合中删除之前那两颗根节点最小的数: ④把新生成的树加入到集合中 一直循环重复上面的过程,直到集合的大小变成1为止: 写出.读

  • 基于C++实现的哈夫曼编码解码操作示例

    本文实例讲述了基于C++实现的哈夫曼编码解码操作.分享给大家供大家参考,具体如下: 哈夫曼编码是一个通过哈夫曼树进行的一种编码,一般情况下,以字符:'0'与'1'表示.编码的实现过程很简单,只要实现哈夫曼树,通过遍历哈夫曼树,这里我们从每一个叶子结点开始向上遍历,如果该结点为父节点的左孩子,则在字符串后面追加"0",如果为其右孩子,则在字符串后追加"1".结束条件为没有父节点.然后将字符串倒过来存入结点中. C++实现代码如下: #include<iostre

  • JS实现的哈夫曼编码示例【原始版与修改版】

    本文实例讲述了JS实现的哈夫曼编码.分享给大家供大家参考,具体如下: 原始版 function cal(str) { if (typeof str !== 'string' || str.length < 1) { return; } var map = {}; var i = 0; while(str[i]) { map[str[i]] ? map[str[i]]++ : (map[str[i]] = 1); i++; } return map; } function sort(map) {

  • C语言实现哈夫曼编码

    本文实例为大家分享了C语言实现哈夫曼编码的具体代码,供大家参考,具体内容如下 代码来自于<小甲鱼C++快速入门> 主程序main.cpp #include "stdafx.h" #include <stdlib.h> #include "huffman.h" int main() { htTree *codeTree = buildTree("I love wwwwwwwwwFishC.com!");//建立哈夫曼树 hl

  • C++实现哈夫曼编码

    本文实例为大家分享了C++实现哈夫曼编码的具体代码,供大家参考,具体内容如下 #include<iostream> #include<string> #include<vector> #include<algorithm> using namespace std; int Max = 300; class tree{ public: char s; int num; tree *left; tree *right; tree(){ s= '!'; num =

随机推荐