Huffman二进制编码以及文本的压缩与解压

偏执的太偏执、 2024-03-30 11:04 128阅读 0赞

#### 目录 ####

*  Huffman树转化成二进制编码
 *  文本压缩
 *  文本解压

## Huffman树转化成二进制编码 ##

在上一篇博客的末尾，将Huffman树转化成了`01` 构成的字符串，显然在实际应用中不是这种操作。我们实际想要的是`01`构成的一串bits；举个例子：`字符"A" 编码：0100 0001（8bit），假设我们重新编码之后字符 "A" 的路径是01，只占2个bit，应该用 01（bit）表示，而不是字符类型的"01"`，如果用字符类型的01来重新编码，那经过Huffman编码之后的数据比原本的数据还大。因此需要改进一下。（ps：如果不太清楚Huffman树的原理，可以先看上一篇[博客][Link 1]）

如果文本包含很多字符，那么从root节点到叶子节点的路径可能会很长。如果将二进制路径保存到int型变量中，路径长度超过32位那么一个int变量就不能完整保存路径。因此只能使用数组来保存路径，可以用byte，short，int，long。选择适中的int\[\]或者其他类型。最好使用byte\[\]这是最节省内存的，但本文采用long\[\]类型来保存路径。（[完整代码地址][Link 2]）

![在这里插入图片描述][9444a41d12114c29bf4981860c9a6f13.png_pic_center]

//统计字符使用频率和构建Huffman树的代码在上一篇文章中贴出来了，不再重复粘贴；完整代码在链接中；
         public void bitCode(HMNode root,Map<Character,long[]> huffmanCode,String code){
        
    
            if(root.leaf){
        
            	System.out.println(root.str+ " -> " + code);
                huffmanCode.put(root.str,convertBits(code));
                return;
            }
             if(root.left != null){
        
                 bitCode(root.left,huffmanCode,code+"0");
             }
             if(root.right != null){
        
                 bitCode(root.right,huffmanCode,code+"1");
             }
    
         }
    
    	//将字符串转化成bits
         public long[] convertBits(String code){
        
            int len = code.length() ;
            int codeLength = len% 64 ==0 ? len/64:len/64+1;
            int index = 1;
            int offset = 63;
            long[] bitCodes = new long[codeLength+1];
            char[] codes = code.toCharArray();
             for (int i = 0; i < codes.length; i++) {
        
                 long bitCode = bitCodes[index];
                 long c = codes[i]-'0';
                 bitCode |= (c<<offset);
                 bitCodes[index]=bitCode;
                 if(offset== 0){
        
                     offset = 63;
                     index += 1;
                 }else{
        
                     offset -= 1;
                 }
    
             }
             bitCodes[0]=(long)len;//第一个数字是用来记录编码的长度；
             return bitCodes;
         }

测试：

@Test
        public void test(){
        
            String text = "aaabbbbbccccccddddee";
            HMNode root =buildHuffManTree(text);
            Map<Character,long[]>code = new HashMap<>();
            bitCode(root,code,"");
            System.out.println("+++++++++++++++++++++++++++++++++++++++++++++");
            code.forEach((key,val)->{
        
                long codeLen = val[0];
                System.out.print(key+"编码长度："+codeLen +"\tcode: ");
                for (int i = 1; i < val.length-1; i++) {
        
                    System.out.print(" "+val[i]);
                }
                System.out.print(" "+(val[val.length-1]>>>(64-codeLen)));
                System.out.println("\n");
            });
    
        }
    
    
    =========================================res=================================================
    d -> 00
    c -> 11
    b -> 01
    e -> 100
    a -> 101
    +++++++++++++++++++++++++++++++++++++++++++++
    d编码长度：2	 code: 0
    
    b编码长度：2	 code: 1
    
    a编码长度：3	 code: 5
    
    c编码长度：2	 code: 3
    
    e编码长度：3	 code: 4

## 文本压缩 ##

EncodeInfo是保存压缩后的文本，设置成了一个二维数组。（现在想想其实没必要，因为必定是一边压缩一边保存到磁盘的。不可能把数据完全压缩之后再保存。）

![在这里插入图片描述][13f0d1574d864a48aee5273e0dbe2f29.png_pic_center]

![在这里插入图片描述][7999fafcb4ef4f669ae4f81caa86024c.png_pic_center]  
  
  
![在这里插入图片描述][999dfe2c44004858bd9e4c8517c19572.png_pic_center]

遍历文本将每一个字符的Huffman二进制码数组按顺序保存到压缩文本的二维数组中，这个需要稍微熟悉下位运算。（保存到二位数组就没有必要，之后再改吧）

class EncodeInfo{
        
            List<List<Long>> encodes = new ArrayList<>();
            int lastLength = 0;//encodes最后一个list的最后一个long元素中，有效bit个数
            HMNode root;
            public EncodeInfo(HMNode root){
        
                List<Long> code = new ArrayList<>(ARRAY_SIZE);
                code.add(0L);
                encodes.add(code);
                this.root = root;
            }
        }
    
        static int ARRAY_SIZE = 1024;
        static int BIT_CELL_LENGTH = 64;
    
        public void encode(String text,EncodeInfo info){
        
            Map<Character,long[]>code = new HashMap<>();
            bitCode(info.root,code,"");
    
            for (char c : text.toCharArray()) {
        
                addBitCode(info,code.get(c));
            }
        }
    
    
        private void addBitCode(EncodeInfo info ,long[] bits){
        
            List<List<Long>> encodes = info.encodes;
            List<Long> codes = encodes.get(encodes.size()-1);//获取到最后一个List;
            //得到二进制码数组最后一个元素的有效bit数；
            long last = bits[0]%BIT_CELL_LENGTH == 0 ? BIT_CELL_LENGTH : bits[0] % BIT_CELL_LENGTH;
            for (int i = 1; i < bits.length-1; i++) {
        
                long b = bits[i];
                int size = codes.size();
                long val = codes.get(size-1) ;
                val |= (b >>> info.lastLength);//前半部分
                codes.set(size-1,val);
                long after = b << (BIT_CELL_LENGTH-info.lastLength);//后半部分
                codes = addLast(info,after);
                info.lastLength = info.lastLength == 0 ? 0: BIT_CELL_LENGTH-info.lastLength;
            }
            long lastBits = bits[bits.length-1];
            long val = codes.get(codes.size()-1);
            val |= (lastBits >>> info.lastLength);
            codes.set(codes.size()-1,val);
            if(last + info.lastLength < BIT_CELL_LENGTH){
        
                info.lastLength += last;
            }else if(last + info.lastLength == BIT_CELL_LENGTH){
        
                info.lastLength =0;
                addLast(info,0L);
            }else{
        
                lastBits<<= (BIT_CELL_LENGTH-info.lastLength);
                addLast(info,lastBits);
                info.lastLength +=(last-BIT_CELL_LENGTH);
            }
        }
    
    
        private List<Long> addLast(EncodeInfo info,long val){
        
            List<List<Long>> encodes = info.encodes;
            List<Long> codes = encodes.get(encodes.size() - 1);
            int size = codes.size();
            if(size == ARRAY_SIZE){
        
                codes = new ArrayList<>(ARRAY_SIZE);
                encodes.add(codes);
            }
            codes.add(val);
            return codes;
        }

*  测试

@Test
        public void testEncode(){
        
            String text = " sfsdftechfdfhgjhtghrytthnhGGHMBDV打发士大夫SDCYUGERFASDSDW,.*&^%$#[]_+{};;;;;,.XCCCCC地方法规";
            int beforeEncode = text.getBytes().length;
            System.out.println("编码前：beforeEncode:"+beforeEncode +";");
            HMNode root =buildHuffManTree(text);
            EncodeInfo info =  new EncodeInfo(root);
            encode(text,info);
            info.encodes.forEach(x->{
        
                for (Long aLong : x) {
        
                    System.out.println(aLong);
                }
            });
    
            System.out.println("最后一个long的有效bit个数："+info.lastLength);
    
        }

*  结果

编码前：beforeEncode:103;
    * -> 000000
    夫 -> 000001
    + -> 000010
    地 -> 000011
    方 -> 000100
    A -> 000101
    B -> 000110
    规 -> 000111
    E -> 001000
    F -> 001001
    H -> 001010
    M -> 001011
    发 -> 001100
    R -> 001101
    打 -> 001110
    U -> 001111
    法 -> 010000
    V -> 010001
    W -> 010010
    X -> 010011
    Y -> 010100
    [ -> 010101
    ] -> 010110
    ^ -> 010111
    _ -> 011000
    c -> 011001
    e -> 011010
    j -> 011011
    士 -> 011100
    n -> 011101
    r -> 011110
    y -> 011111
    ; -> 1000
    {
         -> 100100
    } -> 100101
    G -> 10011
    C -> 1010
    h -> 1011
    S -> 11000
    D -> 11001
    f -> 11010
    t -> 11011
    , -> 111000
    . -> 111001
    d -> 111010
    g -> 111011
    s -> 111100
      -> 1111010
    # -> 1111011
    $ -> 1111100
    % -> 1111101
    & -> 1111110
    大 -> 1111111
    -727686570736772137
    6538905317935103933
    -2614557749356706589
    2089122890596168205
    2620082441562243324
    -4620800053492013930
    2459590903680641548
    4901886719416074240
    最后一个long的有效bit个数：16

数字就是文本经过Huffman编码压缩之后保存的信息；每个long保存8byte信息；可以计算出来被压缩之后的byte数：8 \* 7 + 16 /8= 58；比最原始的103要小一点。因为这段文本基本没有重复的，所以压缩效果不好。

## 文本解压 ##

在解压时按顺序读每一个bit位，对照Huffman树，如果是1就走右分支，如果是 0就走左分支。（这个还是要看之前怎么编码的，如果之前在构建Huffman树时，1表示左 ；0表示右那就按对应的方式解析）找到叶子节点就输出字符，然后继续顺序读读取bit知道将所有bit读完为止。

*  代码

public String decode(EncodeInfo info){
        
            List<List<Long>> encodes = info.encodes;
            int endListIndex = encodes.size()-1;
            int endElementIndex = encodes.get(endListIndex).size()-1;
            HMNode cur= info.root;
            for (int i = 0; i < encodes.size(); i++) {
        
                List<Long> codes = encodes.get(i);
                for (int j = 0; j < codes.size(); j++) {
        
                    if(i == endListIndex && j == endElementIndex){
        
                        cur= parse(cur,codes.get(j),info.lastLength,info);
                    }else{
        
                        cur= parse(cur,codes.get(j),BIT_CELL_LENGTH,info);
                    }
                }
            }
    
            return null;
        }
    
        /**
         * @param cur
         * @param bits
         * @param len long型变量的有效bit长度；
         * @param info
         * @return
         */
        public HMNode parse(HMNode cur,long bits,int len,EncodeInfo info){
        
            long curBit = 0;
            while(cur != null && len > 0){
        
              curBit = (bits>>>(BIT_CELL_LENGTH-1));
              if(curBit == 1 ){
        
                  cur= cur.right;
              }else{
        
                  cur= cur.left;
              }
              bits<<=1;
              len--;
              if(cur.leaf){
        
                  System.out.print(cur.str);
                  if(len ==0)
                      return null;
                  else
                    break;
              }
    
            }
            if(len == 0)return cur;
            return parse(cur=info.root,bits,len,info);
        }

*  测试

@Test
        public void testDecode(){
        
    
            String text = "急急急uu  ,.;/.'*&^%$广东福建的好的的德国费尔法的的发夫算法发生过和323434234123吧vDVD产生的";
            int beforeEncode = text.getBytes().length;
            System.out.println("编码前：beforeEncode:"+beforeEncode +";");
            HMNode root =buildHuffManTree(text);
            EncodeInfo info =  new EncodeInfo(root);
            encode(text,info);
            decode(info);
            System.out.println("\n+++++++++++++++");
            System.out.println(text);
            
        }

*  结果

编码前：beforeEncode:121;
    的 -> 000
    2 -> 0010
    4 -> 0011
    广 -> 01000
    D -> 01001
    发 -> 01010
    法 -> 01011
    生 -> 01100
      -> 01101
    . -> 01110
    u -> 01111
    过 -> 100000
    和 -> 100001
    福 -> 100010
    尔 -> 100011
    V -> 100100
    算 -> 100101
    东 -> 100110
    ^ -> 100111
    $ -> 101000
    % -> 101001
    & -> 101010
    ' -> 101011
    吧 -> 101100
    产 -> 101101
    * -> 101110
    夫 -> 101111
    , -> 110000
    / -> 110001
    1 -> 110010
    v -> 110011
    德 -> 110100
    费 -> 110101
    建 -> 110110
    ; -> 110111
    3 -> 1110
    好 -> 111100
    国 -> 111101
    急 -> 11111
    急急急uu  ,.;/.'*&^%$广东福建的好的的德国费尔法的的发夫算法发生过和323434234123吧vDVD产生的
    +++++++++++++++
    急急急uu  ,.;/.'*&^%$广东福建的好的的德国费尔法的的发夫算法发生过和323434234123吧vDVD产生的

[Link 1]: https://blog.csdn.net/m0_37550986/article/details/128385211
[Link 2]: https://github.com/mydlxy/huffman-project/blob/master/src/main/java/huffman/HuffmanCode.java
[9444a41d12114c29bf4981860c9a6f13.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/177a712694de435c9cc4dbca24247164.png
[13f0d1574d864a48aee5273e0dbe2f29.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/6112c1c939dc49979feada53502f5d4f.png
[7999fafcb4ef4f669ae4f81caa86024c.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/56e4deac69a747dcb52dfcafcecdc23a.png
[999dfe2c44004858bd9e4c8517c19572.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/3469922f7167403088a1dd274f015409.png