当前位置：首页 > news >正文

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

news 来源：原创 2024/11/17 2:06:47

Huffman树转化成二进制编码

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

如果文本包含很多字符，那么从root节点到根节点的路径可能会很长。如果将二进制路径保存到int型变量中，路径长度超过32位那么一个int变量就不能完整保存路径。因此只能使用数组来保存路径，可以用byte，short，int，long。选择适中的int[]或者知道有很多字符时，可以选择long[]。还是要根据具体情况分析，下面采用long[]类型来保存路径。

在这里插入图片描述


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

遍历文本将每一个字符的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 = 72；比最原始的103要小一点。因为这段文本基本没有重复的，所以压缩效果不好。

文本解压

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

代码


    public String decode(EncodeInfo info){
        List<List<Long>> encodes = info.encodes;
        HMNode root = info.root;
        int endListIndex = encodes.size()-1;
        int endElementIndex = encodes.get(endListIndex).size()-1;
        HMNode prev = null;
        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){
                    prev = parse(prev,codes.get(j),info.lastLength,info);
                }else{
                    prev = parse(prev,codes.get(j),BIT_CELL_LENGTH,info);
                }
            }
        }

        return null;
    }

    /**
     * @param prev
     * @param bits
     * @param len long型变量的有效bit长度；
     * @param info
     * @return
     */
    public HMNode parse(HMNode prev,long bits,int len,EncodeInfo info){
        long curBit = 0;
        while(prev != null && len > 0){
          curBit = (bits>>>(BIT_CELL_LENGTH-1));
          if(curBit == 1 ){
              prev = prev.right;
          }else{
              prev = prev.left;
          }
          bits<<=1;
          len--;
          if(prev.leaf){
              System.out.print(prev.str);
              if(len ==0)
                  return null;
              else
                break;
          }

        }
        if(len == 0)return prev;
        return parse(prev=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产生的