精华内容
下载资源
问答
  • 这样,处理全部信息的总码长一定小于实际信息的符号长度,从而达到压缩的目的。本文用java实现的Huffman编码压缩技术是实现的编码压缩技术。1Huffman编码原理霍夫曼(Huffman)编码是1952年为文本文件而建立,是一种...

    在某一个特定的文件系统中,某些字符可能会累计重复出现多次。编码压缩技术采用的原理就是统计这些字符出现的频率,并根据频率的高低对该字符进行编码。这样,处理全部信息的总码长一定小于实际信息的符号长度,从而达到压缩的目的。本文用java实现的Huffman编码压缩技术是实现的编码式压缩技术。1Huffman编码原理霍夫曼(Huffman)编码是1952年为文本文件而建立,是一种统计编码。属于无损压缩编码。霍夫曼编码的码长是变化的,对于出现频率高的信息,编码的长度较短;而对于出现频率低的信息,编码长度较长。构造Huffman编码的可以先将原始数据构造成一棵带权值的Huffman树。步骤如下:(1)将信号源的符号按照出现概率递减的顺序排列。(2)将两个最小出现概率进行合并相加,得到的结果作为新符号的出现概率。(3)重复进行步骤1和2直到概率相加的结果等于1为止。(4)在合并运算时,概率大的符号用编码0表示,概率小的符号用编码1表示。(5)记录下概率为1处到当前信号源符号之间的0,l序列,从而得到每个符号的编码。例如电文“ABACCDA”,有4种字符。可以用两位二进制代码:00,01,10,11分别表示A,B,C,D。译码为”00010010101100”。这样的二进制串长度为16位。比原始的字符串长度8*8=64远小。若采用Huffman编码,则得:A:1;B:000C:01;D:001。译码字符串为:1000101010011。长度为13位,比16又小。对于应用文档来说,一般会有大量词汇重复出现,这样两者之间的差距也随着文件的大小与词汇重复出现的频率而越来越高。2用java实现huffman压缩算法的程序流程图1程序流图3程序实现根据上面的流程以及huffman算法的原理,有如下的程序类组织结构:3.1程序相关类Frame类:框架类,用于实现程序的界面,其中还包括文件的读入,统计字符的频率,各字符按频率排序等函数HuffmanNode类:利用Huffman算法的特点,进行Huffman数据结构定义,如图2。BuildHuffman类:初始化Huffman树,并得到编码。其中包括生成Huffman树结构的函数(具体实现参看附程序),编码函数,写二进制文件函数,解码函数等,结构参看图3。3.1.1在Frame类中,可能会遇到的问题在图1的步骤1中(也就是在统计字符串频率时),对于简单的英文字母与数字字符来说,没有什么难度。而对于统计中文字符或其他一些由2个字节构成的字符时,可能会遇到某些问题。因为在对文件进行遍历统计频率时,需要对读入字符的步长加以控制。如果是单字节的字母,则步长为1,而如果是2个字节的字符,步长就需要相应的改为2。这样,就存在一个步长控制问题了。根据目前国际通用的Unicode代码表示的汉字存储区位,位于4E009FFF的为中日韩文字,其他双字节字符也有相应固定的区位。有这样的unicode编码条件,问题就可能解决了:在读入字符时,只需要判断读入的字符是否是位于双字节字符的存储区中。而对于java1.5以上的版本中,character类中提供了isHighSurrogate函数。该函数能判断能判断所读入的字符是否是双字节字符的前半部分。这样就能有效解决读入字符步长控制问题。从而正确统计各种类型的字符出现频率(代码可以见附表)。3.1.2构造HuffmanNode类HuffmanNode是一个定义的典型的Huffman型的数据结构。具体形式如图2。图2就是即将构造的Huffman结构。接下来需要将按频率已经排好序的各字符初始化成该类的实例(具

    展开全文
  • 实验名称:英文文本Huffman编码压缩一、实验目的和要求了解Huffman编码...霍夫曼(Huffman)编码是一种统计编码属于无损压缩编码。霍夫曼编码的码长是变化,对于出现频率高的信息编码的长度较短;而对于出现频...

    实验名称:英文文本的Huffman编码压缩

    一、实验目的和要求

    了解Huffman编码的特点,掌握Huffman编码基本原理及编码算法的设计与程序实现。

    二、实验内容和原理

    以任意选择一个纯英文文本为数据,设计出Huffman编码的压缩和解压缩算法,并写出程序予以实现。

    霍夫曼(Huffman)编码是一种统计编码,属于无损压缩编码。

    霍夫曼编码的码长是变化的,对于出现频率高的信息,编码的长度较短;而对于出现频率低的信息,编码长度较长。这样,处理全部信息的总码长一定小于实际信息的符号长度。

    三、实验环境

    硬件:计算机

    软件:Windows 2000和MATLAB编程环境。

    四、算法描述及实验步骤

    (1)输入一串字符串x=s,即s=hmmyyjhjjgjjpqw,k为其长度,分别用a、b两个数组来表示字符串中出现的不同字母及其出现的个数,调用findstr函数进行统计。

    (2)调用Huffmandict函数,即[dict,avglen]=huffmandict(c,d),使用数组C及其概率数组d进行Huffman编码,编码后产生一个编码词典dict,以及平均码长avglen。

    (3)调用huffmanenco函数,即sig_encoded =

    huffmanenco(x,dict),利用上面Huffmandict函数中产生的编码词典dict对sig_encoded来解码,其结果存放在dsig中以及dsig=huffmandeco(sig_encoded,dict)。

    (4)代码如下所示:

    clear;

    x=input('输入一串字符串','s');

    k=length(x);

    t1=1;

    a(t1:k)=0;

    b(t1:k)=0;

    for i=1 :k

    kk=findstr(a,x(i));

    if

    isempty(kk)

    a(t1)=x(i);

    b(t1)=b(t1)+1;

    t1=t1+1;

    else

    t2=kk(1);

    b(t2)=b(t2)+1;

    end

    end

    for i=1:t1-1

    c(i)=a(i);

    d(i)=b(i)/k;

    end

    [dict,avglen] = huffmandict(c,d)

    sig_encoded = huffmanenco(x,dict)

    dsig=huffmandeco(sig_encoded,dict)

    s=char(dsig)

    五、调试过程

    六、实验结果

    (1)输入的字符串以及所得编码词典dict和平均长度avglen:

    (2)运行后所得sig_encoded数据:

    (3)解码结果dsig数据(最后得到的字符串与输入的字符串一致):

    七、总结

    通过这次英文文本的Huffman编码压缩的实验,使我对霍夫曼(Huffman)编码、解码有了更进一步的了解,也知道了Huffman编码的一些函数的调用及其功能,如:huffmanenco函数、Huffmandict函数、Huffmandeco函数等;也对Matlab有了更进一步的了解。

    展开全文
  • 赫夫曼编码数据压缩

    2021-04-07 20:42:45
    赫夫曼编码也翻译为 哈夫曼编码(HuffmanCoding),又称霍夫曼编码,是一种编码方式, 属于一种程序算法 赫夫曼编码是赫哈夫曼树在电讯通信中经典应用之一。 赫夫曼编码广泛地用于数据文件压缩。其压缩率通常在 20%...

    赫夫曼编码数据压缩

    一、基本介绍

    1. 赫夫曼编码也翻译为 哈夫曼编码(HuffmanCoding),又称霍夫曼编码,是一种编码方式, 属于一种程序算法
    2. 赫夫曼编码是赫哈夫曼树在电讯通信中的经典的应用之一。
    3. 赫夫曼编码广泛地用于数据文件压缩。其压缩率通常在 20%~90%之间
    4. 赫夫曼码是可变字长编码(VLC)的一种。Huffman 于 1952 年提出一种编码方法,称之为最佳编码

    二、 原理剖析

    通信领域中信息的处理方式 1-定长编码
    在这里插入图片描述
    通信领域中信息的处理方式 2-变长编码
    在这里插入图片描述
    通信领域中信息的处理方式 3-赫夫曼编码

    传输的 字符串

    1)i like like like java do you like a java

    1. d:1y:1u:1j:2 v:2 o:2 l:4 k:4 e:4i:5 a:5 :9 // 各个字符对应的个数
    2. 按照上面字符出现的次数构建一颗赫夫曼树, 次数作为权值

    步骤:

    构成赫夫曼树的步骤:

    1. 从小到大进行排序, 将每一个数据,每个数据都是一个节点 , 每个节点可以看成是一颗最简单的二叉树

    2. 取出根节点权值最小的两颗二叉树

    3. 组成一颗新的二叉树, 该新的二叉树的根节点的权值是前面两颗二叉树根节点权值的和

    4. 再将这颗新的二叉树,以根节点的权值大小 再次排序, 不断重复 1-2-3-4 的步骤,直到数列中,所有的数据都被处理, 就得到一颗赫夫曼树
      在这里插入图片描述

    5. 根据赫夫曼树,给各个字符,规定编码 (前缀编码), 向左的路径为 0 向右的路径为 1 , 编码
      如下:
      o:1000 u:10010 d:100110 y:100111 i:101
      a:110 k:1110 e:1111 j:0000 v:0001
      l:001 :01

    6. 按照上面的赫夫曼编码,我们的"ilikelikelikejavadoyoulikeajava" 字符串对应的编码为 (注
      意这里我们使用的无损压缩)
      10101001101111011110100110111101111010011011110111101000011000011100110011110000110
      01111000100100100110111101111011100100001100001110 通过赫夫曼编码处理 长度为 133

    长度为 : 133
    说明:
    原来长度是 359, 压缩了 (359-133)/359=62.9%

    此编码满足前缀编码, 即字符的编码都不能是其他字符编码的前缀。不会造成匹配的多义性赫夫曼编码是无损处理方案

    注意事项: 这个赫夫曼树根据排序方法不同,也可能不太一样,这样对应的赫夫曼编码也不完全一样,但是 wpl 是 一样的,都是最小的, 最后生成的赫夫曼编码的长度是一样,比如: 如果我们让每次生成的新的二叉树总是排在权 值相同的二叉树的最后一个,则生成的二叉树为:
    在这里插入图片描述

    将给出的一段文本,比如 “i like likelikejava doyou likeajava” , 根据前面的讲的赫夫曼编码原理,对其进行数
    据 压 缩 处 理 , 形 式 如 "1010100110111101111010011011110111101001101111011110100001100001110011001111000011001111000100100100 110111101111011100100001100001110 "

    步骤 1:根据赫夫曼编码压缩数据的原理,需要创建 “i like like like java do you like a java” 对应的赫夫曼树.

    //可以通过List 创建对应的赫夫曼树
        private static Nodes createHuffmanTree(List<Nodes> Nodess) {
    
            while(Nodess.size() > 1) {
                //排序, 从小到大
                Collections.sort(Nodess);
                //取出第一颗最小的二叉树
                Nodes leftNodes = Nodess.get(0);
                //取出第二颗最小的二叉树
                Nodes rightNodes = Nodess.get(1);
                //创建一颗新的二叉树,它的根节点 没有data, 只有权值
                Nodes parent = new Nodes(null, leftNodes.weight + rightNodes.weight);
                parent.left = leftNodes;
                parent.right = rightNodes;
    
                //将已经处理的两颗二叉树从Nodess删除
                Nodess.remove(leftNodes);
                Nodess.remove(rightNodes);
                //将新的二叉树,加入到Nodess
                Nodess.add(parent);
    
            }
            //Nodess 最后的结点,就是赫夫曼树的根结点
            return Nodess.get(0);
    
        }
    

    我们已经生成了 赫夫曼树, 下面我们继续完成任务 1) 生成赫夫曼树对应的赫夫曼编码 , 如下表: =01 a=100 d=11000 u=11001 e=1110 v=11011 i=101 y=11010 j=0010 k=1111 l=000 o=0011
    2) 使用赫夫曼编码来生成赫夫曼编码数据 ,即按照上面的赫夫曼编码,将"i like like like java do you like a java" 字符串生成对应的编码数据, 形式如下. 10101000101111111100100010111111110010001011111111001001010011011100011100000110111010001111001010 00101111111100110001001010011011100 3) 思路:前面已经分析过了,而且我们讲过了生成赫夫曼编码的具体实现。

     /**
         * 功能:将传入的Nodes结点的所有叶子结点的赫夫曼编码得到,并放入到huffmanCodes集合
         * @param Nodes  传入结点
         * @param code  路径: 左子结点是 0, 右子结点 1
         * @param stringBuilder 用于拼接路径
         */
        private static void getCodes(Nodes Nodes, String code, StringBuilder stringBuilder) {
            StringBuilder stringBuilder2 = new StringBuilder(stringBuilder);
            //将code 加入到 stringBuilder2
            stringBuilder2.append(code);
            if(Nodes != null) { //如果Nodes == null不处理
                //判断当前Nodes 是叶子结点还是非叶子结点
                if(Nodes.data == null) { //非叶子结点
                    //递归处理
                    //向左递归
                    getCodes(Nodes.left, "0", stringBuilder2);
                    //向右递归
                    getCodes(Nodes.right, "1", stringBuilder2);
                } else { //说明是一个叶子结点
                    //就表示找到某个叶子结点的最后
                    huffmanCodes.put(Nodes.data, stringBuilder2.toString());
                }
            }
        }
     /**
         *
         * @param bytes 接收字节数组
         * @return 返回的就是 List 形式   [Nodes[date=97 ,weight = 5], Nodes[]date=32,weight = 9]......],
         */
        private static List<Nodes> getNodess(byte[] bytes) {
    
            //1创建一个ArrayList
            ArrayList<Nodes> Nodess = new ArrayList<Nodes>();
    
            //遍历 bytes , 统计 每一个byte出现的次数->map[key,value]
            Map<Byte, Integer> counts = new HashMap<>();
            for (byte b : bytes) {
                Integer count = counts.get(b);
                if (count == null) { // Map还没有这个字符数据,第一次
                    counts.put(b, 1);
                } else {
                    counts.put(b, count + 1);
                }
            }
    
            //把每一个键值对转成一个Nodes 对象,并加入到Nodess集合
            //遍历map
            for(Map.Entry<Byte, Integer> entry: counts.entrySet()) {
                Nodess.add(new Nodes(entry.getKey(), entry.getValue()));
            }
            return Nodess;
    
        }
    

    使用赫夫曼编码来解码数据,具体要求是

    1. 前面我们得到了赫夫曼编码和对应的编码 byte[], 即:[-88,-65,-56,-65,-56,-65,-55,77 ,-57,6,-24,-14,-117,-4,-60,-90,28]
    2. 现在要求使用赫夫曼编码, 进行解码,又 重新得到原来的字符串"ilikelikelikejavadoyoulikeajava"
    3. 思路:解码过程,就是编码的一个逆向操作。
    //编写一个方法,完成对压缩数据的解码
        /**
         *
         * @param huffmanCodes 赫夫曼编码表 map
         * @param huffmanBytes 赫夫曼编码得到的字节数组
         * @return 就是原来的字符串对应的数组
         */
        private static byte[] decode(Map<Byte,String> huffmanCodes, byte[] huffmanBytes) {
    
            //1. 先得到 huffmanBytes 对应的 二进制的字符串 , 形式 1010100010111...
            StringBuilder stringBuilder = new StringBuilder();
            //将byte数组转成二进制的字符串
            for(int i = 0; i < huffmanBytes.length; i++) {
                byte b = huffmanBytes[i];
                //判断是不是最后一个字节
                boolean flag = (i == huffmanBytes.length - 1);
                stringBuilder.append(byteToBitString(!flag, b));
            }
            //把字符串安装指定的赫夫曼编码进行解码
            //把赫夫曼编码表进行调换,因为反向查询 a->100 100->a
            Map<String, Byte>  map = new HashMap<String,Byte>();
            for(Map.Entry<Byte, String> entry: huffmanCodes.entrySet()) {
                map.put(entry.getValue(), entry.getKey());
            }
    
            //创建要给集合,存放byte
            List<Byte> list = new ArrayList<>();
            //i 可以理解成就是索引,扫描 stringBuilder
            for(int  i = 0; i < stringBuilder.length(); ) {
                int count = 1; // 小的计数器
                boolean flag = true;
                Byte b = null;
    
                while(flag) {
                    //1010100010111...
                    //递增的取出 key 1
                    String key = stringBuilder.substring(i, i+count);//i 不动,让count移动,指定匹配到一个字符
                    b = map.get(key);
                    if(b == null) {//说明没有匹配到
                        count++;
                    }else {
                        //匹配到
                        flag = false;
                    }
                }
                list.add(b);
                i += count;//i 直接移动到 count
            }
            //当for循环结束后,我们list中就存放了所有的字符  "i like like like java do you like a java"
            //把list 中的数据放入到byte[] 并返回
            byte b[] = new byte[list.size()];
            for(int i = 0;i < b.length; i++) {
                b[i] = list.get(i);
            }
            return b;
    
        }
    
        /**
         * 将一个byte 转成一个二进制的字符串, 如果看不懂,可以参考我讲的Java基础 二进制的原码,反码,补码
         * @param b 传入的 byte
         * @param flag 标志是否需要补高位如果是true ,表示需要补高位,如果是false表示不补, 如果是最后一个字节,无需补高位
         * @return 是该b 对应的二进制的字符串,(注意是按补码返回)
         */
        private static String byteToBitString(boolean flag, byte b) {
            //使用变量保存 b
            int temp = b; //将 b 转成 int
            //如果是正数我们还存在补高位
            if(flag) {
                temp |= 256; //按位与 256  1 0000 0000  | 0000 0001 => 1 0000 0001
            }
            String str = Integer.toBinaryString(temp); //返回的是temp对应的二进制的补码
            if(flag) {
                return str.substring(str.length() - 8);
            } else {
                return str;
            }
        }
    

    给你一个图片文件,要求对其进行无损压缩, 看看压缩效果如何

    1. 思路:读取文件-> 得到赫夫曼编码表 -> 完成压缩
     //编写一个方法,将字符串对应的byte[] 数组,通过生成的赫夫曼编码表,返回一个赫夫曼编码 压缩后的byte[]
        /**
         *
         * @param bytes 这时原始的字符串对应的 byte[]
         * @param huffmanCodes 生成的赫夫曼编码map
         * @return 返回赫夫曼编码处理后的 byte[]
         * 举例: String content = "i like like like java do you like a java"; =》 byte[] contentBytes = content.getBytes();
         * 返回的是 字符串 "1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000101111111100110001001010011011100"
         * => 对应的 byte[] huffmanCodeBytes  ,即 8位对应一个 byte,放入到 huffmanCodeBytes
         * huffmanCodeBytes[0] =  10101000(补码) => byte  [推导  10101000=> 10101000 - 1 => 10100111(反码)=> 11011000= -88 ]
         * huffmanCodeBytes[1] = -88
         */
        private static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) {
    
            //1.利用 huffmanCodes 将  bytes 转成  赫夫曼编码对应的字符串
            StringBuilder stringBuilder = new StringBuilder();
            //遍历bytes 数组
            for(byte b: bytes) {
                stringBuilder.append(huffmanCodes.get(b));
            }
    
            //System.out.println("测试 stringBuilder~~~=" + stringBuilder.toString());
    
            //将 "1010100010111111110..." 转成 byte[]
    
            //统计返回  byte[] huffmanCodeBytes 长度
            //一句话 int len = (stringBuilder.length() + 7) / 8;
            int len;
            if(stringBuilder.length() % 8 == 0) {
                len = stringBuilder.length() / 8;
            } else {
                len = stringBuilder.length() / 8 + 1;
            }
            //创建 存储压缩后的 byte数组
            byte[] huffmanCodeBytes = new byte[len];
            int index = 0;//记录是第几个byte
            for (int i = 0; i < stringBuilder.length(); i += 8) { //因为是每8位对应一个byte,所以步长 +8
                String strByte;
                if(i+8 > stringBuilder.length()) {//不够8位
                    strByte = stringBuilder.substring(i);
                }else{
                    strByte = stringBuilder.substring(i, i + 8);
                }
                //将strByte 转成一个byte,放入到 huffmanCodeBytes
                huffmanCodeBytes[index] = (byte)Integer.parseInt(strByte, 2);
                index++;
            }
            return huffmanCodeBytes;
        }
    

    文件解压(文件恢复)

    具体要求:将前面压缩的文件,重新恢复成原来的文件。

    1. 思路:读取压缩文件(数据和赫夫曼编码表)-> 完成解压(文件恢复)
     //编写一个方法,完成对压缩文件的解压
        /**
         *
         * @param zipFile 准备解压的文件
         * @param dstFile 将文件解压到哪个路径
         */
        public static void unZipFile(String zipFile, String dstFile) {
    
            //定义文件输入流
            InputStream is = null;
            //定义一个对象输入流
            ObjectInputStream ois = null;
            //定义文件的输出流
            OutputStream os = null;
            try {
                //创建文件输入流
                is = new FileInputStream(zipFile);
                //创建一个和  is关联的对象输入流
                ois = new ObjectInputStream(is);
                //读取byte数组  huffmanBytes
                byte[] huffmanBytes = (byte[])ois.readObject();
                //读取赫夫曼编码表
                Map<Byte,String> huffmanCodes = (Map<Byte,String>)ois.readObject();
    
                //解码
                byte[] bytes = decode(huffmanCodes, huffmanBytes);
                //将bytes 数组写入到目标文件
                os = new FileOutputStream(dstFile);
                //写数据到 dstFile 文件
                os.write(bytes);
            } catch (Exception e) {
                // TODO: handle exception
                System.out.println(e.getMessage());
            } finally {
    
                try {
                    os.close();
                    ois.close();
                    is.close();
                } catch (Exception e2) {
                    // TODO: handle exception
                    System.out.println(e2.getMessage());
                }
    
            }
        }
    

    完整代码:

    package;
    
    import java.io.FileInputStream;
    import java.io.FileOutputStream;
    import java.io.InputStream;
    import java.io.ObjectInputStream;
    import java.io.ObjectOutputStream;
    import java.io.OutputStream;
    import java.util.ArrayList;
    import java.util.Collections;
    import java.util.HashMap;
    import java.util.List;
    import java.util.Map;
    
    public class HuffmanCode {
    
        public static void main(String[] args) {
    
           /* //测试压缩文件
    		String srcFile = "d://a.txt";
    	    String dstFile = "d://a.zip";
    
    	zipFile(srcFile, dstFile);
    	System.out.println("压缩文件ok~~");
    */
    
            //测试解压文件
            String zipFile = "D://a.zip";
            String dstFile = "D://b.txt";
            unZipFile(zipFile, dstFile);
            System.out.println("解压成功!");
    
    		/*
    		String content = "i like like like java do you like a java";
    		byte[] contentBytes = content.getBytes();
    		System.out.println(contentBytes.length); //40
    
    		byte[] huffmanCodesBytes= huffmanZip(contentBytes);
    		System.out.println("压缩后的结果是:" + Arrays.toString(huffmanCodesBytes) + " 长度= " + huffmanCodesBytes.length);
    
    
    		//测试一把byteToBitString方法
    		//System.out.println(byteToBitString((byte)1));
    		byte[] sourceBytes = decode(huffmanCodes, huffmanCodesBytes);
    
    		System.out.println("原来的字符串=" + new String(sourceBytes)); // "i like like like java do you like a java"
    		*/
    
    
    
            //如何将 数据进行解压(解码)
            //分步过程
    		/*
    		List<Nodes> Nodess = getNodess(contentBytes);
    		System.out.println("Nodess=" + Nodess);
    
    		//测试一把,创建的赫夫曼树
    		System.out.println("赫夫曼树");
    		Nodes huffmanTreeRoot = createHuffmanTree(Nodess);
    		System.out.println("前序遍历");
    		huffmanTreeRoot.preOrder();
    
    		//测试一把是否生成了对应的赫夫曼编码
    		Map<Byte, String> huffmanCodes = getCodes(huffmanTreeRoot);
    		System.out.println("~生成的赫夫曼编码表= " + huffmanCodes);
    
    		//测试
    		byte[] huffmanCodeBytes = zip(contentBytes, huffmanCodes);
    		System.out.println("huffmanCodeBytes=" + Arrays.toString(huffmanCodeBytes));//17
    
    		//发送huffmanCodeBytes 数组 */
    
    
        }
    
        //编写一个方法,完成对压缩文件的解压
        /**
         *
         * @param zipFile 准备解压的文件
         * @param dstFile 将文件解压到哪个路径
         */
        public static void unZipFile(String zipFile, String dstFile) {
    
            //定义文件输入流
            InputStream is = null;
            //定义一个对象输入流
            ObjectInputStream ois = null;
            //定义文件的输出流
            OutputStream os = null;
            try {
                //创建文件输入流
                is = new FileInputStream(zipFile);
                //创建一个和  is关联的对象输入流
                ois = new ObjectInputStream(is);
                //读取byte数组  huffmanBytes
                byte[] huffmanBytes = (byte[])ois.readObject();
                //读取赫夫曼编码表
                Map<Byte,String> huffmanCodes = (Map<Byte,String>)ois.readObject();
    
                //解码
                byte[] bytes = decode(huffmanCodes, huffmanBytes);
                //将bytes 数组写入到目标文件
                os = new FileOutputStream(dstFile);
                //写数据到 dstFile 文件
                os.write(bytes);
            } catch (Exception e) {
                // TODO: handle exception
                System.out.println(e.getMessage());
            } finally {
    
                try {
                    os.close();
                    ois.close();
                    is.close();
                } catch (Exception e2) {
                    // TODO: handle exception
                    System.out.println(e2.getMessage());
                }
    
            }
        }
    
        //编写方法,将一个文件进行压缩
        /**
         *
         * @param srcFile 你传入的希望压缩的文件的全路径
         * @param dstFile 我们压缩后将压缩文件放到哪个目录
         */
        public static void zipFile(String srcFile, String dstFile) {
    
            //创建输出流
            OutputStream os = null;
            ObjectOutputStream oos = null;
            //创建文件的输入流
            FileInputStream is = null;
            try {
                //创建文件的输入流
                is = new FileInputStream(srcFile);
                //创建一个和源文件大小一样的byte[]
                byte[] b = new byte[is.available()];
                //读取文件
                is.read(b);
                //直接对源文件压缩
                byte[] huffmanBytes = huffmanZip(b);
                //创建文件的输出流, 存放压缩文件
                os = new FileOutputStream(dstFile);
                //创建一个和文件输出流关联的ObjectOutputStream
                oos = new ObjectOutputStream(os);
                //把 赫夫曼编码后的字节数组写入压缩文件
                oos.writeObject(huffmanBytes); //我们是把
                //这里我们以对象流的方式写入 赫夫曼编码,是为了以后我们恢复源文件时使用
                //注意一定要把赫夫曼编码 写入压缩文件
                oos.writeObject(huffmanCodes);
    
    
            }catch (Exception e) {
                // TODO: handle exception
                System.out.println(e.getMessage());
            }finally {
                try {
                    is.close();
                    oos.close();
                    os.close();
                }catch (Exception e) {
                    // TODO: handle exception
                    System.out.println(e.getMessage());
                }
            }
    
        }
    
        //完成数据的解压
        //思路
        //1. 将huffmanCodeBytes [-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, 28]
        //   重写先转成 赫夫曼编码对应的二进制的字符串 "1010100010111..."
        //2.  赫夫曼编码对应的二进制的字符串 "1010100010111..." =》 对照 赫夫曼编码  =》 "i like like like java do you like a java"
    
    
        //编写一个方法,完成对压缩数据的解码
        /**
         *
         * @param huffmanCodes 赫夫曼编码表 map
         * @param huffmanBytes 赫夫曼编码得到的字节数组
         * @return 就是原来的字符串对应的数组
         */
        private static byte[] decode(Map<Byte,String> huffmanCodes, byte[] huffmanBytes) {
    
            //1. 先得到 huffmanBytes 对应的 二进制的字符串 , 形式 1010100010111...
            StringBuilder stringBuilder = new StringBuilder();
            //将byte数组转成二进制的字符串
            for(int i = 0; i < huffmanBytes.length; i++) {
                byte b = huffmanBytes[i];
                //判断是不是最后一个字节
                boolean flag = (i == huffmanBytes.length - 1);
                stringBuilder.append(byteToBitString(!flag, b));
            }
            //把字符串安装指定的赫夫曼编码进行解码
            //把赫夫曼编码表进行调换,因为反向查询 a->100 100->a
            Map<String, Byte>  map = new HashMap<String,Byte>();
            for(Map.Entry<Byte, String> entry: huffmanCodes.entrySet()) {
                map.put(entry.getValue(), entry.getKey());
            }
    
            //创建要给集合,存放byte
            List<Byte> list = new ArrayList<>();
            //i 可以理解成就是索引,扫描 stringBuilder
            for(int  i = 0; i < stringBuilder.length(); ) {
                int count = 1; // 小的计数器
                boolean flag = true;
                Byte b = null;
    
                while(flag) {
                    //1010100010111...
                    //递增的取出 key 1
                    String key = stringBuilder.substring(i, i+count);//i 不动,让count移动,指定匹配到一个字符
                    b = map.get(key);
                    if(b == null) {//说明没有匹配到
                        count++;
                    }else {
                        //匹配到
                        flag = false;
                    }
                }
                list.add(b);
                i += count;//i 直接移动到 count
            }
            //当for循环结束后,我们list中就存放了所有的字符  "i like like like java do you like a java"
            //把list 中的数据放入到byte[] 并返回
            byte b[] = new byte[list.size()];
            for(int i = 0;i < b.length; i++) {
                b[i] = list.get(i);
            }
            return b;
    
        }
    
        /**
         * 将一个byte 转成一个二进制的字符串, 如果看不懂,可以参考我讲的Java基础 二进制的原码,反码,补码
         * @param b 传入的 byte
         * @param flag 标志是否需要补高位如果是true ,表示需要补高位,如果是false表示不补, 如果是最后一个字节,无需补高位
         * @return 是该b 对应的二进制的字符串,(注意是按补码返回)
         */
        private static String byteToBitString(boolean flag, byte b) {
            //使用变量保存 b
            int temp = b; //将 b 转成 int
            //如果是正数我们还存在补高位
            if(flag) {
                temp |= 256; //按位与 256  1 0000 0000  | 0000 0001 => 1 0000 0001
            }
            String str = Integer.toBinaryString(temp); //返回的是temp对应的二进制的补码
            if(flag) {
                return str.substring(str.length() - 8);
            } else {
                return str;
            }
        }
    
        //使用一个方法,将前面的方法封装起来,便于我们的调用.
        /**
         *
         * @param bytes 原始的字符串对应的字节数组
         * @return 是经过 赫夫曼编码处理后的字节数组(压缩后的数组)
         */
        private static byte[] huffmanZip(byte[] bytes) {
            List<Nodes> Nodess = getNodess(bytes);
            //根据 Nodess 创建的赫夫曼树
            Nodes huffmanTreeRoot = createHuffmanTree(Nodess);
            //对应的赫夫曼编码(根据 赫夫曼树)
            Map<Byte, String> huffmanCodes = getCodes(huffmanTreeRoot);
            //根据生成的赫夫曼编码,压缩得到压缩后的赫夫曼编码字节数组
            byte[] huffmanCodeBytes = zip(bytes, huffmanCodes);
            return huffmanCodeBytes;
        }
    
    
        //编写一个方法,将字符串对应的byte[] 数组,通过生成的赫夫曼编码表,返回一个赫夫曼编码 压缩后的byte[]
        /**
         *
         * @param bytes 这时原始的字符串对应的 byte[]
         * @param huffmanCodes 生成的赫夫曼编码map
         * @return 返回赫夫曼编码处理后的 byte[]
         * 举例: String content = "i like like like java do you like a java"; =》 byte[] contentBytes = content.getBytes();
         * 返回的是 字符串 "1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000101111111100110001001010011011100"
         * => 对应的 byte[] huffmanCodeBytes  ,即 8位对应一个 byte,放入到 huffmanCodeBytes
         * huffmanCodeBytes[0] =  10101000(补码) => byte  [推导  10101000=> 10101000 - 1 => 10100111(反码)=> 11011000= -88 ]
         * huffmanCodeBytes[1] = -88
         */
        private static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) {
    
            //1.利用 huffmanCodes 将  bytes 转成  赫夫曼编码对应的字符串
            StringBuilder stringBuilder = new StringBuilder();
            //遍历bytes 数组
            for(byte b: bytes) {
                stringBuilder.append(huffmanCodes.get(b));
            }
    
            //System.out.println("测试 stringBuilder~~~=" + stringBuilder.toString());
    
            //将 "1010100010111111110..." 转成 byte[]
    
            //统计返回  byte[] huffmanCodeBytes 长度
            //一句话 int len = (stringBuilder.length() + 7) / 8;
            int len;
            if(stringBuilder.length() % 8 == 0) {
                len = stringBuilder.length() / 8;
            } else {
                len = stringBuilder.length() / 8 + 1;
            }
            //创建 存储压缩后的 byte数组
            byte[] huffmanCodeBytes = new byte[len];
            int index = 0;//记录是第几个byte
            for (int i = 0; i < stringBuilder.length(); i += 8) { //因为是每8位对应一个byte,所以步长 +8
                String strByte;
                if(i+8 > stringBuilder.length()) {//不够8位
                    strByte = stringBuilder.substring(i);
                }else{
                    strByte = stringBuilder.substring(i, i + 8);
                }
                //将strByte 转成一个byte,放入到 huffmanCodeBytes
                huffmanCodeBytes[index] = (byte)Integer.parseInt(strByte, 2);
                index++;
            }
            return huffmanCodeBytes;
        }
    
        //生成赫夫曼树对应的赫夫曼编码
        //思路:
        //1. 将赫夫曼编码表存放在 Map<Byte,String> 形式
        //   生成的赫夫曼编码表{32=01, 97=100, 100=11000, 117=11001, 101=1110, 118=11011, 105=101, 121=11010, 106=0010, 107=1111, 108=000, 111=0011}
        static Map<Byte, String> huffmanCodes = new HashMap<Byte,String>();
        //2. 在生成赫夫曼编码表示,需要去拼接路径, 定义一个StringBuilder 存储某个叶子结点的路径
        static StringBuilder stringBuilder = new StringBuilder();
    
    
        //为了调用方便,我们重载 getCodes
        private static Map<Byte, String> getCodes(Nodes root) {
            if(root == null) {
                return null;
            }
            //处理root的左子树
            getCodes(root.left, "0", stringBuilder);
            //处理root的右子树
            getCodes(root.right, "1", stringBuilder);
            return huffmanCodes;
        }
    
        /**
         * 功能:将传入的Nodes结点的所有叶子结点的赫夫曼编码得到,并放入到huffmanCodes集合
         * @param Nodes  传入结点
         * @param code  路径: 左子结点是 0, 右子结点 1
         * @param stringBuilder 用于拼接路径
         */
        private static void getCodes(Nodes Nodes, String code, StringBuilder stringBuilder) {
            StringBuilder stringBuilder2 = new StringBuilder(stringBuilder);
            //将code 加入到 stringBuilder2
            stringBuilder2.append(code);
            if(Nodes != null) { //如果Nodes == null不处理
                //判断当前Nodes 是叶子结点还是非叶子结点
                if(Nodes.data == null) { //非叶子结点
                    //递归处理
                    //向左递归
                    getCodes(Nodes.left, "0", stringBuilder2);
                    //向右递归
                    getCodes(Nodes.right, "1", stringBuilder2);
                } else { //说明是一个叶子结点
                    //就表示找到某个叶子结点的最后
                    huffmanCodes.put(Nodes.data, stringBuilder2.toString());
                }
            }
        }
    
        //前序遍历的方法
        private static void preOrder(Nodes root) {
            if(root != null) {
                root.preOrder();
            }else {
                System.out.println("赫夫曼树为空");
            }
        }
    
        /**
         *
         * @param bytes 接收字节数组
         * @return 返回的就是 List 形式   [Nodes[date=97 ,weight = 5], Nodes[]date=32,weight = 9]......],
         */
        private static List<Nodes> getNodess(byte[] bytes) {
    
            //1创建一个ArrayList
            ArrayList<Nodes> Nodess = new ArrayList<Nodes>();
    
            //遍历 bytes , 统计 每一个byte出现的次数->map[key,value]
            Map<Byte, Integer> counts = new HashMap<>();
            for (byte b : bytes) {
                Integer count = counts.get(b);
                if (count == null) { // Map还没有这个字符数据,第一次
                    counts.put(b, 1);
                } else {
                    counts.put(b, count + 1);
                }
            }
    
            //把每一个键值对转成一个Nodes 对象,并加入到Nodess集合
            //遍历map
            for(Map.Entry<Byte, Integer> entry: counts.entrySet()) {
                Nodess.add(new Nodes(entry.getKey(), entry.getValue()));
            }
            return Nodess;
    
        }
    
        //可以通过List 创建对应的赫夫曼树
        private static Nodes createHuffmanTree(List<Nodes> Nodess) {
    
            while(Nodess.size() > 1) {
                //排序, 从小到大
                Collections.sort(Nodess);
                //取出第一颗最小的二叉树
                Nodes leftNodes = Nodess.get(0);
                //取出第二颗最小的二叉树
                Nodes rightNodes = Nodess.get(1);
                //创建一颗新的二叉树,它的根节点 没有data, 只有权值
                Nodes parent = new Nodes(null, leftNodes.weight + rightNodes.weight);
                parent.left = leftNodes;
                parent.right = rightNodes;
    
                //将已经处理的两颗二叉树从Nodess删除
                Nodess.remove(leftNodes);
                Nodess.remove(rightNodes);
                //将新的二叉树,加入到Nodess
                Nodess.add(parent);
    
            }
            //Nodess 最后的结点,就是赫夫曼树的根结点
            return Nodess.get(0);
    
        }
    
    
    }
    
    
    
    //创建Nodes ,待数据和权值
    class Nodes implements Comparable<Nodes>  {
        Byte data; // 存放数据(字符)本身,比如'a' => 97 ' ' => 32
        int weight; //权值, 表示字符出现的次数
        Nodes left;//
        Nodes right;
        public Nodes(Byte data, int weight) {
    
            this.data = data;
            this.weight = weight;
        }
        @Override
        public int compareTo(Nodes o) {
            // 从小到大排序
            return this.weight - o.weight;
        }
        @Override
        public String toString() {
            return "Nodes [data = " + data + " weight=" + weight + "]";
        }
    
        //前序遍历
        public void preOrder() {
            System.out.println(this);
            if(this.left != null) {
                this.left.preOrder();
            }
            if(this.right != null) {
                this.right.preOrder();
            }
        }
    }
    
    

    赫夫曼编码压缩文件注意事项

    1. 如果文件本身就是经过压缩处理的,那么使用赫夫曼编码再压缩效率不会有明显变化, 比如视频,ppt 等等文件 [举例压一个 .ppt]
    2. 赫夫曼编码是按字节来处理的,因此可以处理所有的文件(二进制文件、文本文件)[举例压一个.xml 文件]
    3. 如果一个文件中的内容,重复的数据不多,压缩效果也不会很明显.

    在这里插入图片描述

    展开全文
  • 赫夫曼编码基本介绍1.赫夫曼编码也翻译为 哈夫曼编码(Huffman Coding),又称霍夫曼编码,是一种编码方式, 属于一种程序...Huffman于1952年提出一种编码方法,称之为最佳编码原理剖析》》》》通信领域中信息的处理...

    赫夫曼编码
    基本介绍
    1.赫夫曼编码也翻译为 哈夫曼编码(Huffman Coding),又称霍夫曼编码,是一种编码方式, 属于一种程序算法
    赫夫曼编码是赫哈夫曼树在电讯通信中的经典的应用之一。
    2.赫夫曼编码广泛地用于数据文件压缩。其压缩率通常在20%~90%之间
    赫夫曼码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法,称之为最佳编码
    原理剖析

    》》》》通信领域中信息的处理方式1-定长编码

    i like like like java do you like a java // 共40个字符(包括空格)

    105 32 108 105 107 101 32 108 105 107 101 32 108 105 107 101 32 106 97 118 97 32 100 111 32 121 111 117 32 108 105 107 101 32 97 32 106 97 118 97 //对应Ascii码

    01101001 00100000 01101100 01101001 01101011 01100101 00100000 01101100 01101001 01101011 01100101 00100000 01101100 01101001 01101011 01100101 00100000 01101010 01100001 01110110 01100001 00100000 01100100 01101111 00100000 01111001 01101111 01110101 00100000 01101100 01101001 01101011 01100101 00100000 01100001 00100000 01101010 01100001 01110110 01100001 //对应的二进制

    按照二进制来传递信息,总的长度是 359 (包括空格)

    在线转码 工具 :ASCII在线转换工具 - 魔酷阁

    》》》》通信领域中信息的处理方式2-变长编码

    i like like like java do you like a java // 共40个字符(包括空格)

    d:1 y:1 u:1 j:2 v:2 o:2 l:4 k:4 e:4 i:5 a:5 :9 // 各个字符对应的个数

    0= , 1=a, 10=i, 11=e, 100=k, 101=l, 110=o, 111=v, 1000=j, 1001=u, 1010=y, 1011=d 说明:按照各个字符出现的次数进行编码,原则是出现次数越多的,则编码越小,比如 空格出现了9 次, 编码为0 ,其它依次类推.

    按照上面给各个字符规定的编码,则我们在传输 "i like like like java do you like a java" 数据时,编码就是 10010110100...

    字符的编码都不能是其他字符编码的前缀,符合此要求的编码叫做前缀编码, 即不能匹配到重复的编码(这个在赫夫曼编码中,我们还要进行举例说明,

    》》》》通信领域中信息的处理方式3-赫夫曼编码

    i like like like java do you like a java // 共40个字符(包括空格)

    d:1 y:1 u:1 j:2 v:2 o:2 l:4 k:4 e:4 i:5 a:5 :9 // 各个字符对应的个数

    按照上面字符出现的次数构建一颗赫夫曼树, 次数作为权值.(图后)

    b03788be5bab003d6e7a658a514f40d9.png

    c2de2f980efdb9277958f5595e3fac37.png

    将给出的一段文本,比如 "i like like like java do you like a java" , 根据前面的讲的赫夫曼编码原理,对其进行数据压缩处理 ,形式如 "1010100110111101111010011011110111101001101111011110100001100001110011001111000011001111000100100100110111101111011100100001100001110

    "

    步骤1:根据赫夫曼编码压缩数据的原理,需要创建 "i like like like java do you like a java" 对应的赫夫曼树.

    我们已经生成了 赫夫曼树, 下面我们继续完成任务

    1.生成赫夫曼树对应的赫夫曼编码 , 如下表: =01 a=100 d=11000 u=11001 e=1110 v=11011 i=101 y=11010 j=0010 k=1111 l=000 o=0011

    2.使用赫夫曼编码来生成赫夫曼编码数据 ,即按照上面的赫夫曼编码,将"i like like like java do you like a java" 字符串生成对应的编码数据, 形式如下. 1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000101111111100110001001010011011100

    /**
     *
     赫夫曼编码
    基本介绍
    
    1.赫夫曼编码也翻译为    哈夫曼编码(Huffman Coding),又称霍夫曼编码,是一种编码方式, 属于一种程序算法
    赫夫曼编码是赫哈夫曼树在电讯通信中的经典的应用之一。
    
    2.赫夫曼编码广泛地用于数据文件压缩。其压缩率通常在20%~90%之间
    赫夫曼码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法,称之为最佳编码
    
     *
     *
     */
    
    class Node {
        data;//存放数据(字符本身),比如 'a' => 97, ' '=>32
        weight;//权值,表示字符串出现的次数
        left;//
        constructor(data, weight) {
            this.data = data;
            this.weight = weight;
        }
    
        //前序遍历
        preOrder(arr) {
            arr.push(this);
            if (this.left) {
                this.left.preOrder(arr);
            }
            if (this.right) {
                this.right.preOrder(arr);
            }
        }
    }
    
    
    /**
     * 
     * @param {接受字符数组} bytes 
     * @return 返回的就是list形式
     */
    function getNodes(bytes) {
        //创建一个list
        let list = [];
        //counts 统计每一个byte出现的次数
        let counts = {};
        for (let b of bytes) {
            let count = counts[b];//map还没有这个字符数据
            if (count == null) {
                counts[b] = 1;
            } else {
                counts[b]++;
            }
        }
    
        for (const [key, value] of Object.entries(counts)) {
            list.push(new Node(key, value));
        }
        return list;
    }
    
    
    //通过list创建赫夫曼树
    function createHuffmanTree(nodes) {
        const compareFun = function (a, b) {
            return a.weight - b.weight
        };
        while (nodes.length > 1) {
            //排序,从小到大
            nodes.sort(compareFun);
            //取出第一颗最小的二叉树
            let leftNode = nodes.shift(), rightNode = nodes.shift();
            //创建一个新的二叉树,它的根节点,没有data,只有权值
            let parent = new Node(null, leftNode.weight + rightNode.weight);
            parent.left = leftNode;
            parent.right = rightNode;
    
            //将新的二叉树,加入到nodes
            nodes.unshift(parent);
        }
        //nodes最后的节点,就是根节点
        return nodes.shift();
    }
    
    //生成赫夫曼树对应的赫夫曼编码表
    function getCodes2(root) {
        if (root == null) {
            return null;
        }
        //生成赫夫曼树对应的赫夫曼编码表
        //思路
        //1.将赫夫曼编码表存放在map里面
        //2.在生成赫夫曼编码表时,需要拼接路径,定义一个数组string,存储某个叶子节点的路径
    
        let huffmanCodes = {};
        let string = [];
        /**
         * 将传入的node节点的所有叶子节点的赫夫曼编码得到,并放入到huffmanCodes集合中
         * @param {传入节点} node 
         * @param {路径:左子节点是0,右子节点是1} code 
         * @param {用于拼接路径} string 
         */
        function getCodes(node, code, string) {
            let string2 = [...string];
            //将code加入到string中
            string2.push(code);
            if (node != null) { //如果node == null不处理
                //判断当前node是叶子节点还是非叶子节点
                if (node.data == null) {//非叶子节点
                    //递归处理
                    //向左递归
                    getCodes(node.left, '0', string2);
                    //向右递归
                    getCodes(node.right, '1', string2)
                } else {//说明是一个叶子节点
                    //就表示找到了某个叶子节点的最后
                    huffmanCodes[node.data] = string2.join('');
                }
            }
        }
        getCodes(root, "", string);
        return huffmanCodes;
    }
    
    //编写一个方法,将字符串对应的bytes数组,通过生成的赫夫曼编码表,返回一个赫夫曼编码压缩后的byte数组
    /**
     * 
     * @param {原始的字符串对应的bytes数组} bytes 
     * @param {生成的赫夫曼编码表} huffmanCodes 
     * @return 返回的是字符串对应的一个byte数组
     */
    function zip(bytes, huffmanCodes) {
        //1.利用huffmanCodes将bytes转成赫夫曼编码对应的字符串
        let string = [];
        //遍历数组
        for (let b of bytes) {
            string.push(huffmanCodes[b]);
        }
        return string;
    }
    
    function huffstringToByte(string) {
        //计算赫夫曼编码字符串的长度
        string = string.join('');
        let len = Math.ceil(string.length / 8);
        //创建存储压缩后的byte数组
        let huffmanCodeByte = new Array(len + 1);
        let index = 0, strByte;//记录是第几个byte
        for (let i = 0; i < string.length; i += 8) {
            strByte = string.substring(i, i + 8);
            //将strByte转成一个byte,放入huffmanCodeByte
            huffmanCodeByte[index] = parseInt(strByte, 2);
            index++;
        }
        //记录最后一位二进制码的长度,因为,比如最后一位二进制strByte为00101时,
        //parseInt(strByte, 2)后等于5,前面的两个00已经丢失,所以必须记录长度,以便解码时补足前面的0
        huffmanCodeByte[index] = strByte.length;
        return huffmanCodeByte
    }
    
    //使用一个方法,封装前面的方法,便于调用
    /**
     * 
     * @param {原始的字符串对应的字节数组} bytes
     * @returns 是经过赫夫曼编码处理后,压缩后的字节数组
     *  
     */
    function huffmanZip(bytes) {
        //1.生成节点数组
        let nodes = getNodes(bytes);
        //2.根据节点数组创建赫夫曼树
        let root = createHuffmanTree(nodes);
        //3.根据赫夫曼树生成赫夫曼编码
        let hufumanCodes = getCodes2(root);
        //4.根据生成的赫夫曼编码生成压缩后的赫夫曼编码字节数组
        let hufumanStrArr = zip(bytes, hufumanCodes);
        let hufumanByteArr = huffstringToByte(hufumanStrArr);
    
        return hufumanByteArr;
    }
    
    //完成数据的解压
    //思路
    //1.将huffmanBytesArr先转成赫夫曼编码对应的二进制字符串
    //2.将赫夫曼编码对应的二进制的字符串转成赫夫曼编码字符串
    
    /**
     * 
     * @param {表示是否需要补高位,如果是true,表示需要,如果是false,表示不需要,如果是最后一个字节不需要补高位} flag 
     * @param {传入的byte} byte 
     * @returns 是byte对应的二进制字符串
     */
    function heffmanByteToString(flag, byte) {
        //如果是
        if (flag) {
            byte |= 256;
        }
        let str = Number(byte).toString(2)
        if (flag) {
            return str.substring(str.length - 8);
        } else {
            return str;
        }
    }
    
    //编写一份方法,完成对压缩数据的解码
    /**
     * 
     * @param {赫夫曼编码表} huffmanCodes 
     * @param {赫夫曼编码得到的二进制数组} huffmanBytes 
     */
    function decode(huffmanCodes, huffmanBytes) {
        //1.先得到二进制字符串 形式11001111111011......
        let heffmanStrArr = [];
        for (let i = 0; i < huffmanBytes.length - 1; i++) {
            //判断是不是最后一个字节
            let flag = (i !== huffmanBytes.length - 2);
            heffmanStrArr.push(heffmanByteToString(flag, huffmanBytes[i]))
        }
        //最后一位记录的是最后一位二进制字符串的长度,该长度主要用于补足最后一位丢失的0,所以要单独处理,
        let lastByteStr = heffmanStrArr[heffmanStrArr.length - 1];
        let lastByteLength = huffmanBytes[huffmanBytes.length - 1];
        lastByteStr = '00000000'.substring(8 - (lastByteLength - lastByteStr.length)) + lastByteStr;
        heffmanStrArr[heffmanStrArr.length - 1] = lastByteStr;
    
        //把赫夫曼编码表进行调换
        let map = {};
        for (const [key, value] of Object.entries(huffmanCodes)) {
            map[value] = key;
        }
    
        let heffmanStr = heffmanStrArr.join('');
        let list = [];
        //
        for (let i = 0; i < heffmanStr.length;) {
            let count = 1;
            let flag = true;
            let b = null;
            while (flag) {
                //取出一个1或0
                //i不动,count移动,直到匹配到一个字符
                let key = heffmanStr.substring(i, i + count);
                b = map[key]
                if (!b) {//没有匹配到
                    count++;
                } else {
                    //匹配到
                    flag = false;
                }
            }
            list.push(parseInt(b));
            i += count;
        }
        //当for循环结束后,list中就存放了所有的字符
    
        return list;
    }
    
    let content = 'i like like like java do you like a java';
    let bytes = stringToByte(content);
    let nodes = getNodes(bytes);
    let root = createHuffmanTree(nodes);
    console.log('根节点:', root);
    let list = [];
    root.preOrder(list);
    console.log('前序遍历:', list);
    
    //测试
    let hufumanCodes = getCodes2(root);
    console.log('生成的赫夫曼编码表:', hufumanCodes);
    
    //生成赫夫曼编码字符串
    let hufumanStrArr = zip(bytes, hufumanCodes);
    console.log('赫夫曼编码字符串:', hufumanStrArr.join(''))
    console.log('赫夫曼编码字符串的长度:', hufumanStrArr.join('').length)//应该是133
    
    //将生成赫夫曼编码字符串转成字节数组, 要发送的数组
    let hufumanByteArr = huffstringToByte(hufumanStrArr);//长度为17
    console.log('压缩后的字节数组', hufumanByteArr);
    console.log('压缩率:', (bytes.length - hufumanByteArr.length) / bytes.length * 100 + '%');
    
    //测试封装后的方法
    console.log('压缩后的字节数组', huffmanZip(bytes));
    
    //测试解码
    console.log('解码后的的:', decode(hufumanCodes, hufumanByteArr));
    console.log('原字符数组:', bytes);
    console.log('解码后字符串:', byteToString(bytes));
    console.log('原先的字符串:', byteToString(bytes));
    
    
    
    //js byte[] 和string 相互转换 UTF-8
    function stringToByte(str) {
        var bytes = new Array();
        var len, c;
        len = str.length;
        for (var i = 0; i < len; i++) {
            c = str.charCodeAt(i);
            if (c >= 0x010000 && c <= 0x10FFFF) {
                bytes.push(((c >> 18) & 0x07) | 0xF0);
                bytes.push(((c >> 12) & 0x3F) | 0x80);
                bytes.push(((c >> 6) & 0x3F) | 0x80);
                bytes.push((c & 0x3F) | 0x80);
            } else if (c >= 0x000800 && c <= 0x00FFFF) {
                bytes.push(((c >> 12) & 0x0F) | 0xE0);
                bytes.push(((c >> 6) & 0x3F) | 0x80);
                bytes.push((c & 0x3F) | 0x80);
            } else if (c >= 0x000080 && c <= 0x0007FF) {
                bytes.push(((c >> 6) & 0x1F) | 0xC0);
                bytes.push((c & 0x3F) | 0x80);
            } else {
                bytes.push(c & 0xFF);
            }
        }
        return bytes;
    
    
    }
    
    
    function byteToString(arr) {
        if (typeof arr === 'string') {
            return arr;
        }
        var str = '',
            _arr = arr;
        for (var i = 0; i < _arr.length; i++) {
            var one = _arr[i].toString(2),
                v = one.match(/^1+?(?=0)/);
            if (v && one.length == 8) {
                var bytesLength = v[0].length;
                var store = _arr[i].toString(2).slice(7 - bytesLength);
                for (var st = 1; st < bytesLength; st++) {
                    store += _arr[st + i].toString(2).slice(2);
                }
                str += String.fromCharCode(parseInt(store, 2));
                i += bytesLength - 1;
            } else {
                str += String.fromCharCode(_arr[i]);
            }
        }
        return str;
    }
    

    测试:

    03c397f78700e34decb433b64623f765.png
    展开全文
  • 本发明属于图片处理技术领域,尤其涉及一种基于Huffman编码的图像再压缩处理方法。背景技术:目前,业内常用现有技术是这样:由于各种新型传感器出现,图像质量得到了巨大提升,随之而来数据量对图像...
  • 视频压缩编码基本原理

    千次阅读 2018-09-26 16:26:31
    数据冗余:空间冗余、时间冗余、结构冗余、信息熵冗余等,图像各个像素之间存在着很强相关性,消除这些冗余不会导致信息损失,属于无损压缩。 视觉冗余:人眼一些特性,例如亮度分辨阈值、视觉阈值、对亮度和...
  • 如果要求在编码过程中不丢失信息量,即要求保存信息熵,这种信息保持的编码又叫熵保存编码,或叫熵编码。熵编码是无失真压缩。当然在考虑人眼失真不易察觉的生理特性时,有些图像编码不严格要求熵保存,信息允许通过...
  • iOS直播(四)对视频进行压缩编码

    千次阅读 2019-01-26 09:38:45
    1.为什么要进行编码? 不经过压缩编码的原视频,所占空间大...消除这些冗余并不会导致信息损失,属于无损压缩。可以细分为: (1)空间冗余:同一帧图像像素之间有较强相关性,可以进行帧内预测编码去除冗余。 ...
  • 学习尚硅谷韩顺平老师的Java数据结构笔记,详情请移步网站 1、基本介绍 (1) 赫夫曼编码也翻译为 哈夫曼编码(Huffman Coding),又称霍夫曼编码,是一种编码方式, 属于一种...(1)通信领域中信息的处理方式 1-定长编码
  • 霍夫曼编码 霍夫曼编码是 1952 年为文本文件而建立是一种统计编码属于无损压缩编码霍夫曼编码的码长 是变化的对于出现频率高的信息编码的长度较短而对于出现频率低的信息编码长度较长这样 处理全部信息的总码长一定...
  • 文本文件的二进制预统计...属于无损压缩编码。霍夫曼编码的码长是变化的,对于出现频率高的信息,编码的长度较短;而对于出现频率低的信息,编码长度较长。这样,处理全部信息的总码长一定小于实际信息的符号长...
  • 树结构实际应用 赫夫曼编码 赫夫曼编(霍夫曼、哈夫曼)码基本介绍 1.赫夫曼编码也翻译为 哈夫曼编码(Huffman Coding),又称霍夫曼编码,是一种编码方式, 属于一种程序算法 ...1. 通信领域中信息的处理方式1-定长编码
  • 霍夫曼编码的C语言实现

    万次阅读 2009-11-08 09:55:00
    属于无损压缩编码。霍夫曼编码的码长是变化的,对于出现频率高的信息,编码的长度较短;而对于出现频率低的信息,编码长度较长。这样,处理全部信息的总码长一定小于实际信息的符号长度。霍夫曼编码同香农、费诺编码...
  • 信源编码:通过对0/1进制的信号源(比如声源、图像信号源)的编码, 采取一定的编码方式, 对0/1进制信号源进行编码(压缩/加密), 达到有效、准确传输信息的目的。 扩频码和扩时码的设计属于信源编码这一大类。 ...
  • 赫夫曼编码

    2021-03-21 17:31:23
    1 赫夫曼编码也翻译为哈夫曼编码(Huffman Coding),又称霍夫曼编码,是一种编码方式, 属于一种程序算法。 2 赫夫曼编码是赫哈夫曼树在电讯通信中经典应用之一。 3 赫夫曼编码广泛地用于数据文件压缩。 其压缩...
  • 赫夫曼编码也翻译为哈夫曼编码(Huffman Coding),又称霍夫曼编码,是一种编码方式, 属于一种程序算法。 赫夫曼编码是赫哈夫曼树在电讯通信中经典应用之一。 赫夫曼编码广泛地用于数据文件压缩。其压缩率通常在20...
  • 1.零阶哥伦布指数编码(属于变长编码,VLC),主要用于VPS、SPS、PPS、slice头部信息的编码; 变长编码的原理:给大概率符号分配较短码字,给小概率符号分配符较短码字; 2.CABAC(算数编码),主要用于...
  • 人类获取的信息中70%来自于视觉,视频信息...传统压缩编码建立在仙农信息论基础之上,以经典集合论为工具,用概率统计模型来描述信源,其压缩思想基于数据统计,因此只能去除数据冗余,属于低层压缩编码的范畴。 ...
  • LZW字典编码

    2020-04-26 02:42:05
    字典编码属于一遍编码,不同于一般压缩编码所利用两遍编码得到统计信息后在编码传输,因此有可能在一些情况中压缩码率反而大于直接传输情况。 LZW 编码步骤 步骤1:将词典初始化为包含所有可能单字符,当前...
  • 算术编码

    2017-07-27 08:30:25
    算术编码是一种无损数据压缩方法,是图像压缩的主要算法之一,由IBM的信息论学家J. Rissanen于1976年发明。同霍夫曼码一样,算术码也属于概率匹配码。不同是,算术编码不是分组码,而是全序列编码,将整个数据...
  • 1315: 游程编码

    2019-10-08 23:16:02
    游程编码又称“运行长度编码”或“行程长度编码”,是一种统计编码,该编码属于无损压缩编码。对于二值图有效。 RLE行程长度编码概述 目前, 压缩技术已经广泛应用于各种软件、声音、影像格式等领域。总来说, 有两...
  • 霍夫曼编码总结

    千次阅读 2010-01-09 13:24:00
    属于无损压缩编码。霍夫曼编码的码长是变化的,对于出现频率高的信息,编码的长度较短;而对于出现频率低的信息,编码长度较长。这样,处理全部信息的总码长一定小于实际信息的符号长度。霍夫曼计算法步骤进行:l)将...
  • SWUST OJ 190 游程编码

    2021-02-10 12:27:37
    游程编码又称“运行长度编码”或“行程长度编码”,是一种统计编码,该编码属于无损压缩编码。对于二值图有效。 RLE行程长度编码概述 目前, 压缩技术已经广泛应用于各种软件、声音、影像格式等领域。总来说, 有两...

空空如也

空空如也

1 2 3 4 5 ... 9
收藏数 174
精华内容 69
关键字:

压缩属于信息的编码