【C】使用霍夫曼树压缩数据

usr

以下介绍使用StoneValley库的霍夫曼树进行数据的压缩和解压缩。
霍夫曼压缩算法位于StoneValley库的/src/svctree.c文件内。
压缩前和压缩后的数据存储在比特流（BITSTREAM）结构体内。
示例使用了treHuffmanEncoding对数据进行压缩，使用了treHuffmanDecoding解压缩数据。

1. #include <stdio.h>
   
2. #include <string.h>
   
3. #include "../src/svdef.h"
   
4. #include "../src/svstring.h"
   
5. #include "../src/svtree.h"
   
6. 
   
7. static const unsigned char sdata[] = { /* Prepared and compressed data. */
   
8.         0xE4, 0x4E, 0x0F, 0x56, 0x27, 0x71, 0x5A, 0xF7,
   
9.         0x1F, 0x2F, 0x59, 0xBF, 0xEE, 0x0F, 0x6A, 0x63,
   
10.         0x0F, 0x66, 0xE3, 0x93, 0x17, 0xA5, 0x9E, 0xB5,
    
11.         0x92, 0x5A, 0x3B, 0x6C, 0xAC, 0x88, 0x4D, 0x77,
    
12.         0x39, 0xAB, 0x09, 0x16, 0x7D, 0x8B, 0x53, 0xB3,
    
13.         0x37, 0xC3, 0xF5, 0xA8, 0x4C, 0x56, 0x61, 0xD7,
    
14.         0xCA, 0xFE, 0x92, 0x90
    
15. };
    
16. 
    
17. static const HFM_SYMBOL stabl[] = { /* Prepared symbol table. */
    
18.         0040, 0002, 0000, 0145, 0003, 0003, 0164, 0004,
    
19.         0017, 0157, 0004, 0013, 0151, 0004, 0012, 0150,
    
20.         0004, 0005, 0141, 0004, 0004, 0163, 0005, 0031,
    
21.         0154, 0005, 0030, 0156, 0005, 0020, 0143, 0005,
    
22.         0021, 0000, 0005, 0022, 0144, 0006, 0047, 0162,
    
23.         0006, 0073, 0147, 0006, 0046, 0111, 0006, 0071,
    
24.         0155, 0006, 0070, 0123, 0007, 0157, 0077, 0007,
    
25.         0164, 0126, 0007, 0155, 0056, 0007, 0156, 0160,
    
26.         0007, 0152, 0146, 0007, 0153, 0124, 0007, 0150,
    
27.         0047, 0007, 0165, 0166, 0007, 0151, 0171, 0007,
    
28.         0154
    
29. };
    
30. 
    
31. /* Strings. */
    
32. static const char * pstr[2] = {"Hello, ", "library."};
    
33. 
    
34. /* This's a tricky function. */
    
35. int foo(void)
    
36. {
    
37.         P_ARRAY_Z ptbl;
    
38.         BITSTREAM bsin;
    
39.         P_BITSTREAM pbsout;
    
40.         if (NULL == strInitBitStream(&bsin))
    
41.                 return __LINE__; /* Can not initialize bit-stream. */
    
42.         if (NULL == (ptbl = strCreateArrayZ(sizeof(stabl), sizeof(HFM_SYMBOL))))
    
43.                 return __LINE__; /* Can not initialize array. */
    
44.         /* Set bsin and symbol table up. */
    
45.         bsin.bilc = 5; /* This number is recorded after encoding. */
    
46.         strResizeArrayZ(&bsin.arrz, sizeof(sdata), sizeof(UCHART));
    
47.         memcpy(bsin.arrz.pdata, sdata, sizeof(sdata));
    
48.         memcpy(ptbl->pdata, stabl, sizeof(stabl));
    
49.         /* Decode and display. */
    
50.         pbsout = treHuffmanDecoding(ptbl, &bsin);
    
51.         printf("%s%s\n", (char *)pbsout->arrz.pdata, pstr[1]);
    
52.         /* Cleanup. */
    
53.         strDeleteBitStream(pbsout);
    
54.         /* Don't delete bsin here. Free bsin. */
    
55.         strFreeBitStream(&bsin);
    
56.         strDeleteArrayZ(ptbl);
    
57.         return 0;
    
58. }
    
59. 
    
60. /* This function illustrates how to use Huffman algorithm to compress data. */
    
61. int main(void)
    
62. {
    
63.         P_ARRAY_Z ptbl = NULL; /* Used to store a symbol table. */
    
64.         P_BITSTREAM pbsout, pbsin; /* Bit-streams that used to contain data. */
    
65.         /* Encode string 'hello'. Caution that table is important for decoding. */
    
66.         if (NULL == (pbsin = treHuffmanEncoding(&ptbl, (const PUCHAR)pstr[0], 8)))
    
67.         {
    
68.                 fprintf(stderr, "Error! Can not Encode.\n");
    
69.                 return __LINE__;
    
70.         }
    
71.         if (NULL == (pbsout = treHuffmanDecoding(ptbl, pbsin)))
    
72.         {
    
73.                 fprintf(stderr, "Error! Can not Decode.\n");
    
74.                 return __LINE__;
    
75.         }
    
76.         /* Print hello. */
    
77.         printf("%s", (char *)pbsout->arrz.pdata);
    
78.         /* Don't forget to free bit-streams and symbol table after use. */
    
79.         strDeleteBitStream(pbsout);
    
80.         strDeleteBitStream(pbsin);
    
81.         strDeleteArrayZ(ptbl);
    
82.         return foo();
    
83. }
    

复制代码

比特流pbsout中包含了97Bytes的数据，压缩后的sdata全局变量只包含52Bytes的数据。
但是因为数据量小还要加上全局变量stabl内包含的符号表所以体现不出压缩的优势。

0xAA55

我还以为你自己实现了Huffman压缩算法呢

usr

0xAA55 发表于 2020-11-7 23:41
我还以为你自己实现了Huffman压缩算法呢

霍夫曼算法在StoneValley库里面实现了，而且是开源的。要把实现代码贴出来吗？

watermelon

new_starter 发表于 2020-11-8 08:46
霍夫曼算法在StoneValley库里面实现了，而且是开源的。要把实现代码贴出来吗？ ...

站长说的是你自己实现的Huffman算法......
就像我这样：https://www.0xaa55.com/thread-16843-1-1.html